新乡网站建设求职简历,哪些网站用python做的,建设网站的意义 作用是什么,国外电商网站题意理解#xff1a; 给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 如#xff1a;n3,k2,则有#xff1a;12 13 23 一般#xff0c;我们使用回溯法来解决组合问题。 组合问题没有顺序要求#xff0c;所以 12 21 是同一个组合#xff08;如… 题意理解 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 如n3,k2,则有12 13 23 一般我们使用回溯法来解决组合问题。 组合问题没有顺序要求所以 12 21 是同一个组合如果是排列12 21 是两种排列 一般我们可以把回溯法要解决的问题抽象成树结构 集合大小树的宽度n 组合大小递归深度k 所以 我们可以将这个问题抽象为树问题在递归方法中使用回溯来暴力搜索。 由于回溯是暴力解锁的方式为了实现性能优化我们提前对于一些不可能搜到正确结果的树枝进行剪枝操作。 1.暴力解锁的回溯
注意 removeLast()是LinkedList的方法List listnew LinkedListM()是调用不到的。 添加结果是path的内容要复制给一个新的对象new LinkedList()否则对同一个path对象修改的话results记录的结果值也会发生改变最终的结果就是result里面重复加入相同的path对象。。
/*** 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合* param n* param k* return*/ListListInteger resultsnew ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {backtracking(n,k,1);return results;}public void backtracking(int n,int k,int startIndex){//结果收集,结束if(path.size()k){//重新new一个是因为如果对同一个path操作最终result是一堆相同的pathresults.add(new ArrayList(path));return;}//未收集结果遍历当前分支子孩子for(int istartIndex;in;i){path.add(i);backtracking(n,k,i1);path.removeLast();}}
2.采用剪枝的回溯
采用剪枝是为了在进行暴力的回溯搜索时及时剪除不可能搜到正确结果的树枝对整体搜索过程进行优化。 图摘自《代码随想录》
【剪枝优化】
从startIndex收集path
n-pathSize还需要收集的数据量
n-statIndex剩余的数据量
如果 k-pathSizen-startIndex1,则剩余的搜索现有数据不足以搜到大小为k的组合
所以我们要保证k-pathSizen-startIndex1变形得 startIndexn-(k-pathSize)1 /*** 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合* param n* param k* return*/ListListInteger resultsnew ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {backtracking(n,k,1);return results;}public void backtracking(int n,int k,int startIndex){//结果收集,结束if(path.size()k){//重新new一个是因为如果对同一个path操作最终result是一堆相同的pathresults.add(new ArrayList(path));return;}//未收集结果遍历当前分支子孩子//【剪枝优化】for(int istartIndex;in-(k-path.size())1;i){path.add(i);backtracking(n,k,i1);path.removeLast();}}
3.分析 时间复杂度 暴力回溯O(2^n) 剪枝回溯O() 空间复杂度 暴力回溯O(k) 简直回溯O(k)
