清远做网站seo,小程序的定义,无锡画室网站建设,搭建一个app平台要多少钱今天是第21天刷leetcode#xff0c;立个flag#xff0c;打卡60天。
算法挑战链接
77. 组合https://leetcode.cn/problems/combinations/description/
第一想法
需要从N个数中选取K个数#xff0c;那么第一想法肯定是k个for循环#xff0c;每个for循环选取一个数#x…今天是第21天刷leetcode立个flag打卡60天。
算法挑战链接
77. 组合https://leetcode.cn/problems/combinations/description/
第一想法
需要从N个数中选取K个数那么第一想法肯定是k个for循环每个for循环选取一个数比如从4个数中选取两个数代码如下 for (int i 1; i 4; i) {for (int j i 1; j 4; j) {//i 和 j 就是想要得到的两个数}
}
但是现在的问题是K是不确定的也就是我需要在代码中写出K的for循环。
直接写感觉是写不出来的递归是一个好办法。
于是递归三要素就上阵了
返回值和参数 返回一个列表 参数: n, k, index, 列表结束递归的条件。 列表为null 或者 列表的size k本层要完成的事情。 for循环index之后的数并且添加到列表中进入下一个递归
代码写出来之后会有一个很严重的问题那就是列表会保留上一次结果添加的数。
看完代码随想录之后的想法
回溯也是递归的一种。但是回溯是比较特殊的一种关于回溯的介绍在这里回溯的介绍 学习完成回溯之后我们可以得出回溯的模版
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}于是我们按照模版来写出了下面的代码
class Solution {LinkedListInteger result new LinkedList();ListListInteger results new ArrayList();public ListListInteger combine(int n, int k) {backtracking(n, k, 1);return results;}void backtracking(int n, int k,int index){if (result.size() k) {results.add(new ArrayList(result));return;}for (int i index; i n; i){result.add(i);backtracking(n, k, i1);result.removeLast();}}
}
实现过程中遇到哪些困难
理解回溯是一件很困难的事情主要困难的点在于回溯的思想是将解题过程看成是一颗树穷举了所有的解体过程然后先横向遍历在纵向遍历获取到每一种解题的可能。
今日收获
理解了回溯算法并且拿到了回溯算法的模版
