【算法刷题】Day28

1. 买卖股票的最佳时机 III

原题链接

---

题干：

第 i 个元素是一支给定的股票在第 i 天的价格
最多可以完成 两笔 交易
注意：你不能同时参与多笔交易

---

算法原理：

1. 状态表示：

dp[i] 表示：第 i 天结束之后，所能获得的最大利润

f[i][j] 表示：第 i 天结束之后，完成了 j 次交易，此时处于“买入”状态下的，最大利润
g[i][j] 表示：第 i 天结束之后，完成了 j 次交易，此时处于“卖出”状态下的，最大利润

2. 状态转移方程

f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i])

g[i][j] = g[i - 1][j]
if(j - 1 >= 0) {
g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
}

3. 初始化

4. 填表顺序

从上往下填写每一行
每一行从左往右，两个表一起填

5. 返回值

g 表的最后一行里面的最大值

---

代码：

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int INF = 0x3f3f3f3f;int[][] f = new int[n][3];int[][] g = new int[n][3];for(int j = 0; j < 3; j++) {f[0][j] = g[0][j] = -INF;}f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1; i < n; i++) {for(int j = 0; j < 3; j++) {f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j - 1 >= 0) {g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}int ret = 0;for(int j = 0; j < 3; j++) {ret = Math.max(ret, g[n - 1][j]);}return ret;}
}

---

2. Z 字形变换

原题链接

---

题干：

字符串 s，给定的行数 numRows
从上往下、从左到右进行 Z 字形排列
输出需要从左往右逐行读取

---

算法原理：

1. 模拟

2. 找规律

第一行：0 到 0+d 到 0+2d…0+kd

第 k 行：(k, d-k) 到 (k+d, d-k+d) 到 (k+2d, d-k+2d)

第 n-1 行：n-1 到 n-1+d 到 n-1+2d…n-1+kd

当 n = 1 的时候特殊处理

---

代码：

class Solution {public String convert(String s, int numRows) {// 处理一下边界情况if(numRows == 1) {return s;}int d = 2 * numRows - 2;int n = s.length();StringBuilder ret = new StringBuilder();//1. 处理第一行for(int i = 0; i < n; i += d) {ret.append(s.charAt(i));}//2. 处理中间行for(int k = 1; k < numRows - 1; k++) {// 依次枚举中间行for(int i = k, j = d - i; i < n || j < n; j += d, i += d) {if(i < n) {ret.append(s.charAt(i));}if(j < n) {ret.append(s.charAt(j));}}}//3. 处理最后一行for(int i = numRows - 1; i < n; i += d) {ret.append(s.charAt(i));}return ret.toString();}
}