leetcode hot100（3）

21.139.单词拆分

字符串动态规划

本题中为了方便，dp数组不使用0下标，从1开始

（1）确定dp数组及下标含义

dp[i]：给定字符串的前i个字符组成的字符串 能否切割成wordDict中的字符串

（2）递推方程

递推顺序是从前往后的，因此计算dp[i]需要考虑前面的dp数组，对于dp[i]，新增加了s的第i个字符，我们需要枚举这之前的所有切割点j，并结合对应的dp[j]进行考虑

for(int j = 0 ; j < i ; j++){
    dp[i] = dp[j] && set.contains(s.substring(j,i));
}

（3）遍历顺序

从前往后

（4）初始化

枚举一个例子，可以发现需要dp[0] = true；

同时dp[0] 的含义为：空字符串是否能由wordDict表示出来，从含义上来说wordDict不选择任何字符串，可以表示出空字符串，即dp[0] = true;

（5）dp模拟

public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1 ; i <= s.length() ; i++){
            for(int j = 0 ; j < i ; j++){
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];

    }

时间复杂度：需要遍历字符串的每一个位置，对于每一个位置还要遍历之前的分割点，复杂度为O(n^2)

空间复杂度：O(n)

本题属于字符串动态规划问题。在字符串动态规划问题中，为了和字符串下标的统一表示，dp数组一般从下标1开始使用。

22.136.只出现一次的数字

public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

23.647.回文子串

本题属于字符串动态规划问题，其中dp数组的设计，适合设计成独立的含义，最后使用累加。

这种设计是从回文子串能够表示出的递推关系得来的，更详细的在代码随想录动态规划52回文子串中有介绍。

1、暴力解法

时间复杂度O(n^3)

public static int countSubstrings(String s) {
        int res = 0;
        for(int i = 0 ; i < s.length() ; i++){
            for(int j = i+1 ; j < s.length() + 1; j++){
                if(checkIfPalin(s.substring(i,j))){
                    res++;
                }
            }
        }
        return res;
    }

    public static boolean checkIfPalin(String s){
        int head = 0;
        int tail = s.length()-1;
        while(head < tail){
            if(s.charAt(head) != s.charAt(tail)){
                return false;
            }
            head++;
            tail--;
        }
        return true;
    }

2、动态规划

从记忆化的角度来考虑回文子串的判断，判断s.substring(i,j+1)是否是回文串，只需要判断其边缘和内部（已经判断过的）是否满足回文要求，即dp[i+1][j-1] && s.charAt(i) == s.charAt(j)

（1）确定dp数组及下标含义

dp[i][j] : s.substring(i,j+1)是否是回文串，即s的从第i个字符开始，到第j个字符结束组成的子串是否是回文串。

（2）递推方程

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

以上三种情况分析完了，那么递归公式如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

（3）初始化

dp[i][j]初始化为false，对于单个字符的边界情况在递推公式中都有考虑，不会对起步造成影响。

（4）遍历顺序

画出递推公式需要的递推关系的位置图：

我们需要从左下角得到右上角，所以遍历顺序为i从后往前，j从前往后。

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。

（5）dp模拟

代码：

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        boolean dp[][] = new boolean[s.length()][s.length()];
        for(int i = s.length() - 1 ; i >= 0 ; i--){
            for(int j = i; j < s.length() ; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i <= 1){
                        dp[i][j] = true;
                        res++;
                    }else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;
    }
}

24.128.最长连续序列

本题介绍如何从暴力，到查找到可以记忆优化的点，进而实现动态规划思想。

根据题目的要求，我们会首先想到先将nums存到set里，然后对set进行遍历：

对于每一个num，都要遍历查询其可能的序列，直到中断，这样最坏情况下的时间复杂度是O(n^2)。

但实际上，对于一个num，如果它是另一个更长序列的中间元素，它就已经被遍历过了，我们没有必要再遍历一遍；并且，它作为中间元素，也没有可能是我们要找的序列的开头，没有必要遍历。

要实现这一点的关键在于查询num的值的前一个值是否在set里。

即：

 按照上面的方式进行遍历，

层循环需要 O(n) 的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)，符合题目要求。

public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int longestLength = 0;
        for (Integer i : set) {
            if(set.contains(i-1)){
                continue;
            }else{
                int currentLength = 1;
                while(set.contains(++i)){
                    currentLength++;
                }
                longestLength = Math.max(longestLength,currentLength);
            }

        }
        return longestLength;
    }

25.124.二叉树中的最大路径和

结合树本身的特点，容易考虑使用递归解决。可以用递归实现自底向上的后序遍历。

递归函数要做的事（本层逻辑），就是找到以当前节点为根节点的子树，能够达到的最大路径和；并向上层的递归调用返回最大的贡献值。

递归三部曲：

（1）递归函数参数和返回值

参数：当前的根节点

返回值：以当前节点为根节点的子树，能够达到的最大路径和

对于从当前节点左右子树递归返回来的值，可以舍弃，取Math.max(0,value)，但根节点的值不能舍弃。

（2）返回条件

空节点，根据返回值的含义，空节点的最大贡献值等于 0。

（3）单层逻辑

考虑路径有哪些情况：

a.最大路径不由以当前节点为根的子树决定，由其祖先节点决定，那么根应当返回最大贡献值。最大贡献值为考虑左右子树返回的贡献值，选择最大的一个和本节点的值加和 返回。如果左右子树返回的值都是负数，那么应当舍弃。

b.最大路径就是本层节点分别连接左右子树的路径。那么最大路径长度currentPath = left + right + node.val;

   在每一次递归时都令 maxPath = Math.max(maxPath,currentPath)，最后得到最大路径长度

在递归的过程中，实际考虑到了所有子树的情况，也就考虑到了所有路径的情况。

时间复杂度:O(N)，实际上是后序遍历

空间复杂度:O(N)，由递归调用得来

private int maxPath = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxPath;
    }

    public int maxGain(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftMax = Math.max(maxGain(root.left),0);
        int rightMax = Math.max(maxGain(root.right),0);
        int currentMax = leftMax + rightMax + root.val;
        maxPath = Math.max(maxPath,currentMax);
        return root.val + Math.max(leftMax,rightMax);

    }

26.322.零钱兑换

先来回顾一系列背包问题

（一）0-1背包问题

1.暴力解法：枚举每一种物品放或不放的情况，时间复杂度O(n^2)

2.动态规划

（1）确定dp数组及下标含义

dp[i][j] : 考虑前i种物品在背包容量为j的情况下，能够达到的最大价值为dp[i][j]

（2）递推公式

对于当前所处的情况，对于当前要抉择的第i种物品，有拿或不拿两种情况

- 拿 dp[i][j] = dp[i-1][j]

-不拿 dp[i][j] = dp[i-1][j - weight[i]] + values[i]

即 dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j - weight[i]] + values[i])

（3）遍历顺序

先遍历物品，再遍历背包

或者先遍历背包，再遍历物品

都可以

（均为从上到下，从左到右）

根据递推公式，可以看到当前值由上面的值和左上的值推导而来，先遍历物品再遍历背包，和先遍历背包再遍历物品都是符合递推顺序的。

（4）初始化

根据递推公式，i = 0 和 j = 0 的部分都需要初始化

根据dp数组的含义，j = 0 时 dp[i][0] = 0;

当 j < weight[0] 时， dp[0][j] = 0 ; 当 j >= weight[0] 时，dp[0][j] = weight[0]

（5）dp模拟

对0-1背包问题动态规划的空间复杂度进行优化：

在先遍历物品，再遍历背包的情况下，求得当前的值，即遍历过程中，我们需要的只有上一行的值，并且只需要上一行对应当前位置及其左半部分。即如果使用滚动数组覆盖的话，只需要将j倒序遍历，不会覆盖到有效数据，覆盖到的数据都是未来用不到的。可以用滚动数组将空间复杂度优化到O(n)

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

同时，在完全背包的背景下，也可以利用覆盖这一点，如果是正序遍历的话，就可以实现完全背包背景下的问题，即倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了，那么物品就会被重复加入多次。

关于使用滚动数组的情况下，0-1背包问题的遍历顺序能否颠倒？

不能，这样实际上会变成每轮遍历只使用一种物品，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

（二）完全背包问题

与0-1背包不同的是，完全背包的每个物品数量无限。

那么在0-1背包的背景下，允许重叠即可：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的，可以交换顺序。

本题中属于完全背包问题背景下的问题，要求恰好装满，各种硬币数量为无限个。

（1）确定dp数组及下标含义

dp[j] ：凑够金额j所需要的最少硬币个数为 dp[j]个

（2）递推公式

dp[j] = Math.min(dp[j] , dp[j - coins[i] ] + 1 )

（3）遍历顺序

从前往后

（4）初始化 dp[j] = Integer.MAX_VALUE

（5）dp模拟

27.目标和

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，用nums装满容量为x的背包，有几种方法。

(target + sum)%2 == 1 和 Math.abs(target) > sum的情况下都是无解的。

（x = (target + sum) / 2转换一下就是 2*x = target+sum ，左边是偶数，右边是奇数的情况下是无解的）

28.461.汉明距离

本题考查异或的性质。

相同数字异或为0，不同数字异或为0。

把x与y异或，然后转换成二进制的形式，数1的个数就可以。

转换二进制的方法是除二取余，逆序排列。

class Solution {
    public int hammingDistance(int x, int y) {
        int t = x ^ y;
        int res = 0;
        while(t != 0){
            res += t%2;
            t/=2;
        }
        return res;
    }
}

Java也支持内置的位计数功能：

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

也可以使用移位计数：

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }
}

时间复杂度O(logn)

空间复杂度O(1)

使用Brian Kernighan 算法可以对移位计数进行优化，对于0的部分可以直接跳过：

class Solution {
    public int hammingDistance(int x, int y) {
        int t = x ^ y;
        int res = 0;
        while(t != 0){
            t &= (t-1);
            res++;
        }
        return res;
    }
}

29.找到所有数组中消失的数字

（一）遍历，哈希思想

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 1 ; i <= nums.length ; i++){
            set.add(i);
        }
        for (int num : nums) {
            set.remove(num);
        }
        List<Integer> list = new ArrayList<>(set);
        return list;

    }
}

时间复杂度O(n)，空间复杂度O(n)

这里其实没必要用set，可以用哈希思想的数组实现，本质是哈希思想，即记录出现过的数字。构建一个长度为n的int数组，遍历nums,标记出现的数字，最后统计数组那些数字没有出现过：

public List<Integer> findDisappearedNumbers(int[] nums) {
        int[] hashArray = new int[nums.length];
        Arrays.fill(hashArray,0);
        for (int num : nums) {
            hashArray[num-1] = 1;
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0 ; i < nums.length ; i++){
            if(hashArray[i] == 0){
                res.add(i+1);
            }
        }
        return res;

    }

可以在空间复杂度上进行优化，即可以使用题目给出的数组作为哈希数组，原地记录。

该思想来自leetcode官方题解，个人感觉是奇技淫巧。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int num : nums) {
            int x = (num - 1) % n;
            if( nums[x] + n > 0 ) nums[x] += n;
        }
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.add(i + 1);
            }
        }
        return ret;
    }
}

但感觉存在溢出的风险，nums[x] += n 如果一直执行存在溢出风险，增加了判断溢出的条件

30.438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

在s中构造一个滑动窗口，寻找p的异位词，判断条件：窗口中各个字母的数量与p中各个字母的数量相同。

使用数组记录各字母数量。

public List<Integer> findAnagrams(String s, String p) {

        if(s.length() < p.length()) return new ArrayList<Integer>();

        int[] sCount = new int[26];
        int[] pCount = new int[26];
        List<Integer> res = new ArrayList<>();

        for(int i = 0 ; i < p.length() ; i++){
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if(Arrays.equals(sCount,pCount)){
            res.add(0);
        }
        for(int i = 0 ; i < s.length() - p.length() ; i++){
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + p.length()) - 'a']++;
            if(Arrays.equals(sCount,pCount)){
                res.add(i+1);
            }
        }
        return res;


    }

对滑动窗口进行优化：

可以发现当统计出p的字符数量以后，pCount数组就不再改变了，而是作为与sCount（即滑动窗口的统计）比较的基准，那么可以在滑动窗口时，维护两个数组的差异而不是绝对大小。

选择一个维护的标准differ，定义differ： s中窗口内 与 p的差异的26个字母中的字母数（字母数而不是字母的具体数量，比如a和aa 有差异，是1 ； a和 b有差异 是 1； aaa 和 aaa 没有差异，是0）

这样比较两个数组的差异数量differ 使用常数级时间，比用Arrays.equals逐个比较两个数组元素使用O（数组大小）时间，降低了时间复杂度。

differ仅在s中窗口 与 p  26个字母对应的字母数量 由不同变为相同、由相同变为不同时有变化，那么维护的逻辑如下：

将窗口左侧边缘移出

        count[s.charAt(i) - 'a'] --;

判断窗口边缘移出的影响：如果count[s.charAt(i) - 'a'] 变为了 0 ，说明原来有差异数量的字母减去一个后没有差异了，differ--；如果count[s.charAt(i) - 'a'] 变为了-1，说明原来没有差异的字母数量因为减去了左边的字母，有差异了（左边的字母是需要的字母），differ++

将窗口右侧边缘移入

        count[s.charAt(i + s.length - p.length] ++;

判断窗口边缘移入的影响：如果count[s.charAt(i + s.length - p.length]变为了0，说明由于右侧字母的移入，差异减少了，differ--；如果count[s.charAt(i + s.length - p.length]变为了1，说明由于右侧字母的移入，本来没有差异的变成有差异的了，differ++

完整的代码逻辑如下：

public List<Integer> findAnagrams(String s, String p) {
        if(s.length() < p.length()) return new ArrayList<Integer>();
        int[] count = new int[26];
        List<Integer> res = new ArrayList<>();
        int differ = 0;
        for(int i = 0 ; i < p.length() ; i++){
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }
        for (int i : count) {
            if(i != 0){
                differ++;
            }
        }
        if(differ == 0){
            res.add(0);
        }
        for(int i = 0 ; i < s.length() - p.length() ; i++){
            //左侧移出
            count[s.charAt(i) - 'a']--;
            if(count[s.charAt(i) - 'a'] == 0){
                differ --;
            }else if(count[s.charAt(i) - 'a'] == -1){
                differ++;
            }
            //右侧移入
            count[s.charAt(i + p.length()) - 'a']++;
            if(count[s.charAt(i + p.length() )- 'a'] == 0){
                differ--;
            } else if (count[s.charAt(i + p.length()) - 'a'] == 1) {
                differ++;
            }
            if(differ == 0){
                res.add(i+1);
            }
        }
        return res;
    }