1. 最小覆盖字串（76）
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
class Solution { public String minWindow(String s, String t) { int n = s.length(); int tot = 0; int [] c1= new int[60],c2=new int[60]; // c1 存储t中出现的字符及字数 for(char x:t.toCharArray()){ if (++c1[getId(x)]==1) //统计t中字母出现的次数，在对应字母索引位置 tot++; //tot记录出现的字符种类数 } String ans =""; //j 标识左边界，i标识右边界 for(int i =0,j=0;i<n;i++){ int idx1= getId(s.charAt(i)); //获取s的字符 if(++c2[idx1]==c1[idx1]) //如果已经达到了该字母出现的总字数了，就相当于该字符已经可以不用搜索了，可以少搜查一个种类，表明一个字符已经匹配完成 tot--; //总字符种类-1 //每当往右移一位，就要判断左边界是可以右移并保证c2>c1，使得当前tot不增加 while(j<i){ int idx2=getId(s.charAt(j)); if(c2[idx2]>c1[idx2]&&--c2[idx2]>=0) j++; else break; } if(tot==0 && (ans.length()==0||ans.length()>i-j+1)) //如果长度为0 或者找到更短的就更新 ans=s.substring(j,i+1); } return ans; } //返回字母所在的序号，比如A 就在0，小写也是一样 public int getId(char x){ return x>='A'&&x<='Z' ? x-'A' +26:x-'a'; } }
2.组合（77）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); if(k<=0||n<k){ return res; } Deque<Integer> path = new ArrayDeque<>(); dfsconbime(n,k,1,path,res); return res; } private void dfsconbime(int n, int k, int begin,Deque<Integer> path, List<List<Integer>> res) { if(path.size()==k){ res.add(new ArrayList<>(path)); return; } for (int i = begin; i <=n-(k-path.size())+1 ; i++){ path.addLast(i); dfsconbime(n,k,i+1,path,res); path.removeLast(); } } }
3. 子集（78）
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); bfssubsets(0,nums,ans,new ArrayList<Integer>()); return ans; } private void bfssubsets(int i, int[] nums, List<List<Integer>> ans, ArrayList<Integer> list) { ans.add(new ArrayList<>(list)); for (int j = i; j <nums.length ; j++) { list.add(nums[j]); bfssubsets(j+1,nums,ans,list); list.remove(list.size()-1); } } }
4. 单词搜索（79）
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
思想： 回溯
class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfsexist(board, words, i, j, 0)) return true; } } return false; } private boolean dfsexist(char[][] board,char[] words, int i, int j, int k) { if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=words[k]) return false; if(k==words.length-1) return true; board[i][j]='\0'; boolean res = dfsexist(board,words,i+1,j,k+1)||dfsexist(board,words,i,j+1,k+1) ||dfsexist(board,words,i-1,j,k+1)||dfsexist(board,words,i,j-1,k+1); board[i][j]=words[k]; return res; } }
5. 删除有序数组中的重复项（80）
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
思想： 快慢指针
class Solution { public int removeDuplicates(int[] nums) { int n = nums.length; if(n<=2) return n; int slow = 2,fast =2; while (fast<n){ if(nums[slow-2]!=nums[fast]){ nums[slow]=nums[fast]; slow++; } fast++; } return slow; } }