本文主要是介绍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代码。
力扣hot100题解 62-71
- 72.编辑距离
- 75.颜色分类
- 78.子集
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数组时,长度要+1word1 = ' ' + 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]加进subsetif((mask & (1 << i)) != 0) subset.add(nums[i]);}ans.add(new ArrayList<>(subset));}return ans;}
}
综上,还是建议使用我们常用的dfs
,简单并且耗时少。
由于力扣更新了,刷题顺序被打乱了,所以我准备调整一下刷题策略,按照知识点刷题,先讲解知识点,然后从hot100里找例题,这样更高效一点,在这里说明一下下~
这篇关于LeetCode-hot100题解—Day7的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!