leetcode刷题路线（Leetcode刷题第六周）

77   
    
    
、组合

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new LinkedList<>(); public List<List<Integer>> combine(int n, int k) { int index = 1; travesal(n,k,index); return result; } public void travesal(int n, int k, int index){ // 终止条件   
    
    
，得到k个数的组合 if(temp.size() == k){ result.add(new ArrayList<>(temp)); return; } for (int i = index; i <= n - (k - temp.size()) + 1; i++) { temp.add(i); travesal(n,k,i+1);//递归 temp.remove(temp.size() - 1);//回溯 } } }

216


     


     


   、组合总和 III

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new LinkedList<Integer>(); public List<List<Integer>> combinationSum3(int k, int n) { // 边界条件


     


     


   ，不存在有效的组合 int sum = 0; for(int i = 1; i <= k; i++){ sum += i; } if(sum > n){ return result; } int index = 1; combinationSumHelper(k,n,index); return result; } public void combinationSumHelper(int k, int n,int index){ if(temp.size() == k){ // 判断找出的组合是否满足相加之和为n的条件 int sum = 0; for(Integer i : temp){ sum += i; } if(sum == n){ result.add(new ArrayList<>(temp)); } return; } for(int i = index; i <= 9 - (k - temp.size()) + 1; i++){ temp.add(i); combinationSumHelper(k,n,i+1);//递归 temp.remove(temp.size() - 1);//回溯 } } }

17 




 




 

、电话号码的字母组合

class Solution { public List<String> result = new ArrayList<String>(); public StringBuffer str = new StringBuffer(); public List<String> letterCombinations(String digits) { // 边界条件 if(digits == null || digits.length() == 0){ return result; } char[] digitsArr = digits.toCharArray(); // 映射关系 String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; int index = 0; letterCombinationsHelper(digitsArr, find, index); return result; } public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){ if(index == digitsArr.length){ result.add(new String(str)); return; } // 第index个数字对应的字母 String strTemp = find[digitsArr[index] - 0]; for(int i = 0; i < strTemp.length(); i++){ str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个 letterCombinationsHelper(digitsArr,find,index+1); str.deleteCharAt(str.length() - 1); } } }

39   

   

   

、组合总和

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { int sum = 0; int index = 0; Arrays.sort(candidates); combinationSumHelper(candidates,index,sum,target); return result; } public void combinationSumHelper(int[] candidates, int index, int sum,int target){ if(sum >= target){ if(sum == target){ result.add(new ArrayList<Integer>(temp)); } return; } for(int i = index; i < candidates.length; i++){ sum += candidates[i]; temp.add(candidates[i]); combinationSumHelper(candidates,i,sum,target); temp.remove(temp.size() - 1); sum -= candidates[i]; } } }

40

     

     

  、 组合总和 II

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { int sum = 0; int index = 0; Arrays.sort(candidates); combinationSumHelper(candidates, target, index, sum); return result; } public void combinationSumHelper(int[] candidates, int target, int index, int sum){ if(sum >= target){ if(sum == target){ result.add(new ArrayList<>(temp)); } return; } // 每个数字在每个组合中只能使用一次 for(int i = index; i < candidates.length; i++){ // 去重逻辑 




 




 

，同层剪枝   

   

   

，同枝可取 if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){ continue; } temp.add(candidates[i]); sum += candidates[i]; combinationSumHelper(candidates, target, i + 1, sum); temp.remove(temp.size() - 1); sum -= candidates[i]; } } }

131
  




  




  
、分割回文串

class Solution { public List<List<String>> result = new ArrayList<List<String>>(); public List<String> temp = new ArrayList<String>(); public List<List<String>> partition(String s) { int index = 0; partitionHelper(s, index); return result; } public void partitionHelper(String s, int index){ if(index == s.length()){ result.add(new ArrayList<>(temp)); return; } for(int i = index; i < s.length(); i++){ String s1 = s.substring(index, i + 1); if(!check(s1,0,s1.length() - 1)){ continue;//字符子串不回文的话直接跳过该次分割方案 } temp.add(s1); partitionHelper(s,i+1); temp.remove(temp.size() - 1); } } // 判断是否回文 public boolean check(String s1, int left, int right){ while(left < right){ if(s1.charAt(left) == s1.charAt(right)){ left++; right--; }else{ return false; } } return true; } }

93  


  


  


、复原 IP 地址

class Solution { public List<String> result = new ArrayList<String>(); public StringBuilder stringBuilder = new StringBuilder(); public List<String> restoreIpAddresses(String s) { restoreIpAddressesHelper(s,0,0); return result; } public void restoreIpAddressesHelper(String s, int index,int count){ if (index == s.length() && count == 4) { result.add(stringBuilder.toString()); return; } if (index == s.length() || count == 4) { return; } for (int i = index; i < s.length() && i - index < 3 && Integer.parseInt(s.substring(index, i + 1)) >= 0 && Integer.parseInt(s.substring(index, i + 1)) <= 255; i++) { if (i + 1 - index > 1 && s.charAt(index) - 0 == 0) { continue; } stringBuilder.append(s.substring(index, i + 1)); if (count < 3) { stringBuilder.append("."); } count++; restoreIpAddressesHelper(s,i+1,count); count--; stringBuilder.delete(index + count, i + count + 2); } } }

78 
     
     
 、子集

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> subsets(int[] nums) { subsetsHandler(nums, 0); return result; } public void subsetsHandler(int[] nums, int index){ if(index == nums.length){ result.add(new ArrayList<>(temp)); return; } result.add(new ArrayList<>(temp)); for(int i = index; i < nums.length; i++){ temp.add(nums[i]); subsetsHandler(nums,i+1); temp.remove(temp.size() - 1); } } }

90

   




   




   、子集 II

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); subsetsWithDupHandler(nums, 0); return result; } public void subsetsWithDupHandler(int[] nums, int index){ if(index == nums.length){ result.add(new ArrayList<>(temp)); return; } result.add(new ArrayList<>(temp)); for(int i = index; i < nums.length; i++){ // 不能 包含重复的子集 if(i > 0 &&i > index && nums[i] == nums[i - 1]){ continue; } temp.add(nums[i]); subsetsWithDupHandler(nums, i + 1); temp.remove(temp.size() - 1); } } }

491 



 



 



、递增子序列

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> findSubsequences(int[] nums) { // 递增子序列中 至少有两个元素 findSubsequencesHandler(nums, 0); return result; } public void findSubsequencesHandler(int[] nums, int index){ if(temp.size() > 1){ result.add(new ArrayList<>(temp)); } int[] used = new int[201]; for(int i = index; i < nums.length; i++){ if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){ continue; } used[nums[i] + 100] = 1; temp.add(nums[i]); findSubsequencesHandler(nums, i + 1); temp.remove(temp.size() - 1); } } }

46            、全排列

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> permute(int[] nums) { // 有序 int[] used = new int[30]; permuteHandler(nums, used); return result; } public void permuteHandler(int[] nums, int[] used){ if(temp.size() == nums.length){ result.add(new ArrayList<>(temp)); return; } for(int i = 0; i < nums.length; i++){ if(used[nums[i]+10] == 1){ continue; } used[nums[i]+10] = 1; temp.add(nums[i]); permuteHandler(nums,used); used[temp.get(temp.size() - 1)+10] = 0; temp.remove(temp.size() - 1); } } }

47


    




    




    、全排列 II

class Solution { public List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<Integer> temp = new ArrayList<Integer>(); public List<List<Integer>> permuteUnique(int[] nums) { boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); Arrays.sort(nums); permuteHandler(nums, used); return result; } public void permuteHandler(int[] nums, boolean[] used){ if(temp.size() == nums.length){ result.add(new ArrayList<>(temp)); return; } for(int i = 0; i < nums.length; i++){ if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){ continue; } if(used[i] == false){ used[i] = true; temp.add(nums[i]); permuteHandler(nums,used); used[i] = false; temp.remove(temp.size() - 1); } } } }

332













、重新安排行程

//基本参考代码随想录 class Solution { public LinkedList<String> result; public LinkedList<String> path = new LinkedList<String>(); public List<String> findItinerary(List<List<String>> tickets) { Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1))); path.add("JFK"); int[] used = new int[tickets.size()]; findItineraryHanlder(tickets, used); return result; } public boolean findItineraryHanlder(List<List<String>> tickets, int[] used){ if(path.size() == tickets.size() + 1){ result = new LinkedList<String>(path); return true; } for(int i = 0; i < tickets.size(); i++){ if(used[i] != 1 && tickets.get(i).get(0).equals(path.getLast())){ path.add(tickets.get(i).get(1)); used[i] = 1; if(findItineraryHanlder(tickets,used)){ return true; } path.removeLast(); used[i] = 0; } } return false; } }

51             、N 皇后

class Solution { public List<List<String>> result = new ArrayList<>(); public List<String> temp = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { int[] arr = new int[n]; Arrays.fill(arr, -1); find(arr, 0, n); return result; } public void find(int[] arr, int index,int n){ if(index == n){ result.add(new ArrayList<>(temp)); return; } for(int i = 0; i < n; i++){ arr[index] = i; if(judge(arr,index)){ temp.add(setString(n,i)); find(arr, index+1,n); arr[index]=-1; temp.remove(temp.size() - 1); } } } public boolean judge(int[] arr, int index){ for(int i = 0; i < index; i++){ if(arr[i] == arr[index] || Math.abs(index - i)==Math.abs(arr[index]-arr[i])){ return false; } } return true; } public String setString(int n, int m){ StringBuffer str1 = new StringBuffer(); for(int i = 0; i < n; i++){ if(i == m){ str1.append("Q"); }else{ str1.append("."); } } return new String(str1); } }

37


     



     



    、解数独

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[i][j] != .){ continue; } for(char k = 1; k <= 9; k++){ if(judge(board,i,j,k)){ board[i][j] = k; if(solveSudokuHander(board)){ return true; } board[i][j] = .; } } return false; } } return true; } public boolean judge(char[][] board, int i, int j, char k){ for(int m = 0; m < 9; m++){ if(board[i][m]==k){ return false; } } for(int n = 0; n < 9; n++){ if(board[n][j]==k){ return false; } } int startRow = (i/3)*3; int startCol = (j/3)*3; for(int m = startRow; m < startRow+3; m++){ for(int n = startCol; n < startCol+3; n++){ if(board[m][n]==k){ return false; } } } return true; } }