当前位置：首页 > news >正文

LeetCode 热题 100_全排列（55_46_中等_C++）(递归（回溯）)

news 来源：原创 2025/6/10 11:52:12

LeetCode 热题 100_两数之和（55_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 中的所有整数 互不相同

题解：

解题思路：

思路一（递归（回溯））：

1、这题需求全排列，这里我们可以想到数学上进行全排列的过程。假设求 [1,2,3] 的全排列。我们首先需在[1,2,3] 中，选取一个元素放在第一个位置，再在剩余两个元素中选取一个元素放在第二个位置，再将剩余的一个元素放在最后一个位置。

例：
⭕代表当前位置选取的元素，[ ]代表可选取元素
在这里插入图片描述
通过递归树可以分析出，每层会确定一个元素的位置，从上到下的一条路径正好是一个排列。（在此过程中我们需要记录哪些元素已被选取）

2、具体思路如下：
① 定义一个 used 用来存储当前元素是否被使用。定义一个 path 来存储从上到下的一条路径（正好是一个排列）。定义一个 ans 来存储所有的路径。
② 递归的每层确定一个元素的位置，且每层会列举所有未使用的元素。（每层挑选一个元素（未使用）存入path中，将使用的元素进行标记)。
③ 当path中元素的个数到达全排列的要求时，则将path存入 ans 中，再进行回溯（回溯时需将相应的元素置为未使用）。

3、复杂度分析
① 时间复杂度：O(n * n!)，其中 n 是数组中的元素数量。其主要是递归调用的次数和将path复制到ans中的时间开销。递归调用消耗n！（全排列的个数），每个全排列答案复制到ans中消耗 n 时间。
② 空间复杂度：O(n)，其中 n 是数组中的元素数量。递归n层（每层确定一个元素的位置）O(n)。path存储从上到下的一条路径（正好是一个排列）O(n)。使用一个used数组存储元素是否被使用O(n)。

代码实现

代码实现（思路一（递归（回溯）））：

class Solution {
private://用于存放一种排列vector<int> path;//用于存放所有全排列vector<vector<int>> res;//运用回溯算法求解全排列问题void backtracking(vector<int>&nums,vector<bool> &used){//递归出口（当path达到一个排列的个数时，也就是到达叶子节点时，记录答案）if(path.size()==nums.size()){res.emplace_back(path);return ;}//在每个位置枚举不用的元素for (int i = 0; i < nums.size(); i++){//如果当前元素已经被使用则跳过此元素if(used[i]==true)continue;//若当前元素还未使用，则将其添加到一个排列中，标记已使用path.emplace_back(nums[i]);used[i]=true;//再重复的添加元素，直到一个排列的个数满足条件backtracking(nums,used);//将当前元素移除切换其他元素，移除后标记为未使用path.pop_back();used[i]=false;}}
public:vector<vector<int>> permute(vector<int>& nums) {//标记元素是否被使用vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution {
private://用于存放一种排列vector<int> path;//用于存放所有全排列vector<vector<int>> res;//运用回溯算法求解全排列问题void backtracking(vector<int>&nums,vector<bool> &used){//递归出口（当path达到一个排列的个数时，也就是到达叶子节点时，记录答案）if(path.size()==nums.size()){res.emplace_back(path);return ;}//在每个位置枚举不用的元素for (int i = 0; i < nums.size(); i++){//如果当前元素已经被使用则跳过此元素if(used[i]==true)continue;//若当前元素还未使用，则将其添加到一个排列中，标记已使用path.emplace_back(nums[i]);used[i]=true;//再重复的添加元素，直到一个排列的个数满足条件backtracking(nums,used);//将当前元素移除切换其他元素，移除后标记为未使用path.pop_back();used[i]=false;}}
public:vector<vector<int>> permute(vector<int>& nums) {//记录元素是否被使用vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};int main(){vector<int> a={1,2,3};//对a中的元素进行全排列Solution s;vector<vector<int>> results=s.permute(a);//输出全排列的结果for (auto &result : results){cout<<"[";for (auto &i : result){cout<<i<<"";}cout<<"]  ";}return 0;
}

LeetCode 热题 100_全排列(55_46)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

LeetCode 热题 100_全排列（55_46_中等_C++）(递归（回溯）)

LeetCode 热题 100_两数之和（55_46） 题目描述：输入输出样例：题解：解题思路：思路一（递归（回溯））： 代码实现代码实现（思路一&#xff08…...

编程日记 2025/6/4 10:17:18

编译chromium笔记

编译环境： windows10 powershell7.2.24 git 2.47.1 https://storage.googleapis.com/chrome-infra/depot_tools.zip 配置git git config --global user.name "John Doe" git config --global user.email "jdoegmail.com" git config --global …...

编程日记 2025/6/1 10:42:15

PHP语言的数据库编程

PHP语言的数据库编程引言随着互联网的发展，动态网站已成为主流，而动态网站的核心就是与数据库进行交互。PHP（超文本预处理器）是一种流行的开源服务器端脚本语言，被广泛用于Web开发。它以其简单易学和功能强大而受到…...

编程日记 2025/6/3 5:05:52

【PGCCC】PostgreSQL 中表级锁的剖析

本博客解释了 PostgreSQL 中的锁定机制，重点关注数据定义语言 (DDL) 操作所需的表级锁定。锁定还是解锁的艺术？ 人们通常将数据库锁与物理锁进行比较，这甚至可能导致您订购有关锁的历史、波斯锁和撬锁技术的书籍。我们大多数人可能都是通过…...

编程日记 2025/5/30 5:04:22

1.10 自洽性（Self-Consistency）：多路径推理的核心力量

自洽性（Self-Consistency）：多路径推理的核心力量随着人工智能尤其是大规模语言模型的不断进化，如何提升其推理能力和决策准确性成为了研究的重点。在这一背景下，**自洽性（Self-Consistency）**作为一种新的推理方法，逐渐展现出其强大的潜力。自洽性方法通过多路径推理…...

编程日记 2025/6/4 16:45:24

【24】Word：小郑-准考证❗

目录题目准考证.docx 邮件合并-指定考生生成准考证 Word.docx 表格内容居中表格整体相较于页面居中考试时一定要做一问保存一问❗ 题目准考证.docx 插入→表格→将文本转换成表格→✔制表符→确定选中第一列→单击右键→在第一列的右侧插入列→布局→合并单元格&#…...

编程日记 2025/6/4 14:44:58

Linux 信号（Signal）详解

信号（Signal）是 Linux 系统中用于进程间通信的一种机制。它是一种异步通知，用于通知进程发生了某个事件。信号可以来自内核、其他进程或进程自身。信号的基本概念信号的作用： 通知进程发生了某个事件（如用户按下 Ct…...

编程日记 2025/5/29 3:32:25

【数据分享】1929-2024年全球站点的逐年最低气温数据（Shp\Excel\免费获取）

气象数据是在各项研究中都经常使用的数据，气象指标包括气温、风速、降水、湿度等指标！说到气象数据，最详细的气象数据是具体到气象监测站点的数据！ 有关气象指标的监测站点数据，之前我们分享过1929-2024年全球气象站点…...

编程日记 2025/5/30 14:15:19

app版本控制java后端接口版本管理

java api version 版本控制 java接口版本管理 1 自定义 AppVersionHandleMapping 自定义AppVersionHandleMapping实现RequestMappingHandlerMapping里面的方法 public class AppVersionHandleMapping extends RequestMappingHandlerMapping {Overrideprotected RequestCondit…...

编程日记 2025/6/2 4:26:20

2024年度总结-CSDN

2024年CSDN年度总结 Author：OnceDay Date：2025年1月21日一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦… 漫漫长路，有人对你微笑过嘛… 文章目录 2024年CSDN年度总结1. 整体回顾2…...

编程日记 2025/6/3 4:56:33

基于python的博客系统设计与实现

摘要：目前，对于信息的获取是十分的重要，我们要做到的不是裹足不前，而是应该主动获取和共享给所有人。博客系统就能够实现信息获取与分享的功能，博主在发表文章后，互联网上的其他用户便可以看到，…...

编程日记 2025/6/3 6:53:55

服务器日志自动上传到阿里云OSS备份

背景公司服务器磁盘空间有限，只能存近15天日志，但是有时需要查看几个月前的日志，需要将服务器日志定时备份到某个地方，需要查询的时候有地方可查。针对这个问题，想到3个解决方法： 1、买一个配置比较低…...

编程日记 2025/6/3 6:56:03

优化使用 Flask 构建视频转 GIF 工具

优化使用 Flask 构建视频转 GIF 工具优化后的项目概述在优化后的版本中，我们将实现以下功能： 可设置每个 GIF 的帧率和大小：用户可以选择 GIF 的帧率和输出大小。改进的用户界面：使用更现代的设计使界面更美观、整洁。自定义…...

编程日记 2025/6/3 16:11:24

leetcode:511. 游戏玩法分析 I

难度：简单 SQL Schema > Pandas Schema > 活动表 Activity： ----------------------- | Column Name | Type | ----------------------- | player_id | int | | device_id | int | | event_date | date | | games_playe…...

编程日记 2025/6/4 9:19:05

windows git bash 使用zsh 并集成 oh my zsh

参考了这篇文章进行配置，记录了自己的踩坑过程，并增加了 zsh-autosuggestions 插件的集成。主要步骤： 1. git bash 这个就不说了，自己去网上下，windows 使用git时候命令行基本都有它。主要也是用它不方便&…...

编程日记 2025/6/4 16:16:26

【Python运维】Python与网络监控：如何编写网络探测与流量分析工具

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！解锁Python编程的无限可能：《奇妙的Python》带你漫游代码世界随着互联网技术的快速发展，网络性能的监控与分析成为保障信息系统稳定运行的关键环节。本文深入探讨了如何利用Python语言构建高效的网络探…...

编程日记 2025/6/3 4:56:06

OpenCV相机标定与3D重建(61)处理未校准的立体图像对函数stereoRectifyUncalibrated()的使用

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述为未校准的立体相机计算一个校正变换。 cv::stereoRectifyUncalibrated 是 OpenCV 库中的一个函数，用于处理未校准的立体图像对。该函…...

编程日记 2025/6/2 10:36:17

字玩FontPlayer开发笔记12 Vue3撤销重做功能

字玩FontPlayer开发笔记12 Vue3撤销重做功能字玩FontPlayer是笔者开源的一款字体设计工具，使用Vue3 ElementUI开发，源代码：github | gitee 笔记撤销重做功能是设计工具必不可少的模块，以前尝试使用成熟的库实现撤销重做功能…...

编程日记 2025/6/2 17:56:59

无人机图传模块：深入理解其工作原理与实际效用

无人机图传模块作为无人机系统的关键组成部分，承担着将无人机拍摄的图像和视频实时传输至地面控制站或接收设备的重任。本文将深入探讨无人机图传模块的工作原理及其在实际应用中的效用，帮助读者更好地理解这一技术的奥秘。一、无人机图传模块的工作原…...

编程日记 2025/6/3 6:54:26

PDF文件提取开源工具调研总结

概述 PDF是一种日常工作中广泛使用的跨平台文档格式，常常包含丰富的内容：包括文本、图表、表格、公式、图像。在现代信息处理工作流中发挥了重要的作用，尤其是RAG项目中，通过将非结构化数据转化为结构化和可访问的信息&#xff0…...

编程日记 2025/6/4 3:54:24

Linux(Centos 7.6)命令详解：dos2unix

1.命令作用将Windows格式文件件转换为Unix、Linux格式的文件(也可以转换成其他格式的) 2.命令语法 Usage: dos2unix [options] [file ...] [-n infile outfile ...] 3.参数详解 options: -c, --convmode，转换方式，支持ascii, 7bit, iso, mac,默认…...

编程日记 2025/6/2 20:55:42

梯度提升决策树树（GBDT）公式推导

### 逻辑回归的损失函数逻辑回归模型用于分类问题，其输出是一个概率值。对于二分类问题，逻辑回归模型的输出可以表示为： \[ P(y 1 | x) \frac{1}{1 e^{-F(x)}} \] 其中 $ F(x) $ 是一个线性组合函数，通常表示为&#xff…...

编程日记 2025/6/3 10:00:12

跨域问题分析及解决方案

1、跨域指的是浏览器不能执行其他网站的脚本。它是由浏览器的同源策略造成的，是浏览器对javascript施加的安全限制。 2、同源策略：是指协议，域名，端口都要相同，其中有一个不同都会产生跨域； 3、跨域流程…...

编程日记 2025/6/3 16:35:22

【三国游戏——贪心、排序】

题目代码 #include <bits/stdc.h> using namespace std; using ll long long; const int N 1e510; int a[N], b[N], c[N]; int w[4][N]; int main() {int n;cin >> n;for(int i 1; i < n; i)cin >> a[i];for(int i 1; i < n; i)cin >> b[i…...

编程日记 2025/6/3 18:51:08

深入理解 Java 的数据类型与运算符

Java学习资料 Java学习资料 Java学习资料在 Java 编程中，数据类型与运算符是构建程序的基础元素。它们决定了数据在程序中的存储方式以及如何对数据进行各种操作。一、数据类型 （一）基本数据类型整型： 用于存储整数数值&…...

编程日记 2025/6/3 4:32:31

WOA-CNN-GRU-Attention、CNN-GRU-Attention、WOA-CNN-GRU、CNN-GRU四模型对比多变量时序预测

WOA-CNN-GRU-Attention、CNN-GRU-Attention、WOA-CNN-GRU、CNN-GRU四模型对比多变量时序预测目录 WOA-CNN-GRU-Attention、CNN-GRU-Attention、WOA-CNN-GRU、CNN-GRU四模型对比多变量时序预测预测效果基本介绍程序设计参考资料预测效果基本介绍基于WOA-CNN-GRU-Attention、…...

编程日记 2025/6/1 4:05:49

（二叉树）

我们今天就开始引进一个新的数据结构了：我们所熟知的：二叉树； 但是我们在引进二叉树之前我们先了解一下树； 树树的概念和结构： 树是⼀种⾮线性的数据结构，它是由 n （ n>0 ） …...

编程日记 2025/6/4 3:55:27

Linux shell 批量验证端口连通性

脚本 #!/bin/bash # #database check #set -o nounset LOCALIPifconfig | grep inet | head -1 | awk {print $2} | sed s/addr\:// IPLIST192.168.1.99 192.168.1.98 192.168.1.97 PORTLIST81 82 83 84 85 86 check_nc(){ for CHECK_IP in $IPLIST dofor CHECK_PORT in $PORT…...

编程日记 2025/6/3 16:55:49