DAY29| 491.递增子序列 ,46.全排列 ,47.全排列II

2024-04-18 08:28
文章标签 ii 递增 序列 47 排列 46 491 day29

本文主要是介绍DAY29| 491.递增子序列 ,46.全排列 ,47.全排列II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 491.递增子序列
    • 46.全排列
    • 47.全排列II

491.递增子序列

文字讲解:递增子序列

视频讲解:递增子序列

**状态:这题看了文字讲解才AC,掌握了如何在回溯里通过Set集合来对同层节点去重

思路:

代码:

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}//本题的关键在于,同层不能有重复元素,当前层的节点不能大于上一层的值public void backTracking(int[] nums, int startIndex) {if (startIndex>=nums.length) {return;}//借助set集合去重HashSet hs = new HashSet();for (int i = startIndex; i < nums.length; i++) {if ((!tempList.isEmpty() && tempList.get(tempList.size()-1) > nums[i]) || hs.contains(nums[i])) {continue;}hs.add(nums[i]);tempList.offer(nums[i]);if (tempList.size()>1) {result.add(new ArrayList<>(tempList));}backTracking(nums, i+1);tempList.pollLast();}}
}

46.全排列

文字讲解:全排列

视频讲解:全排列

状态:做完组合类的题,这题好简单

思路:

代码:

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();boolean[] usedArr;public List<List<Integer>> permute(int[] nums) {this.usedArr = new boolean[nums.length];for (int i = 0; i < this.usedArr.length; i++) {this.usedArr[i] = false;}backTracking(nums);return result;}public void backTracking(int[] nums) {if (tempList.size()==nums.length) {//收集result.add(new ArrayList<>(tempList));return;}for (int i = 0; i < nums.length; i++) {if (usedArr[i]) {continue;}usedArr[i]=true;tempList.offer(nums[i]);backTracking(nums);tempList.pollLast();usedArr[i]=false;}}
}

47.全排列II

文字讲解:全排列II

视频讲解:全排列

状态:将前两题的思路整合,这题ok

思路:

代码:

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);this.used = new boolean[nums.length];for (int i = 0; i < used.length; i++) {used[i] = false;}backTracking(nums);return result;}public void backTracking(int[] nums) {if (tempList.size()==nums.length) {result.add(new ArrayList<>(tempList));return;}HashSet<Integer> hs = new HashSet();for (int i = 0; i < nums.length; i++) {if (used[i] || hs.contains(nums[i])) {continue;}hs.add(nums[i]);used[i] = true;tempList.offer(nums[i]);backTracking(nums);tempList.pollLast();used[i] = false;}}
}

这篇关于DAY29| 491.递增子序列 ,46.全排列 ,47.全排列II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

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

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

回溯——9.全排列

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