LeetCode-hot100题解—Day7

原题链接：力扣热题-HOT100
我把刷题的顺序调整了一下，所以可以根据题号进行参考，题号和力扣上时对应的，那么接下来就开始刷题之旅吧~
1-8题见LeetCode-hot100题解—Day1
9-16题见LeetCode-hot100题解—Day2
17-24题见LeetCode-hot100题解—Day3
25-34题见LeetCode-hot100题解—Day4
39-56题见LeetCode-hot100题解—Day5
62-71题见LeetCode-hot100题解—Day6
注：需要补充的是，如果对于每题的思路不是很理解，可以点击链接查看视频讲解，是我在B站发现的一个宝藏UP主，视频讲解很清晰（UP主用的是C++），可以结合视频参考本文的java代码。

72.编辑距离

思路：
本题采用动态规划来解决，设f(i,j)为匹配word1中的前i个字符和word2中的前j个字符所需要的最少步数，f(i,j)的值可分为两种情况
（1）word1[i] == word2[j]：此时不需要进行任何操作即可匹配，f(i,j) = f(i-1,j-1)
（2）word1[i] != word2[j]：由于有三种操作可供选择，所以又分为三种情况，最后的结果需要在这三种情况中取最小值：

• 插入：在word1[i]的后面插入word2[j]，回到第一种情况，此时word1[i+1]
=word2[j]，所以f(i,j)=f(i,j-1)+1（这个+1是指插入操作）
• 删除：删除word1[i]，此时需要比较word1[i-1]和word2[j]，所以f(i,j)=f(i-1,j)+1（+1是指删除操作）
• 替换：替换word1[i]为word2[j]，此时与第一种情况完全相同，f(i,j)=f(i-1,j-1)+1（+1是指替换操作）

需要注意的是，我们需要对第一行和第一列特殊处理，在两个字符串前加上空格，在初始化第一列时，f[i][0]表示word1的前i个字符匹配word2[0]的最少步骤，也就是匹配空字符串的步数，因此替换word1前i个字符为空字符即可，所以步骤为i，初始化第一行同理，视频讲解点击视频讲解-编辑距离。
时间复杂度：
这段代码的时间复杂度为 O(n * m)，其中 n 是 word1 的长度，m 是 word2 的长度。
代码实现：

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        //给word1和word2前面添加空格，方便处理，所以在后面f数组时，长度要+1
        word1 = ' ' + word1;
        word2 = ' ' + word2;
        //创建二维数组并初始化
        int[][] f = new int[n + 1][m + 1];
        for(int[] item : f){
            Arrays.fill(item,Integer.MAX_VALUE);
        }

        //处理第一行和第一列
        for(int i = 0; i <= n;i++) f[i][0] = i;
        for(int j = 0; j <= m;j++) f[0][j] = j;

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

75.颜色分类

思路：
本题采用三指针解决，使用三个指针i、j、k来分别表示红色、白色、蓝色的分界位置，通过while循环遍历数组，当j指向的元素为0时，与i位置的元素进行交换，同时将i和j都向后移动一位。当j指向的元素为2时，与k位置的元素进行交换，同时将k向前移动一位。如果j指向的元素为1，则仅将j向后移动一位。这样遍历一次数组后，就可以将数组中的0全部移动到前面，将2全部移动到后面，1的位置则自然被安排在中间。
这里说明一下为什么j指向0时交换后需要后移而指向2时交换不用后移，原因在于i，j是同时从索引0处出发的，在j指向的值为2时，与k指向的值交换，此时k之前指向的值是多少我们是不知道的，可能交换后j指向的新值还需要进行交换，所以此时j指针是不用动的，k指针后移；i指针和j指针刚开始是同步的（指向0和2的时候i，j要么都移动，要么都不移动），只有在指向1的时候j指针后移，i指针不动，所以可以得出j指针和i指针要么同步，要么j指针会在i指针的后面，所以i指针不会指向2（除了索引0处的值是2的情况下），只会指向0和1，且i指针前面的数全部都是0，如果还是不太理解这一点，可以自己多模拟几个例子，视频讲解点击视频讲解-颜色分类。
时间复杂度：
时间复杂度为O(n)，其中n为数组nums的长度。
代码实现：

class Solution {
    public void sortColors(int[] nums) {
        int i = 0;
        int j = 0;
        int k =nums.length - 1;
        while(j <= k){
            if(nums[j] == 0){
                swapnum(nums,i,j);
                i++;
                j++;
            }
            else if(nums[j] == 2) {
                swapnum(nums,j,k);
                k--;
            }
            else j++;
        }
    }
    //注意：这里不能简单的交换两个数（即swap(int a,int b)），因为交换的只是形参的值，并不会影响到原始数组nums中的值
    //所以应该修改为交换数组中指定位置的值，而不是交换形参的值
    private void swapnum(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

78.子集

思路一：深度优先搜索
本题正常解法是采用深度优先遍历来解决，枚举的方法是看每个位置的元素是否选择，当枚举到最后一个元素后，将结果添加到结果集中，注意回溯之后也要进行深度优先搜索，这样才能返回子集的全集。
时间复杂度：
这个算法的时间复杂度是O(2^N)，其中N是nums数组的长度。在每一层递归中，我们有两种选择：选择当前元素和不选择当前元素。因此，递归树的高度是N，每个节点有两个分支。总共有2^N个节点。所以时间复杂度是O(2^N)。
代码实现：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> subset = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
      dfs(nums,0);
      return ans;  
    }

    private void dfs(int[] nums,int idx){
        if(idx == nums.length){
            ans.add(new ArrayList<>(subset));
            return;
        }
        //添加当前元素并深度优先搜索
        subset.add(nums[idx]);
        dfs(nums,idx + 1);
        //丢弃当前元素并深度优先搜索，回溯
        subset.remove(subset.size() - 1);
        dfs(nums,idx + 1);
    }
}

思路2：二进制法
由于数组中无重复元素，那么我们可以用二进制的位数来表示数组中的元素（n个元素即二进制为2^n，它的子集有2^n个），我们知道二进制是0和1的组合，当某一位为1时说明该位置对应的元素被选择了，由于二进制包含所有的组合，所以将0-2^n中所有的二进制数按照上述规则对应成子集，每一个二进制数字对应一个子集（对应位置为0即不选择，对应位置为1即选择），则可以得到子集的全集，视频讲解点击视频讲解-子集，视频中有详细的模拟举例。
时间复杂度：
这段代码的时间复杂度为O(2^n * n)，其中n为数组nums的长度。这是因为对于nums数组的每个元素，都有可能在子集中存在或不存在，所以一共有2^n种可能的子集组合，并且在每一种可能中，需要花费O(n)的时间来生成子集。因此，整体的时间复杂度为O(2^n * n)。
代码实现：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for(int mask = 0;mask < (1 << n); mask++){
            List<Integer> subset = new ArrayList<>();
            for(int i = 0; i < n; i++){
                //(mask & (1 << i)) != 0表示索引为i的位置对应的mask二进制为1，所以将nums[i]加进subset
                if((mask & (1 << i)) != 0) subset.add(nums[i]);
            }
            ans.add(new ArrayList<>(subset));
        }
        return ans;
    }
}

综上，还是建议使用我们常用的dfs，简单并且耗时少。
由于力扣更新了，刷题顺序被打乱了，所以我准备调整一下刷题策略，按照知识点刷题，先讲解知识点，然后从hot100里找例题，这样更高效一点，在这里说明一下下~