Leetcoder Day25| 回溯part05:子集+排列

2024-02-28 16:28

本文主要是介绍Leetcoder Day25| 回溯part05:子集+排列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

491.递增子序列

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

示例:

  • 输入:[4, 7, 6, 7]
  • 输出: [[4, 6], [4, 7], [4, 6, 7], [6, 7], [7,7], [4,7,7]]

说明:

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

在子集中我们是通过排序,再加一个标记数组来达到去重的目的。而本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑。本题抽象为树结构过程如下:

从上图可以看到,如果在同一个父节点下,同一树层使用过的元素便不再取,如果所取元素小于子序列最后一个元素,也不符合条件。因此,可以设置一个哈希集合,来记录当前所取的值是否被使用过,哈希集合在递归后不用回溯,因为记录的是同一树层的使用情况,新的循环会清空重新记录。

class Solution {List<List<Integer>> res =new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public void backTracking(int[] nums, int startIdx){if(path.size()>1){res.add(new ArrayList<>(path));}HashSet record= new HashSet<>();for(int i=startIdx;i<nums.length;i++){/*如果path不为空且当前元素小于path最后一个元素,则不取如果元素的值使用过,不取*/if((!path.isEmpty() &&  path.get(path.size()-1)>nums[i]) || record.contains(nums[i])){continue;}record.add(nums[i]);path.add(nums[i]);backTracking(nums, i+1);path.removeLast();}}public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return res;}
}

46.全排列

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

示例:

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

排列问题不需要使用startIdx因为可以存在重复取值的情况,比如第一次1被取过,形成[1,2,3],后面还可以再取组成[2,1,3],但是需要设置一个数组used来记录当前元素在同一path中是否使用过。如果used[i-1]为true,则取下一个元素,因为本题为不重复的元素,所以不用去重。

class Solution {List<List<Integer>> res =new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public void backTracking(int[] nums, boolean[] used){if(path.size()==nums.length){res.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){/* 如果used[i-1]为true,说明同一树枝上使用过值一样的元素如果used[i-1]为false,说明同一树层上使用过值一样的元素*/if(used[i]==true) continue;used[i]=true;path.add(nums[i]);backTracking(nums, used);path.removeLast();used[i]=false;}}public List<List<Integer>> permute(int[] nums) {boolean[] used=new boolean[nums.length];backTracking(nums, used);return res;}
}

📢注意:在调用回溯算法的时候,要记得创建一个used数组。

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]]

本题和上一题的区别在于有重复的数字,所以需要去重,先对数组进行排序,设置used数组记录是否使用过如果used[i-1]为true,说明同一树枝上使用过值一样的元素;如果used[i-1]为false,说明同一树层上使用过值一样的元素。

import java.util.Arrays;
class Solution {List<List<Integer>> res =new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public void backTracking(int[] nums, boolean[] used){if(path.size()==nums.length){res.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){/*当 used[i-1]== used[i]时used[i-1]为true,说明同一树枝使用过若为false,说明同一树层使用过*/if(used[i]==true || (i>0 && nums[i-1]==nums[i] && used[i-1]==false)){continue;}used[i]=true;path.add(nums[i]);backTracking(nums, used);path.removeLast();used[i]=false;}}public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);used=new boolean[nums.length];backTracking(nums, used);return res;}
}

这篇关于Leetcoder Day25| 回溯part05:子集+排列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

代码随想录打卡Day25

今天一整天都在教研室做实验,没时间刷题,就做了一题,剩下的明天补 491.递增子序列 这道题目和之前的子集问题很像,但是有一点要注意的,这个输入的数组不能进行排序,所以就不能沿用之前的去重逻辑,这道题要去重还是得借助额外的变量来维护元素使用情况,但是这题的used为集合,且不能为全局变量,只能为树层遍历前定义的一个局部变量,除了这个改动以外,其他地方都是高度相似的。 class Soluti

风控系统之指标回溯,历史数据重跑

个人博客:无奈何杨(wnhyang) 个人语雀:wnhyang 共享语雀:在线知识共享 Github:wnhyang - Overview 回顾 默认你已经看过之前那篇风控系统指标计算/特征提取分析与实现01,Redis、Zset、模版方法。 其中已经介绍了如何利用redis的zset结构完成指标计算,为了方便这篇文章的介绍,还是在正式开始本篇之前回顾一下。 时间窗口 zset

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序

165-Stamps【回溯】

回溯 给h和k的意思是在k种邮票中选h个邮票 基本的连续邮资问题 15226160 165 Stamps Accepted C++ 0.062 2015-03-27 07:21:37 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2

C++解决:求排列数

描述 输入两个整数m,n,求m个数字中选n个数的排列数。(1<=n<=m<=50) 输入描述 两个正整数m和n。 输出描述 一个正整数表示排列数。 用例输入 1  6 5 用例输出 1  720 AC code #include<bits/stdc++.h>using namespace std;int fun(int n) {int sum=1;for(int i=n

回溯——8.递增子序列

力扣题目链接 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是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]。给定数组中