动态规划

动态规划

买卖股票的最佳时机

  • 用一个变量记录一个历史最低价格 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;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

编辑距离