IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 递增子序列-leetcode491-java回溯题解 -> 正文阅读

[数据结构与算法]递增子序列-leetcode491-java回溯题解

说明:问题描述来源leetcode

一、问题描述:

491. 递增子序列

难度中等560

给你一个整数数组 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]]

提示:

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

二、题解:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    private int[] nums;

    public List<List<Integer>> findSubsequences(int[] nums) {
        this.nums = nums;
        backTracking(0);
        return res;
    }

    private void backTracking(int startIndex) {
        if (path.size() > 1){
            res.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();

        for (int i = startIndex; i < nums.length; i++) {
            if (path.size() != 0 && nums[i] < path.get(path.size() - 1)) continue;
            
            if (! set.add(nums[i])) continue;
            
            path.add(nums[i]);
            backTracking(i + 1);
            path.remove(path.size() - 1);
        }
    }
}
//[-100,-100,0,0,0,100,100,0,0]
//[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]

这个题解做得真蛋疼,怎么说呢,这个题和leetcode题40确实是有一个是类似的,但是又有不同之处,过滤掉重复的元素就通过set集合或者map,也可以,把这个题解的set来过滤元素的思路是可以放到leetcode题40里的,不信下面就试一下:

可以将下面的代码放到leetcode题40里执行一下,是可以成功的:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int target;
    int[] candidates;
    public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
        //为了将重复的数字都放到一起,所以先进行排序
        this.target = target;
        Arrays.sort( candidates );
        this.candidates = candidates;
        backTracking(  0 ,0);
        return res;
    }

    private void backTracking(  int start ,int sum) {
        if ( sum == target ) {
            res.add( new ArrayList<>( path ) );
            return;
        }
        Set<Integer> set = new HashSet<Integer>();

        for ( int i = start; i < candidates.length ; i++ ) {
            if (sum + candidates[i] > target) return;
            if(!set.add(candidates[i])) continue;

            // if ( i > start && candidates[i] == candidates[i - 1] ) continue;

            path.add( candidates[i] );
            backTracking( i + 1 ,sum + candidates[i]);
            path.removeLast();
        }
    }

}

而题40和题491在过滤条件里有什么区别呢,这里都是为了防止下一次遍历到的元素和上一个元素相等;而题40在此处的过滤条件仅仅i不为startIndex时,并且和上一个元素比较就可以了,因为题40的数组是经过了排序的;但是题491就不可以了,因为nums是乱序,可能相隔几个不同元素又会遇到相同的元素.

[-100,-100,0,0,0,100,100,0,0]便是一个很好的例子,可以模拟下,就会发现有重复的结果出现。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:13 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/17 6:52:20-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码