ToB企服应用市场:ToB评测及商务社交产业平台

标题: Leetcode刷题第六周 [打印本页]
作者: 反转基因福娃    时间: 2022-12-15 15:32
标题: 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



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4