代码随想录算法训练营第二十九天 |491.递增子序列,46.全排列,47.全排列II(待补充)

时间:2024-02-11 23:03:11 标签:  排列  

491.递增子序列

1、题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

2、文章讲解:代码随想录

3、题目:

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例:

  • 输入: [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]]

说明:

  • 给定数组的长度不会超过15。
  • 数组中的整数范围是 [-100,100]。
  • 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

4、视频链接:

回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili

5、思路:

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集,又是去重,是不是不由自主的想起了刚刚讲过的90.子集II(opens new window)。

就是因为太像了,更要注意差别所在,要不就掉坑里了!

在90.子集II(opens new window)中我们是通过排序,再加一个标记数组来达到去重的目的。

而本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑!

本题给出的示例,还是一个有序数组 [4, 6, 7, 7],这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比,我用[4, 7, 6, 7]这个数组来举例,抽象为树形结构如图:

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex) {// 递增子序列的长度至少是2if (path.size() >= 2) {result.add(new ArrayList<>(path));// 注意这里不要加return,因为要取树上的所有节点}// 定义一个hashset来剪枝HashSet<Integer> hs = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {// 剪枝// 1. path里已经包含的元素// 2. 当前元素比path里最后一个元素还小// 3. 当前元素已经在hs里了if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) {continue;}hs.add(nums[i]);path.add(nums[i]);backTracking(nums, i + 1);path.removeLast();}}
}

46.全排列

1、题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

2、文章讲解:代码随想录

3、题目:

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

  • 输入: [1,2,3]
  • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

4、视频链接:

回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集_哔哩哔哩_bilibili

5、首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方

可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果public List<List<Integer>> subsets(int[] nums) {subsetsHelper(nums, 0);return result;}private void subsetsHelper(int[] nums, int startIndex) {result.add(new ArrayList<>(path));//「遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合」。if (startIndex >= nums.length) { // 终止条件可不加return;}for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);subsetsHelper(nums, i + 1);path.removeLast();}}
}

47.全排列II

1、题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

2、文章讲解:代码随想录

3、题目:

给定一个可包含重复数字的序列 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

4、视频链接:

回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili

class Solution {// 存放结果List<List<Integer>> result = new ArrayList<>();// 暂存结果List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backTrack(nums, used);return result;}private void backTrack(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}// 如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] == false) {used[i] = true;// 标记同⼀树⽀nums[i]使⽤过,防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);// 回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复used[i] = false;// 回溯}}}
}
来源:分享自作者个人站点/博客

智能推荐

491.递增子序列 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个整型数组, 你的任务是找到所有该数组的递增子序列&#xff0c;递增子序列的长度至少是2。 示例: 输入: [4, 6, 7, 7]

标签:排列  

今日任务 * 491.递增子序列* 46.全排列* 47.全排列 II 491.递增子序列 - Medium 题目链接&

标签:排列  

回溯算法part05 491.递增子序列解题思路与&#96; 90.子集II &#96;不同的点回溯三部曲

标签:算法  

理论基础 代码随想录原文 什么是回溯法 回溯也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 回溯是递

标签:算法  

回溯算法&#xff1a;其实就是递归&#xff0c;但是其更加考虑是归这个过程&#xff01;得到的是最后的几种可能性&#xff01; 其适合几种问题&#xff1a; 1.组合问题&#xff1b;2.排列问题&#xff1b;3.子集

标签:组合  

77. 组合 题目链接&#xff1a;组合 题目描述&#xff1a; 给定两个整数

标签:组合  

二叉树的层序遍历&#xff08;已观看视频&#xff0c;10道题&#xff09; 102.二叉树层序遍历&#xff08;特别重要&#xff0c;是模板&#xff09; 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给你一个二叉树&#xff0c;请你返回其按 层序遍历 得到的节点值。 &#xff08;即

标签:二叉树  

题目描述 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 输入示例

标签:排列  

46 全排列 给定一个 没有重复 数字的序列&#xff0c;返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]  排列问题与组合问题的不同之处就在于&#xff0c;没有startIndex&#xff0c;同

标签:排列  

代码随想录算法训练营第十一天 | 二叉树基础 文章目录 代码随想录算法训练营第十一天 | 二叉树基础1 二叉树的理论基础1.1 二叉树的类型1

标签:算法  

理论基础及Java实现参考文章&#xff1a;栈和队列 一、LeetCode 232 用栈实现队列 题目链接&#xff1a;232.用栈实现队列

标签:队列  

一、LeetCode 20 有效的括号 题目链接&#xff1a;20.有效的括号https://leetcode.cn/problems/v

标签:队列  

93.复原IP地址 题目链接&#xff1a;93.复原IP地址 有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff

标签:子集  

一、题目大意标签: 搜索https://leetcode.cn/problems/permutations-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,

标签:排列  LeetCode  II  Permutations  

题目&#xff1a;62.不同路径 文章链接&#xff1a;代码随想录 视频链接&#xff1a;LeetCode:62.不同路径 题目链接&#xff1a;力扣题目链接 图释&#xff1a; class Solution {public:// 确定dp数组&#xff08;dp table

标签:路径  

110.平衡二叉树 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示

标签:二叉树  

题目&#xff1a; 代码(首刷看解析 2024年2月3日&#xff09;&#xff1a; class Solution {private:vector<vector<int>> res;vector<int> path;public:void backtracking(vector&l

标签:序列  

题目要求给定一个不含重复数字的数组 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]]

标签:排列  LeetCode  

47.全排列 II 力扣题目链接(opens new window) 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输入&#xff1a;nums &#61; [1,1,2]输出&#xff1a; [[1,1,2], [1,2,1], [2,1,1]] 示例 2&#xff1a; 输入&#xff1a;nums &#61; [1,2,3]输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3

标签:排列  

文章目录 344.反转字符串&#xff1a;双指针思路代码&#xff1a; 541. 反转字符串II思路&#

标签:字符串  

代码随想录算法训练营第五十九天|503.下一个更大元素II 、42. 接雨水 下一个更大元素II 503.下一个更大元素II文章讲解&#xff1a;https://programmercarl.com/0503.%E4%B8

标签:更大  

二叉树的理论基础&#xff1a;&#xff08;二叉树的种类&#xff0c;存储方式&#xff0c;遍历方式 以及二叉树的定义&#xff09; https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86

标签:递归  

仅做学习笔记&#xff0c;详细请访问代码随想录 ● 理论基础 ● 77. 组合 ● 理论基础 回溯法解决的问题 回溯法&#xff0c;一般可以解决如下几种问题&#xff1a; 组合问题&#xf

标签:组合  

猜你喜欢

单调递增的数字 这道题思路挺巧妙的

标签:算法  

代码随想录 (programmercarl.com) 647. 回文子串 1.dp数组及下标含义 我们在判断字符串S是否是回文&#xff0c;那么如果我们知道 s[1]&#xff0c;s[2]&#xff0c;s[3] 这个子串是回文的&#xff0c;那么只需要比较 s[0]和s[4]这两个元素是否相同&#xff0c;如果相同的话&#xff0c;这个字符串s 就是回文串。 布尔类型的dp[i][j]&#xff1a;表示区间范围[i,j] &#xff08;注意是左闭右闭&#xff09;的子串是否是回文子串&#xff0c;如果是dp[i][j]为true&#xf

标签:回文  

第七章 回溯算法 77.组合代码随想录文章详解总结 77.组合 以n&#61;5,k&#61;3为例

标签:算法  

文章目录 二叉树基础二叉树种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 二叉树的存储方

标签:二叉树  

104.二叉树的最大深度 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个二叉树&#xff0c;找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。

标签:二叉树  

代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV 题目 https://www.acwing.com/problem/content/3/

标签:组合  

目录 理论基础  455.分发饼干  &#x1f4a1;解题思路

标签:大子  

系列文章目录 代码随想录算法训练营第一天|数组理论基础&#xff0c;704. 二分查找&#xff0c;27. 移除元素 代码随想录算法训练营第二天|977.有序数组的平方 &#xff0c;209.长度最小的子数组 &#xff0c;59.螺旋矩阵II

标签:算法  

代码随想录算法训练营第四十二天| 01背包问题、416.分割等和子集 题目 https://www.acwing.com/problem/content/2/ 2.01背包问题

标签:子集  

代码随想录算法训练营第二十四天|回溯算法的理论基础、77. 组合 回溯算法的理论基础77. 组合 回溯算法的理论基础 这里我觉得《代码随想录》和y总的课都比较好了

标签:算法  

问题描述 给定一个不含重复数字的数组 nums &#xff0c;返回其所有可能的全排列 。你可以按任意顺序返回答案。 输入示例

标签:排列  

不同路径 可以图论中的深度优先搜索

标签:路径  

今日任务  62.不同路径  63. 不同路径 II 62.不同路径 - Medium 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台     一个机器人位于一个 m x n 网格的左

标签:路径  

代码随想录算法刷题训练营day16&#xff1a;LeetCode(104)二叉树的最大深度 、LeetCode(559)n叉树的最大深度、LeetCode(111)二叉树的最小深度、LeetCode(222)完全二叉树的节点个数 LeetCod

标签:算法  

代码随想录算法刷题训练营day15&#xff1a;LeetCode(226)翻转二叉树、LeetCode(101)对称二叉树 LeetCode(226)翻转二叉树 题目

标签:算法  

代码随想录算法刷题训练营day20&#xff1a;LeetCode(654)最大二叉树、LeetCode(617)合并二叉树、LeetCode(700)二叉搜索树中的搜索、LeetCode(700)二叉搜索树中的搜索、LeetCode(98)验证二叉搜索

标签:算法  

654.最大二叉树 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。

标签:二叉树  

 39. 组合总和// 剪枝优化class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List&

标签:算法  

 93.复原IP地址 class Solution {List<String> result &#61; new ArrayList<>();public List<String> restoreIpAddresses(St

标签:算法  

* 491.递增子序列 class Solution {List<List<Integer>>result &#61;

标签:算法  

 332.重新安排行程 class Solution {private LinkedList<String> res;private LinkedList<String> path &#61; new LinkedList<>

标签:算法  

 理论基础  关于贪心算法&#xff0c;你该了解这些&#xff01; 题目分类大纲如下&#xff1a; #算法公开课

标签:算法  

第八章 贪心算法 part02  122.买卖股票的最佳时机II // 贪心思路clas

标签:算法  

第九章 动态规划part01  509. 斐波那契数 

标签:算法  

一、题目大意标签: 搜索https://leetcode.cn/problems/permutations给定一个不含重复数字的数组 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]输

标签:排列  LeetCode  Permutations  

相关问题

相关文章

热门文章

推荐文章

相关标签