代码随想录算法训练营第二十九天| 491. 非递减子序列、46. 全排列、47. 全排列 II

本文主要是介绍代码随想录算法训练营第二十九天| 491. 非递减子序列、46. 全排列、47. 全排列 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[LeetCode] 491. 非递减子序列

[LeetCode] 491. 非递减子序列 文章解释

[LeetCode] 491. 非递减子序列 视频解释

题目:

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

[LeetCode] 491. 非递减子序列

自己看到题目的第一想法

    和切割问题是一样的, 需要遍历所有可能的组合, 然后判断每个组合是否符合要求.

    重复了怎么办呢? 和之前一样, 如果当前的元素和前一个相同, 则跳过当前元素?

    这样判断是不对的, 因为元素并没有排序.

看完代码随想录之后的想法

    对于每一层的递归, 在单层递归逻辑的 for 循环之前, 创建一个 Set , 该 Set 记录所有出现过的数字. 这样的话就可以知道当前数字和数字之后的元素组成的组合, 是不是已经处理过了.

    妙啊! 又 get 到一个新的去重技巧.

class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex) {Set<Integer> used = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if (used.contains(nums[i])) {continue;}if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {continue;}path.add(nums[i]);used.add(nums[i]);if (path.size() > 1) {result.add(new ArrayList<>(path));}backTracking(nums, i + 1);path.remove(path.size() - 1);}}
}
class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex) {boolean[] used = new boolean[201];// 去重优化, Set 的操作会更耗时一些for (int i = startIndex; i < nums.length; i++) {if (used[nums[i] + 100]) {continue;}if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {continue;}path.add(nums[i]);used[nums[i] + 100] = true;if (path.size() > 1) {result.add(new ArrayList<>(path));}backTracking(nums, i + 1);path.remove(path.size() - 1);}}
}

自己实现过程中遇到哪些困难

    对于去重的逻辑一致没想明白自己哪里错了, 因为 LeetCode 的提交结果上无法复制出完整的运行结果和预期结果.

    使用提交结果页面右上角的 “添加到测试用例” 按钮, 将测试用例添加到本地后, 运行测试用例后, 在本地运行的结果框的右上角有一个 “diff” 按钮. 点击后可以看到完整的数据.

    同时, 系统自带的记事本没办法成功的搜索... 复制到 sublimme text 之后才发现, 像 “1, 2, 7, 5, 1, 1, 1” 这样的序列, 1 的 部分会重复计算多次.

[LeetCode] 46. 全排列

[LeetCode] 46. 全排列 文章解释

[LeetCode] 46. 全排列 视频解释

题目:

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

[LeetCode] 46. 全排列

自己看到题目的第一想法

    画个树图~

    咦, 每个用过的元素都要被剔除, 但是不能用 startIndex 该怎么办呢?

    卡哥的 used 数组大法能用吗?

    bingo!!! 如此顺畅的逻辑...

    毕竟是基础题... 有那么一丝的不会才是可耻的好吗.

看完代码随想录之后的想法

    基本差不多的逻辑, 这一题算是基础中的基础, 比较简单.

class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {backTracking(nums, new boolean[nums.length]);return result;}private void backTracking(int[] nums, boolean[] used) {for (int i = 0; i < nums.length; i++) {if (used[i]) {// 数组去重效率高一些continue;}path.add(nums[i]);used[i] = true;if (path.size() == nums.length) {result.add(new ArrayList<>(path));} else {backTracking(nums, used);}path.remove(path.size() - 1);used[i] = false;}}
}
class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();private Set<Integer> used = new HashSet<>();public List<List<Integer>> permute(int[] nums) {backTracking(nums);return result;}private void backTracking(int[] nums) {for (int i = 0; i < nums.length; i++) {if (used.contains(nums[i])) {continue;}path.add(nums[i]);used.add(nums[i]);if (path.size() == nums.length) {result.add(new ArrayList<>(path));} else {backTracking(nums);}used.remove(nums[i]);path.remove(path.size() - 1);}}
}

自己实现过程中遇到哪些困难

[LeetCode] 47. 全排列 II

[LeetCode] 47. 全排列 II 文章解释

[LeetCode] 47. 全排列 II 视频解释

题目:

给定一个可包含重复数字的序列 nums按任意顺序 返回所有不重复的全排列。

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],[1,2,1],[2,1,1]]

示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

[LeetCode] 47. 全排列 II

自己看到题目的第一想法

    排列的去重版. 使用前后元素一致则忽略后一个元素的办法可行.

看完代码随想录之后的想法

    需要用 int[] used 或者 Set<Integer> used 来排除已经使用的元素.

    使用 int[] used 还可以同时用来去重. 妙啊妙!

class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);backTracking(nums, 0, new boolean[nums.length]);return result;}private void backTracking(int[] nums, int startIndex, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// 因为 i 是从 0 开始的, 因此必须知道前一个元素是否正在使用, 正在使用说明是树层去重, 否则是树叶去重.// 两者都能通过, 但是树叶去重效率低很多, 因为需要遍历更多的叶子结点才能完成去重.if (used[i] || (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])) {continue;}path.add(nums[i]);used[i] = true;backTracking(nums, i + 1, used);path.remove(path.size() - 1);used[i] = false;}}
}

自己实现过程中遇到哪些困难

这篇关于代码随想录算法训练营第二十九天| 491. 非递减子序列、46. 全排列、47. 全排列 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1034377

相关文章

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架,使用的是

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》:本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝?ArrayList 浅拷贝的重要性方法一:使用构造函数方法二:使用 addAll(