Leetcode刷题第六周

77、组合

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new LinkedList<>();
4.     public List<List<Integer>> combine(int n, int k) {
5.         int index = 1;
6.         travesal(n,k,index);
7.         return result;
8.     }
9.     public void travesal(int n, int k, int index){
10.         // 终止条件，得到k个数的组合
11.         if(temp.size() == k){
12.             result.add(new ArrayList<>(temp));
13.             return;
14.         }
15.         for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
16.             temp.add(i);
17.             travesal(n,k,i+1);//递归
18.             temp.remove(temp.size() - 1);//回溯
19.         }
20.     }
21. }

复制代码

131、分割回文串

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new LinkedList<Integer>();
4.     public List<List<Integer>> combinationSum3(int k, int n) {
5.         // 边界条件，不存在有效的组合
6.         int sum = 0;
7.         for(int i = 1; i <= k; i++){
8.             sum += i;
9.         }
10.         if(sum > n){
11.             return result;
12.         }
13.         int index = 1;
14.         combinationSumHelper(k,n,index);
15.         return result;
16.     }
17.     public void combinationSumHelper(int k, int n,int index){
18.         if(temp.size() == k){
19.             // 判断找出的组合是否满足相加之和为n的条件
20.             int sum = 0;
21.             for(Integer i : temp){
22.                 sum += i;
23.             }
24.             if(sum == n){
25.                 result.add(new ArrayList<>(temp));
26.             }
27.             return;
28.         }
29.         for(int i = index; i <= 9 - (k - temp.size()) + 1; i++){
30.             temp.add(i);
31.             combinationSumHelper(k,n,i+1);//递归
32.             temp.remove(temp.size() - 1);//回溯
33.         }
34.     }
35. }

复制代码

93、复原 IP 地址

1. class Solution {
2.     public List<String> result = new ArrayList<String>();
3.     public StringBuffer str = new StringBuffer();
4.     public List<String> letterCombinations(String digits) {
5.         // 边界条件
6.         if(digits == null || digits.length() == 0){
7.             return result;
8.         }
9.         char[] digitsArr = digits.toCharArray();
10.         // 映射关系
11.         String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
12.         int index = 0;
13.         letterCombinationsHelper(digitsArr, find, index);
14.         return result;
15.     }
16.     public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
17.         if(index == digitsArr.length){
18.             result.add(new String(str));
19.             return;
20.         }
21.         // 第index个数字对应的字母
22.         String strTemp = find[digitsArr[index] - '0'];
23.         for(int i = 0; i < strTemp.length(); i++){
24.             str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个
25.             letterCombinationsHelper(digitsArr,find,index+1);
26.             str.deleteCharAt(str.length() - 1);
27.         }
28.     }
29. }

复制代码

78、子集

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new ArrayList<Integer>();
4.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
5.         int sum = 0;
6.         int index = 0;
7.         Arrays.sort(candidates);
8.         combinationSumHelper(candidates,index,sum,target);
9.         return result;
10.     }
11.     public void combinationSumHelper(int[] candidates, int index, int sum,int target){
12.         if(sum >= target){
13.             if(sum == target){
14.                 result.add(new ArrayList<Integer>(temp));
15.             }
16.             return;
17.         }
18.         for(int i = index; i < candidates.length; i++){
19.             sum += candidates[i];
20.             temp.add(candidates[i]);
21.             combinationSumHelper(candidates,i,sum,target);
22.             temp.remove(temp.size() - 1);
23.             sum -= candidates[i];
24.         }
25.     }
26. }

复制代码

90、子集 II

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new ArrayList<Integer>();
4.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
5.         int sum = 0;
6.         int index = 0;
7.         Arrays.sort(candidates);
8.         combinationSumHelper(candidates, target, index, sum);
9.         return result;
10.     }
11.     public void combinationSumHelper(int[] candidates, int target, int index, int sum){
12.         if(sum >= target){
13.             if(sum == target){
14.                 result.add(new ArrayList<>(temp));
15.             }
16.             return;
17.         }
18.         // 每个数字在每个组合中只能使用一次
19.         for(int i = index; i < candidates.length; i++){
20.             // 去重逻辑，同层剪枝，同枝可取
21.             if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){
22.                 continue;
23.             }
24.             temp.add(candidates[i]);
25.             sum += candidates[i];
26.             combinationSumHelper(candidates, target, i + 1, sum);
27.             temp.remove(temp.size() - 1);
28.             sum -= candidates[i];
29.         }
30.     }
31. }

复制代码

491、递增子序列

1. class Solution {
2.     public List<List<String>> result = new ArrayList<List<String>>();
3.     public List<String> temp = new ArrayList<String>();
4.     public List<List<String>> partition(String s) {
5.         int index = 0;
6.         partitionHelper(s, index);
7.         return result;
8.     }
9.     public void partitionHelper(String s, int index){
10.         if(index == s.length()){
11.             result.add(new ArrayList<>(temp));
12.             return;
13.         }
14.         for(int i = index; i < s.length(); i++){
15.             String s1 = s.substring(index, i + 1);
16.             if(!check(s1,0,s1.length() - 1)){
17.                 continue;//字符子串不回文的话直接跳过该次分割方案
18.             }
19.             temp.add(s1);
20.             partitionHelper(s,i+1);
21.             temp.remove(temp.size() - 1);
23.         }
24.     }
25.     // 判断是否回文
26.     public boolean check(String s1, int left, int right){
27.         while(left < right){
28.             if(s1.charAt(left) == s1.charAt(right)){
29.                 left++;
30.                 right--;
31.             }else{
32.                 return false;
33.             }
34.         }
35.         return true;
36.     }
37. }

复制代码

46、全排列

1. class Solution {
2.     public List<String> result = new ArrayList<String>();
3.     public StringBuilder stringBuilder = new StringBuilder();
4.     public List<String> restoreIpAddresses(String s) {
5.         restoreIpAddressesHelper(s,0,0);
6.         return result;
7.     }
8.     public void restoreIpAddressesHelper(String s, int index,int count){
9.         if (index == s.length() && count == 4) {
10.                         result.add(stringBuilder.toString());
11.                         return;
12.                 }
13.                 if (index == s.length() || count == 4) {
14.                         return;
15.                 }
16.         for (int i = index; i < s.length() && i - index < 3 && Integer.parseInt(s.substring(index, i + 1)) >= 0
17.                                 && Integer.parseInt(s.substring(index, i + 1)) <= 255; i++) {
18.             if (i + 1 - index > 1 && s.charAt(index) - '0' == 0) {
19.                                 continue;
20.                         }
21.                         stringBuilder.append(s.substring(index, i + 1));
22.                         if (count < 3) {
23.                                 stringBuilder.append(".");
24.                         }
25.             count++;
26.             restoreIpAddressesHelper(s,i+1,count);
27.             count--;
28.             stringBuilder.delete(index + count, i + count + 2);
29.             
30.         }
31.     }
32. }

复制代码

47、全排列 II

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new ArrayList<Integer>();
4.     public List<List<Integer>> subsets(int[] nums) {
5.         subsetsHandler(nums, 0);
6.         return result;
7.     }
8.     public void subsetsHandler(int[] nums, int index){
9.         if(index == nums.length){
10.             result.add(new ArrayList<>(temp));
11.             return;
12.         }
13.         result.add(new ArrayList<>(temp));
14.         for(int i = index; i < nums.length; i++){
15.             temp.add(nums[i]);
16.             subsetsHandler(nums,i+1);
17.             temp.remove(temp.size() - 1);
18.         }
19.     }
20. }

复制代码

332、重新安排行程

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new ArrayList<Integer>();
4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
5.         Arrays.sort(nums);
6.         subsetsWithDupHandler(nums, 0);
7.         return result;
8.     }
9.     public void subsetsWithDupHandler(int[] nums, int index){
10.         if(index == nums.length){
11.             result.add(new ArrayList<>(temp));
12.             return;
13.         }
14.         result.add(new ArrayList<>(temp));
15.         for(int i = index; i < nums.length; i++){
16.             //  不能 包含重复的子集
17.             if(i > 0 &&i > index && nums[i] == nums[i - 1]){
18.                 continue;
19.             }
20.             temp.add(nums[i]);
21.             subsetsWithDupHandler(nums, i + 1);
22.             temp.remove(temp.size() - 1);
23.         }
24.     }
25. }

复制代码

51、N 皇后

1. class Solution {
2.     public List<List<Integer>> result = new ArrayList<List<Integer>>();
3.     public List<Integer> temp = new ArrayList<Integer>();
4.     public List<List<Integer>> findSubsequences(int[] nums) {
5.     // 递增子序列中 至少有两个元素
6.         findSubsequencesHandler(nums, 0);
7.         return result;
8.     }
9.    
10.     public void findSubsequencesHandler(int[] nums, int index){
11.         if(temp.size() > 1){
12.             result.add(new ArrayList<>(temp));
13.         }
14.         int[] used = new int[201];
15.         for(int i = index; i < nums.length; i++){
16.             if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
17.                 continue;
18.             }
19.             used[nums[i] + 100] = 1;
20.             temp.add(nums[i]);
21.             findSubsequencesHandler(nums, i + 1);
22.             temp.remove(temp.size() - 1);
23.         }
24.     }
25. }

复制代码

37、解数独

[code]class Solution {    public void solveSudoku(char[][] board) {        solveSudokuHander(board);    }    public boolean solveSudokuHander(char[][] board){        for(int i = 0; i < 9; i++){            for(int j = 0; j < 9; j++){                if(board[j] != '.'){                    continue;                }                for(char k = '1'; k