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).确定回溯函数参数
- path来收集符合条件的结果
- result 保存 path,作为结果集
- used 排列问题需要标记已经选择的元素,和用来记录同一树枝上的元素是否使用过
注意:{1,2} 和 {2,1} 是不同的排序组合,因为排序不同;但 {1,2} 和 {2,1} 是相同的组合,因为元素相同。所以处理组合问题需要 startIndex,处理排列问题就不用使用 startIndex 了
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums,vector<bool>& used)
2).递归的终止条件
- 收割叶子节点
if(path.size() == nums.size()) {result.push_back(path);return;
}
3).单层搜索的逻辑
- used 是用来标记取过了哪些元素
- used 是bool型数组,用来记录同一树枝上的元素是否使用过(与leetCode 46.全排列的区别,因为
nums 是可包含重复数字的序列,used有去重作用)
if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
if(used[i]==true) continue;
C++代码:
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,vector<bool>& used) {if(path.size() == nums.size()) {result.push_back(path);return;}for(int i=0;i<nums.size();i++) {if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue; if(used[i]==true) continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,used);used[i]=false;path.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};
- 时间复杂度: O(n! * n)
- 空间复杂度: O(n)
>>与前期文章的区别:
1.leetCode 77.组合问题 、leetCode 131.切割问题、leetCode 78.子集问题需要用startIndex,
- startIndex 来控制for循环的起始位置
- used 是bool型数组,用来记录同一树枝上的元素是否使用过
2.本题
- 每层都是从0开始搜索,并不是startIndex
- used 是用来标记取过了哪些元素
- used 是bool型数组,用来记录同一树枝上的元素是否使用过(与leetCode 46.全排列的区别)
我的往期文章:
leetCode 46. 全排列 + 回溯算法 + 图解 + 笔记-CSDN博客
https://blog.csdn.net/weixin_41987016/article/details/134753366?spm=1001.2014.3001.5501推荐和参考文章、视频:
代码随想录 (programmercarl.com)
https://www.programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1R84y1i7Tm/?spm_id_from=333.788&vd_source=a934d7fc6f47698a29dac90a922ba5a3
相关文章:
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…...
Maya 2024(3D建模、动画和渲染软件)
Maya 2024是一款非常强大的3D建模、动画和渲染软件,它提供了许多新功能和改进,以帮助建模师、动画师和渲染师更加高效地进行创作。 在建模方面,Maya 2024引入了Symmetry(对称)功能,可以在网格两侧生成均匀…...
C++作业5
完成沙发床的多继承(有指针成员) 代码: #include <iostream>using namespace std;class Bed { private:double *money; public:Bed(){cout << "Bed::无参构造函数" << endl;}Bed(double money):money(new doub…...
Go语言很难吗?为什么 Go 岗位这么少?
其实这个话题已经躺在我的 TODO 里很久了,近来很多社区的小伙伴都私下来交流,也有在朋友圈看吐槽 Go 上海的大会没什么人。还不如 Rust 大会,比较尴尬。 今天主要是从个人角度看看为什么 Go 岗位看起来近来很难的样子? 盘一下数…...
为什么要替换 Object.defineProperty?
目录 前言:为什么要替换 Object.defineProperty? 详解:为什么要替换 Object.defineProperty? 总结: 前言:为什么要替换 Object.defineProperty? JavaScript中的Object.defineProperty是一种…...
百马百担c语言编程
以下是一个百马百担问题的C语言编程实现: #include <stdio.h>int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); int a[n], b[m], c[k]; for (int i 0; i < n; i) { scanf("%d", &a[i]);…...
C++检测字符串中有效的括号个数
匹配一个字符串buf中,连续包换运算符reg的次数: #include <iostream>//return 返回匹配的字符个数 //buf, 要检测的字符串 //reg, 包含的连续运算符 int GetMatchCount(std::string& buf, std::string& reg) {int nMatchCount 0;if (reg.…...
前端依赖下载速度过慢解决方法,nrm 镜像管理工具
npm 默认镜像 :https://registry.npmjs.org/ 问题 使用 npm install 安装依赖的时候,受网络的限制,速度会很慢。 解决 使用国内镜像代理。 nrm nrm 是镜像源管理工具; 1. 安装 nrm npm install nrm --global# 查看镜像源列…...
如何为 3D 模型制作纹理的最佳方法
在线工具推荐: 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 您可以通过不同的方式为 3D 模型创建 3D 纹理。下面我们将介绍为 3D …...
智慧校园:TSINGSEE青犀智能视频监控系统,AI助力优化校园管理
随着科技的飞速发展和信息化社会的到来,智慧校园已经成为教育领域的一种新型发展模式。智慧校园的需求和发展趋势日益显现,其建设已成为当今教育信息化发展的重要方向。 TSINGSEE青犀结合高可靠、高性能的云计算、人工智能、大数据、物联网等技术&#…...
Three的lod技术
1、资源:https://sbcode.net/threejs/lod/ import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls import Stats from three/examples/jsm/libs/stats.module import { GUI } from dat.gui import { GLTFLoader }…...
Git配置
个人主页:Lei宝啊 愿所有美好如期而遇 前言 前面我们新建了远程仓库并且在Linux上克隆了远程仓库,但是在新建仓库时我们提到会配置gitignore文件,这次我们将会配置他,并给命令起别名。 目录 前言 忽略特殊文件 给命令起别名…...
阻抗控制下机器人接触刚性环境振荡不稳定进行阻抗调节
阻抗接触 刚性环境为ke10000 虚拟阻抗为:kd100,bd10,md1 虚拟阻抗为:kd100,bd10,md5 虚拟阻抗为:kd100,bd10,md10 性能滤波函数的Bode图: bode(1e5/(0.000…...
【鸿蒙应用ArkTS开发系列】-自定义底部菜单列表弹窗
文章目录 前言创建Demo工程创建dialog 文件夹创建ListMenu 接口创建自定义弹窗 ListMenuDialog使用自定义弹窗 打包测试效果演示默认效果菜单带图标效果设置文本颜色效果不同文本颜色效果无标题效果 前言 上一篇文章中我们实现了选择图片、选择文件、拍照的功能 。 链接在这里…...
yolov8添加ca注意力机制
创建文件 coordAtt.py 位置:ultralytics/nn/modules/coordAtt.py ###################### CoordAtt #### start by AI&CV ############################### # https://zhuanlan.zhihu.com/p/655475515 import torch import torch.nn as nn import t…...
linux java后台启动的几种方式
1.使用 nohup 命令 可以使用 nohup 命令启动 Java 应用程序,使其在后台运行,这样即使退出终端或关闭 SSH 连接,Java 应用程序也能继续运行。nohup java -jar myapp.jar &2.使用 & 符号 使用 & 符号可以将 Java 应用程序放到后台…...
selinux-policy-default(2:2.20231119-2)软件包内容详细介绍(5)
接前一篇文章:selinux-policy-default(2:2.20231119-2)软件包内容详细介绍(4) 4. 重点文件内容解析 (1)control/postist文件 上一回解析了control/postinst文件的部分内容,本回继续往下解析。为了便于理解,再次贴出postinst完整代码: #!/bin/sh set -e# summary o…...
代码随想录二刷 |栈与队列 |理论基础
代码随想录二刷 |栈与队列 |理论基础 栈常用操作 队列常用操作 栈与队列是C标准库中的两个数据结构。 栈 栈先进后出,提供 push 和 pop 等接口,所有元素必须符合先进后出的原则,所以栈不提供走访功能,也不…...
java--接口概述
1.认识接口 ①java提供了一个关键字interface,用这个关键字我们可以定义出一个特殊的结构:接口。 ②注意:接口不能创建对象;接口是用来被类实现(implements)的,实现接口的类称为实现类。 ③一个类可以实现多个接口(接…...
出海风潮:中国母婴品牌征服国际市场的机遇与挑战!
近年来,中国母婴品牌在国内市场蓬勃发展的同时,也逐渐将目光投向国际市场。这一趋势不仅受益于中国经济的崛起,还得益于全球市场对高质量母婴产品的不断需求。然而,面对国际市场的机遇,中国母婴品牌同样面临着一系列挑…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...
