Leetcode-350-两个数组的交集Ⅱ

发表于 2020-07-13 | 分类于 Leetcode

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

哈希表

遍历较短的数组, 使用哈希表来存储每一个元素出现的次数.

然后遍历另外一个数组, 查看元素是否在哈希表中. 如果在, 则将其添加到结果数组中, 并且更新哈希表中的值.

代码如下

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums1) {
            int cnt = hashMap.getOrDefault(num, 0) + 1;
            hashMap.put(num, cnt);
        }
        int[] res = new int[nums1.length];
        int len = 0;
        for (int num : nums2) {
            int cnt = hashMap.getOrDefault(num, 0);
            if (cnt > 0) {
                res[len++] = num;
                cnt--;
                if (cnt > 0) {
                    hashMap.put(num, cnt);
                } else {
                    hashMap.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(res, 0, len);
    }
}

Leetcode-174-地下城游戏

发表于 2020-07-12 | 分类于 Leetcode

题目

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K) -3 3

-5 -10 1

10 30 -5 (P)

说明:

骑士的健康点数没有上限。

任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

动态规划

此处需要按照从右下角到左上角的顺序进行动态规划.

假设dp[i][j]为在位置(i, j)到终点所需要的最小起始生命值. 假设dp[i+1][j]和dp[i][j+1]是已知的, 那么dp[i][j]应该等于dp[i+1][j]和dp[i][j+1]的最小值, 再减去当前位置所要消耗的生命值dungeon(i,j), 并且要注意, 初始生命值应该是大于等于1的.

根据上述描述可知, 动态转移方程为

$dp[i][j]=max(min(dp[i+1][j], dp[i][j+1])-deungen(i, j), 1)$

对于边界条件, 需要对dp[n][m-1]和dp[n-1][m]设置为1, 而dp其他位置则需要设置为Integer.MAX_VALUE.

代码如下

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length, m = dungeon[0].length;
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
}

Leetcode-309-最佳买卖股票时机含冷冻期

发表于 2020-07-10 | 分类于 Leetcode

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

动态规划

使用dp[i]来表示第i天结束之后的累计最大收益. 因为题目中包含了冷冻期的概念, 所以可以用数组的第二维来表示第i天结束之后的状态.:

第i天结束之后, 持有股票, 对应的累计最大收益为dp[i][0]
第i天结束之后, 不持有股票, 处于冷冻期, 对应的累计最大收益为dp[i][1]
第i天结束之后, 不持有股票, 不处于冷冻期, 对应的累计最大收益为dp[i][2]

冷冻期的定义: 第i天处于冷冻期, 则第 i+1天不能买股票.

下面对三种状态进行分析:

第i天结束之后, 持有股票, 对应的累计最大收益为dp[i][0].

对于第i天结束之后持有的股票, 存在两种情况:
1. 是第i天购买的, 那么说明第i-1天不能持有股票, 且不处于冷冻期, 对应的累计最大收益为dp[i-1][2], 还需要考虑到第i天买了股票, 产生了负收益-prices[i], 那么该情况下的累计最大收益为dp[i-1][2]-prices[i]
2. 是第i-1天时就已经持有(注意, 不是购买)的股票, 那么对应的累计最大收益为dp[i-1][0]
第 i天结束后持有股票对应的累计最大收益为上述两种情况的较大者, 即
第i天结束之后, 不持有股票, 处于冷冻期, 对应的累计最大收益为dp[i][1]

第i天结束之后, 不持有股票, 处于冷冻期, 说明了第i天刚卖出了股票, 对应的累计最大收益为前一天的累计最大收益加上今天卖出股票所获得的收益, 而前一天的累计最大收益是持有股票的情况, 即dp[i-1][0]. 总的来说, 就是
$dp[i][1]=prices[i]+dp[i-1][0]$
第i天结束之后, 不持有股票, 不处于冷冻期, 对应的累计最大收益为dp[i][2]

第i天结束之后, 不持有股票, 不处于冷冻期, 说明这一天没有进行操作, 也说明了第i-1天没有持有股票:
1. 如果第i-1天不处于冷冻期, 对应的累计最大收益为dp[i-1][1]
2. 如果第i-1天处于冷冻期, 对应的累计最大收益为dp[i-1][2]
第i天的累计最大收益为

最后一天(n-1天)结束之后, 累计最大收益为三种状态下的最大值.

$max(dp[n-1][0], dp[n-1][1], dp[n-1][2])$

然而比较dp[n-1][0]是没有意义的, 因为这说明最后一天结束的时候还持有股票. 也就是只要比较后面两种状态就可以了:

$max(dp[n-1][1], dp[n-1][2])$

代码如下:

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
        }
        return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
    }
}

Leetcode-1504-统计全1子矩阵

发表于 2020-07-07 | 分类于 Leetcode

题目

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个子矩形的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],
[1,1,0],
[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
示例 2：

输入：mat = [[0,1,1,0],
[0,1,1,1],
[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
示例 3：

输入：mat = [[1,1,1,1,1,1]]
输出：21
示例 4：

输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5

提示：

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

动态规划

定义dp数组

用dp[i][j]来表示从mat[i][0]到mat[i][j]最多有多少个连续的1. 动态转移方程为:

而临界值dp[i][0]则等于mat[i][0].

比如下面的矩阵中, dp[3][2]=3, dp[2][2]=2, dp[1][2]=3, dp[0][2]=1

计算思路

对于每一个元素mat[i][j], 我们将其当作一个矩阵的右下角来计算他能组成的矩阵数目.

比如, 对于元素mat[3][2], 以其作为矩阵的右下角, 只考虑最后一行(从0开始数, 第3行, 下同)所构成的矩阵, 他能构成的矩阵为三个, 如图所示.

然后考虑由第2, 3行构成的, 以mat[3][2]为右下角的矩阵, 有两个, 如图所示.

然后考虑由第1, 2, 3行构成的, 以mat[3][2]为右下角的矩阵, 也是有两个, 如图所示.

最后, 由第0, 1, 2, 3行构成的, 以mat[3][2]为右下角的矩阵, 有一个, 如图所示.

也就是说, 照着以上步骤的对矩阵mat中的每一个元素进行一遍以上的运算, 然后计算矩阵数的总和即可.

那么, 最后还有一个问题. 以元素mat[i][j]为右下角的矩阵能构成的个数是怎么计算的呢?

由上面的步骤可以轻松看出来, 对于元素mat[i][j], 计算k到i行构成的矩阵数目时, 该数目等于dp[k..i][j]的最小值, 也就是连续为1的数量的最小值. 如图所示, 因为最小值为1, 所以可以构建的矩阵个数为1.

实现代码

代码如下

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int sum = 0;
        
        // dp初始化
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = mat[i][0];
        }
        
        // 遍历每一个元素, 计算矩阵个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // mat[i][j]为0时, dp[i][j]直接置零, 说明在此位置没有连续1
                if (mat[i][j] == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                int min = Integer.MAX_VALUE;
                if (j > 0) {
                    dp[i][j] = dp[i][j - 1] + 1;
                }
                for (int k = i; k >= 0; k--) {
                    min = Math.min(min, dp[k][j]);
                    sum += min;
                }
            }
        }
        return sum;
    }
}

Leetcode-1503-所有蚂蚁掉下来前的最后一刻

发表于 2020-07-07 | 分类于 Leetcode

有一块木板，长度为 n 个单位。一些蚂蚁在木板上移动，每只蚂蚁都以每秒一个单位的速度移动。其中，一部分蚂蚁向左移动，其他蚂蚁向右移动。

当两只向不同方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1：

输入：n = 4, left = [4,3], right = [0,1]
输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。
示例 2：

输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。
示例 3：

输入：n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
示例 4：

输入：n = 9, left = [5], right = [4]
输出：5
解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。
示例 5：

输入：n = 6, left = [6], right = [0]
输出：6

提示：

1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
left 和 right 中的所有值都是唯一的，并且每个值只能出现在二者之一中。

思路

乍一看这题目很复杂, 但是其实只要转换一下思路, 不区分具体的蚂蚁, 其实碰撞之后掉头和直接穿过去的结果是一样的. 那么问题就变成了求最晚落地的蚂蚁所需要的时间. 也就是最晚落地蚂蚁所走过的路径长度.

代码如下

class Solution {
    public int getLastMoment(int n, int[] left, int[] right) {
        int max = -1;
        for (int i = 0; i < left.length; i++) {
            if (left[i] > max) max = left[i];
        }
        for (int i = 0; i < right.length; i++) {
            if (n - right[i] > max) max = n - right[i];
        }
        return max;
    }
}

Leetcode-112-路径总和

发表于 2020-07-07 | 分类于 Leetcode

题目

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

分治算法

很简单, 直接左右子树进行判断, 然后对布尔量求逻辑或即可. 注意边界条件, 在root==null的时候, 说明没有该路径, 返回false.

代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (sum - root.val == 0 && root.left == null && root.right == null) return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); 
    }
}

Leetcode-63-不同路径Ⅱ

发表于 2020-07-06 | 分类于 Leetcode

题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

向右 -> 向右 -> 向下 -> 向下

向下 -> 向下 -> 向右 -> 向右

动态规划

本题就是经典的动态规划题目.

使用dp[i][j]来表示到达obstacleGrid[i][j]时的路径数. 明显dp[i][j]的路径数目等于左边dp[i][j-1]的路径数目加上上面dp[i-1][j]的路径数目. 即动态转移方程为

$dp[i][j]=dp[i][j-1]+dp[i-1][j]$

初始化时, 需要将dp[0][0]设置为1.

在遍历的过程中如果遇到obstacleGrid[i][j]==1, 说明遇到了障碍, 对应的dp[i][j]需要置为0, 表示此处已经没有路径了.

代码如下

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i - 1 >= 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j - 1 >= 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
        return dp[m -1][n - 1];
    }
}

需要注意的地方是, Leetcode的测试用例中, 包含了在入口和出口设置障碍的情况. 但是上述代码中, 当obstacleGrid[i][j]==1时, 将dp[i][j]设置为0, 则可以避开这个问题.

Leetcode-44-通配符匹配

发表于 2020-07-05 | 分类于 Leetcode

题目

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = ““
输出: true
解释: ‘‘ 可以匹配任意字符串。
示例 3:

输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:

输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.
示例 5:

输入:
s = “acdcb”
p = “a*c?b”
输出: false

动态规划

可以用动态规划的思想来解决此题.

假设dp[i][j]表示字符串s的前i个字符和模式p的前j个字符能否匹配.

那么就有:

若p[j]是*, 说明模式p对字符串没有任何要求, 若*匹配的是空字符串, 则说明当前dp[i][j]依赖于dp[i][j-1]. 如果*匹配的不是空字符串, 那么dp[i][j]则依赖于dp[i-1][j]. 即转移方程为:
$dp[i][j]=dp[i][j-1]\ ||\ dp[i-1][j]$
若p[j]是?, 说明模式p可以匹配任何一个字符, 当前字符匹配的结果取决于前一个字符匹配的结果. 动态转移方程为:
$dp[i][j]=dp[i-1][j-1]$
若p[j]是小写字母(最后剩下的情况), 那么s[i]和p[j]必须是相同的字母, 动态转移方程为:
$dp[i][j]=(s[i]==s[j])\ and\ dp[i-1][j-1]$

接下来看一下dp数组的边界情况.

当i=j=0时, 用空模式去匹配空字符串, 结果必然为真, 即dp[0][0]=true
当j=0, i!=0时, 用空模式去匹配非空字符串, 结果必然为假, 即dp[i][0]=false
当i=0, j!=0时, 用模式去匹配空字符串, 此时只有模式在j之前都为*才为真.

具体代码如下

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();

        // 初始化dp
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        // dp迭代
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else if (p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1)) && dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
}

Leetcode-32-最长有效括号

发表于 2020-07-04 | 分类于 Leetcode

题目

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

栈

对于括号匹配问题, 最经典的处理方法是使用栈.

遍历字符串:

遇到(时, 将其下标入栈
遇到)时, 说明括号匹配正常. 出栈并计算当前下标能够成的有效括号子串.

问题就在于如何计算出栈时的最长有效括号字串.

我们可以先将-1置于栈底.

如果出栈之后栈底不为空, 则将当前的下标减去栈顶, 就是当前的有效括号子串.
如果出栈之后栈底为空, 那么将当前下标(必为右括号)的下标) 放入栈底即可.

过程如图所示

代码如下

class Solution {
    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(-1); 
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}

Leetcode-108-将有序数组转换为二叉搜索树

发表于 2020-07-03 | 分类于 Leetcode

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

二分思路

将数组中最中间的元素作为根结点构建二叉树, 并递归构建左右子树即可.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
        return root;
    }
}