网站seo优化方案策划书,有没有一个网站做黄油视频,绍兴seo网站管理,专业网页制作平台一、组合
1. 问题描述
给定两个整数 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;
输…一、组合
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]]
2. 代码实现
1c实现代码
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合int stack[999], top -1; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {// 当结果的长度符合时将结果存放到result结果集合中if (top1 k) {vectorint ans;for(int i0;itop;i){ans.push_back(stack[i]);}result.push_back(ans);return;}for (int i startIndex; i n; i) {stack[top] i;backtracking(n, k, i 1); // 递归top--;// 回溯撤销处理的节点}}public:vectorvectorint combine(int n, int k) {result.clear();backtracking(n, k, 1);return result;}
}; 2c语言实现代码
struct Combination {// 嵌套数组结果int **result;// 中间数组int *path;// 中间数组的长度int pathSize;// 结果数组的总数int returnSize;
};void backtrack(struct Combination *com, int n, int k, int startIndex) {// 当组合的大小达到k时将其添加到结果中if (com-pathSize k) {// 在result的数组returnSize也就是第几个结果集的位置的位置提前申请一个空间com-result[com-returnSize] (int *)malloc(k * sizeof(int));// 将中间数组存入result数组中for (int i 0; i k; i) {com-result[com-returnSize][i] com-path[i];}// 将结果集1com-returnSize;return;}// 横向遍历加入了剪枝操作即最后组成的数无法到要求直接剪掉即可for (int i startIndex; i n - (k - com-pathSize) 1; i) {// 处理当前节点com-path[com-pathSize] i; // 中间数组长度1com-pathSize;// 纵向遍历选择之后不能继续再选即i1backtrack(com, n, k, i 1);// 回溯撤销处理的节点com-pathSize--; }
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {// 定义暂存结构体struct Combination com;com.returnSize 0;com.pathSize 0;// 初始条件是否符号条件if (n 0 || k 0 || k n) {return NULL;}// 计算组合的总数int totalCombinations 1;for (int i 1; i k; i) {totalCombinations * (n - i 1);totalCombinations / i;}// 分配结果数组的空间com.result (int **)malloc(totalCombinations * sizeof(int *));com.path (int *)malloc(k * sizeof(int));// 使用回溯法生成组合backtrack(com, n, k, 1);// 返回每一个子数组的大小*returnColumnSizes (int *)malloc(com.returnSize * sizeof(int));for (int i 0; i com.returnSize; i) {(*returnColumnSizes)[i] k;}// 返回结果数组的大小*returnSize com.returnSize;return com.result;
}
二、全排列
1. 问题描述
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2
输入nums [0,1]
输出[[0,1],[1,0]]
示例 3
输入nums [1]
输出[[1]]
2. 代码实现 c代码实现
class Solution {
private:vectorvectorint result;int stack[999], top-1;void backtracking (vectorint nums, vectorbool used) {// 此时说明找到了一组if (top1 nums.size()) {vectorint ans;for(int i0;itop;i){ans.push_back(stack[i]);}result.push_back(ans);return;}for (int i 0; i nums.size(); i) {// 已经使用过直接跳过即可if(used[i] true){continue;}// used[i - 1] true说明同一树枝nums[i - 1]使用过// used[i - 1] false说明同一树层nums[i - 1]使用过 // 如果同一树层nums[i - 1]使用过则直接跳过if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;}used[i] true;stack[top] nums[i];backtracking(nums, used);top--;used[i] false;}}
public:vectorvectorint permute(vectorint nums) {result.clear();sort(nums.begin(), nums.end()); // 排序vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
};
c语言实现
struct Combination{// 结果数组int **result;int resultSize;// 中间数组int *path;int pathSize;
};void backtrace(struct Combination *com, int nums[], int n, int used[])
{// 当组合的大小达到k时将其添加到结果中if(com-pathSize n){com-result[com-resultSize] (int*)malloc(n*sizeof(int));for(int i0;in;i){com-result[com-resultSize][i] com-path[i];}com-resultSize;return;}// 横向遍历for(int i0; in; i){// 如果已经使用过就不再次使用if(used[i] 1){continue;}used[i] 1;com-path[com-pathSize] nums[i];com-pathSize;// 纵向遍历backtrace(com, nums, n, used);com-pathSize--;used[i] 0;}
}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){struct Combination com;com.resultSize 0;com.pathSize 0;// 结果集总数int total 1;for(int i1;inumsSize;i){total * i;}// malloc申请空间com.result (int**)malloc(total*sizeof(int*)); // 嵌套数组com.path (int*)malloc(numsSize*sizeof(int)); // 数组// 状态数组int used[numsSize];for(int i0;inumsSize;i){used[i] 0;}// 开始回溯backtrace(com, nums, numsSize, used);// 返回每一个子数组的大小*returnColumnSizes (int *)malloc(com.resultSize * sizeof(int));for (int i 0; i com.resultSize; i) {(*returnColumnSizes)[i] numsSize;}// 返回结果数组的大小*returnSize com.resultSize;return com.result;
}
三、 全排列 II
1. 问题描述
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]
示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2. 代码实现
c代码实现
class Solution {
private:vectorvectorint result;int stack[999], top-1;void backtracking (vectorint nums, vectorbool used) {// 此时说明找到了一组if (top1 nums.size()) {vectorint ans;for(int i0;itop;i){ans.push_back(stack[i]);}result.push_back(ans);return;}for (int i 0; i nums.size(); i) {// 已经使用过直接跳过即可if(used[i] true){continue;}// used[i - 1] true说明同一树枝nums[i - 1]使用过// used[i - 1] false说明同一树层nums[i - 1]使用过 // 如果同一树层nums[i - 1]使用过则直接跳过if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;}used[i] true;stack[top] nums[i];backtracking(nums, used);top--;used[i] false;}}
public:vectorvectorint permuteUnique(vectorint nums) {result.clear();sort(nums.begin(), nums.end()); // 排序vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
}; 从上面三个题目的代码可以看到其实这三个题目出自同一个模板稍微总结一下就可以得出也可以从上面三个题目很好的学习回溯的方法 上面两个组合和全排列都给出来C和C语言的代码C主要借助vector容器的实现而C则要复杂一些我选择使用的是结构的方法实现。 解题思路和代码模板均来自代码随想录 - 力扣LeetCode 77. 组合 46. 全排列 47. 全排列 II
