动态规划

动态规划

买卖股票的最佳时机

  • 用一个变量记录一个历史最低价格 minprice,如果当前值比 minPrice 小,则更新 minPrice。即我们全程都在寻找一个历史最低值。
  • 否则就考虑是否可以卖出:看当前值减去 minPrice 是否可以更新 maxProfit
public int maxProfit(int prices[]) {
    int minprice = Integer.MAX_VALUE;
    int maxprofit = 0;

    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minprice) {
            minprice = prices[i];
        } else if (prices[i] - minprice > maxprofit) {
            maxprofit = prices[i] - minprice;
        }
    }

    return maxprofit;
}

最大子序和

找到一个具有最大和连续子数组

看当前累加的 sum 对求最终的最大和是否有正向的增益效果。

腾讯:返回子数组

public int maxSubArray(int[] nums) {
    int ans = nums[0];
    int sum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (sum > 0) {
            sum += nums[i];
        } else {
            sum = nums[i];
        }

        ans = Math.max(sum, ans);
    }

    return ans;
}

最长上升子序列

又名:最长递增子序列。

思路:记录下来,当前找到的长度为 1、2、3 … 序列的各自的最大值。例如长度为 2 有 [3, 7],那么当前记录的就是 7,如果接下来遇到了 5,那么就将 7 这个数字更新为 5,也就意味着长度为 2 的序列的最大值是 5。

如下图代码所示,建立一个与原 array 长度相同的数组 lisLength。此数组的每一个数值的含义:索引 0 的值代表的是长度为 1 的序列的最小值;索引 1 的值代表的是长度为 2 的序列的最小值;索引 2 的值代表的是长度为 3 的序列的最小值 …

hi 的值是用来指向索引的,其标识的是当前最大序列长度的索引。如果 hi 当前值是 2,那么表示当前序列的最大长度为 3。

索引:[0, 1, 2, 3, 4, ...] array
      |  |  |  |  |   |
长度:[1, 2, 3, 4, 5, ...] lisLength

array[i]lisLength[hi] 小于或者等于的时候,可以运用二分查找来更新。首先 lisLength 一定是一个严格递增的数组。

lisLength: 1, 3, 5, 7, 9, 遇到了一个 4

我们的目标是找到第一个大于等于 target = 4 的这个值 5,然后将 5 替换成 4。注意是 lisLength[mi]target 进行对比,而非 array[mi] ,这个地方千万不要写错了(我就写错过)!!!

int find = 0;

while (lo <= hi) {
    int mi = lo + ((hi - lo) >> 1);
    if (lisLength[mi] >= target) {
        // target, lisLength[mi], ...
        if (mi == 0 || lisLength[mi - 1] < target) {
            // mi 确实是了
            find = mi;
            break;
        } else {
            // target, A, B, C, lisLength[mi]
            hi = mi - 1;
        }
    } else {
        lo = mi + 1;
    }
}

lisLength[find] = target;
public int lengthOfLIS(int[] array) {
    if (array.length == 0) {
        return 0;
    }

    // [10,9,2,5,3,7,101,18]
    //  1(10)
    //     1(9)
    //       1(2)
    //         2(5)
    //           2(3)
    //             3(7)
    //               4(101)
    //                   4(18)
    //
    // 每个长度 i + 1 的最小值
    // 这是一个有序序列
    int[] lisLength = new int[array.length];
    lisLength[0] = array[0];
    int hi = 0;

    // [10,9,2,5,3,4]
    //  1(10)
    //     1(9)
    //       1(2)
    //         2(5)
    //          2(3)
    //             3(4)

    for (int i = 1; i < array.length; i++) {
        if (array[i] > lisLength[hi]) {
            lisLength[++hi] = array[i];
        } else {
            // [2,3,5] 4, 
            //
            // 我们不是要将 [2,3,5] 中的 3 替换为 4
            // 而是要将 5 替换 4
            //
            // =============================
            // 二叉树版本
            // 找到第一个大于 target 的值的索引
            //
            // 测试未通过 [18,55,66,2,3,54]
            // 
            // [18,55,66,2,3,54]
            //   1(18)
            //     2(55)
            //        2(66)
            //           1(2)
            //            2(3)
            //               3(54)
            // =============================

            int l = 0;
            int h = hi;
            int target = array[i];
            int find = 0;

            while (l <= h) {
                int mi = l + ((h - l) >> 1);
                if (lisLength[mi] >= target) {
                    // target, lisLength[mi], ...
                    if (mi == 0 || lisLength[mi - 1] < target) {
                        // mi 确实是了
                        find = mi;
                        break;
                    } else {
                        // target, A, B, C, lisLength[mi]
                        h = mi - 1;
                    }
                } else {
                    l = mi + 1;
                }
            }

            lisLength[find] = array[i];
        }
    }

    return hi + 1;
}

猿辅导二面:返回那个最长的子序列而不是长度。

接雨水

思路 求每一列的水,我们只需要关注当前列,以及左边最高的墙右边最高的墙就够了。

装水的多少,当然根据木桶效应,我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

明白了这种情况,程序就很好写了,遍历每一列,然后分别求出这一列两边最高的墙。找出较矮的一端,和当前列的高度比较。这种复杂度是 O(N^2)

我们注意到,上述解法二中。对于每一列,我们求它左边最高的墙和右边最高的墙,都是重新遍历一遍所有高度,这里我们可以优化一下。

首先用两个数组,max_left[i] 代表第 i 列左边最高的墙的高度,max_right[i] 代表第 i 列右边最高的墙的高度。

对于 max_left我们其实可以这样求。

max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度它前边的墙的高度选一个较大的,就是当前列左边最高的墙了。

对于 max_right 我们可以这样求。

max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度它后边的墙的高度选一个较大的,就是当前列右边最高的墙了。

下面是自己根据上述思路写出来的代码。需要注意:

  • leftMaxHeight[i] = Math.max(height[i - 1], leftMaxHeight[i - 1]) 这个地方必须是 height[i - 1],不能是 height[i] 否则会出错。同理 rightMaxHeight 也是一样。某一列左侧的最高高度,不能将自己这一列的高度也算进去
public int trap(int[] height) {
    int[] leftMaxHeight = new int[height.length];
    int[] rightMaxHeight = new int[height.length];

    for (int i = 1; i < height.length; i++) {
        leftMaxHeight[i] = Math.max(height[i - 1], leftMaxHeight[i - 1]);
    }

    for (int i = height.length - 2; i >= 0; i--) {
        rightMaxHeight[i] = Math.max(height[i + 1], rightMaxHeight[i + 1]);
    }

    int sum = 0;
    for (int i = 1; i < height.length - 1; i++) {
        int minHeight = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
        if (minHeight > height[i]) {
            sum += minHeight - height[i];
        }
    }

    return sum;
}

爬楼梯

其实就是斐波那契数列。

扩展:不能爬到7及7的倍数——2021.3 字节跳动-教育-后端-一面

打家劫舍②

原题

所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下 ,能够偷窃到的最高金额。

class Solution {

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), 
                        myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int myRob(int[] nums) {
        // [前一次,现在]
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;

            // 只有前一次才可以窃取
            // 当前 = max(前一次 + 新窃取的, 维持当前)
            cur = Math.max(pre + num, cur);

            // 更新了当前了,那么前一次也需要改为当前了
            pre = tmp;
        }
        return cur;
    }
}

打劫房屋 III

知识点: 树形动态规划

每一层的任何一个节点都有两个状态, 偷或者不被偷。

rob3[0] 代表这一层不偷rob3[1] 代表这一层

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    public int houseRobber3(TreeNode root) {
        // write your code here
        int[] rob3 = dfs(root);
        return Math.max(rob3[0], rob3[1]);
    }
    
    private int[] dfs(TreeNode root){
      if(root == null){
        return new int[2];
      }
      
      int[] left = dfs(root.left);
      int[] right = dfs(root.right);
      
      int[] res = new int[2];
      
      //这一层不偷, 下一层随便偷
      res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
      // 这一层偷
      //          root(偷)
      //         /       \
      // left[0](不偷)  right[0](不偷)
      res[1] = root.val + left[0] + right[0];
      
      return res;
    }
}

编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

解析:dp[i][j] 代表 word1i 位置转换成 word2j 位置需要最少步数。

  • word1[i] == word2[j]dp[i][j] = dp[i-1][j-1]
  • word1[i] != word2[j]dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

针对第一行第一列要单独考虑。

public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];

    // 第一行
    for (int j = 1; j <= n2; j++) 
        dp[0][j] = dp[0][j - 1] + 1;

    // 第一列
    for (int i = 1; i <= n1; i++) 
        dp[i][0] = dp[i - 1][0] + 1;

    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) 
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
        }
    }
    return dp[n1][n2];  
}