【代码随想录25】491.非递减子序列 46.全排列 47.全排列II

在这里插入图片描述

目录

    • 491.非递减子序列
      • 题目描述
      • 参考代码
    • 46.全排列
      • 题目描述
      • 参考代码
    • 47.全排列II
      • 题目描述
      • 参考代码

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

参考代码

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Set<Integer> set = new HashSet<Integer>();
    int n;

    public List<List<Integer>> findSubsequences(int[] nums) {
        n = nums.length;
        for (int i = 0; i < (1 << n); ++i) {
            findSubsequences(i, nums);
            int hashValue = getHash(263, (int) 1E9 + 7);
            if (check() && !set.contains(hashValue)) {
                ans.add(new ArrayList<Integer>(temp));
                set.add(hashValue);
            }
        }
        return ans;
    }

    public void findSubsequences(int mask, int[] nums) {
        temp.clear();
        for (int i = 0; i < n; ++i) {
            if ((mask & 1) != 0) {
                temp.add(nums[i]);
            }
            mask >>= 1;
        }
    }

    public int getHash(int base, int mod) {
        int hashValue = 0;
        for (int x : temp) {
            hashValue = hashValue * base % mod + (x + 101);
            hashValue %= mod;
        }
        return hashValue;
    }

    public boolean check() {
        for (int i = 1; i < temp.size(); ++i) {
            if (temp.get(i) < temp.get(i - 1)) {
                return false;
            }
        }
        return temp.size() >= 2;
    }
}

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 中的所有整数 互不相同

参考代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

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

参考代码

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/377136.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Netty的常用组件及线程模型设计(一)

Netty常用组件 Bootstrap Bootstrap是Netty框架的启动类和主入口类&#xff0c;发呢为客户端类Bootstrap和服务器类ServerBootstrap两种 Channel Channel是JavaNIO的一个基本构造&#xff0c;它代表一个到实体(如一个硬件设备、一个文件、一个网络套接字或者一个能够执行一…

如何恢复已删除的数据?3个方法,轻松恢复文件!

“我在删除了一些数据后&#xff0c;突然意识到这些数据是很重要的&#xff0c;有什么方法可以帮我恢复这些已删除的数据吗&#xff1f;希望大家给我出出主意&#xff01;” 在日常使用电脑的过程中&#xff0c;用户可能会因为各种原因误删重要的数据&#xff0c;这有时会对我们…

python实现k路归并排序

从归并排序中可以衍生出来一个新的问题&#xff0c;关于k路归并排序&#xff0c;给定k个已经排好序的数组&#xff0c;每个数组含有n各元素&#xff0c;要求将这k个数组合并成一个排好序的大数组。在对两路排好序的数组进行归并时候&#xff0c;会用两个指针指向两个数组首元素…

[超分辨率重建]ESRGAN算法训练自己的数据集过程

一、下载数据集及项目包 1. 数据集 1.1 文件夹框架的介绍&#xff0c;如下图所示&#xff1a;主要有train和val&#xff0c;分别有高清&#xff08;HR&#xff09;和低清&#xff08;LR&#xff09;的图像。 1.2 原图先通过分割尺寸的脚本先将数据集图片处理成两个相同的图像…

NLP_Seq2Seq编码器-解码器架构

文章目录 Seq2Seq架构构建简单Seq2Seq架构1.构建实验语料库和词汇表2.生成Seq2Seq训练数据3. 定义编码器和解码器类4.定义Seq2Seq架构5. 训练Seq2Seq架构6.测试Seq2Seq架构 归纳Seq2Seq编码器-解码器架构小结 Seq2Seq架构 起初&#xff0c;人们尝试使用一个独立的RNN来解决这种…

数据结构——算法的时间复杂度和空间复杂度

1、算法效率 1.1如何衡量一个算法的好坏&#xff1f; 比如我们最熟悉的斐波那契数列 long long Fib(int N) {if(N < 3)return 1;return Fib(N-1) Fib(N-2); } 上面的斐波那契数列使用递归实现&#xff0c;看起来非常的简洁&#xff0c;那么代码一定是越简洁越好么&…

仰暮计划|“​爷爷说这些话的时候眼睛都红着,他那变形的脊柱和瘸拐的双腿都证明他曾为这个家付出了血汗拼尽了全力”

赴一场拾光之旅&#xff0c;集往年回忆碎片 爷爷生于1952年&#xff0c;今年已有七十一了&#xff0c;是河南焦作沁阳北金村的一位地道农民&#xff0c;劳苦一生&#xff0c;如今终于得以颐养天年。许是早年经历过于难忘&#xff0c;爷爷如今与我讲起仍是记忆犹新&#xff0c;…

kafka客户端生产者消费者kafka可视化工具(可生产和消费消息)

点击下载《kafka客户端生产者消费者kafka可视化工具&#xff08;可生产和消费消息&#xff09;》 1. 前言 因在工作中经常有用到kafka做消息的收发&#xff0c;每次调试过程中&#xff0c;经常需要查看接收的消息内容以及人为发送消息&#xff0c;从网上搜寻了一下&#xff0…

航道大数据应用专项研究报告(附下载)

总体目标 充分认识航道大数据对行业治理的重要性和必要性&#xff0c;航道大数据的开发和利用是建设智慧航道的基础。基于大数据的航道管理体系&#xff0c;实现了现有数据的梳理和汇聚&#xff0c;跨部门数据的交换和整合&#xff0c;建立了数据关联和深度学习的模型机制&…

【win】vscode无法使用ctrl+shift+p快捷键的解决方案

本文首发于 ❄️慕雪的寒舍 今天使用vscode的时候遇到的这个问题&#xff0c;明明快捷键设置的是ctrlshiftp&#xff0c;但是在电脑上怎么敲都敲不出来&#xff0c;因为用这个快捷键打开命令面板都习惯了&#xff0c;也不想换&#xff0c;就在找原因。 同时百度的时候还遇到了…

C++ 搜索二叉树的删除

首先查找元素是否在二叉搜索树中&#xff0c;如果不存在&#xff0c;则返回 要删除的结点可能分下面四种情况&#xff1a; a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中…

宠物空气净化器哪个牌子好?养猫家庭如何挑选宠物空气净化器?

养猫的朋友都知道&#xff0c;猫咪掉毛是一个令人头痛的问题。猫毛和皮屑会漂浮在空气中&#xff0c;不仅遍布全屋的各个角落&#xff0c;而且清理起来也非常麻烦&#xff0c;特别是那些难以清除的猫毛。更糟糕的是&#xff0c;这些猫毛还可能引发人们的过敏反应&#xff0c;如…

Excel——分类汇总

1.一级分类汇总 Q&#xff1a;请根据各销售地区统计销售额总数。 第一步&#xff1a;排序&#xff0c;我们需要根据销售地区汇总数据&#xff0c;我们就要对【销售地区】的内容进行排序。点击【销售地区】列中任意一个单元格&#xff0c;选择【数据】——【排序】&#xff0c…

parse库,一个优雅的python库

前言 在Python中&#xff0c;format方法和f-strings是两种常用的字符串插值方法。 name "Haige" age "18" print(f"{name} is {age} years old.")# Haige is 18 years old.而如果是要从字符串中提取期望的值呢&#xff1f;相信很多人的第一或…

代码随想录 Leetcode46. 全排列

题目&#xff1a; 代码&#xff08;首刷自解 2024年2月6日&#xff09;&#xff1a; class Solution { private:vector<vector<int>> res;vector<int> path; public:void backtracking(vector<int>& nums, int depth, vector<bool>& us…

CTF-PWN-堆-【chunk extend/overlapping-2】(hack.lu ctf 2015 bookstore)

文章目录 hack.lu ctf 2015 bookstore检查IDA源码main函数edit_notedelete_notesubmit .fini_array段劫持(回到main函数的方法) 思路格式化字符串是啥呢0x开头或者没有0x开头的十六进制的字符串或字节的转换为整数构造格式化字符串的其他方法 exp 佛系getshell 常规getshell ha…

【maven相关问题】Could not transfer artifact ...与Transfer failed for ...报错及解决办法

一、问题描述 拉取一个新项目后&#xff0c;maven解析下载文件时出现如下报错信息&#xff1a; 二、错误原因分析 提示信息是传输失败&#xff0c;无法传输的原因应该是出现错误的包文件夹已经缓存在本地存储库中&#xff0c;然后maven在经过发布的更新间隔或强制进行更新之前…

深入了解Spring Expression Language(SpEL)

深入了解Spring Expression Language&#xff08;SpEL&#xff09; Spring Expression Language&#xff08;SpEL&#xff09;是Spring框架中强大的表达式语言&#xff0c;它在运行时提供了一种灵活的方式来评估字符串表达式。SpEL的设计目标是在各种Spring配置和编程场景中提供…

Go语言每日一练链表篇(二)

传送门 牛客面试笔试必刷101题 ---------------- 链表内指定区间反转 题目以及解析 题目 解题代码及解析 package main import _"fmt" import . "nc_tools" /** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参…

PyTorch 2.2 中文官方教程(七)

使用 torchtext 库进行文本分类 原文&#xff1a;pytorch.org/tutorials/beginner/text_sentiment_ngrams_tutorial.html 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 注意 点击这里下载完整示例代码 在本教程中&#xff0c;我们将展示如何使用 torchtext 库构建文…