乐清 网站建设,南昌小程序开发哪家公司好,湖南省住房和城乡建设厅老网站,苏州seo关键词优化价格java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 递归实现 解题思路 这种题只能暴力求解#xff0c;枚举所有可…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 递归实现 解题思路 这种题只能暴力求解枚举所有可能得组合例如要找2个数的组合那么就两层for循环3个数的就3层for循环k层就k个for循环但是这样显然不现实所以我们可以使用回溯的思路利用递归只写一层for循环就可以实现普通方法下k层for循环的效果。当然效率是一样的。但是代码实现起来嵌套for循环可没法实现试想k 50就得写50层for循环。 我们要进行k个数的组合这些数字只能从1-n中去选。也就是从1-n中调出k个不同的数组合起来。第一个位置可以选择1-n从1开始每个数都需要作为第1个位置的数进行枚举既然是穷举如果第一个位置当前从3开始那么第二个位置就从4开始枚举因为前面的几个数组一定已经在前几次第一个位置为1,2的时候就组合过了所以每一个位置都要尝试可选的每一种可能。 枝剪操作 如果当前已经组合的数和剩下可以参与组合的数不够组合成一个长度为k的组合例如我们k 4目前组合出来的是[4,8],剩下可以组合就剩下一个9了最多组合成一个[4,8,9],根本不够4个数遇到这种情况就不需要继续枚举当前情况了。俗称枝剪操作。 1. 递归实现
代码基本上是官方增加大量测试用例后目前优化到的比较快的了。最前面4ms到9ms的是远古时期提交的人它们的代码放到现在只能跑到35ms超越25%的人 这个是比较难理解的版本没有使用经典的回溯模版递归套forfor套递归但是这个做法的速度更快 class Solution {ListListInteger result;//保存答案int k;//用几个数来组合int n;//可以参与组合的数是[1,n]public ListListInteger combine(int n, int k) {this.nn;this.kk;resultnew ArrayListListInteger();//初始化链表保存答案Integer[] records new Integer[k];//每个保存一种组合保存当前正在处理的组合traversal(0,1,records);//return result;}//row表示当前是第几个数参与组合最多k个简单来说就是records数组的下标//column表示[1,n]的下标也就是限定哪些数可以参与组合[column,n]简单来说是当前用哪个数字参与组合//records 保存当前组合出来的数public void traversal(int row,int column,Integer[] records){if (columnn){//如果没有数可以参与组合终止本次组合尝试return;}else if(records.length (n-column1)k) {//剪枝操作如果当前已经组合到的数加上剩下还能参与组合的数不够k个说明无论如何都无法完成k个数的组合了。return;}else {//如果没啥问题则当前数字column可以作为第row个数参与当前的组合records[row]column;//让column作为第row个数参与组合if (rowk-1){//如果当前组合完成后正好k个值说明得到一种满足条件的组合result.add(List.of(records));}else {//否则进行下一个数字的枚举组合traversal(row1,column1, records);}//不可以排除后面其它数字也可以作为第row个数字参与组合的情况。//也就是说上面处理了用当前column作为第row个数的方案//这里处理放弃column作为第row个数的方案而试图继续向后找数字来作为第row个traversal(row, column, records);}}
} 经典回溯模版 class Solution {public ListListInteger combine(int n, int k) {ListListInteger res new ArrayList();if (k 0 || n k) return res;//如果1-n根本不够k个就返回空[]ArrayListInteger path new ArrayList();//用于保存当前组合路径dfs(n, k, 1, path, res);//从1开始组合return res;}void dfs(int n, int k, int begin, ArrayListInteger path, ListListInteger res) {int size path.size();if (size k) {//如果当前path保存的正好是一个满足条件的组合res.add(new ArrayList(path));//将其放入结果中return;}//每一个位置都要将能尝试的都尝试一遍for (int i begin; i n - (k - size) 1; i) {path.add(i);//尝试当前位置放idfs(n, k, i 1, path, res);//下一个位置的数字选择必须从i1开始path.removeLast();//选择不尝试当前位置放iif(path.size()(n-begin) k) return;//剪枝操作如果剩下的可选数字不够组成k个就终止这次组合}}
}
