洛阳网站建设联系方式,少儿编程课网课免费,新媒体营销方案,媒体邀约递增子序列
491. 非递减子序列 - 力扣#xff08;LeetCode#xff09; 非递减子序列#xff0c;则答案的子集中#xff0c;需保持下一个元素大于等于前一个元素的顺序#xff0c;由于题目中指出#xff0c;所有的子序列长度需大于等于2#xff0c;考虑当条件为path.siz…递增子序列
491. 非递减子序列 - 力扣LeetCode 非递减子序列则答案的子集中需保持下一个元素大于等于前一个元素的顺序由于题目中指出所有的子序列长度需大于等于2考虑当条件为path.size()1时进行收获结果且需要注意这时不应该直接return因为后续仍有可能存在子序列长度大于2的结果仍需要继续遍历。此时结束的标志是单层遍历的结束。 如果只按照上述向下运行没有完成子序列的去重操作为了完成子序列的去重以及保证下一个元素大于当前元素才加入数组考虑加入一个set在对当前层进行遍历时若该元素没有使用过将其加入set若该元素大于path的末尾元素将其加入path。之后继续回溯回溯完成后复原path。具体思路参考代码随想录。
代码随想录 (programmercarl.com)https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
class Solution {
public:vectorint path; // 存储当前递增子序列vectorvectorint paths; // 存储所有不同的递增子序列void backtracking(vectorint nums, int start) {if (path.size() 2) {paths.push_back(path); // 将满足条件的子序列添加到结果中}unordered_setint uset; // 用于去重for (int i start; i nums.size(); i) {if ((!path.empty() nums[i] path.back()) || uset.find(nums[i]) ! uset.end()) {continue; // 跳过不满足条件的元素}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i 1); // 递归搜索下一个元素path.pop_back(); // 回溯移除当前元素}}vectorvectorint findSubsequences(vectorint nums) {backtracking(nums, 0); // 从第一个元素开始搜索return paths;}
};回溯法寻找递增子序列的过程在最差情况下需要遍历所有可能的子序列每个元素都有可能存在或者不存在与子序列中所以算法的时间复杂度为O(2^n)就空间复杂度来说使用了哈希集合来检查是否已经包含了某个元素使用了一个辅助的path来存储当前的子序列在递归的过程中path和uset都会不断改变但最大的情况为递归的最深处此时应有n层因此空间复杂度为O(n)。 全排列
46. 全排列 - 力扣LeetCode
思路从数组的第一个元素开始逐步构建排列对于每个位置将不同的数字放在该位置上然后递归地处理下一个位置。若当前位置已经包含了某元素则我们要跳过它选择其他数字条件为 if (find(path.begin(), path.end(), nums[i]) path.end())
治理find函数返回的迭代器等于path.end(),说明nums[i]不在path中即当前数字还没有被使用过。
当排列的长度等于数组的长度时收获为一个有效的排列。
if (path.size() nums.size()) {result.push_back(path); // 当排列长度等于数组长度时保存该排列return;}
整体代码如下。
class Solution {
public:vectorint path; // 保存当前排列vectorvectorint result; // 保存所有不同的排列void backtracking(vectorint nums, int start) {if (path.size() nums.size()) {result.push_back(path); // 当排列长度等于数组长度时保存该排列return;}for (int i 0; i nums.size(); i) {if (find(path.begin(), path.end(), nums[i]) path.end()) {// 如果当前数字不在排列中将其添加到排列中path.push_back(nums[i]);backtracking(nums, i 1); // 递归搜索下一个位置path.pop_back(); // 回溯移除当前数字}}}vectorvectorint permute(vectorint nums) {backtracking(nums, 0); // 从第一个位置开始搜索return result;}
};
排列的时间复杂度为O(n!)每个位置都可以选择不同的数字。
空间复杂度为O(n)。
全排列II
47. 全排列 II - 力扣LeetCode
错误代码使用了start
class Solution {
public:vectorint path; // 保存当前排列vectorvectorint result; // 保存所有不同的排列void backtracking(vectorint nums, int start) {if (path.size() nums.size()) {result.push_back(path); // 当排列长度等于数组长度时保存该排列return;}for (int i 0; i nums.size(); i) {if(start 0 and nums[i] nums[i - 1]){continue;}path.push_back(nums[i]);backtracking(nums, i 1); // 递归搜索下一个位置path.pop_back(); // 回溯移除当前数字}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end()); // 首先排序以便去除重复排列backtracking(nums, 0);return result;}
};
正确代码
class Solution {
public:vectorint path; // 保存当前排列vectorvectorint result; // 保存所有不同的排列void backtracking(vectorint nums, vectorbool used, int start) {if (path.size() nums.size()) {result.push_back(path); // 当排列长度等于数组长度时保存它return;}for (int i 0; i nums.size(); i) {if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue; // 跳过重复的元素}if (!used[i]) {path.push_back(nums[i]);used[i] true;backtracking(nums, used, i 1); // 递归搜索下一个位置path.pop_back(); // 回溯移除当前数字used[i] false;}}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end()); // 首先排序以便去除重复排列vectorbool used(nums.size(), false); // 初始化 used 数组backtracking(nums, used, 0);return result;}
};start可有可无
算法的时间复杂度为O(n!)空间复杂度为O(n)同上。
