电话号码的字母组合
解法一
dfs
每次把当前数字的情况都列举出来
然后深搜
class Solution { public List<String> letterCombinations(String digits) { List<String> list = new ArrayList<>(); if(digits == null) return null; if("".equals(digits))return list; StringBuilder sb = new StringBuilder(); HashMap<Character,String> map = new HashMap<>(); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); dfs(digits,map,0,sb,list); return list; } public void dfs(String digits, HashMap<Character,String> map, int index, StringBuilder sb, List<String> list){ if(sb.length() == digits.length()){ list.add(sb.toString()); return; } String s = map.get(digits.charAt(index)); for(int i = 0;i < s.length();i++){ sb.append(s.charAt(i)); dfs(digits,map,index+1,sb,list); sb.deleteCharAt(index); } } }
解法二
队列
队列中保存当前已经匹配好的字符串
每次把队列中的字符串都与当前字符的多种情况做匹配然后新增入队列
class Solution { public List<String> letterCombinations(String digits) { List<String> list = new ArrayList<>(); int len = digits.length(); if(digits == null) return null; if(len == 0)return list; HashMap<Character,String> map = new HashMap<>(); LinkedList<String> queue = new LinkedList<>(); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); String s = map.get(digits.charAt(0)); for(int i = 0;i < s.length();i++){ queue.add(String.valueOf(s.charAt(i))); } for(int i = 1;i < digits.length();i++){ int size = queue.size(); s = map.get(digits.charAt(i)); for(int j = 0;j < size;j++){ String t = queue.pollLast(); for(int k = 0;k < s.length();k++){ queue.addFirst(t+s.charAt(k)); } } } while(!queue.isEmpty()){ list.add(queue.pop()); } return list; } }
字母异位词分组
解法一
使用HashMap，map中的value就为字母异位词的List，所以需要找到一个唯一的key来区分List
而字母异位词中的字母出现的次数是一致的所以使用字母出现次数作为key来区分
class Solution { public List<List<String>> groupAnagrams(String[] strs) { HashMap<String,List<String>> map = new HashMap<>(); List<List<String>> list = new ArrayList<>(); for(int i = 0;i < strs.length;i++){ int [] count = new int[26]; for(int j = 0;j < strs[i].length();j++){ count[strs[i].charAt(j)-'a']++; } StringBuilder sb = new StringBuilder(); for(int j = 0;j< 26;j++){ if(count[j] != 0){ sb.append((char)('a'+j)); sb.append(count[j]); } } List<String> l = map.get(sb.toString()); if(l == null){ List<String> t = new ArrayList<String>(); t.add(strs[i]); map.put(sb.toString(),t); }else{ l.add(strs[i]); } } if(!map.isEmpty()){ Set<String> set = map.keySet(); for(String t : set){ List<String> tlist = map.get(t); list.add(tlist); } } return list; } }
找到所有数组中消失的数字
解法一
暴力遍历
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; int[] res = new int[n+1]; for(int i = 0;i < n;i++){ res[nums[i]] = 1; } List<Integer> ans = new ArrayList<>(); for(int i = 1;i <= n;i++){ if(res[i] == 0){ ans.add(i); } } return ans; } }
解法二
使用原来的数组不新建数组
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; for(int i = 0;i < n;i++){ int index = (nums[i]-1)%n; nums[index] +=n; } List<Integer> ans = new ArrayList<>(); for(int i = 0;i < n;i++){ if(nums[i] <= n){ ans.add(i+1); } } return ans; } }
