Keshawn_lu's Blog

Leetcode 491. 递增子序列

字数统计: 566阅读时长: 2 min
2020/08/25 Share

题目简介:

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例:

1
2
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  1. 给定数组的长度不会超过15。
  2. 数组中的整数范围是 [-100,100]。
  3. 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

思路:

又是做的头疼的一道题,深度优先搜索,每次记录当前遍历到的位置以及上一次访问的位置。

遍历结束的条件是当前的位置curpos == nums.size(),即遍历了所有元素。

每次遍历有两种情况:

  1. 选择该元素,满足要求后加入数组(要求在下面叙述)
  2. 不选择该元素,即直接跳过该元素进行下次遍历

选择该元素时,有以下条件需要满足:

  1. 要么当前temp数组为空,即此元素是第一个加入数组的元素;要么当前的元素大于等于上次访问到的元素。
  2. 不管第一个满足的条件是哪个,都需要进行判定是否为重复项。

判定重复项时,我们可以从[lastpos + 1, curpos)这个区间里去寻找是否有和nums[curpos]相同的元素,若有,则说明该元素插入数组后形成的递增序列之前已经构造过了,直接跳过该元素即可。

tip:

  • 需要弹出元素进行回溯操作。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:

vector<vector<int>> res;
vector<int> temp;

//去重
bool judge(vector<int>& nums, int curpos, int lastpos){

for(int i = lastpos + 1; i < curpos; i++){

if(nums[i] == nums[curpos])
return false;
}

return true;
}

void dfs(vector<int>& nums, int curpos, int lastpos){

if(curpos == nums.size())
return;

if((temp.empty() || nums[curpos] >= nums[lastpos]) && judge(nums, curpos, lastpos)){

temp.push_back(nums[curpos]);

if(temp.size() >= 2)
res.push_back(temp);

dfs(nums, curpos + 1, curpos); //选择该元素

temp.pop_back(); //撤销选择, 回溯
}

dfs(nums, curpos + 1, lastpos); //不选择该元素
}

vector<vector<int>> findSubsequences(vector<int>& nums) {

dfs(nums, 0, -1);
return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: