17. 电话号码的字母组合

image.png
自己的答案:
自己写的时候,多次用到了String的拼接,很耗时间,对StringBuffer不熟悉,并且对回溯也不太熟悉

  1. class Solution {
  2.     public List<String> letterCombinations(String digits) {
  3.         List<String> list = new ArrayList();
  4.         if(digits==null||digits.length()==0) {
  5.             return list;
  6.         }
  7.         Map<Integer,char[]>  map =new HashMap();
  8.         map.put(2,new char[]{'a','b','c'});
  9.         map.put(3,new char[]{'d','e','f'});
  10.         map.put(4,new char[]{'g','h','i'});
  11.         map.put(5,new char[]{'j','k','l'});
  12.         map.put(6,new char[]{'m','n','o'});
  13.         map.put(7,new char[]{'q','p','r','s'});
  14.         map.put(8,new char[]{'t','u','v'});
  15.         map.put(9,new char[]{'w','x','y','z'});
  16.         char[] ch = map.get(digits.charAt(0)-'0');
  17.         for(int i = 0; i < ch.length;i++) {
  18.             list.add(new String(ch[i]+""));
  19.         }
  20.         for(int i = 1 ; i < digits.length();i++) {
  21.             ch = map.get(digits.charAt(i)-'0');
  22.             List<String> listTemp = new ArrayList();
  23.             for(int j = 0; j < list.size();j++){
  24.                 String s = list.get(j);
  25.                 for(int k = 0; k < ch.length;k++) {
  26.                     listTemp.add(s+ch[k]);          
  27.                 }
  28.             }
  29.             list.clear();
  30.             list.addAll(listTemp);
  31.         }
  32.         // list.stream().forEach(System.out::println);
  33.         return list;
  34.     }
  35. }

人家的代码:
我做的时候没有弄清楚buffer里的东西使用完以后该怎么删除. 没有掌握回溯的精髓

  1. class Solution {
  2.     public List<String> letterCombinations(String digits) {
  3.         List<String> list = new ArrayList();
  4.         if(digits==null||digits.length()==0) {
  5.             return list;
  6.         }
  7.         Map<Integer,char[]>  map =new HashMap();
  8.         map.put(2,new char[]{'a','b','c'});
  9.         map.put(3,new char[]{'d','e','f'});
  10.         map.put(4,new char[]{'g','h','i'});
  11.         map.put(5,new char[]{'j','k','l'});
  12.         map.put(6,new char[]{'m','n','o'});
  13.         map.put(7,new char[]{'q','p','r','s'});
  14.         map.put(8,new char[]{'t','u','v'});
  15.         map.put(9,new char[]{'w','x','y','z'});
  17.         letter(list,digits,map,0,new StringBuffer());
  18.         return list;
  19.     }
  21.     public void letter(List<String> list,String digits,Map<Integer,char[]>  map ,
  22.                             int index,StringBuffer buffer) {
  23.         if(digits.length()==index) {
  24.             list.add(buffer.toString());
  25.             return;
  26.         }
  27.         char[] ch  = map.get(digits.charAt(index)-'0');
  28.         for(int i = 0 ; i < ch.length;i++) {
  29.             buffer.append(ch[i]);
  30.             letter(list,digits,map,index+1,buffer);  // 做的时候没有弄清楚buffer里的东西使用完以后该怎么删除. 没有掌握回溯的精髓
  31.             buffer.deleteCharAt(index);
  32.         }
  34.     }
  35. }

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
image.png
自己写的:
代码写的很啰嗦,而且会有重复的,用了一个hashmap来判断

  1. class Solution {
  3.     List<String>[] resList = new ArrayList[9];
  6.     public List<String> generateParenthesis(int n) {
  7.         if(resList[n]!=null)
  8.             return resList[n];
  9.         List<String> list = new ArrayList();
  10.         if(n==1){
  11.             list.add("()");
  12.             resList[1] =list;
  13.             return list;
  14.         }
  15.         Set<String> set = new HashSet<>();
  16.         List<String> L = generateParenthesis(n-1);
  17.         for(String s:L) {
  18.             String s1 = "("+s+")";
  19.             list.add(s1);
  20.             set.add(s1);
  21.         }
  22.         for(int i = 1 ; i < n;i++) {
  23.             List<String> L1 = generateParenthesis(i);
  24.             List<String> L2 = generateParenthesis(n-i);
  25.             for(String s1:L1) {
  26.                 for(String s2:L2){
  27.                     String s = s1+s2;
  28.                     if(set.add(s))
  29.                         list.add(s1+s2);
  30.                 }
  31.             }
  32.         }
  33.         resList[n] = list;
  34.         return list;
  35.     }
  36. }

回溯版本的答案

每次添加一个(或者一个)
(的数目>)的数目才添加)

  1. class Solution {
  2.     List<String>[] resList = new ArrayList[9];
  3.     public List<String> generateParenthesis(int n) {
  4.         List<String> list = new ArrayList();
  5.         generate(list,new StringBuffer(),0,0,0,n);
  6.         return list;
  7.     }
  9.     public void generate(List<String> list,StringBuffer buffer,
  10.                         int open,int close,int index,int max) {
  11.         if(index == max*2){
  12.             list.add(buffer.toString());
  13.             return;
  14.         }
  15.         if(open<max) {
  16.             buffer.append('(');
  17.             generate(list,buffer,open+1,close,index+1,max);
  18.             buffer.deleteCharAt(index);
  19.         }
  20.         if(close<open) {
  21.             buffer.append(')');
  22.             generate(list,buffer,open,close+1,index+1,max);
  23.             buffer.deleteCharAt(index);
  24.         }
  25.     }
  26. }

答案版本的自己写的

  1. class Solution {
  2.     ArrayList[] cache = new ArrayList[100];
  4.     public List<String> generate(int n) {
  5.         if (cache[n] != null) {
  6.             return cache[n];
  7.         }
  8.         ArrayList<String> ans = new ArrayList<String>();
  9.         if (n == 0) {
  10.             ans.add("");
  11.         } else {
  12.             for (int c = 0; c < n; ++c) {
  13.                 for (String left: generate(c)) {
  14.                     for (String right: generate(n - 1 - c)) {
  15.                         ans.add("(" + left + ")" + right);
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         cache[n] = ans;
  21.         return ans;
  22.     }
  24.     public List<String> generateParenthesis(int n) {
  25.         return generate(n);
  26.     }
  27. }
  29. 作者：LeetCode-Solution
  30. 链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
  31. 来源：力扣（LeetCode）
  32. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

47. 全排列 II

很好的题目！
image.png
对于[1,1,1,1,2,3,4,4,5]来说，要保证重复的数字的放置顺序是有序的。

  1. class Solution {
  2.     int n = 0;
  3.     List<List<Integer>> result = new ArrayList();
  4.     List<Integer> list = new ArrayList();
  5.     boolean[] flag = null;
  8.     public List<List<Integer>> permuteUnique(int[] nums) {
  9.         n = nums.length;
  10.         if(n==0){
  11.             return result;
  12.         }
  13.         flag = new boolean[n];
  14.         Arrays.sort(nums);
  15.         dfs(nums,0);
  17.         return result;
  19.     }
  21.     public void dfs(int[] nums,int idx) {
  22.         if(idx==n){
  23.             result.add(new ArrayList(list));
  24.             return;
  25.         }
  27.         for(int i = 0; i < n;i++) {
  28.             // 这个命令就是规定使重复的元素相对有序
  29.             if(flag[i] || i >= 1 && nums[i] == nums[i-1] && !flag[i-1])
  30.                 continue;
  32.             flag[i] = !flag[i];
  33.             list.add(nums[i]);
  34.             dfs(nums,idx+1);
  35.             list.remove(idx);
  36.             flag[i] = !flag[i];
  38.         }
  40.     }
  41. }

子集

78. 子集

image.png

  1. 回溯 ```java class Solution { int length = 0; List> result = new ArrayList(); boolean[] flag = null; List list = new ArrayList();

    public List> subsets(int[] nums) {

    1.  length = nums.length;
    2.  result.add(new ArrayList());
    3.  if(length==0)
    4.      return result;
    5.  for(int i = 1; i <= length;i++) {
    6.      dfs(nums,i,0,0);  // 每次选择i长度的元素
    7.  }
    8.  return result;

    }

    void dfs(int[] nums,int size,int numSize,int start) {

    1.  if(size==numSize) {
    2.      result.add(new ArrayList(list));
    3.      return;
    4.  }
    6.  for(int i = start ; i < length;i++) {
    7.      list.add(nums[i]);
    8.      dfs(nums,size,numSize+1,i+1);
    9.      list.remove(numSize);
    10.  }

    }

}

  2. 2. 位运算
  3. ```java
  4. class Solution {
  5.     public List<List<Integer>> subsets(int[] nums) {
  6.         int length = nums.length;
  7.         int num = (1<<length)-1;
  8.         List<List<Integer>> result = new ArrayList();
  9.         result.add(new ArrayList());
  10.         List<Integer> list = new ArrayList();
  11.         for(int i = 1; i <= num;i++) {
  12.             int j = i;
  13.             int len = 0;
  14.             while(len<length) {
  15.                 if((j&(1<<len))!=0) {
  16.                     list.add(nums[len]);
  17.                 }
  18.                 len++;
  19.             }
  20.             result.add(new ArrayList(list));
  21.             list.clear();
  22.         }
  23.         return result;
  24.     }
  25. }

90. 子集 II

image.png
对于1,2,2,3,4,4,4:
1:0个1,一个1两种情况
2:0个、1个、2个 三种情况
3：0、1 两种
4:0、1、2、3 四种
共有：232*4=48

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList();
  3.     List<Integer> list = new ArrayList();
  4.     int n =0;
  6.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  7.         n = nums.length;
  8.         Arrays.sort(nums);
  9.         dfs(nums,0);
  11.         return result;
  12.     }
  14.     void dfs(int[] nums,int idx) {
  15.         if(idx==n){
  16.             result.add(new ArrayList(list));
  17.             return;
  18.         }
  20.         int k =0;  //重复元素的个数
  21.         while(idx+k<n && nums[idx+k]==nums[idx]) k++;
  22.         for(int i = 0 ; i <= k;i++) { 
  23.             // ==k的目的是为了使当前元素的最后一个重复元素可以在最后一步加入res中
  24.             dfs(nums,idx+k);
  25.             list.add(nums[idx]);
  26.         }
  27.         for(int i = 0 ; i <= k;i++) {
  28.             list.remove(list.size()-1);
  29.         }
  31.     }
  32. }

473. 火柴拼正方形

剪枝的题目
https://www.acwing.com/solution/content/3785/
image.png
image.png

  1. class Solution {
  2.     int length;
  3.     int has = 0;
  4.     long size=0;
  5.     boolean[] flag;
  6.     List<Integer> nums;
  7.     public boolean makesquare(int[] s) {
  8.         length = s.length;
  9.         long all = 0;
  10.         for(int n:s) {
  11.             all+=n;
  12.         }
  13.         if(length==0||all%4!=0)
  14.             return false;
  16.         size = all/4;
  17.         flag = new boolean[length];
  18.         nums = Arrays.stream(s).boxed().collect(Collectors.toList());
  19.         Collections.sort(nums,Collections.reverseOrder());
  21.         return dfs(0,0);
  22.     }   
  24.     boolean dfs(int u,int cur) {
  25.         if(cur == size) {
  26.             u++;cur=0;
  27.         }
  28.         if(u==4) // u==4一定已经完成了，而且已经到达了最末尾，因为nums的总和=4*size
  29.             {return true;}
  31.         for(int i = 0 ;i < length;i++) {
  33.            if(!flag[i] && cur+nums.get(i)<=size) {
  34.                flag[i] = true;
  35.                if(dfs(u,cur+nums.get(i))) {
  36.                    return true;
  37.                }
  38.                flag[i] = false;
  39.                if(i==0) return false;
  40.                while(i+1<length && nums.get(i+1)==nums.get(i)) i++;
  41.             }
  42.         }
  44.         return false;
  45.     }
  46. }