网站建设公司利润,如何进行营销型企业网站的优化,上海做网站公,做微课常用的网站力扣日记#xff1a;【回溯算法篇】491. 非递减子序列 日期#xff1a;2023.2.20 参考#xff1a;代码随想录、力扣 ps#xff1a;放了个寒假#xff0c;日记又搁置了三星期……#xff08;下跪忏悔#xff09; 491. 非递减子序列
题目描述 难度#xff1a;中等 给你一…力扣日记【回溯算法篇】491. 非递减子序列 日期2023.2.20 参考代码随想录、力扣 ps放了个寒假日记又搁置了三星期……下跪忏悔 491. 非递减子序列
题目描述 难度中等 给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
示例 1 输入nums [4,6,7,7] 输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 示例 2 输入nums [4,4,3,2,1] 输出[[4,4]] 提示
1 nums.length 15-100 nums[i] 100
题解
cpp ver
class Solution {
public:vectorint path;vectorvectorint result;vectorvectorint findSubsequences(vectorint nums) {// nums.size 2if (nums.size() 2) return result;backtracking(nums, 0, -200); // -100 nums[i] 100return result;}void backtracking(vectorint nums, int startindex, int lastnum) {// 子序列至少有两个值if (path.size() 2) result.push_back(path);int used[201] {0}; // 这里使用数组来进行去重操作题目说数值范围[-100, 100]在for循环前重置每个for循环对应一个// for 循环for (int i startindex; i nums.size(); i) {// // 树层去重(如果本次取出元素与上一个元素一样则跳过该元素)// if (i startindex nums[i] nums[i - 1]) continue;// 注意本题由于不能对元素进行排序所以树层中也可能出现不连续元素重复的可能所以不能简单的用相邻元素重复来去重// 可以用哈希表来去重(或数组)if (used[nums[i] 100] ! 0) continue; // 如果是已经取过的元素则跳过该元素used[nums[i] 100] 1; // 记录该元素// 如果本次取出元素比上一次取的元素低则不进入递归但不结束for循环// (注意取值可不连续!!!如[4,7,6,7]中[4,7,7]也是递增子序列所以这里不能break)if (nums[i] lastnum) continue;// 处理节点path.push_back(nums[i]);backtracking(nums, i 1, nums[i]);path.pop_back();}}
};复杂度
时间复杂度: O(n * 2^n) 空间复杂度: O(n)
思路总结
本题首先要明确“递增子序列”的概念 子序列问题本质上是子集问题递增子序列或者说非递减子序列是可以从原集合中非连续取值的 这点是易错点且单从题目描述或例子中不能得出此结论但经过测试用例确实如此以[4,7,6,7]为例子[4,7,7]或[7,7]也是其子序列这是不同于只能连续取值的字符串子串的 所以本题在去重时不能像 90.子集 II 那样通过相邻元素相同来去重那种去重思路仅适用于能先对原集合进行排序的情况但本题提前排序会改变原集合的非递增性质故不能提前排序因为可能会在不连续的地方出现重复的元素。 可以通过哈希表的方法来去重如用哈希set或效率更高的数组如代码所示 每层for循环都对应一个数组来记录某元素是否已经取过如果已经取过则跳过该元素即 int used[201] {0}; // 这里使用数组来进行去重操作题目说数值范围[-100, 100]在for循环前重置每个for循环对应一个// for 循环for (int i startindex; i nums.size(); i) {//用哈希表来去重(或数组)if (used[nums[i] 100] ! 0) continue; // 如果是已经取过的元素则跳过该元素used[nums[i] 100] 1; // 记录该元素...对于需要为“递增子序列”的判断实际上也是能否进行取值和递归即所谓处理节点的前提条件即只有当前值不小于上一次取的值才能进行取值和递归 首先用last_num作为参数来记录上一次取的值即在递归时令last_num nums[i]并且在满足上面的去重条件后通过if (nums[i] lastnum) continue;来过滤不满足递增条件的元素。这里也可以不用last_num作为递归参数而是用if (!path.empty() nums[i] path.back()) continue来表示因为path.back()即为上一个取的值前提是path不为空同时注意不能用break而要用contnue理由是子序列的取值可以不连续即使当前值不满足递增其后面的元素也可能满足因此不能直接break 树形结构示意图 可见其中存在两种不符合条件的情况一是“同一父节点下本层重复使用”对应去重二是“所取元素小于子序列最后一个元素”对应“递增”条件。 三部曲 返回值及传递参数参数为经典的原数组nums以及startindex记录for循环取值的起始位置除此之外还用一个last_num记录递归纵向遍历中的上一个取值 如果直接用path.back()表示则不需要此参数终止条件对于子集问题由于需要遍历各个节点进行存储所以不需要专门的终止条件。这里注意子序列至少包含两个值即path需要满足size2 注在原先的代码实现中本来是在终止条件处实现递增条件的判断即当出现小于上一个取值的元素则终止但是这样会使得最后一个path的存储非常麻烦所以作废还是需要将此递增条件的判断作为for循环中、处理节点即取值并递归的前提条件。 for循环处理 去重哈希表记录重复元素重复则跳过递增条件小于上一个取值则跳过处理节点取值、递归、回溯
