每日刷题记录 (六)

转x33g5p2x  于2022-06-27 转载在 其他  
字(6.1k)|赞(0)|评价(0)|浏览(368)

第一题: 剑指 Offer II 079. 所有子集

LeetCode: 剑指 Offer II 079. 所有子集
描述:
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

解题思路:

经典回溯题;
注意这里的剪枝.

  • 剪枝1: 不能重复使用同一元素
  • 剪枝2: 不能包含重复的子集

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         dfs(nums,0);
  6.         return result;
  7.     }
  8.     public void dfs(int[] nums, int start) {
  9.         result.add(new ArrayList<>(ret));
  10.         // 剪枝1: i=start 就是确保了不包含重复子集
  11.         for(int i = start; i < nums.length; i++) {
  12.             ret.add(nums[i]);
  13.             // 剪枝2: 这里传 i+1 确保了不重复使用同一个元素
  14.             dfs(nums,i+1);
  15.             ret.remove(ret.size()-1);
  16.         }
  17.     }
  18. }

第二题: 剑指 Offer II 080. 含有 k 个元素的组合

LeetCode: 剑指 Offer II 080. 含有 k 个元素的组合
描述:
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

解题思路:

经典回溯
注意剪枝

  • 剪枝1: 不能使用重复元素
  • 剪枝2: 不能有重复的子集

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> combine(int n, int k) {
  5.         int[] arr = new int[n];
  6.         for(int i = 0; i < n; i++) {
  7.             arr[i] = i+1;
  8.         }
  9.         dfs(arr,0,k);
  10.         return result;
  11.     }
  12.     public void dfs(int[] arr,int start, int k) {
  13.         if(ret.size() == k) {
  14.             result.add(new ArrayList<>(ret));
  15.             return;
  16.         }
  17.         // 剪枝1: 让i=start 确保了没有重复的子集
  18.         for(int i = start; i < arr.length; i++) {
  19.             ret.add(arr[i]);
  20.             // 剪枝2: 传入 i+1 确保了不使用重复元素
  21.             dfs(arr,i+1,k);
  22.             ret.remove(ret.size() - 1);
  23.         }
  24.     }
  25. }

第三题: 剑指 Offer II 081. 允许重复选择元素的组合

LeetCode: 剑指 Offer II 081. 允许重复选择元素的组合
描述:
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

解题思路:

经典回溯
注意剪枝

  • 剪枝1: 不要出现重复的情况

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  5.         Arrays.sort(candidates);
  6.         dfs(candidates,0,target);
  7.         return result;
  8.     }
  9.     public void dfs(int[] candidates, int start, int target) {
  10.         if (target == 0) {
  11.             result.add(new ArrayList<>(ret));
  12.             return;
  13.         }
  14.         // 剪枝1: i = start 确保不会重复子集
  15.         for(int i = start; i < candidates.length; i++) {
  16.             if(candidates[i] <= target){
  17.                 ret.add(candidates[i]);
  18.                 // 传入i 就会重复使用当前元素
  19.                 dfs(candidates,i,target-candidates[i]);
  20.                 ret.remove(ret.size()-1);
  21.             }
  22.         }
  23.     }
  24. }

第四题: 剑指 Offer II 082. 含有重复元素集合的组合

LeetCode: 剑指 Offer II 082. 含有重复元素集合的组合
描述:
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

解题思路:

经典回溯:
这里注意剪枝:

  • 剪枝1: 不能出现重复组合
  • 剪枝2: 不能重复使用元素
  • 剪枝3: 数组含有重复元素

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  5.         Arrays.sort(candidates);
  6.         boolean[] tmp = new boolean[candidates.length];
  7.         dfs(candidates,0,target,tmp);
  8.         return result;
  9.     }
  10.     public void dfs(int[] candidates, int start, int target,boolean[] tmp) {
  11.         if(target == 0) {
  12.             result.add(new ArrayList<>(ret));
  13.             return;
  14.         }
  15.         // 剪枝1: i=start确保不会出现重复组合
  16.         for (int i = start; i < candidates.length; i++) {
  17.          	// 剪枝3: 使用boolean数组来标记,确保了出现重复元素的情况
  18.             if(i>0 && candidates[i] == candidates[i-1] && !tmp[i-1]){
  19.                 continue;
  20.             }
  21.             if(candidates[i] <= target) {
  22.                 ret.add(candidates[i]);
  23.                 tmp[i] = true;
  24.                 // 剪枝2: i+1就是为了确保不会出现使用自己, 但是可以使用别人
  25.                 dfs(candidates,i+1,target-candidates[i],tmp);
  26.                 tmp[i] = false;
  27.                 ret.remove(ret.size()-1);
  28.             }
  29.             
  30.         }
  31.     }
  32. }

第五题: 剑指 Offer II 083. 没有重复元素集合的全排列

LeetCode: 剑指 Offer II 083. 没有重复元素集合的全排列
描述:
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

解题思路:

经典回溯
注意剪枝

  • 剪枝1: 不能重复使用当前元素

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> permute(int[] nums) {
  5.         boolean[] tmp = new boolean[nums.length];
  6.         dfs(nums,tmp);
  7.         return result;
  8.     }
  9.     public void dfs(int[] nums, boolean[] tmp) {
  10.         if (ret.size() == nums.length) {
  11.             result.add(new ArrayList<>(ret));
  12.             return;
  13.         }
  14.         for (int i = 0; i < nums.length; i++) {
  15.             // 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
  16.             if (!tmp[i]) {
  17.                 tmp[i] = true;
  18.                 ret.add(nums[i]);
  19.                 dfs(nums,tmp);
  20.                 tmp[i] = false;
  21.                 ret.remove(ret.size()-1);
  22.             }
  23.         }
  24.     }
  25. }

第六题: 剑指 Offer II 084. 含有重复元素集合的全排列

LeetCode: 剑指 Offer II 084. 含有重复元素集合的全排列
描述:
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

解题思路:

经典回溯
注意剪枝

  • 剪枝1: 不能重复使用当前元素
  • 剪枝2: 注意数组中重复的元素

代码实现:

  1. class Solution {
  2.     List<List<Integer>> result = new ArrayList<>();
  3.     List<Integer> ret = new ArrayList<>();
  4.     public List<List<Integer>> permuteUnique(int[] nums) {
  5.         Arrays.sort(nums);
  6.         boolean[] tmp = new boolean[nums.length];
  7.         dfs(nums,tmp);
  8.         return result;
  9.     }
  10.     public void dfs(int[] nums, boolean[] tmp) {
  11.         if (ret.size() == nums.length) {
  12.             result.add(new ArrayList<>(ret));
  13.             return;
  14.         }
  15.         for (int i = 0; i < nums.length; i++) {
  16.        		// 剪枝2: 从第二个元素开始, 如果当前元素和前一个元素是一样的,且前一个元素没有使用, 直接跳过
  17.             if(i > 0 && nums[i] == nums[i-1] && !tmp[i-1]){
  18.                 continue;
  19.             }
  20.             // 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
  21.             if(!tmp[i]){
  22.                 tmp[i] = true;
  23.                 ret.add(nums[i]);
  24.                 dfs(nums,tmp);
  25.                 tmp[i] = false;
  26.                 ret.remove(ret.size()-1);
  27.             }
  28.         }
  29.     }
  30. }

第七题: 剑指 Offer II 085. 生成匹配的括号

LeetCode: 剑指 Offer II 085. 生成匹配的括号
描述:
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思路:

这里left表示左括号数, right表示右括号数
剪枝1: right或left<0
剪枝2: right<left (确保了先使用左括号,排除了不合法情况)

代码实现:

  1. class Solution {
  2.     public List<String> generateParenthesis(int n) {
  3.         List<String> result = new ArrayList<>();
  4.         backstrack(result,"",n,n);
  5.         return result;
  6.     }
  7.     public void backstrack(List<String> result,String str,int left, int right) {
  8.     	// 剪枝1
  9.         if(left < 0 || right <0) return;
  10.         // 剪枝2
  11.         if(left > right) return;
  12.         if(left == 0 && right == 0 ) {
  13.             result.add(str);
  14.             return;
  15.         }
  16.         backstrack(result,str+"(",left-1,right);
  17.         backstrack(result,str+")",left,right-1);
  18.     }
  19. }

第八题: 剑指 Offer II 086. 分割回文子字符串

LeetCode: 剑指 Offer II 086. 分割回文子字符串

描述:
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

解题思路

经典回溯
注意剪枝
剪枝1: 不能重复使用当前元素
剪枝2: 不能出现重复组合
剪枝3: 必须是回文

代码实现:

  1. class Solution {
  2.     List<List<String>> result = new ArrayList<>();
  3.     List<String> ret = new ArrayList<>();
  4.     public String[][] partition(String s) {
  5.         bfs(s,0);
  6.         String[][] str = new String[result.size()][];
  7.         int i = 0;
  8.         for(List<String> list : result){
  9.             str[i++] = list.toArray(new String[list.size()]);
  10.         }
  11.         return str;
  12.     }
  13.     public void dfs(String s,int start) {
  14.         if(s.length() == start) {
  15.             result.add(new ArrayList<>(ret));
  16.             return;
  17.         }
  18.         // 剪枝1: 不能出现重复组合
  19.         for(int i = start; i < s.length(); i++) {
  20.        		// 剪枝3: 必须是回文
  21.             if(isHui(s,start,i)) {
  22.             	// 剪枝2: 不能重复使用同一个元素
  23.                 ret.add(s.substring(start,i+1));
  24.                 bfs(s,i+1);
  25.                 ret.remove(ret.size()-1);
  26.             }
  27.         }
  28.     }
  29.     public boolean isHui(String s,int left, int right) {
  30.         while(left<right) {
  31.             if(s.charAt(left) == s.charAt(right)){
  32.                 left++;
  33.                 right--;
  34.             }else{
  35.                 return false;
  36.             }
  37.         }
  38.         return true;
  39.     }
  40. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125478218

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法深度优先宽度优先

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com