本文主要是介绍代码随想录打卡Day25,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天一整天都在教研室做实验,没时间刷题,就做了一题,剩下的明天补
491.递增子序列
这道题目和之前的子集问题很像,但是有一点要注意的,这个输入的数组不能进行排序,所以就不能沿用之前的去重逻辑,这道题要去重还是得借助额外的变量来维护元素使用情况,但是这题的used为集合,且不能为全局变量,只能为树层遍历前定义的一个局部变量,除了这个改动以外,其他地方都是高度相似的。
class Solution {
public:vector<vector<int>> result;vector<int> path;vector<vector<int>> findSubsequences(vector<int>& nums) {BackTracking(nums, 0);return result;}void BackTracking(vector<int> &nums, int Start_Index){//确定终止条件if(Start_Index >= nums.size()) return ;//确定单层递归逻辑set<int> used; //用哈希表来记录元素是否使用for(int i = Start_Index; i < nums.size(); i++){if(used.find(nums[i]) != used.end()) //需要去重continue;if(path.size() > 0 && nums[i] < path[path.size() - 1])continue;path.push_back(nums[i]);used.insert(nums[i]);if(path.size() >= 2)result.push_back(path);BackTracking(nums, i + 1);path.pop_back();}}
};
剩下的明天再补,太累了┭┮﹏┭┮
这篇关于代码随想录打卡Day25的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!