当前位置: 首页 > news >正文

代码随想录算法训练营第二十天

LeetCode题目:

  • 39. 组合总和
  • 40. 组合总和 II
  • 131. 分割回文串
  • 2176. 统计数组中相等且可以被整除的数对(每日一题)

其他:

今日总结
往期打卡


39. 组合总和

跳转: 39. 组合总和

学习: 代码随想录公开讲解

问题:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

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

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

思路:

回溯,可以当成组合问题一次一次的选,也可以每个元素多次的选(不过效率不高).

复杂度:

  • 时间复杂度: O ( 2 n ) O(2^n) O(2n)
  • 空间复杂度: O ( n 2 ) O(n^2) O(n2)

代码(一层选一个):

class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum,int index){if(sum>target) return;if(sum==target) ans.add(new ArrayList<>(path));for(int i=index;i<candidates.length;i++){path.add(candidates[i]);dfs(candidates,sum+candidates[i],i);path.remove(path.size()-1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;dfs(candidates,0,0);return ans;}
}

代码(每个选0-n次):

class Solution {List<List<Integer>> ans;int target;int[] candidates;private final List<Integer> path = new ArrayList<>();int n;void dfs(int index,int value){if(value>target) return;if(value == target){ans.add(new ArrayList<>(path));return;}if(index<0) return;int sum = 0;while(sum+value<=target){dfs(index-1,value+sum);path.add(candidates[index]);sum+=candidates[index];}int count = sum/candidates[index];path.removeAll(path.subList(path.size()-sum/candidates[index],path.size()));}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;this.candidates = candidates;n = candidates.length;dfs(n-1,0);return ans;}
}

40. 组合总和 II

跳转: 40. 组合总和 II

学习: 代码随想录公开讲解

问题:

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次

**注意:**解集不能包含重复的组合。

思路:

每层同种元素只能选一个,为了更好的分辨同种元素,可以先排序

复杂度:

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( n ) O(n) O(n)

代码(回溯):

class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum, int index) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = index; i < candidates.length; i++) {if (sum + candidates[i] > target) {break;}if (i > index && candidates[i] == candidates[i - 1]) {continue;}path.add(candidates[i]);dfs(candidates, sum + candidates[i], i + 1);path.remove(path.size() - 1);}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {ans = new ArrayList<>();Arrays.sort(candidates);// System.out.println(Arrays.toString(candidates));this.target = target;dfs(candidates, 0, 0);return ans;}
}

131. 分割回文串

跳转: 131. 分割回文串

学习: 代码随想录公开讲解

问题:

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

思路:

在回文串位置切割,切割到最后一个位置时返回

复杂度:

  • 时间复杂度: O ( n 3 ) O(n^3) O(n3)
  • 空间复杂度: O ( n 2 ) O(n^2) O(n2)

代码:

class Solution {List<List<String>> ans;List<String> path = new ArrayList<>();void dfs(String s,int startIndex){if(startIndex==s.length()){ans.add(new ArrayList<>(path));}for(int i=startIndex+1;i<=s.length();i++){if(isPalindrome(s,startIndex,i-1)){path.add(s.substring(startIndex,i));}else continue;dfs(s,i);path.remove(path.size()-1);}}boolean isPalindrome(String s,int startIndex,int endIndex){while(startIndex<endIndex){if(s.charAt(startIndex++)!=s.charAt(endIndex--)) return false;}return true;}public List<List<String>> partition(String s) {ans = new ArrayList<>();dfs(s,0);return ans;}
}

2176. 统计数组中相等且可以被整除的数对(每日一题)

跳转: 2176. 统计数组中相等且可以被整除的数对

问题:

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ,请你返回满足 0 <= i < j < nnums[i] == nums[j](i * j) 能被 k 整除的数对 (i, j)数目

思路:

直接两层for循环遍历,遇到满足条件的位置+1

复杂度:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

代码:

class Solution {public int countPairs(int[] nums, int k) {int n = nums.length;int ans = 0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(nums[i]==nums[j]&&i*j%k==0) ans++;}}return ans;}
}

总结

练习了带条件的组合回溯

往期打卡

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天

http://www.xdnf.cn/news/1315.html

相关文章:

  • 关于C语言的模拟物理模型
  • vue3 el-dialog新增弹窗,不希望一进去就校验名称没有填写
  • SQL刷题记录贴
  • Oracle测试题目及笔记(单选)
  • 赛灵思 XCVU3P‑2FFVC1517I XilinxFPGA Virtex UltraScale+
  • AI在市场营销分析中的核心应用及价值,分场景详细说明
  • 【创新实训个人博客】前端实现
  • 【运维学习】lvs + keepalived + 主从dns 项目搭建
  • Valgrind的使用复习
  • 更换 CentOS 7.9 的系统源
  • 【软考-系统架构设计师】ATAM方法及效用树
  • 【python】pyCharm常用快捷键使用-(2)
  • C++入门基础:命名空间,缺省参数,函数重载,输入输出
  • blender 录课键位显示插件(图文傻瓜式安装)
  • .net core 项目快速接入Coze智能体-开箱即用-全局说明
  • 数据结构之BFS广度优先算法(腐烂的苹果)
  • ARINC818-1协议
  • visual Studio+Qt插件检查内存泄漏
  • Azure 私有端点和存储帐户用例
  • 基于springboot医药连锁店管理系统(源码+lw+部署文档+讲解),源码可白嫖!
  • 【论文精读】COLMAP-Free 3D Gaussian Splatting
  • vue入门:路由 router
  • [GESP202409 二级] 小杨的 N 字矩阵 题解
  • 《如何用 Function 实现动态配置驱动的处理器注册机制?》
  • Ubuntu多用户VNC远程桌面环境搭建:从零开始的完整指南
  • 多路由器通过三层交换机互相通讯(单臂路由+静态路由+默认路由版),通过三层交换机让pc端相互通讯
  • C++之类模板
  • 定制化突围:遨游防爆手机的差异化竞争策略
  • 实战|使用环信Flutter SDK构建鸿蒙HarmonyOS应用及推送配置
  • vue MarkdownIt标签多出了<p>标签导致高度变丑