上杭网站,wordpress themes 目录,做网站找什么公司好,seo营销推广费用寻找递增子序列
力扣原题链接
问题描述
给定一个整数数组 nums#xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以视作递增序…寻找递增子序列
力扣原题链接
问题描述
给定一个整数数组 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]] 解题思路
初始化一个列表 res 用于存储结果。调用回溯函数 backtrack传入参数 nums 数组、起始索引 0、当前路径 path 和结果列表 res。在回溯函数中首先将当前路径 path 加入到结果列表 res 中。然后从起始索引 start 开始向后遍历数组 nums依次选择元素加入当前路径 path 中。在选择元素加入路径之前需要判断是否满足递增条件和是否重复如果满足条件则递归调用回溯函数继续探索下一个位置的选择。当遍历结束后回溯函数结束返回结果列表 res。
复杂度分析
回溯算法的时间复杂度取决于最终的结果数量而结果数量取决于数组 nums 中满足条件的递增子序列的个数。假设数组 nums 的长度为 n则时间复杂度为 O(2^n)其中 n 表示数组的长度。
算法步骤
初始化一个列表 res 用于存储结果。调用回溯函数 backtrack传入参数 nums 数组、起始索引 0、当前路径 path 和结果列表 res。在回溯函数中首先将当前路径 path 加入到结果列表 res 中。遍历数组 nums从索引 start 开始依次选择元素加入当前路径 path 中。在选择元素加入路径之前需要进行判断 如果当前路径的长度大于等于 2则将当前路径加入结果列表。使用一个哈希集合 used 来记录已经选择过的元素以避免重复选择。如果选择的元素小于当前路径的最后一个元素则跳过保证递增。如果当前元素已经被选择过则跳过避免重复。 递归调用回溯函数传入更新后的起始索引 i 1、当前路径 path 和结果列表 res。当遍历结束后回溯函数结束返回结果列表 res。 java代码
class Solution {ListListInteger res new ArrayList();// 主函数用于找到数组中的递增子序列public ListListInteger findSubsequences(int[] nums) {backtrack(nums, 0, new ArrayList()); // 回溯函数的入口return res; // 返回结果列表}// 回溯函数用于寻找数组中的递增子序列private void backtrack(int[] nums, int start, ListInteger path) {// 当路径中元素数量大于等于 2 时将当前路径加入结果列表中if (path.size() 2) {res.add(new ArrayList(path));}// 用于记录已经使用过的元素避免重复使用SetInteger used new HashSet();// 遍历数组从当前位置开始for (int i start; i nums.length; i) {//树层去重操作// 若当前路径不为空且当前数字小于路径中最后一个数字则跳过当前数字因为要求递增子序列if (!path.isEmpty() nums[i] path.get(path.size() - 1)) {continue;}// 树枝剪枝操作// 若当前数字已经使用过则跳过当前数字避免重复if (used.contains(nums[i])) {continue;}// 将当前数字加入路径中并标记为已使用used.add(nums[i]);path.add(nums[i]);// 递归进入下一层继续寻找递增子序列backtrack(nums, i 1, path);// 回溯撤销选择将当前数字移出路径path.remove(path.size() - 1);}}
}
通过使用回溯算法我们可以有效地找到数组中所有满足条件的递增子序列。在回溯过程中我们需要维护一个当前路径逐步探索所有可能的选择并及时剪枝以避免重复。
