当前位置：首页 > news >正文

C++算法练习-day62——491.非递减子序列

news 来源：原创 2025/5/13 20:58:36

题目来源：. - 力扣（LeetCode）

题目思路分析

这个问题要求找出数组 nums 中的所有非严格递增子序列，其中每个子序列至少包含两个元素。非严格递增子序列意味着子序列中的元素可以相等，但不允许递减。

为了解决这个问题，可以使用回溯法。回溯法是一种通过探索所有可能的候选解来找出所有解的算法。具体到这个问题，我们从数组的第一个元素开始，尝试将其加入当前的子序列中，然后递归地尝试将后续的元素加入子序列。如果当前子序列的长度达到或超过2，则将其加入结果集中。

代码:

#include <vector>  class Solution {  
public:  // 回溯函数  void Backstracking(vector<vector<int>>& ans, vector<int>& pos, vector<int>& nums, int startIndex) {  // 如果当前子序列长度达到或超过2，则加入结果集  if (pos.size() >= 2) {  ans.push_back(pos);  }  // 数组used用于记录已经访问过的数字，避免重复数字在同一层产生相同的子序列  int used[201] = {0};  // 从startIndex开始遍历数组  for (int i = startIndex; i < nums.size(); ++i) {  // 如果当前子序列非空且新元素小于子序列的第一个元素，或者新元素已经被使用过（在同一层），则跳过  if (!pos.empty() && (pos.front() > nums[i] || used[nums[i]+100]== 1)) {  continue;  }   // 将新元素加入当前子序列  pos.push_back(nums[i]);  // 标记该元素为已使用  used[nums[i]+100]=1;  // 递归调用回溯函数，尝试将后续元素加入子序列  Backstracking(ans, pos, nums, i + 1);  // 回溯：撤销选择  pos.pop_back();  }  }  // 主函数，调用回溯函数并返回结果集  vector<vector<int>> findSubsequences(vector<int>& nums) {  vector<vector<int>> ans;  vector<int> pos;  // 用于存储当前构建的子序列  Backstracking(ans, pos, nums, 0);  return ans;  }  
};

知识点摘要

回溯法：一种通过递归地探索所有可能的候选解来找出所有解的算法。在每一步中，算法都会尝试所有可能的选项，并在必要时撤销选择（回溯），以便尝试其他选项。
数组与向量：在C++中，数组和向量都是用于存储一系列元素的容器。数组的大小在编译时确定，而向量的大小可以在运行时动态改变。
条件判断与循环：用于控制程序流程的基本结构。条件判断用于根据条件执行不同的代码块，而循环用于重复执行一段代码直到满足特定条件。

这个问题是一个典型的回溯法问题，通过递归地探索所有可能的子序列来找出所有非严格递增子序列。在回溯过程中，我们使用了一个向量 pos 来存储当前构建的子序列，并使用一个数组 used 来避免在同一层产生重复的子序列。通过条件判断和循环，我们有效地控制了回溯过程，并最终得到了所有满足条件的子序列。这个问题不仅考察了回溯法的应用，还涉及了数组与向量的使用、条件判断与循环等基础知识。

题目来源：. - 力扣（LeetCode）

题目思路分析

代码:

知识点摘要

相关文章：