Видимость: 🌟🌟🌟🌟🌟
Вкус: Золотой суп Жирная говядина
Время приготовления: 10 мин.
Я хочу очистить склад и пойти домой, но боюсь, что он быстро восстановится, и будет очень холодно шагать по воздуху. Вместо того, чтобы копить отрицательную прибыль, лучше околачиваться в ее середине, меньше гоняться, не продавать вниз, спать спокойно по ночам, ненависти быть не должно, прибыль всегда непреднамеренная. Месяц может быть пасмурным и солнечным, а акции будут колебаться вбок. -- Известный древний белый торговец
Эта статья попала в одноименный склад Github фронтенд-столовойgithub.com/Geekhyt, Добро пожаловать в кафетерий. Если вы считаете, что еда и вино вкусные, Звезда станет отличным поощрением для владельца кафетерия.
Фондовый рынок в 2021 году взлетел и резко упал с начала года. Сразу после приветствия Бога Богатства молодые люди, которые с нетерпением ждали высокомерия, просто вошли на рынок и съели тяжелый молот с рынка капитала.
По очереди проводятся различные «Награды за поведение в замешательстве», которые делают и без того волшебный мир еще более волшебным.如果你最近也跌了，请点个赞，让我们互相抱团取暖。
Возвращаясь к 6 стандартным вопросам LeetCode, на самом деле эти 6 вопросов можно сгруппировать в один вопрос:
- Лучшее время для покупки и продажи акций
- Лучшее время для покупки и продажи акций II
- Лучшее время для покупки и продажи акций III
- Лучшее время для покупки и продажи акций IV
- Лучшее время для покупки и продажи акций включает период заморозки.
- Лучшее время для покупки и продажи акций с комиссией
И реальность немного отличается, заголовок добавляет некоторые ограничения, не сложно найти после прочтения проблемы анализа.
- Первый вопрос торгуется только один раз, то есть k = 1.
- Второй вопрос не ограничивает количество транзакций, то есть k = +бесконечность.
- Третий вопрос торгуется только дважды, то есть k = 2.
- Четвертый предел максимального количества транзакций k — произвольное число.
- Пятый и шестой курсы не ограничены, что эквивалентно добавлению транзакций на основе второго вопроса.
冷冻期а также手续费Дополнительные условия.
Мы можем сделать не более чем ежедневные операции следующих трех:
- купить
- продавать
- бездействие
Однако имейте в виду следующие четыре ограничения.
- Купите, прежде чем продать.
- Название требует, чтобы вы не могли участвовать в нескольких транзакциях одновременно, то естьВам нужно продать акции, которые у вас есть, прежде чем покупать снова.
- Никакая операция не основана на двух состояниях,холдинг акцийа такженет в наличии.
- Количество транзакций k также ограничено,Купить, только если k >= 0.
После анализа этих состояний следующим шагом будет их перевод в код.
Во-первых, мы можем создать трехмерный массив для представления вышеуказанных состояний, давайте проясним значение некоторых переменных.
- i: количество дней Диапазон: (0
- K: максимальное количество транзакций
- 0: запасов нет
- 1: держать запас
- n: длина массива запасов
dp[i][k][0]
dp[i][k][1]
// 举个🌰
dp[2][2][1] // 今天是第 2 天，手中持有股票，最多还可以进行 2 次交易
Самая большая выгода, о которой мы в конечном итоге просим, этоdp[n - 1][k][0], что представляет собой максимальную прибыль после продажи акций в последний день. (Продажа должна быть более прибыльной, чем хранение, поэтому [0], а не [1])
Далее мы пытаемся составить список уравнений перехода состояний.
// 今天手中没有持有股票，有两种可能：
// 1. 昨天没有持有，今天选择不操作。 对应: dp[i - 1][k][0]
// 2. 昨天持有，今天卖出了，所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
// 今天手中持有股票，有两种可能：
// 1. 昨天手中持有股票，今天选择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票，今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
Очевидно, что прибыль от продажи акций увеличивается, а прибыль от покупки акций уменьшается. Потому что каждая сделка состоит из двух парных операций, покупки и продажи.
Так что только когда вам нужно купить k - 1, тогда максимальная прибыль будет максимальной из двух вышеуказанных возможностей.
Вопрос 1 к = 1
Вставьте уравнение перехода состояния в условия этой задачи, k = 1, и запишите уравнение перехода состояния.
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
= Math.max(dp[i - 1][1][1], -prices[i])
// k = 0 时，dp[i - 1][0][0] = 0
Замечено, что, поскольку k равно 1 и не изменится, то есть k не влияет на переход состояния, и мы можем еще больше упростить уравнение.
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
Для дня 0 нам нужно инициализировать:
- Не держит:
dp[0][0] = 0 - держать:
dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
const maxProfit = function(prices) {
let n = prices.length
let dp = Array.from(new Array(n), () => new Array(2))
dp[0][0] = 0
dp[0][1] = -prices[0]
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
}
return dp[n - 1][0]
}
- Временная сложность: O(n)
- Космическая сложность: O(n)
Мы обнаружили, что при передачеdp[i]только отdp[i - 1]могут быть переданы, поэтому первое измерение может быть удалено, а пространственная сложность оптимизирована до O (1).
const maxProfit = function(prices) {
let n = prices.length
let dp = Array.from(new Array(n), () => new Array(2))
dp[0] = 0
dp[1] = -prices[0]
for (let i = 1; i < n; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i])
dp[1] = Math.max(dp[1], -prices[i])
}
return dp[0]
}
- Временная сложность: O(n)
- Космическая сложность: O(1)
Мы также можем сделать имена переменных более удобными.
- profit_out: прибыль при продаже
- profit_in: прибыль при покупке
const maxProfit = function(prices) {
let n = prices.length
let profit_out = 0
let profit_in = -prices[0]
for (let i = 1; i < n; i++) {
profit_out = Math.max(profit_out, profit_in + prices[i])
profit_in = Math.max(profit_in, -prices[i])
}
return profit_out
}
- Временная сложность: O(n)
- Космическая сложность: O(1)
Вопрос 2 k = +бесконечность
Подставьте в этом вопросе условия уравнения переноса состояния, k = + бесконечность.
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
= Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])
Мы обнаружили, что k в массиве также не изменилось, то есть k не влияет на переход состояний, и уравнение можно еще больше упростить.
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
Для дня 0 мы хотим задать начальное значение:
- Не держит:
dp[0][0] = 0 - держать:
dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
const maxProfit = function(prices) {
let n = prices.length
let dp = Array.from(new Array(n), () => new Array(2))
dp[0][0] = 0
dp[0][1] = -prices[0]
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
}
return dp[n - 1][0]
}
Также при передаче dp[i] будет передаваться только из dp[i - 1], поэтому первое измерение можно удалить, а пространственная сложность оптимизирована до O(1).
const maxProfit = function(prices) {
let n = prices.length
let dp = Array.from(new Array(n), () => new Array(2))
dp[0] = 0
dp[1] = -prices[0]
for (let i = 1; i < n; i++) {
let tmp = dp[0] // 中间变量可省略，因为当天买入卖出不影响结果
dp[0] = Math.max(dp[0], dp[1] + prices[i])
dp[1] = Math.max(dp[1], tmp - prices[i])
}
return dp[0]
}
Как и в предыдущем вопросе, мы можем сделать имена переменных более удобными.
const maxProfit = function(prices) {
let n = prices.length
let profit_out = 0
let profit_in = -prices[0]
for (let i = 1; i < n; i++) {
profit_out = Math.max(profit_out, profit_in + prices[i])
profit_in = Math.max(profit_in, profit_out - prices[i])
}
return profit_out
}
Третий вопрос К = 2
В первых двух случаях, независимо от того, k = 1 или k = +бесконечность, k не влияет на уравнение перехода состояния.
Однако, когда k = 2, k влияет на уравнение перехода состояния. Перечислите уравнения перехода состояний:
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
В настоящее время k нельзя упростить, и нам нужно использовать два цикла для исчерпывающего перечисления k.
for (let i = 0; i < n; i++) {
for (let k = maxK; k >= 1; k--) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
}
}
Однако, поскольку диапазон значений k относительно невелик, мы также можем перечислить их все напрямую.
dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
= Math.max(dp[i - 1][1][1], -prices[i])
Предвосхищая два вышеуказанных вопроса, мы сразу напишем решение после уменьшения размерности в следующих нескольких вопросах.
const maxProfit = function(prices) {
let n = prices.length
let dp_i10 = 0
let dp_i11 = -prices[0]
let dp_i20 = 0
let dp_i21 = -prices[0]
for (let i = 1; i < n; i++) {
dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
dp_i11 = Math.max(dp_i11, -prices[i])
}
return dp_i20
}
Как и выше, мы можем сделать имена переменных более удобными.
const maxProfit = function(prices) {
let profit_1_in = -prices[0], profit_1_out = 0
let profit_2_in = -prices[0], profit_2_out = 0
let n = prices.length
for (let i = 1; i < n; i++) {
profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
profit_1_in = Math.max(profit_1_in, -prices[i])
}
return profit_2_out
}
Четвертая проблема - произвольное число k
Для прибыльной сделки требуется не менее двух дней (покупка накануне и продажа послезавтра, при условии, что цена покупки ниже цены продажи).
Если длина массива цен акций равна n, количество прибыльных сделок не превышает n/2 (целочисленное деление). Таким образом, критическое значение k равно n/2.
Если заданное k не меньше критического значения, то есть k >= n/2, то k можно продолжить до положительной бесконечности, что и имеет место во втором вопросе, следующей функции maxProfit2.
const maxProfit = function(k, prices) {
let n = prices.length
const maxProfit2 = function(prices) {
let profit_out = 0
let profit_in = -prices[0]
for (let i = 1; i < n; i++) {
profit_out = Math.max(profit_out, profit_in + prices[i])
profit_in = Math.max(profit_in, profit_out - prices[i])
}
return profit_out
}
if (k > n / 2) {
return maxProfit2(prices)
}
let profit = new Array(k)
// 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维
for (let j = 0; j <= k; j++) {
profit[j] = {
profit_in: -prices[0],
profit_out: 0
}
}
for (let i = 0; i < n; i++) {
for (let j = 1; j <= k; j++) {
profit[j] = {
profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]),
profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
}
}
}
return profit[k].profit_out
}
Вопрос 5 k положительная бесконечность, но имеет время охлаждения
После каждой продажи вы должны ждать один день, чтобы продолжить сделку, то есть, когда вы выбираете покупку в i-й день, вы должны перевести из состояния i-2.
Перечислите уравнения перехода состояний.
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
= Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])
k также не влияет на переход состояний, и уравнение можно еще больше упростить.
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])
const maxProfit = function(prices) {
let n = prices.length
let dp_i0 = 0
let dp_i1 = -prices[0];
let dp_pre = 0 // 代表 dp[i-2][0]
for (let i = 0; i < n; i++) {
let tmp = dp_i0
dp_i0 = Math.max(dp_i0, dp_i1 + prices[i])
dp_i1 = Math.max(dp_i1, dp_pre - prices[i])
dp_pre = tmp
}
return dp_i0
}
Как и выше, мы можем сделать имена переменных более удобными.
const maxProfit = function(prices) {
let n = prices.length
let profit_in = -prices[0]
let profit_out = 0
let profit_freeze = 0
for (let i = 1; i < n; i++) {
let temp = profit_out
profit_out = Math.max(profit_out, profit_in + prices[i])
profit_in = Math.max(profit_in, profit_freeze - prices[i])
profit_freeze = temp
}
return profit_out
}
Задача 6 k положительная бесконечность, но есть плата за обработку
На основании второго вопроса добавляется плата за обработку.
Каждая транзакция должна платить комиссию, просто вычтите комиссию из прибыли, и вы можете составить следующие два уравнения.
Уравнение 1. Вычтите комиссию за обработку каждый раз, когда вы покупаете акцию.
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
Уравнение 2: вычитать комиссионные каждый раз, когда вы продаете акции
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
const maxProfit = function(prices, fee) {
let n = prices.length
let dp = Array.from(new Array(n), () => new Array(2))
dp[0] = 0
dp[1] = -prices[0]
for (let i = 1; i < n; i++) {
let tmp = dp[0]
dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
dp[1] = Math.max(dp[1], tmp - prices[i])
}
return dp[0]
}
Как и выше, мы можем сделать имена переменных более удобными.
const maxProfit = function(prices, fee) {
let profit_out = 0
let profit_in = -prices[0]
for (let i = 1; i < prices.length; i++) {
profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
profit_in = Math.max(profit_in, profit_out - prices[i])
}
return profit_out
}
После того, как группа разрушит алгоритм серии акций, давайте поговорим о так называемых инвестиционных часах.
Экономика делится на два основных цикла:经济复苏期а также经济衰退期.结合通胀和流动性的组合，可以分为四个小周期，衰退前期、衰退后期、复苏前期以及复苏后期.
Разным экономическим циклам соответствуют разные активы и рыночные стили. Все активы цикличны, и нет активов, которые только растут и не падают.Даже основные потребительские активы, такие как Маотай, могут в среднем превышать 30% в неподходящем цикле.Даже закатная отрасль, такая как сталелитейная, также может восстановиться в подходящем цикле. , До 50%.
Если вы выясните, в каком цикле находится сейчас, и скорректируете свои активы для разумного распределения, вы не будете луком-пореем.
Стоя на плечах гигантов
- Общее решение серии Stock Problem (Перепечатанный перевод)
- Простой дп, поймите торговлю акциями за считанные секунды
- 6 вопросов о наилучшем времени для покупки и продажи акций
Групповой план решения проблем на 2021 год
Установить флаг в начале года, указанный выше склад будет заполнен 100 высокочастотными вопросами для интервью в 2021 году, и прогресс был завершен.50%.
Если вы также готовы почистить или чистите LeetCode, вы также можете присоединиться к столовой переднего плана, сражаться бок о бок и хорошо проводить время.
❤️Любовное тройное комбо
1. Если вы считаете, что еда и напитки в столовой все еще аппетитны, просто поставьте лайк и поддержите это, вашеотличныймоя самая большая мотивация.
2. Обратите внимание на фронтальную столовую официального аккаунта,Ешьте каждый прием пищи!
3. Нравится, комментирует, пересылает === призывает больше!