【算法刷题】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();
    }
}

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>