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 的时候特殊处理文章来源:https://www.toymoban.com/news/detail-786763.html
代码:
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();
}
}
文章来源地址https://www.toymoban.com/news/detail-786763.html
到了这里,关于【算法刷题】Day28的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!