月度归档： 2021年9月

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

示例 1：

输入：machines = [1,0,5]
输出：3
解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   

示例 2：

输入：machines = [0,3,0]
输出：2
解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     

示例 3：

输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

提示：

• n == machines.length
• 1 <= n <= 104
• 0 <= machines[i] <= 105

有点绕。

大意是，最大次数为要往某个区域内移入的最大次数，或者当前位置的洗衣机移出的最大次数，这两个值中较大的一个。

class Solution {
    public int findMinMoves(int[] machines) {
        int sum = 0;
        int[] preSum = new int[machines.length+1];
        for (int i = 0; i < machines.length; i++) {
            preSum[i+1] = preSum[i] + machines[i];
        }
        sum = preSum[machines.length];
        if (sum % machines.length != 0){
            return -1;
        }
        int avg = sum/machines.length;
        int ans = 0;
        for (int i = 0; i < machines.length; i++) {
            ans = Math.max(ans,Math.abs(preSum[i] - avg * i));
            ans = Math.max(machines[i]-avg,ans);
        }
        return ans;
    }
}

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

• 二叉树的节点个数的范围是 [0,1000]
• -109 <= Node.val <= 109 
• -1000 <= targetSum <= 1000 

解析

首先要求从根节点往下的某个链路上的区间合，这个问题点上携带了两个信息，

1. 从根节点往下的链路：自然会想到深度优先遍历
2. 区间合：那么对应的是前缀和概念

以图上二叉树为例

1. 从根节点5开始遍历，当前节点的前缀和为5
2. 遍历5的左子树，当前节点的值为4，那么当前对应前缀和为9，但是前面的上级节点的前缀和依旧要带下来，拿当前节点和上级节点的前缀和相减，判断结果值是否为targetSum，其实到这一步基本实现逻辑就已经比较清晰了
3. 继续遍历下面的11节点，得到前缀和`[5,9,20]`，但是依旧没能得到targetSum=22
4. 继续遍历下面的节点7，得到前缀和`[5,9,20,27]`，此时我们拿27和前面的相减判断targetSum的时候发现和5相减可以得到22，那么要求解的符合targetSum的数量加1
5. 再继续遍历右边的2节点`[5,9,20,22]`，这时候容易忽略了一个点，此时的22和前面的值相减的确实没有能得到targetSum=22，但是如果此时的节点的前缀和为22的话表示的是当前节点到根节点一整个链路的和为0
6. 剩下的就继续这样处理了

在编码之前的思考

保存这样一个节点的前缀和的时候[5,9,20,22]，最先想到的是 List 集合，但是 List 集合的话，我们就需要挨个遍历这个集合，这显然不够优美。

而这一步我们需要的判断的仅仅是判断 currentSum 减去这个集合中的某个数字能否等于 targetSum ，那么自然的可以想到用 Hash 来保存之前的前缀和集合，而判断能否凑成 targetSum 只需判断在这个 Hash 集合中是否存在 currentSum-targetSum 这个值。

但是这样就又有了另外一个问题，因为节点中的值是存在负数的，就存在可能某两个节点的前缀和相同的情况，所以原来的Hash集合就可以用 HashMap ，key存放的是前缀和，而 value 存放的是这个前缀和的个数， 如果有相同的则个数加1，而在退出这个节点的递归的时候则对这个 key 的 value 值减1。

在现在的这个思路下，我们还可以在初始的 HashMap中多增加一个 key = 0 、 value = 1来表示根节点上面一个不存在的节点的情况。

class Solution {
    int count = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    int preSum = 0;
    int targetSum;
    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        map.put(0,1);
        dfs(root);
        return count;
    }

    public void dfs(TreeNode node) {
        if (null==node){
            return;
        }
        int currentSum = preSum + node.val;
        preSum = currentSum;
        count += map.getOrDefault(currentSum-targetSum,0);
        map.put(currentSum,map.getOrDefault(currentSum,0)+1);
        dfs(node.left);
        preSum = currentSum;
        dfs(node.right);
        map.put(currentSum,map.get(currentSum)-1);
    }
}

另外一个细节点，在dfs(node.left);之后 preSum值会被更新掉，所以我在dfs(node.right);之前重新修正了一下 preSum，当然你可以选择把这个preSum作为DFS方法的参数往下传递。

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

直接上图，以一组数据【1,2,1,3,1】为例，浅蓝色部分为建立的DP数组的下标。

• 没有任何数字凑出结果1的方式有1种，这是一种额外的情况，以这个为基础
• 当拿到一个数字1的时候，在上一层的结果0的基础上可以加1也可以减1，那么就到达-1和1的方法就各为1种
• 当额外拿到一个数字2的时候，在原来数字1的结果-1和1的基础上，都可以进行+2和减2操作，那么此时可以得到的结果为-3、-1、1、3
• 在上一轮的结果上，继续加减1操作，如果有结果重合的部分，说明可以有不同的路径可以到达，此时结果应进行叠加
• 继续循环处理上面的操作

那么转移方程

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

代码，不过没有这么写，而是反向的，由第i层把值推向第i+1层

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target>sum || target < -sum){
            return 0;
        }
        int[][] dp = new int[nums.length+1][sum * 2 + 1];
        dp[0][sum] = 1;
        for (int row = 0; row < nums.length; row++) {
            for (int col = 0; col < dp[row].length; col++) {
                if (dp[row][col]!=0){
                    dp[ row + 1 ][ col - nums[row] ] += dp[row][col];
                    dp[ row + 1 ][ col + nums[row] ] += dp[row][col];
                }
            }
        }
        return dp[dp.length-1][sum + target];
    }
}

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

• 首位为0的定然不符合
• 如果字符串长度只有1的话，肯定只有一种情况直接先返回
• 如果字符串长度大于2，对第二位单独做个情况处理。
  • 如果第二个字符串为0，此时他不能单独处理，需要跟前一位合并解析
    1. 如果合并起来大于26，那么是解析不到对应的，直接返回0
    2. 如果合并起来不大于26，那么此时应该是10或者20的情况，只有一种解析方式，此时的组合数为1
  • 如果第二个字符串不为0
    1. 如果和前面组合起来小于等于26，说明可以分开也可以组合起来解析，此时组合数为1
    2. 如果大于26，则只能分开解析。可能组合数仍然为1
• 从第三位往后开始解析处理，假设当前位置的索引为i
  • 和上面类似，如果当前字符为‘0’，只能和前面字符组合起来解析
    1. 如果值大于26，或者前一个数字也为0，无法解析，返回0
    2. 否则当前位置一定为10或者20，当前位置【i】和前一位【i-1】是一个整体，这样能解析出来的组合数量和【i-2】位能获得的组合数量是一致的
  • 如果当前位置字符不为0，
    • 如果和前面组合起来的话大于26，说明不能和前面的值组合起来解析，则当前位置能获得的组合数量和前面一位【i-1】一致
    • 如果不大于26
      • 如果前一位为0，即组合起来的值小于等于9，则不能和前一位组合，可能的组合数依旧和前一位【i-1】的组合数一致
      • 如果不为0，那么可能组合成11到19和21到26之间的数值，即说明可以和前一位组合（值等于【i-2】位的），也可以不组合（值等于【i-1】位的）。即为【i-1】加上【i-2】位的和

class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0' ){
            return 0;
        }
        if (s.length() == 1){
            return 1;
        }
        int[] dp = new int[s.length()];
        dp[0] = 1;
        int i = 1;
        int curNum = s.charAt(i)-'0';
        int withBefore = (s.charAt(i-1)-'0') * 10 + (s.charAt(i)-'0');
        if (curNum==0 ){
            if (withBefore > 26 || withBefore ==0){
                return 0;
            }
            dp[i] = 1;
        }else{
            if (withBefore <= 26){
                dp[i] = 2;
            }else{
                dp[i] = 1;
            }
        }
        i++;
        for (; i < dp.length; i++) {
            curNum = s.charAt(i)-'0';
            withBefore = (s.charAt(i-1)-'0') * 10 + (s.charAt(i)-'0');
            if (curNum == 0){
                if (withBefore > 26 || withBefore ==0){
                    return 0;
                }
                dp[i] = dp[i-2];
            }else{
                if (withBefore > 26){
                    dp[i] = dp[i-1];
                }else {
                    if (withBefore>9){
                        dp[i] = dp[i-1] + dp[i-2];
                    }else {
                        dp[i] = dp[i-1];
                    }
                }
            }
        }
        return dp[dp.length-1];
    }
}

这题动归本身并不复杂，复杂的各种逻辑情况的判定分析，分支略有点多。

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

给定几个数字，看这几个数字能否凑出另一个数字，这个数字是这些数字的总和的一半，非常经典的0/1背包问题。

我们建立如下图中的DP数组

垂直方向上的表示使用从这个数字到他上面的数字，比如7这行，表示使用1,5,7这几个数字。而对应的横行表示要凑出的数字，对应坐标表示能否凑出这个数字。

比如纵列7横列8的格子，表示用1,5,7这几个数字能凑出值为8的和，这个答案是显然的，用1和7即可凑出来。

这里的横纵坐标上的0非常重要，表示不使用任何数字和凑出数字0的情况，显然这一行全是1，但是我们不着急先全都填上，先从左上角第一个格子开始。

1. 第一行不使用任何数字，要凑出0的话，是可行的，先标记1，但是想凑出其他任何数字的话都是不可行的，都标记0，图中我们把标记0的格子全都省略不做标记了。
2. 第二行，我们有了一个数字1，显然要凑出0的话，我们在上一行已经知道了，不使用任何数字就可以凑出0，直接把[0,0]里的值复制到[1,0]过来，而要凑齐1的话可以在之前0个数字凑齐0的基础上用上当前的数字1来凑到1，所以同样的我们把[0,0]的值复制到[1,1中来]
3. 到了第三行，在原来拥有的数字集合0,1的基础上，我们又多出了数字5，那么同样的想要凑出数字0或者1的话，可以继续沿用原来的方案，那么就直接把之前的[1,0]和[1,1]的值复制到对应的[2,0]和[2,1]。而在原来的这两个凑数字的方案的基础上，额外加上现在多得到的5话，可以得到和位5或者6，那么同样对应的我们把[1,0]和[1,1]的值复制到[2,0+5]和[2,1+5]即[2,5]和[2,6]上。
4. 此时是不是应该已经发现规律了。那么我们再看下第四行。在原有的数字0,1,5的基础上我们又多了个数字7，照样的，把原来第三行表示能凑出和的值复制下来，同时，对应往后移动7位的也设置成可以凑出来。即[3,0],[3,1],[3,5],[3,6],[3,7],[3,8]都设置为1表示可以凑出来。
5. 后面的就不用多讲了，在这个过程中只要判断下看最终需要求的那个数字能否被凑出来，就可以立刻中断并返回结果了

除了上面主要的逻辑之外，如果一个数组的总和是一个奇数的话，那么必然是不能符合题意的，以及如果最大数字如果大于总和的一半的话也必然不能凑出来。

代码如下

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = num > maxNum? num : maxNum;
        }
        if (sum % 2 == 1){
            //总和为奇数，必然不能等分
            return false;
        }
        if (maxNum > sum/2){
            //最大的数值已经大于了总和的一半，也必然不能等分
            return false;
        }
        int target = sum/2;

        int[][] dp = new int[nums.length+1][target+1];
        dp[0][0] = 1;
        //下面部分dp的逻辑见图
        for (int row = 1; row < nums.length; row++) {
            for (int col = 0; col < (target + 1); col++) {
                if (dp[row-1][col] == 1){
                    dp[row][col] = 1;
                    if ((col+nums[row])<=target){
                        dp[row][col+nums[row]] = 1;
                    }
                }
                if (dp[row][target] == 1){
                    return true;
                }
            }
        }
        return false;

    }
}

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

经典动态规划问题

这样一个思路，分别假设text1和text2长度从0开始生长到最长长度的时候的情况。

如图中举例，text1 = "qcssopd"，text2 = "abcsdku"，

1. 当text1或者text2长度都为0的时候最长公共子序列的长度显然为0，此时可以把左边一竖排和最顶上一横排的值都填上0
2. 当text1为“q”，text2从“a”依次增加到全长度的时候可以非常简单的判断得到最长公共子序列长度都为0
3. 当text1为“qc”的时候，text2从“a”依次增加到全长度，可以明显的知道，直接拿字符串“c”和text2上的每一位字符对比，如果相等肯定表示有了一个最长公共子序列“c”
4. 这一步是重点，text1变换为“qcs”，text2从“a”依次增加到全长度，当text2的值为“abcs”的时候，我们可以知道末尾字符串字符相同，所以可以把这个问题转变为“qc”和“abc”的最长公共子序列的长度加1，而“qc”和“abc”的最长公共子序列长度我们在之前上一步3中已经得到了为1，所以此时的最长公共子序列长度为2。后面同理
5. 如果末尾字符串不相等的情况，举例text1=“qcs”，text2=“abc”，这个情况可以转换为“qc”与“abc”的最长公共子序列或者“qcs”与“ab”的公共子序列中较大的一个。
6. 后面依次循环执行4、5部分的逻辑

所以我们得到了状态转移方程

//当前字符相同的情况
dp[i][j] = dp[i-1][j-1]+1;
//当前字符不相同的情况
dp[i][j] = max( dp[i][j-1], dp[i-1][j]);

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for (int row = 1; row <= text1.length(); row++) {
            for (int col = 1; col <= text2.length(); col++) {
                if (text1.charAt(row-1) == text2.charAt(col-1)){
                    dp[row][col] = dp[row-1][col-1]+1;
                }else{
                    dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

而，如果再扩展一下，想要知道最长公共子序列是啥的话，只需要在长度发生变化的时候把新增进来的字符记录下来即可。

该字符串最长公共子序列的查找的算法，我们比较直观的能想到的用法在两段文本内容相似度比较，或者文本变更内容查找之类的地方

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

提示：

• -1000 <= a, b <= 1000

/**
 * 与&：0&0=0 0&1=0 1&0=0 1&1=1
 * 异或^：0^0=0 0^1=1 1^0=1 1^1=0
 *
 * 异或计算，运行后能表示当前位置相加之后的值是0还是1
 * 01010  ^
 * 11011
 * 10001   结果1
 *
 * 与运算能表示，当前位运算之后是否需要进位
 * 01010  &
 * 11011
 * 01010   结果2
 * 所以需要把结果2再左移一位再次和结果1做异或运算，如此循环直到结果2为0
 * 10001
 * 10100
 * 00101    ^结果
 * 10000    &结果
 * 继续处理
 * 000101
 * 100000
 * 100101   ^结果
 * 000000   &结果
 * 结束
 */
class Solution {
    public int getSum(int a, int b) {
        int c = (a & b) << 1;
        a = a ^ b;
        int tmp = 0;
        while (c != 0){
            tmp = a;
            a = a ^ c;
            c = (tmp & c) << 1;
        }
        return a;
    }
}