算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写题吧。
遇事不决，可问春风，春风不语，即是本心。
我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。
目录
1、最小覆盖子串
2、组合
3、子集
4、单词搜索
5、删除有序数组中的重复项II
1、最小覆盖子串
略
2、组合
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/combinations/description/
思路：递归+回溯，每次选择一个元素加入集合，当集合元素数目等于k时，将当前集合tmp加入最终的结果集合ans。
class Solution {
List<Integer> tmp = new ArrayList<>() ;
List<List<Integer>> ans = new ArrayList<>() ;
public List<List<Integer>> combine(int n, int k) {
dfs(n,k, 1) ;
return ans ;
}
public void dfs(int n, int k, int cnt){
if(tmp.size() == k){
ans.add(new ArrayList<>(tmp)) ;
}
for(int i=cnt; i<=n; i++){
tmp.add(i) ;
dfs(n, k, i+1) ;
tmp.remove(tmp.size()-1) ;
}
}
}3、子集
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/subsets/
思路：两层for循环，依次取出子集并存入结果集合即可。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>() ;
res.add(new ArrayList<>()) ;
for(int i=0; i<nums.length; i++){
int len = res.size() ;
for(int j=0; j<len; j++){
List<Integer> tmp = new ArrayList<>(res.get(j)) ;
tmp.add(nums[i]) ;
res.add(tmp) ;
}
}
return res ;
}
}4、单词搜索
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/word-search/description/
思路：递归+回溯+标记，注意找到递归出口。返回true与false的出口。
Java代码：
class Solution {
// dfs + 标记
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
boolean [][] vis ;
public boolean exist(char[][] board, String word) {
vis = new boolean[board.length][board[0].length] ;
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
boolean flag = dfs(i,j,board, word,0) ;
if(flag){
return true ;
}
}
}
return false ;
}
public boolean dfs(int row, int col, char [][] board, String word, int begin){
if(board[row][col] != word.charAt(begin)){
return false ;
}
if(begin == word.length()-1){
return true ;
}
vis[row][col] = true ;
for(int i=0; i<dx.length; i++){
int tx = row + dx[i];
int ty = col + dy[i] ;
if(tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length){
continue ;
}
if(!vis[tx][ty]){
boolean flag = dfs(tx, ty, board, word, begin + 1) ;
if(flag){
return flag ;
}
}
}
// 回溯
vis[row][col]= false ;
return false ;
}
}
5、删除有序数组中的重复项II
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/
思路：方法1：用额外的空间存储元素出现的次数，然后调整元素的值。
方法2:由于题目要求用O(1)的空间复杂度，所以需要采用方法2，原地改造有序数组，本质上就是让当前元素大于上上个元素即可，根据这个原则修改数组。
Java代码：
class Solution {
public int removeDuplicates(int[] nums) {
// O(n)空间复杂度
Map<Integer, Integer> map = new HashMap<>() ;
for(int i=0; i<nums.length; i++){
if(map.get(nums[i]) != null){
if(map.get(nums[i])== 1){
map.put(nums[i], map.get(nums[i]) + 1) ;
}
}else{
map.put(nums[i], 1) ;
}
}
int res = 0 ;
int j = 0 ;
List<Integer> list = new ArrayList<>(map.keySet()) ;
Collections.sort(list) ;
for(int key: list){
int value = map.get(key) ;
res += value;
for(int i=0; i<value; i++){
nums[j++] = key ;
}
}
return res ;
}
}
方法2:
class Solution {
public int removeDuplicates(int[] nums) {
// 不使用额外的空间
int i = 0 ;
for(int num : nums){
// 当前的元素要大于上上个元素，也就保证最多两个元素相同
if(i < 2 || num > nums[i-2]){
nums[i++] = num ;
}
}
return i ;
}
}
