前言
持续更新了
正文
问题来源
本问题来自leetcode上的491题。
问题描述
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例 1:
输入: [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]]
分析：
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
void dfs(int cur, int last, vector<int>& nums) {
if (cur == nums.size()) {
if (temp.size() >= 2) {
ans.push_back(temp);
}
return;
}
if (nums[cur] >= last) {
temp.push_back(nums[cur]);
dfs(cur + 1, nums[cur], nums);
temp.pop_back();
}
if (nums[cur] != last) {
dfs(cur + 1, last, nums);
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(0, INT_MIN, nums);
return ans;
}
};
func findSubsequences(nums []int) [][]int {
rec := make([]int, 0)
res := make([][]int, 0)
dfs(nums, 0, math.MinInt32, &rec, &res)
return res
}
func dfs(nums []int, cur, last int, rec *[]int, res *[][]int) {
if cur == len(nums) {
if len(*rec) >= 2 {
tmp := make([]int, len(*rec))
copy(tmp, *rec)
*res = append(*res, tmp)
}
return
}
if nums[cur] >= last {
*rec = append(*rec, nums[cur])
dfs(nums, cur+1, nums[cur], rec, res)
*rec = (*rec)[:len(*rec)-1]
}
if nums[cur] != last {
dfs(nums, cur+1, last, rec, res)
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
