一仓洼、路徑問題
2021.05.13
No.514 自由之路
電子游戲“輻射4”中玷禽，任務(wù)“通向自由”要求玩家到達(dá)名為“Freedom Trail Ring”的金屬表盤根暑，并使用表盤拼寫特定關(guān)鍵詞才能開門惹骂。
給定一個字符串 ring，表示刻在外環(huán)上的編碼毛仪；給定另一個字符串 key搁嗓，表示需要拼寫的關(guān)鍵詞。您需要算出能夠拼寫關(guān)鍵詞中所有字符的最少步數(shù)箱靴。
最初腺逛，ring 的第一個字符與12:00方向?qū)R。您需要順時針或逆時針旋轉(zhuǎn) ring 以使 key 的一個字符在 12:00 方向?qū)R衡怀，然后按下中心按鈕棍矛，以此逐個拼寫完 key 中的所有字符。
旋轉(zhuǎn) ring 拼出 key 字符 key[i] 的階段中：
您可以將 ring 順時針或逆時針旋轉(zhuǎn)一個位置狈癞，計為1步茄靠。旋轉(zhuǎn)的最終目的是將字符串 ring 的一個字符與 12:00 方向?qū)R茂契，并且這個字符必須等于字符 key[i] 蝶桶。
如果字符 key[i] 已經(jīng)對齊到12:00方向，您需要按下中心按鈕進(jìn)行拼寫掉冶，這也將算作 1 步真竖。按完之后脐雪，您可以開始拼寫 key 的下一個字符（下一階段）, 直至完成所有拼寫。
示例：
輸入: ring = "godding", key = "gd"
輸出: 4
解釋:
對于 key 的第一個字符 'g'恢共，已經(jīng)在正確的位置, 我們只需要1步來拼寫這個字符战秋。
對于 key 的第二個字符 'd'，我們需要逆時針旋轉(zhuǎn) ring "godding" 2步使它變成 "ddinggo"讨韭。
當(dāng)然, 我們還需要1步進(jìn)行拼寫脂信。
因此最終的輸出是 4。
提示：
ring 和 key 的字符串長度取值范圍均為 1 至 100透硝；
兩個字符串中都只有小寫字符狰闪，并且均可能存在重復(fù)字符；
字符串 key 一定可以由字符串 ring 旋轉(zhuǎn)拼出濒生。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/freedom-trail
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有埋泵。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處罪治。
方案：
/*
* @lc app=leetcode.cn id=514 lang=javascript
*
* [514] 自由之路
*/
// @lc code=start
/**
* @param {string} ring
* @param {string} key
* @return {number}
*/
var findRotateSteps = function(ring, key) {
// 用于存儲ring中的索引信息
const keyMap = {};
for(let i = 0; i < ring.length; i++) {
const k = ring[I];
if(keyMap[k]) {
keyMap[k].push(i)
} else {
keyMap[k] = [I]
}
}
// 緩存用于dfs剪枝
const memo = new Array(ring.length);
for(let i = 0; i < ring.length; i++) {
memo[i] = new Array(key.length).fill(-1)
}
// dfs遞歸
const dfs = ( ringI, keyI ) => {
if(keyI == key.length) return 0;
// 剪枝 有緩存直接返回緩存的結(jié)果
if( memo[ringI][keyI] !== -1 ) return memo[ringI][keyI]
const cur = key[keyI];
// 返回的結(jié)果
let res = Infinity;
for(const targetI of keyMap[cur]) {
// 正向位置
let d1 = Math.abs(ringI - targetI),
d2 = ring.length - d1;
const curMin = Math.min(d1, d2)
// 遞歸的循環(huán)不變式
res = Math.min(res, curMin + dfs(targetI, keyI+1))
}
memo[ringI][keyI] = res;
return res;
}
return dfs(0,0) + key.length;
};
動態(tài)規(guī)劃丽声，關(guān)鍵在于找到剪枝優(yōu)化方案
2021.05.16
No.576 出界的路徑數(shù)
給定一個 m × n 的網(wǎng)格和一個球。球的起始坐標(biāo)為 (i,j) 觉义，你可以將球移到相鄰的單元格內(nèi)雁社，或者往上、下晒骇、左歧胁、右四個方向上移動使球穿過網(wǎng)格邊界。但是厉碟，你最多可以移動 N 次喊巍。找出可以將球移出邊界的路徑數(shù)量。答案可能非常大箍鼓，返回 結(jié)果 mod 109 + 7 的值崭参。
示例 1：
輸入: m = 2, n = 2, N = 2, i = 0, j = 0
輸出: 6
解釋:
示例 2：
輸入: m = 1, n = 3, N = 3, i = 0, j = 1
輸出: 12
解釋:
說明:
球一旦出界，就不能再被移動回網(wǎng)格內(nèi)款咖。
網(wǎng)格的長度和高度在 [1,50] 的范圍內(nèi)何暮。
N 在 [0,50] 的范圍內(nèi)。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/out-of-boundary-paths
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有铐殃。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)海洼，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=576 lang=javascript
*
* [576] 出界的路徑數(shù)
*/
// @lc code=start
/**
* @param {number} m
* @param {number} n
* @param {number} maxMove
* @param {number} startRow
* @param {number} startColumn
* @return {number}
*/
var findPaths = function(m, n, N, i, j) {
const helper = (i, j, N) => {
// N 次用完了富腊，此時不能再走了就返回 0
if (N < 0) {
return 0
}
// 出界條件滿足了坏逢，說明有一條出界路徑，就返回 1
if (i < 0 || i >= m || j < 0 || j >= n) {
return 1
}
// 記憶化搜索（如果重復(fù)訪問了那就用之前的值）
const key = `${i}-${j}-${N}`
if (visited.has(key)) {
return visited.get(key)
}
let res = 0
// 找上、下是整、左肖揣、右 四個方向
for (let k = 0; k < 4; k++) {
res = (res + helper(i + direction[k][0], j + direction[k][1], N -1)) % mod
}
// 將當(dāng)前的值緩存下來
visited.set(key, res)
return res
}
const mod = Math.pow(10, 9) + 7
const direction = [[1, 0], [-1, 0], [0, -1], [0, 1]]
const visited = new Map()
return helper(i, j, N)
};
利用Map進(jìn)行遞歸判斷，狀態(tài)轉(zhuǎn)移是四個方向的探索
2021.05.17
No.980 不同路徑-iii
在二維網(wǎng)格 grid 上浮入，有 4 種類型的方格：
1 表示起始方格。且只有一個起始方格。
2 表示結(jié)束方格易迹，且只有一個結(jié)束方格。
0 表示我們可以走過的空方格菩浙。
-1 表示我們無法跨越的障礙。
返回在四個方向（上句伶、下先嬉、左疫蔓、右）上行走時，從起始方格到結(jié)束方格的不同路徑的數(shù)目滚躯。
每一個無障礙方格都要通過一次，但是一條路徑中不能重復(fù)通過同一個方格丧凤。
示例 1：
輸入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
輸出：2
解釋：我們有以下兩條路徑：
- (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
- (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：
輸入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
輸出：4
解釋：我們有以下四條路徑：
- (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
- (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
- (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
- (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3：
輸入：[[0,1],[2,0]]
輸出：0
解釋：
沒有一條路能完全穿過每一個空的方格一次。
請注意蚁廓，起始和結(jié)束方格可以位于網(wǎng)格中的任意位置相嵌。
提示：
1 <= grid.length * grid[0].length <= 20
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-iii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有批糟。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=980 lang=javascript
*
* [980] 不同路徑 III
*/
// @lc code=start
/**
* @param {number[][]} grid
* @return {number}
*/
var uniquePathsIII = function(grid) {
if(!grid.length) return 0;
const helper = ( grid, i, j, step ) => {
if( i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == -1 ) {
return 0;
}
if(grid[i][j] == 2) return step == -1 ? 1 : 0;
grid[i][j] = -1;
let res = 0;
// 向四個方向探索
res += helper( grid, i+1, j, step - 1 );
res += helper( grid, i, j+1, step - 1 );
res += helper( grid, i-1, j, step - 1 );
res += helper( grid, i, j-1, step - 1 );
grid[i][j] = 0
return res;
}
let startI = 0, startJ = 0, total = 0;
// 遍歷
for( let i = 0; i < grid.length; i++ ) {
for( let j = 0; j < grid[i].length; j++ ) {
if( grid[i][j] == 1 ) {
startI = I;
startJ = j;
}
if( grid[i][j] == 0 ) {
total++;
}
}
}
return helper(grid, startI, startJ, total);
};
同576題，不同之處在于不能返回啰扛，動態(tài)規(guī)劃進(jìn)行四個方向的探索回溯
2021.05.18
No.1129 顏色交替的最短路徑
在一個有向圖中，節(jié)點分別標(biāo)記為 0, 1, ..., n-1厢漩。這個圖中的每條邊不是紅色就是藍(lán)色，且存在自環(huán)或平行邊。
red_edges 中的每一個 [i, j] 對表示從節(jié)點 i 到節(jié)點 j 的紅色有向邊土全。類似地瑞凑，blue_edges 中的每一個 [i, j] 對表示從節(jié)點 i 到節(jié)點 j 的藍(lán)色有向邊。
返回長度為 n 的數(shù)組 answer技掏，其中 answer[X] 是從節(jié)點 0 到節(jié)點 X 的紅色邊和藍(lán)色邊交替出現(xiàn)的最短路徑的長度。如果不存在這樣的路徑，那么 answer[x] = -1弧哎。
示例 1：
輸入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
輸出：[0,1,-1]
示例 2：
輸入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
輸出：[0,1,-1]
示例 3：
輸入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
輸出：[0,-1,-1]
示例 4：
輸入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
輸出：[0,1,2]
示例 5：
輸入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
輸出：[0,1,1]
提示：
1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-path-with-alternating-colors
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處程奠。
方案：
/*
* @lc app=leetcode.cn id=1129 lang=javascript
*
* [1129] 顏色交替的最短路徑
*/
// @lc code=start
/**
* @param {number} n
* @param {number[][]} red_edges
* @param {number[][]} blue_edges
* @return {number[]}
*/
var shortestAlternatingPaths = function(n, red_edges, blue_edges) {
var re_0=new Array(n).fill(Number.MAX_VALUE);
var re_1=new Array(n).fill(Number.MAX_VALUE);
var graph_red=new Array(n);
var graph_blue=new Array(n);
for(var i=0;i<n;i++){
graph_red[i]= new Array();
graph_blue[i]=new Array();
}
for(var i=0;i<red_edges.length;i++){
graph_red[red_edges[i][0]].push(red_edges[i][1]);
}
for(var i=0;i<blue_edges.length;i++){
graph_blue[blue_edges[i][0]].push(blue_edges[i][1]);
}
re_1[0]=0;
re_0[0]=0;
var now_b=[0],now_r=[0];
step=0;
while(now_b.length!==0 ||now_r.length!==0){
var new_b=[], new_r=[];
var point,adj;
step++;
while(now_b.length!==0){
point=now_b.pop();
adj=graph_red[point];
for(var next of adj){
if(re_0[next]===Number.MAX_VALUE){
re_0[next]=step;
new_r.push(next);
}
}
}
while(now_r.length!=0){
point=now_r.pop();
adj=graph_blue[point];
for(var next of adj){
if(re_1[next]===Number.MAX_VALUE){
re_1[next]=step;
new_b.push(next);
}
}
}
now_r=new_r;
now_b=new_b;
}
//console.log(re_0,re_1);
for(var i=0;i<n;i++){
re_0[i]=Math.min(re_0[i],re_1[I]);
if(re_0[i]===Number.MAX_VALUE) re_0[i]=-1;
}
return re_0;
};
Dijistra算法變形距境，使用動態(tài)規(guī)劃進(jìn)行逐步bfs
總結(jié)：
- 路徑問題最常見的就是回溯探索垫桂，關(guān)鍵在于剪枝優(yōu)化霹粥，對于狀態(tài)轉(zhuǎn)移函數(shù)的歸納總結(jié)；
- 動態(tài)規(guī)劃是一種逐步處理問題的思路，常見的需要利用二維數(shù)組及hashMap等數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理
二馋袜、股票問題
2021.05.19
No.121 買賣股票的最佳時機(jī)
給定一個數(shù)組 prices 察皇，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格矾缓。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票琉雳。設(shè)計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤绪妹，返回 0 。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入糕簿，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 殃恒。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。
示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0熟呛。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=3 lang=javascript
*
* [3] 無重復(fù)字符的最長子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let max = 0, index = 0;
for(let i=0,j=0;j<s.length;j++) {
index = s.slice(i,j).indexOf(s[j]);
if(isRepeat(s.slice(i,j))) {
i += index + 1;
}
max = Math.max(max, j - i + 1)
}
return max;
function isRepeat(s) {
return s.length == Array.from(new Set(s.split(''))).length;
}
};
動態(tài)規(guī)劃，股票問題i
2021.05.20
No.122 買賣股票的最佳時機(jī)-ii
給定一個數(shù)組 prices 笔链，其中 prices[i] 是一支給定股票第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤炕婶。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入宋渔，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后谈飒，在第 4 天（股票價格 = 3）的時候買入费什，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: prices = [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票酣栈，之后再將它們賣出。因為這樣屬于同時參與了多筆交易榆综，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: prices = [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)中燥，非商業(yè)轉(zhuǎn)載請注明出處吟秩。
方案：
/*
* @lc app=leetcode.cn id=122 lang=javascript
*
* [122] 買賣股票的最佳時機(jī) II
*/
// @lc code=start
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit_in = -prices[0],
profit_out = 0,
n = prices.length;
for(let i =0; 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;
};
動態(tài)規(guī)劃闹伪，股票問題ii
2021.05.21
No.123 買賣股票的最佳時機(jī)-iii
給定一個數(shù)組椰憋，它的第 i 個元素是一支給定的股票在第 i 天的價格证舟。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）辛藻。
示例 1:
輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 桥氏。
隨后奸忽，在第 7 天（股票價格 = 1）的時候買入欠雌，在第 8 天 （股票價格 = 4）的時候賣出检号，這筆交易所能獲得利潤 = 4-1 = 3 。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票混弥，之后再將它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票胖齐。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這個情況下, 沒有交易完成, 所以最大利潤為 0辛慰。
示例 4：
輸入：prices = [1]
輸出：0
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 105
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=123 lang=javascript
*
* [123] 買賣股票的最佳時機(jī) III
*/
// @lc code=start
/**
* @param {number[]} prices
* @return {number}
*/
var 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]);
//第二次買入后的利潤， 第一次賣出的利潤 - 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]);
//第一次買入后，利潤為 -prices[i]
profit_1_in = Math.max(profit_1_in, -prices[I]);
}
return profit_2_out;
};
動態(tài)規(guī)劃朋截，股票問題iii
2021.05.24
No.188 買賣股票的最佳時機(jī)-iv
給定一個整數(shù)數(shù)組 prices 部服，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格唆姐。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易廓八。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）奉芦。
示例 1：
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入剧蹂，在第 2 天 (股票價格 = 4) 的時候賣出声功，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價格 = 2) 的時候買入宠叼，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 济竹。
隨后嫌佑，在第 5 天 (股票價格 = 0) 的時候買入饭于，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 缠沈。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)简烤，非商業(yè)轉(zhuǎn)載請注明出處剂邮。
方案：
/*
* @lc app=leetcode.cn id=188 lang=javascript
*
* [188] 買賣股票的最佳時機(jī) IV
*/
// @lc code=start
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
let n = prices.length;
if (k > n / 2) {
k = Math.floor(n/2);
}
let profits = [];
for(let j=0; j <= k; j++) {
profits[j] = {
profits_out: 0,
profits_in: -prices[0]
}
}
for( let i = 0; i < n; i++ ) {
for( let j=1; j <= k; j++ ) {
profits[j] = {
profits_out: Math.max(profits[j][`profits_out`], profits[j][`profits_in`] + prices[I]),
profits_in: Math.max(profits[j][`profits_in`], profits[j-1][`profits_out`] - prices[I])
}
}
}
return profits[k][`profits_out`];
};
動態(tài)規(guī)劃，股票問題iv
2021.05.26
No.309 最佳買賣股票時機(jī)含冷凍期
給定一個整數(shù)數(shù)組横侦，其中第 i 個元素代表了第 i 天的股票價格 挥萌。
設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下枉侧，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）引瀑。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)棵逊。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有伤疙。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處辆影。
方案：
/*
* @lc app=leetcode.cn id=309 lang=javascript
*
* [309] 最佳買賣股票時機(jī)含冷凍期
*/
// @lc code=start
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let n = prices.length,
profits_in = -prices[0],
profits_out = 0,
profits_freeze = 0;
for( let i = 0; i < prices.length; i++ ) {
let temp = profits_out;
profits_out = Math.max(profits_out, prices[i] + profits_in);
profits_in = Math.max(profits_in, profits_freeze - prices[I]);
profits_freeze = temp;
}
return profits_out;
};
動態(tài)規(guī)劃，股票問題v
2021.05.27
No.714 買賣股票的最佳時機(jī)含手續(xù)費
給定一個整數(shù)數(shù)組 prices黍特，其中第 i 個元素代表了第 i 天的股票價格 蛙讥；整數(shù) fee 代表了交易股票的手續(xù)費用。
你可以無限次地完成交易灭衷，但是你每筆交易都需要付手續(xù)費次慢。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值迫像。
注意：這里的一筆交易指買入持有并賣出股票的整個過程劈愚，每筆交易你只需要為支付一次手續(xù)費。
示例 1：
輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達(dá)到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
輸入：prices = [1,3,7,5,10,3], fee = 3
輸出：6
提示：
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有闻妓。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)菌羽，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=714 lang=javascript
*
* [714] 買賣股票的最佳時機(jī)含手續(xù)費
*/
// @lc code=start
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
let n = prices.length,
profits_in = 0 - prices[0],
profits_out = 0;
for( let i=0; i < prices.length; i++ ) {
profits_out = Math.max(profits_out, prices[i] + profits_in - fee);
profits_in = Math.max(profits_in, profits_out - prices[I]);
}
return profits_out < 0 ? 0 : profits_out;
};
動態(tài)規(guī)劃由缆，股票問題vi
總結(jié)：
- 股票問題關(guān)鍵在于對輸入輸出的狀態(tài)進(jìn)行判斷轉(zhuǎn)移注祖，運用動態(tài)規(guī)劃思想進(jìn)行處理；
- 在動態(tài)規(guī)劃實現(xiàn)中比較常見的是多維數(shù)組的逐步迭代均唉，對于股票問題可以進(jìn)行降維處理是晨，優(yōu)化效率
三、拆分組合
2021.05.31
No.132 分割回文串-ii
給你一個字符串 s舔箭，請你將 s 分割成一些子串罩缴，使每個子串都是回文。
返回符合要求的 最少分割次數(shù) 层扶。
示例 1：
輸入：s = "aab"
輸出：1
解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串靴庆。
示例 2：
輸入：s = "a"
輸出：0
示例 3：
輸入：s = "ab"
輸出：1
提示：
1 <= s.length <= 2000
s 僅由小寫英文字母組成
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)怒医，非商業(yè)轉(zhuǎn)載請注明出處炉抒。
方案一：
/*
* @lc app=leetcode.cn id=132 lang=javascript
*
* [132] 分割回文串 II
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var minCut = function (s) {
let j, dp = new Array(s.length).fill(s.length)
for (let i = 0; i < s.length; i++) {
j = 0
while (i - j >= 0 && i + j < s.length) {
if (s[i - j] === s[i + j]) dp[i + j] = i - j === 0 ? 0 : dp[i + j] <= dp[i - j - 1] + 1 ? dp[i + j] : dp[i - j - 1] + 1
else break
j++
}
j = 0
while (i - j >= 0 && i + j + 1 < s.length) {
if (s[i - j] === s[i + j + 1]) dp[i + j + 1] = i - j === 0 ? 0 : dp[i + j + 1] <= dp[i - j - 1] + 1 ? dp[i + j + 1] : dp[i - j - 1] + 1
else break
j++
}
}
return dp[s.length - 1]
};
方案二：
/*
* @lc app=leetcode.cn id=132 lang=javascript
*
* [132] 分割回文串 II
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var minCut = function (s) {
var manacher = function(s){
if(!s) return [];
var lstRadios=[];
//拼裝manacher字符串
s=s.replace(/\w/g,(a)=>{return '#'+a;})+'#';
//三個指針，現(xiàn)在先定義中心指針c和最右指針r,剩下一個就是運動指針了
var r=-1, c=-1;
for(var i=0; i<s.length;i++){
//判斷i在不在r右側(cè)
//在稚叹，當(dāng)前指針對應(yīng)的半徑無從判斷焰薄，先賦值1
//不在，就判斷當(dāng)前i以c為中心的對應(yīng)指針i'的半徑扒袖，
//如果i'的半徑超過了c半徑的范圍塞茅，就說明i的半徑就為r-i+1；
//如果i'的半徑剛好在c半徑的的范圍內(nèi)季率，且不在邊界上野瘦，那么i的半徑就為i'的半徑
//如果i'的半徑剛好在c半徑的指針上，那么i的半徑是有可能再擴(kuò)大的飒泻，需要再驗證
lstRadios[i]=r>i?Math.min(lstRadios[2*c-i],r-i+1):1;
while(i+lstRadios[i]<s.length && i-lstRadios[i]>-1){
if(s.charAt(i-lstRadios[i]) == s.charAt(i+lstRadios[i]))lstRadios[i]++;
else break;
}
if(i+lstRadios[i]-1 > r){
r=1+lstRadios[i]-1;
c=I;
}
}
return lstRadios;
};
if(s.length<=1) return 0;
var lstRadios=manacher(s);
var dp=[];
for(var i=0; i<s.length; i++){
if(dp[i] == undefined) dp[i]=i;
if(i!=0)dp[i]=Math.min(dp[i-1]+1,dp[i]);
//先以i為中點
var d=lstRadios[2*i+1]/2 - 1;
for(var j=1; j<=d; j++){
if(dp[i+j] == undefined) dp[i+j]=i+j;
dp[i+j]=Math.min(((i-j-1)>=0?(dp[i-j-1]+1):0),dp[i+j]);
}
//以i和i+1的中間為中心
d=lstRadios[2*i+2]/2;
if(d<=0)continue;
for(var j=1; j<=d; j++){
if(dp[i+j] == undefined) dp[i+j]=i+j;
dp[i+j]=Math.min(((i-j)>=0?(dp[i-j]+1):0),dp[i+j]);
}
}
return dp[s.length-1];
};
方案三：
/*
* @lc app=leetcode.cn id=132 lang=javascript
*
* [132] 分割回文串 II
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
const n = s.length;
const g = new Array(n).fill(0).map(() => new Array(n).fill(true));
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
g[i][j] = s[i] == s[j] && g[i + 1][j - 1];
}
}
const f = new Array(n).fill(Number.MAX_SAFE_INTEGER);
for (let i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (let j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
};
動態(tài)規(guī)劃鞭光，有三種不同的實現(xiàn)方案：1、利用字符串的位置特性泞遗，只用一遍動態(tài)規(guī)劃惰许；2、利用manacher進(jìn)行一個查找的優(yōu)化史辙；3汹买、兩次動態(tài)規(guī)劃
2021.06.01
No.1278 分割回文串-iii
給你一個由小寫字母組成的字符串 s佩伤，和一個整數(shù) k。
請你按下面的要求分割字符串：
首先晦毙，你可以將 s 中的部分字符修改為其他的小寫英文字母生巡。
接著，你需要把 s 分割成 k 個非空且不相交的子串见妒，并且每個子串都是回文串孤荣。
請返回以這種方式分割字符串所需修改的最少字符數(shù)。
示例 1：
輸入：s = "abc", k = 2
輸出：1
解釋：你可以把字符串分割成 "ab" 和 "c"徐鹤，并修改 "ab" 中的 1 個字符垃环，將它變成回文串。
示例 2：
輸入：s = "aabbc", k = 3
輸出：0
解釋：你可以把字符串分割成 "aa"返敬、"bb" 和 "c"遂庄，它們都是回文串。
示例 3：
輸入：s = "leetcode", k = 8
輸出：0
提示：
1 <= k <= s.length <= 100
s 中只含有小寫英文字母劲赠。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-partitioning-iii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有涛目。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處凛澎。
方案一：
/*
* @lc app=leetcode.cn id=1278 lang=javascript
*
* [1278] 分割回文串 III
*/
// @lc code=start
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var palindromePartition = function(s, k) {
const n = s.length;
const dp = Array.from({length: n}, () => Array(k+1).fill(100));
const cost = Array.from({length: n}, () => Array(n).fill(0));
for (let len = 1; len < n; len++) {
for (let i = 0; i < n - len; i++) {
const j = i + len;
cost[i][j] = cost[i+1][j-1] + (s[i] == s[j] ? 0 : 1);
}
}
for (let i = 0; i < n; i++) {
dp[i][1] = cost[0][I];
for (let kk = 2; kk <= k; kk++) {
for (let j = 0; j < i; j++) {
dp[i][kk] = Math.min(dp[i][kk], dp[j][kk-1] + cost[j+1][I]);
}
}
}
return dp[n-1][k];
};
方案二：
/*
* @lc app=leetcode.cn id=1278 lang=javascript
*
* [1278] 分割回文串 III
*/
// @lc code=start
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var palindromePartition = function (s, k) {
const m = s.length;
const dp = Array.from(Array(k), () => Array(m));
const map = Array.from(Array(m), () => Array(m));
const helper = (i, j) => {
const str = s.substring(i, j + 1);
let res = 0;
for (let l = 0; l < str.length / 2; l++)
if (str[l] !== str[str.length - 1 - l]) res++;
return res;
};
for (let i = 0; i < m; I++)
for (let j = i; j < m; j++) map[i][j] = helper(i, j);
for (let i = 0; i < k; i++) {
for (let j = i; j < m; j++) {
if (i === j || i === 0) {
dp[i][j] = map[i][j]; // No need to remove, each char is a substring
continue;
}
let res = Infinity;
for (let k = 1; j - k >= i - 1; k++)
res = Math.min(res, map[j + 1 - k][j] + dp[i - 1][j - k]);
dp[i][j] = res;
}
}
return dp[k - 1][m - 1];
};
兩次dp霹肝，方法2對字符串進(jìn)行了過濾截取
2021.06.02
No.1745 回文串分割-iv
給你一個字符串 s ，如果可以將它分割成三個 非空 回文子字符串塑煎，那么返回 true 沫换，否則返回 false 。
當(dāng)一個字符串正著讀和反著讀是一模一樣的最铁，就稱其為 回文字符串 讯赏。
示例 1：
輸入：s = "abcbdd"
輸出：true
解釋："abcbdd" = "a" + "bcb" + "dd"，三個子字符串都是回文的冷尉。
示例 2：
輸入：s = "bcbddxy"
輸出：false
解釋：s 沒辦法被分割成 3 個回文子字符串漱挎。
提示：
3 <= s.length <= 2000
s 只包含小寫英文字母。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-partitioning-iv
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有雀哨。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)磕谅，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=1745 lang=javascript
*
* [1745] 回文串分割 IV
*/
// @lc code=start
/**
* @param {string} s
* @return {boolean}
*/
var checkPartitioning = function(s) {
let dp = new Array(s.length);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(s.length).fill(true);
}
for (let i = s.length - 1; i >=0 ;i--) {
for (let j = i; j < s.length; j++) {
if (i !== j) {
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
}
}
}
for (let i = 0; i < s.length - 2; i++) {
if(dp[0][i] == false) continue;
for (let j = i + 1; j < s.length - 1; j++) {
if(dp[i+1][j] == false || dp[j + 1][s.length - 1] == false ) continue;
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][s.length - 1]) {
return true;
}
}
}
return false;
};
動態(tài)規(guī)劃雾棺，對循環(huán)可進(jìn)行提前判斷
2021.07.02
No.139 單詞拆分
給定一個非空字符串 s 和一個包含非空單詞的列表 wordDict膊夹，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。
說明：
拆分時可以重復(fù)使用字典中的單詞垢村。
你可以假設(shè)字典中沒有重復(fù)的單詞割疾。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"嘉栓。
注意你可以重復(fù)使用字典中的單詞宏榕。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-break
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)侵佃，非商業(yè)轉(zhuǎn)載請注明出處麻昼。
方案：
/*
* @lc app=leetcode.cn id=139 lang=javascript
*
* [139] 單詞拆分
*/
// @lc code=start
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
const n = s.length;
const wordDictSet = new Set(wordDict);
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordDictSet.has(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
};
典型動態(tài)規(guī)劃問題，通過dp[i]確定切割位置
2021.07.07
No.140 單詞拆分-ii
給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict馋辈，在字符串中增加空格來構(gòu)建一個句子抚芦，使得句子中所有的單詞都在詞典中。返回所有這些可能的句子迈螟。
說明：
分隔時可以重復(fù)使用字典中的單詞叉抡。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：
輸入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
輸出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
輸入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
輸出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解釋: 注意你可以重復(fù)使用字典中的單詞答毫。
示例 3：
輸入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出:
[]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-break-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有褥民。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處洗搂。
方案一：
/*
* @lc app=leetcode.cn id=140 lang=javascript
*
* [140] 單詞拆分 II
*/
// @lc code=start
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
let dp = new Array(s.length + 1).fill(false)
dp[0] = true
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j <= i; j++) {
if (dp[j] && wordDict.indexOf(s.slice(j, i)) >= 0) {
dp[i] = true
break
}
}
}
if(!dp[s.length]) return []
let ans = []
function backTrack(cur, str) {
if(str.length == 0) {
ans.push(cur)
return
}
for(let i = 0; i < str.length; i++) {
if(wordDict.indexOf(str.slice(0, i + 1)) >= 0) {
if(cur.length > 0) backTrack(cur + ' ' + str.slice(0, i + 1), str.slice(i + 1))
else backTrack(str.slice(0, i + 1), str.slice(i + 1))
}
}
}
backTrack('', s)
return ans
};
方案二：
/*
* @lc app=leetcode.cn id=140 lang=javascript
*
* [140] 單詞拆分 II
*/
// @lc code=start
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
// 輔助函數(shù)
const backtrack = (s, length, wordSet, index, map) => {
if (map.has(index)) {
return map.get(index);
}
const wordBreaks = [];
if (index === length) {
wordBreaks.push([]);
}
for (let i = index + 1; i <= length; i++) {
const word = s.substring(index, i);
if (wordSet.has(word)) {
const nextWordBreaks = backtrack(s, length, wordSet, i, map);
for (const nextWordBreak of nextWordBreaks) {
const wordBreak = [word, ...nextWordBreak]
wordBreaks.push(wordBreak);
}
}
}
map.set(index, wordBreaks);
return wordBreaks;
}
const map = new Map();
const wordBreaks = backtrack(s, s.length, new Set(wordDict), 0, map);
const breakList = [];
for (const wordBreak of wordBreaks) {
breakList.push(wordBreak.join(' '));
}
return breakList;
};
有兩種方案：1消返、借助139題先進(jìn)行判斷，然后再進(jìn)行回溯耘拇；2撵颊、利用Map數(shù)據(jù)結(jié)構(gòu)，直接回溯
2021.07.08
No.343 整數(shù)拆分
給定一個正整數(shù) n惫叛，將其拆分為至少兩個正整數(shù)的和倡勇，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積嘉涌。
示例 1:
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1妻熊。
示例 2:
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
說明: 你可以假設(shè) n 不小于 2 且不大于 58洛心。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/integer-break
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有固耘。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處词身。
方案一：
/*
* @lc app=leetcode.cn id=343 lang=javascript
*
* [343] 整數(shù)拆分
*/
// @lc code=start
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
// 利用均值不等式 x1 * x2 * ··· * xn ≤ ( ( x1 + x2 + ··· + xn ) / n )^n
let max = -Infinity;
for( let i = 2; i <= n; i++ ) {
let v = -Infinity;
if(n % i == 0) {
v = Math.pow(n/i,i)
} else {
let v1 = Math.ceil(n/i),
v2 = Math.floor(n/i)
v = Math.max(
Math.pow(v1,i-1) * (n - v1*(i-1)) ,
Math.pow(v2,i-1) * (n - v2*(i-1))
)
}
max = Math.max(v, max)
}
return max;
};
方案二：
/*
* @lc app=leetcode.cn id=343 lang=javascript
*
* [343] 整數(shù)拆分
*/
// @lc code=start
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 1;
for (let i = 3; i <= n; i++) {
dp[i] = 0;
// 對于數(shù)字 i厅目，它可以分為兩份：j 和 i-j，j 的范圍是 1 到 i-j
for (let j = 1; j <= i - j; j++) {
// 對于 i-j 這部分可以拆或不拆法严，不拆就是 i-j损敷，拆就是 dp[i-j]
dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
}
}
return dp[n];
};
有兩種方案：1、數(shù)學(xué)方案深啤，利用均值不等式進(jìn)行判斷處理拗馒；2、動態(tài)規(guī)劃
2021.07.09
No.410 分割數(shù)組的最大值
給定一個非負(fù)整數(shù)數(shù)組 nums 和一個整數(shù) m 溯街，你需要將這個數(shù)組分成 m 個非空的連續(xù)子數(shù)組诱桂。
設(shè)計一個算法使得這 m 個子數(shù)組各自和的最大值最小洋丐。
示例 1：
輸入：nums = [7,2,5,10,8], m = 2
輸出：18
解釋：
一共有四種方法將 nums 分割為 2 個子數(shù)組。 其中最好的方式是將其分為 [7,2,5] 和 [10,8] 挥等。
因為此時這兩個子數(shù)組各自的和的最大值為18友绝，在所有情況中最小。
示例 2：
輸入：nums = [1,2,3,4,5], m = 2
輸出：9
示例 3：
輸入：nums = [1,4,4], m = 3
輸出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/split-array-largest-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有肝劲。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)迁客，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=410 lang=javascript
*
* [410] 分割數(shù)組的最大值
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} m
* @return {number}
*/
var splitArray = function(nums, m) {
let max = 0
sum = 0;
for (let i = 0; i < nums.length; i++) {
if (max < nums[i]) max = nums[I];
sum += nums[I];
}
while (max < sum) {
let mid = parseInt((sum - max) / 2, 10) + max;
// 隨機(jī)選擇的值成立則這個值默認(rèn)為最大的可能結(jié)果繼續(xù)查找
if (check(nums, mid, m)) {
sum = mid;
} else {
// 不滿足辞槐，重置最小可能結(jié)果
max = mid + 1;
}
}
function check(nums, val, m) {
let sum = 0,
index = 1;
for (let i = 0; i < nums.length; i++) {
// 如果分段和大于了假設(shè)的結(jié)果說明掷漱，i是該分段的終點，形成一個分段
// index記錄+1榄檬，i就成了下一個分段的起點（重置sum）開始校驗下一個分段
if (sum + nums[i] > val) {
index++;
sum = nums[I];
} else {
sum += nums[I];
}
}
// 如果index即分段數(shù)量滿足小于等于m則說明這個假設(shè)值成立
return index <= m;
}
// 返回最小可能結(jié)果
return max;
};
方案二：
/*
* @lc app=leetcode.cn id=410 lang=javascript
*
* [410] 分割數(shù)組的最大值
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} m
* @return {number}
*/
var splitArray = function(nums, m) {
let len = nums.length,
sumList = Array(len + 1).fill(0),
dp = Array.from({ length: len + 1 }, () => Array(m + 1).fill(Number.MAX_VALUE));
// 逐位增加卜范，反面后面根據(jù)區(qū)間求區(qū)間和
for (let i = 0; i < len; i++) {
sumList[i + 1] = sumList[i] + nums[I];
}
// 默認(rèn)值
dp[0][0] = 0;
for (let i = 1; i <= len; i++) {
for (let j = 1; j <= Math.min(m, i); j++) {
// 前i個數(shù)分成j段
for (let x = j - 1; x < i; x++) {
// x最后一段的起點
// perv本輪分割完成 分段中最大的和
let prev = Math.max(dp[x][j - 1], sumList[i] - sumList[x])
// 該分割情況下最大分段和的最小值
dp[i][j] = Math.min(prev, dp[i][j])
}
}
}
return dp[len][m]
};
有兩種方案：1、二分法丙号；2先朦、動態(tài)規(guī)劃
2021.07.11
No.413 等差數(shù)列劃分
如果一個數(shù)列至少有三個元素，并且任意兩個相鄰元素之差相同犬缨，則稱該數(shù)列為等差數(shù)列喳魏。
例如，以下數(shù)列為等差數(shù)列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下數(shù)列不是等差數(shù)列怀薛。
1, 1, 2, 5, 7
數(shù)組 A 包含 N 個數(shù)刺彩，且索引從0開始。數(shù)組 A 的一個子數(shù)組劃分為數(shù)組 (P, Q)枝恋，P 與 Q 是整數(shù)且滿足 0<=P<Q<N 创倔。
如果滿足以下條件，則稱子數(shù)組(P, Q)為等差數(shù)組：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的焚碌。并且 P + 1 < Q 畦攘。
函數(shù)要返回數(shù)組 A 中所有為等差數(shù)組的子數(shù)組個數(shù)。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三個子等差數(shù)組: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]十电。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/arithmetic-slices
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有知押。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處鹃骂。
方案一：
/*
* @lc app=leetcode.cn id=413 lang=javascript
*
* [413] 等差數(shù)列劃分
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var numberOfArithmeticSlices = function(nums) {
// 判斷是否是等差數(shù)列
const isArithmetic = arr => {
const diff = arr[1] - arr[0];
for( let p = 0, q = p+ 1; p < arr.length -1; p++, q++ ) {
if( arr[q] - arr[p] != diff ) {
return false;
}
}
return true;
}
// 返回的個數(shù)
let n = 0;
for(let a = 0; a < nums.length - 2;a++ ) {
for(let b = a + 2; b < nums.length; ) {
if(!isArithmetic(nums.slice(a,b+1))) {
break;
} else {
n++;
b++
}
}
}
return n;
};
方案二：
/*
* @lc app=leetcode.cn id=413 lang=javascript
*
* [413] 等差數(shù)列劃分
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var numberOfArithmeticSlices = function(nums) {
let len = nums.length
if (len < 3) {
return 0
}
let dp = Array(len).fill(0)
for (let i = 2;i <= len;i++) {
if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
dp[i] = dp[i - 1] + 1
}
}
return dp.reduce((prev, cur) => { return prev + cur }, 0)
};
有兩種方案：1台盯、暴解；2畏线、動態(tài)規(guī)劃
2021.07.12
No.416 分割等和子集
給你一個 只包含正整數(shù) 的 非空 數(shù)組 nums 静盅。請你判斷是否可以將這個數(shù)組分割成兩個子集，使得兩個子集的元素和相等寝殴。
示例 1：
輸入：nums = [1,5,11,5]
輸出：true
解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 蒿叠。
示例 2：
輸入：nums = [1,2,3,5]
輸出：false
解釋：數(shù)組不能分割成兩個元素和相等的子集明垢。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)栈虚，非商業(yè)轉(zhuǎn)載請注明出處袖外。
方案：
/*
* @lc app=leetcode.cn id=416 lang=javascript
*
* [416] 分割等和子集
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
if(nums.length < 2) return false;
const sum = nums.reduce((prev, curr) => prev + curr);
if( sum % 2 !== 0) {
return false;
}
const target = sum / 2;
nums.sort((a,b) => b-a);
if(nums[0] > target) {
return false;
}
// 動態(tài)規(guī)劃
const dp = new Array(nums.length).fill(0).map(v => new Array(target + 1, false));
for (let i = 0; i < nums.length; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (let i = 1; i < nums.length; i++) {
const num = nums[I];
for (let j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[nums.length - 1][target];
};
NP完全史隆，可轉(zhuǎn)化為0-1背包問題魂务，動態(tài)規(guī)劃解決
2021.07.13
No.446 等差數(shù)列拆分 ii-子序列
如果一個數(shù)列至少有三個元素，并且任意兩個相鄰元素之差相同泌射，則稱該數(shù)列為等差數(shù)列粘姜。
例如，以下數(shù)列為等差數(shù)列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下數(shù)列不是等差數(shù)列熔酷。
1, 1, 2, 5, 7
數(shù)組 A 包含 N 個數(shù)孤紧，且索引從 0 開始。該數(shù)組子序列將劃分為整數(shù)序列 (P0, P1, ..., Pk)拒秘，滿足 0 ≤ P0 < P1 < ... < Pk < N号显。
如果序列 A[P0]，A[P1]躺酒，...押蚤，A[Pk-1]，A[Pk] 是等差的羹应，那么數(shù)組 A 的子序列 (P0揽碘，P1，…园匹，PK) 稱為等差序列雳刺。值得注意的是，這意味著 k ≥ 2裸违。
函數(shù)要返回數(shù)組 A 中所有等差子序列的個數(shù)掖桦。
輸入包含 N 個整數(shù)。每個整數(shù)都在 -231 和 231-1 之間供汛，另外 0 ≤ N ≤ 1000枪汪。保證輸出小于 231-1。
示例：
輸入：[2, 4, 6, 8, 10]
輸出：7
解釋：
所有的等差子序列為：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有紊馏。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)料饥，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @lc app=leetcode.cn id=446 lang=javascript
*
* [446] 等差數(shù)列劃分 II - 子序列
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var numberOfArithmeticSlices = function(nums) {
// 定義 i 的數(shù)組
let dp = Array(nums.length).fill(0).map(x=> new Object())
let ans = 0
for(let i=1; i<nums.length; ++i){
for(let j=0; j<i; ++j){
let sub = nums[i] - nums[j]
// 定義 sub 的鍵值對 [], 第0位代表序列長度為 2朱监，從第1位開始滿足題意要求
if(!(sub in dp[i])){
dp[i][sub] = [0]
}
dp[i][sub][0] += 1
if(sub in dp[j]){
for(let k=0; k<dp[j][sub].length; ++k){
if(dp[i][sub][k+1] === undefined) dp[i][sub][k+1] = 0
dp[i][sub][k+1] += dp[j][sub][k]
ans += dp[j][sub][k]
}
}
}
}
return ans
};
動態(tài)規(guī)劃
2021.07.14
No.698 劃分為k個相等的子集
給定一個整數(shù)數(shù)組 nums 和一個正整數(shù) k岸啡，找出是否有可能把這個數(shù)組分成 k 個非空子集，其總和都相等赫编。
示例 1：
輸入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
輸出： True
說明： 有可能將其分成 4 個子集（5）巡蘸，（1,4）奋隶，（2,3），（2,3）等于總和悦荒。
提示：
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有唯欣。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處搬味。
方案一：
/*
* @lc app=leetcode.cn id=698 lang=javascript
*
* [698] 劃分為k個相等的子集
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var canPartitionKSubsets = function(nums, k) {
const sum = nums.reduce((prev, curr) => prev + curr);
if( sum % k !== 0 ) return false;
const target = sum / k;
nums.sort((a,b) => b - a);
if(nums[0] > target) return false;
// 動態(tài)規(guī)劃
const MAX_STATE = (1 << nums.length) - 1 // 1 <= N <= 16
let dp = new Array(MAX_STATE + 1).fill(null)
dp[0] = 0
// 枚舉所有狀態(tài)境氢，遞推
for (let state = 1; state <= MAX_STATE; ++state) { // O(2^N)
for (let i = 0; i < nums.length; ++i) { // O(N)
const iBit = 1 << I
// 如果 state 表示未選取 nums[i] ，說明不能達(dá)到 (state, i) 狀態(tài)
if ((state & iBit) === 0) continue
const prevState = state ^ iBit
// NOTICE: 如果不能到達(dá) prevState 狀態(tài)
if (dp[prevState] === null) continue
const prevSubsetSum = dp[prevState] % target
// 最優(yōu)性剪枝優(yōu)化：nums 已升序排序碰纬，如果 nums[i] 已偏大萍聊，后續(xù)更加偏大，無需嘗試
if (prevSubsetSum + nums[i] > target) break
dp[state] = dp[prevState] + nums[i]
}
}
// console.log(dp)
return dp[MAX_STATE] === sum
};
方案二：
/*
* @lc app=leetcode.cn id=698 lang=javascript
*
* [698] 劃分為k個相等的子集
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var canPartitionKSubsets = function(nums, k) {
const sum = nums.reduce((prev, curr) => prev + curr);
if( sum % k !== 0 ) return false;
const target = sum / k;
nums.sort((a,b) => b - a);
if(nums[0] > target) return false;
// 回溯
const sums = new Array(k).fill(0);
const helper = (i, sums, target, nums, k) => {
if(i === nums.length) return true;
for( let j = 0; j< k; j++ ) {
if(sums[j] < target && nums[i] + sums[j] <= target) {
sums[j] += nums[I];
if(helper(i+1, sums, target, nums, k)) {
return true;
}
sums[j] -= nums[I];
}
}
return false;
}
return helper(0,sums, target, nums, k);
};
有兩種方案：1悦析、動態(tài)規(guī)劃寿桨，用二進(jìn)制對數(shù)組進(jìn)行表示；2强戴、回溯遞歸
2021.07.15
No.902 最大為N的數(shù)字組合
我們有一組排序的數(shù)字 D亭螟，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（請注意骑歹，'0' 不包括在內(nèi)预烙。）
現(xiàn)在，我們用這些數(shù)字進(jìn)行組合寫數(shù)字陵刹，想用多少次就用多少次默伍。例如 D = {'1','3','5'}，我們可以寫出像 '13', '551', '1351315' 這樣的數(shù)字衰琐。
返回可以用 D 中的數(shù)字寫出的小于或等于 N 的正整數(shù)的數(shù)目也糊。
示例 1：
輸入：D = ["1","3","5","7"], N = 100
輸出：20
解釋：
可寫出的 20 個數(shù)字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
輸入：D = ["1","4","9"], N = 1000000000
輸出：29523
解釋：
我們可以寫 3 個一位數(shù)字，9 個兩位數(shù)字羡宙，27 個三位數(shù)字狸剃，
81 個四位數(shù)字，243 個五位數(shù)字狗热，729 個六位數(shù)字钞馁，
2187 個七位數(shù)字，6561 個八位數(shù)字和 19683 個九位數(shù)字匿刮。
總共僧凰，可以使用D中的數(shù)字寫出 29523 個整數(shù)。
提示：
D 是按排序順序的數(shù)字 '1'-'9' 的子集熟丸。
1 <= N <= 10^9
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/numbers-at-most-n-given-digit-set
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有训措。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=902 lang=javascript
*
* [902] 最大為 N 的數(shù)字組合
*/
// @lc code=start
/**
* @param {string[]} digits
* @param {number} n
* @return {number}
*/
var atMostNGivenDigitSet = function(digits, n) {
digits.sort((a,b) => Number(a) - Number(b))
// 獲取n的位數(shù)
const UNIT = (n + '').length;
console.log('UNIT', UNIT)
// 獲取n對應(yīng)位置數(shù)組
const queue = (n + '').split('');
let sum = 0;
for(let i = 1; i < UNIT; i++) {
sum += Math.pow(digits.length, i)
}
// 輔助函數(shù)
const helper = (pos, queue, digits) => {
if (pos === queue.length) {
return 1;
}
let count = 0;
for (let i = 0; i < digits.length; i++) {
if (digits[i] < queue[pos]) {
count += Math.pow(digits.length, queue.length - pos - 1);
} else if (digits[i] == queue[pos]) {
count += helper(pos + 1, queue, digits);
} else {
break;
}
}
return count;
}
sum += helper(0, queue, digits)
return sum;
};
方案二：
/*
* @lc app=leetcode.cn id=902 lang=javascript
*
* [902] 最大為 N 的數(shù)字組合
*/
// @lc code=start
/**
* @param {string[]} digits
* @param {number} n
* @return {number}
*/
var atMostNGivenDigitSet = function(digits, n) {
const s = n + '';
const K = s.length;
const dp = new Array(K+1).fill(0);
dp[K] = 1;
for(let i = K -1; i >= 0; --i) {
let si = s[i];
for(let j=0; j < digits.length; j++) {
if(digits[j] < si) {
dp[i] += Math.pow(digits.length, K-i-1)
} else if(digits[j] == si) {
dp[i] += dp[i+1];
}
}
}
for(let k=1; k< K; ++k) {
dp[0] += Math.pow(digits.length, k)
}
return dp[0]
};
有兩種方案：1绩鸣、遞歸怀大；2、動態(tài)規(guī)劃
2021.07.16
No.923 三數(shù)之和的多種可能
給定一個整數(shù)數(shù)組 A呀闻，以及一個整數(shù) target 作為目標(biāo)值化借，返回滿足 i < j < k 且 A[i] + A[j] + A[k] == target 的元組 i, j, k 的數(shù)量。
由于結(jié)果會非常大捡多，請返回 結(jié)果除以 10^9 + 7 的余數(shù)蓖康。
示例 1：
輸入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
輸出：20
解釋：
按值枚舉（A[i]，A[j]局服，A[k]）：
(1, 2, 5) 出現(xiàn) 8 次钓瞭；
(1, 3, 4) 出現(xiàn) 8 次；
(2, 2, 4) 出現(xiàn) 2 次淫奔；
(2, 3, 3) 出現(xiàn) 2 次。
示例 2：
輸入：A = [1,1,2,2,2,2], target = 5
輸出：12
解釋：
A[i] = 1堤结，A[j] = A[k] = 2 出現(xiàn) 12 次：
我們從 [1,1] 中選擇一個 1唆迁，有 2 種情況，
從 [2,2,2,2] 中選出兩個 2竞穷，有 6 種情況唐责。
提示：
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/3sum-with-multiplicity
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)瘾带，非商業(yè)轉(zhuǎn)載請注明出處鼠哥。
方案：
/*
* @lc app=leetcode.cn id=923 lang=javascript
*
* [923] 三數(shù)之和的多種可能
*/
// @lc code=start
/**
* @param {number[]} arr
* @param {number} target
* @return {number}
*/
var threeSumMulti = function(arr, target) {
console.log('arr', arr.length)
// mod數(shù)
const mod = (10**9)+7;
// 階乘
const factorial = n => {
if (0 === n) {
return 1;
}
let res = 1;
for (let i = 1; i <= n; ++i) {
res *= I;
}
return res;
}
// Cmn函數(shù)
const combination = (m,n) => {
let s = 1;
for(let i =0;i< n;i++) {
s *= (m - i);
}
return s / factorial(n)
}
console.log('combination', combination(3000,3))
// 數(shù)組去重 并按從小到大排序
const _ = Array.from(new Set(arr)).sort((a,b) => a-b);
const LEN = _.length,
MAX = _[LEN-1],
MIN = _[0];
console.log('_', _)
// 在去重數(shù)組中去選擇符合要求的三個數(shù)
let i = 0,
j = LEN - 1,
m = ~~((i+j)/2);
// r用于存儲符合要求的數(shù)組
const r = [];
for(let i=0; i < LEN; i++) {
let j= LEN -1;
for(let m = i; m <= j;) {
if(_[i]+_[m]+_[j] == target) {
r.push([_[i], _[m], _[j]])
}
if(_[i]+_[m]+_[j]>target && m < j) {
j--;
m--
}
m++
}
}
console.log('r', r)
// 構(gòu)建值對應(yīng)數(shù)量的map
const map = {};
for(let num = 0; num < LEN; num++) {
let key = _[num],
value = arr.filter(f => f == key).length;
map[key] = value;
}
console.log('map', map)
// 對r進(jìn)行排查
let sum = 0;
r.forEach(item => {
if(item[0] == item[1] && item[1] == item[2]) {
if(map[`${item[0]}`] >= 3) {
console.log('走了 A A A')
sum += combination(map[`${item[0]}`], 3)
}
} else if(item[0] != item[1] && item[1] == item[2]) {
if(map[`${item[1]}`] >= 2) {
console.log('走了 A B B')
sum += combination(map[`${item[0]}`], 1)*combination(map[`${item[1]}`], 2)
}
} else if(item[0] == item[1] && item[1] != item[2]) {
if(map[`${item[0]}`] >= 2) {
console.log('走了 A A B')
sum += combination(map[`${item[0]}`], 2)*combination(map[`${item[2]}`], 1)
}
} else if(item[0] != item[1] && item[1] != item[2] && item[0] != item[2]) {
console.log('走了 A B C')
sum += combination(map[`${item[0]}`], 1)*combination(map[`${item[1]}`], 1)*combination(map[`${item[2]}`], 1)
}
})
console.log('sum', sum)
return sum % mod;
};
三指針法，階乘可進(jìn)行動態(tài)規(guī)劃實現(xiàn)
總結(jié)：
- 拆分組合問題關(guān)鍵在于對問題的轉(zhuǎn)移方程定義及建模看政，將狀態(tài)可以逐步轉(zhuǎn)移朴恳，從而解決問題；
- 在狀態(tài)方程建立過程中允蚣，常常需要結(jié)合其他常見方法如指針于颖、遞歸等方法來進(jìn)行優(yōu)化
