文章目录

• 1. 买卖股票的最佳时机 III
• • 题干：
  • 算法原理：
  • • 1. 状态表示：
    • 2. 状态转移方程
    • 3. 初始化
    • 4. 填表顺序
    • 5. 返回值
    • 代码：
    • 2. Z 字形变换
    • • 题干：
      • 算法原理：
      • • 1. 模拟
        • 2. 找规律
        • 代码：

          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();
              }
          }
          

          

           
           流量套餐哪个最划算  网站流量  山东企业网站建设  沈阳网站制作多少钱  摄影网站制作  网站的建设与优化