.mom域名可以做网站吗,打开网站 磁盘空间不足,专业做网站哪里好,网站建设中html模板一、题目
给定两个整数n和k#xff0c;返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
示例 1#xff1a; 输入#xff1a;n 4, k 2 输出#xff1a; [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2#xff1a; 输入#xff1a;n 1…一、题目
给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
示例 1 输入n 4, k 2 输出 [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2 输入n 1, k 1 输出[[1]] 1 n 20 1 k n 二、代码
【1】递归实现组合型枚举 从n个当中选k个的所有方案对应的枚举是组合型枚举。在「方法一」中我们用递归来实现组合型枚举。首先我们先回忆一下如何用递归实现二进制枚举子集枚举假设我们需要找到一个长度为n的序列a的所有子序列代码框架是这样的
vectorint temp;
void dfs(int cur, int n) {if (cur n 1) {// 记录答案// ...return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur 1, n, k);
}上面的代码中dfs(cur,n)参数表示当前位置是cur原序列总长度为n。原序列的每个位置在答案序列种的状态有被选中和不被选中两种我们用temp数组存放已经被选出的数字。在进入dfs(cur,n)之前[1,cur−1]位置的状态是确定的而[cur,n]内位置的状态是不确定的dfs(cur,n)需要确定cur位置的状态然后求解子问题dfs(cur1,n)。对于cur位置我们需要考虑a[cur]取或者不取如果取我们需要把a[cur]放入一个临时的答案数组中即上面代码中的temp再执行dfs(cur1,n)执行结束后需要对temp进行回溯如果不取则直接执行dfs(cur1,n)。在整个递归调用的过程中cur是从小到大递增的当cur增加到n1的时候记录答案并终止递归。可以看出二进制枚举的时间复杂度是O(2^n)。
组合枚举的代码框架可以借鉴二进制枚举。例如我们需要在n个元素选k个在dfs的时候需要多传入一个参数k即dfs(cur,n,k)。在每次进入这个dfs函数时我们都去判断当前temp的长度是否为k如果为k就把temp加入答案并直接返回即
vectorint temp;
void dfs(int cur, int n) {// 记录合法的答案if (temp.size() k) {ans.push_back(temp);return;}// cur n 1 的时候结束递归if (cur n 1) {return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur 1, n, k);
}这个时候我们可以做一个剪枝如果当前temp的大小为s未确定状态的区间[cur,n]的长度为t如果stk那么即使t个都被选中也不可能构造出一个长度为k的序列故这种情况就没有必要继续向下递归即我们可以在每次递归开始的时候做一次这样的判断
if (temp.size() (n - cur 1) k) {return;
}代码就变成了这样
vectorint temp;
void dfs(int cur, int n) {// 剪枝temp 长度加上区间 [cur, n] 的长度小于 k不可能构造出长度为 k 的 tempif (temp.size() (n - cur 1) k) {return;}// 记录合法的答案if (temp.size() k) {ans.push_back(temp);return;}// cur n 1 的时候结束递归if (cur n 1) {return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur 1, n, k);
}至此其实我们已经得到了一个时间复杂度为O((nk))的组合枚举由于每次记录答案的复杂度为O(k)故这里的时间复杂度为O((nk)×k)但是我们还可以进一步优化代码。在上面这份代码中有三个if判断其实第三处的if是可以被删除的。因为 【1】首先curn1的时候一定不可能出现sks是前文中定义的temp的大小因为自始至终s绝不可能大于k它等于k的时候就会被第二处if记录答案并返回 【2】如果curn1的时候sk它也会被第二处 if\text{if}if 记录答案并返回 【3】如果curn1的时候sk一定会在curn1的某个位置的时候发现stk它也会被第一处if剪枝。
因此第三处if可以删除。最终我们得到了如下的代码。
class Solution {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();public ListListInteger combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int cur, int n, int k) {// 剪枝temp 长度加上区间 [cur, n] 的长度小于 k不可能构造出长度为 k 的 tempif (temp.size() (n - cur 1) k) {return;}// 记录合法的答案if (temp.size() k) {ans.add(new ArrayListInteger(temp));return;}// 考虑选择当前位置temp.add(cur);dfs(cur 1, n, k);temp.remove(temp.size() - 1);// 考虑不选择当前位置dfs(cur 1, n, k);}
}时间复杂度 O((k/n)×k)分析见「思路」部分。 空间复杂度 O(nk)O(n)即递归使用栈空间的空间代价和临时数组temp的空间代价。
【2】非递归字典序法实现组合型枚举 这个方法理解起来比「方法一」复杂建议读者遇到不理解的地方可以在草稿纸上举例模拟这个过程。这里的非递归版不是简单的用栈模拟递归转化为非递归我们希望通过合适的手段消除递归栈带来的额外空间代价。假设我们把原序列中被选中的位置记为1不被选中的位置记为0对于每个方案都可以构造出一个二进制数。我们让原序列从大到小排列即{n,n−1,⋯1,0}。我们先看一看n4k2的例子
原序列中被选中的数对应的二进制数方案43[2][1]00112,14[3]2[1]01013,14[3][2]101103,2[4]32[1]10014,1[4]3[2]110104,2[4][3]2111004,3我们可以看出「对应的二进制数」一列包含了由k个1和n−k个0组成的所有二进制数并且按照字典序排列。这给了我们一些启发我们可以通过某种方法枚举使得生成的序列是根据字典序递增的。我们可以考虑我们一个二进制数数字x它由k个1和n−k个0组成如何找到它的字典序中的下一个数字next(x)这里分两种情况规则一x的最低位为1这种情况下如果末尾由t个连续的1我们直接将倒数第t位的1和倒数第t1位的0替换就可以得到next(x)。如0011→01010101→01101001→10101001111→10101111。规则二x的最低位为0这种情况下末尾有t个连续的0而这t个连续的0之前有m个连续的1我们可以将倒数第tm位置的1和倒数第tm1位的0对换然后把倒数第t1位到倒数第tm−1位的1移动到最低位。如0110→10011010→11001011100→11000111。
至此我们可以写出一个朴素的程序用一个长度为n的0/1数组来表示选择方案对应的二进制数初始状态下最低的k位全部为1其余位置全部为0然后不断通过上述方案求next就可以构造出所有的方案。
我们可以进一步优化实现我们来看n5k3的例子根据上面的策略我们可以得到这张表
二进制数方案001113,2,1010114,2,1011014,3,1011104,3,2100115,2,1101015,3,1101105,3,2110015,4,1110105,4,2111005,4,3
在朴素的方法中我们通过二进制数来构造方案而二进制数是需要通过迭代的方法来获取next的。考虑不通过二进制数直接在方案上变换来得到下一个方案。假设一个方案从低到高的k个数分别是{a0,a1,⋯ ,ak−1}我们可以从低位向高位找到第一个j使得aj1≠aj1我们知道出现在a序列中的数字在二进制数中对应的位置一定是1即表示被选中那么aj1≠aj1意味着aj和aj1对应的二进制位中间有0即这两个1不连续。我们把aj对应的1向高位推送也就对应着aj←aj1而对于i∈[0,j−1]内所有的ai把值恢复成i1即对应这j个1被移动到了二进制数的最低j位。这似乎只考虑了上面的「规则二」。但是实际上 「规则一」是「规则二」在t0时的特殊情况因此这么做和按照两条规则模拟是等价的。
在实现的时候我们可以用一个数组temp来存放a序列一开始我们先把1到k按顺序存入这个数组他们对应的下标是0到k−1。为了计算的方便我们需要在下标k的位置放置一个哨兵n1思考题为什么是n1呢。然后对这个temp序列按照这个规则进行变换每次把前k位即除了最后一位哨兵的元素形成的子数组加入答案。每次变换的时候我们把第一个aj1≠aj1的j找出使aj自增1同时对i∈[0,j−1]的aia重新置数。如此循环直到temp中的所有元素为n内最大的k个元素。
回过头看这个思考题它是为了我们判断退出条件服务的。我们如何判断枚举到了终止条件呢其实不是直接通过temp来判断的我们会看每次找到的j的位置如果jk了就说明[0,k−1]内的所有的数字是比第k位小的最后k个数字这个时候我们找不到任何方案的字典序比当前方案大了结束枚举。
class Solution {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();public ListListInteger combine(int n, int k) {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();// 初始化// 将 temp 中 [0, k - 1] 每个位置 i 设置为 i 1即 [0, k - 1] 存 [1, k]// 末尾加一位 n 1 作为哨兵for (int i 1; i k; i) {temp.add(i);}temp.add(n 1);int j 0;while (j k) {ans.add(new ArrayListInteger(temp.subList(0, k)));j 0;// 寻找第一个 temp[j] 1 ! temp[j 1] 的位置 t// 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]while (j k temp.get(j) 1 temp.get(j 1)) {temp.set(j, j 1);j;}// j 是第一个 temp[j] 1 ! temp[j 1] 的位置temp.set(j, temp.get(j) 1);}return ans;}
}时间复杂度 O((nk)×k)。外层循环的执行次数是(n/k)次每次需要做一个O(k)的添加答案和O(k)的内层循环故时间复杂度O((n/k)×k)。 空间复杂度 O(k)。即temp的空间代价。
