文章目录
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();
}
}
