【算法与数据结构】46、47、LeetCode全排列I, II

文章目录

  • 一、46.全排列I
  • 二、47.全排列II
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、46.全排列I

在这里插入图片描述

  思路分析:本题要求是全排列,意味着每次递归的时候startIndex都要从0开始,否则只会得到一个[1 2 3]的组合。从零开始还需要筛选掉重复的组合,引入一个used数组,使用过的元素赋值为1,跳过该循环。因为是全排列,终止条件就是单个组合中元素个数等于nums数组大小。
  程序如下

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) {	// 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]);	// 处理节点	used[i] = true;backtracking(nums, 0, used);	// 递归used[i] = false;path.pop_back();			// 回溯}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), 0);backtracking(nums, 0, used);return result;}
};

复杂度分析:

  • 时间复杂度: O ( n ! ) O(n!) O(n!)
  • 空间复杂度: O ( n ) O(n) O(n)

二、47.全排列II

在这里插入图片描述

  思路分析:在上一题的基础之上本题中的nums元素可以是重复的,因此需要进一步去重,首先题目对全排列组合的顺序没有要求,可以对nums数组进行排序操作。i>0的条件是对nums[i-1]的限制,表示数组的索引不能小于0。nums[i]等于nums[i-1]时就是出现了重复元素,当重复元素首次在nums(排序后的)中出现时(例如[1 1 2]中的第一个1),组合不会有重复的,再次出现时(第二个1),会出现重复组合,此时的used[i-1] = 0。这道题used[i-1]=0或者used[i-1]=1都能够去重,但是used[i-1]=0的去重效率更高
  程序如下

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) {	// 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == 0 || used[i]) continue;path.push_back(nums[i]);	// 处理节点	used[i] = true;backtracking(nums, 0, used);	// 递归used[i] = false;path.pop_back();			// 回溯}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), 0);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};

复杂度分析:

  • 时间复杂度: O ( n ! ∗ n ) O(n!*n) O(n!n)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

// 46全排列I
# include <iostream>
# include <string>
# include <vector>
using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) {	// 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]);	// 处理节点	used[i] = true;backtracking(nums, 0, used);	// 递归used[i] = false;path.pop_back();			// 回溯}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), 0);backtracking(nums, 0, used);return result;}
};int main() {Solution s1;vector<int> nums = { 1, 2, 3 };vector<vector<int>> result = s1.permute(nums);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}
// 47全排列II
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) {	// 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == 0 || used[i]) continue;path.push_back(nums[i]);	// 处理节点	used[i] = true;backtracking(nums, 0, used);	// 递归used[i] = false;path.pop_back();			// 回溯}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), 0);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};int main() {Solution s1;vector<int> nums = { 1, 1, 2 };vector<vector<int>> result = s1.permuteUnique(nums);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}

end

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java排序算法之归并排序

图解 归并排序是一种效率比较高的分治排序算法&#xff0c;主要分为两个步骤&#xff0c;分别为“分”和“并”。 分&#xff1a;将序列不断二分&#xff0c;直到每个子序列只有一个元素为止。 并&#xff1a;将相邻两个子序列进行合并&#xff0c;合并时比较两个子序列的元素…

数字人,虚拟数字人——你看好数字人领域的发展吗?

你看好数字人领域的发展吗&#xff1f; 目录 一、虚拟人、数字人、虚拟数字人基本概念 1.1、虚拟人&#xff08;Virtual Person&#xff09; 1.2、 数字人&#xff08;Digital Human&#xff09; 1.3、虚拟数字人&#xff08;Virtual Digital Human&#xff09; 1.4、侧重…

牛客网:OR36 链表的回文结构

一、题目 函数原型&#xff1a; bool chkPalindrome(ListNode* A) 二、思路 判断一个单链表是否为回文结构&#xff0c;由于单链表不能倒序遍历&#xff0c;所以需要找到单链表的后半段&#xff0c;并将其逆置&#xff0c;再与前半段链表进行比较。 如何找到单链表的后半段呢&a…

Scala---方法与函数

一、Scala方法的定义 有参方法&无参方法 def fun (a: Int , b: Int) : Unit {println(ab) } fun(1,1)def fun1 (a: Int , b: Int) ab println(fun1(1,2)) 注意点&#xff1a; 方法定义语法 用def来定义可以定义传入的参数&#xff0c;要指定传入参数的类型方法可以写返…

CSS的初步学习

CSS 层叠样式表 (Cascading Style Sheets). CSS 能够对网页中元素位置的排版进行像素级精确控制, 实现美化页面的效果. 能够做到页面的样式和结 构分离. CSS 就是 “东方四大邪术” 之化妆术 CSS 基本语法规范: 选择器 若干属性声明 选择器决定针对谁修改 (找谁) 声明决定修…

uniapp 小程序 身份证 和人脸视频拍摄

使用前提&#xff1a; 已经在微信公众平台的用户隐私协议&#xff0c;已经选择配置“摄像头&#xff0c;录像”等权限 开发背景&#xff1a;客户需要使用带有拍摄边框的摄像头 &#xff0c;微信小程序的方法无法支持&#xff0c;使用camera修改 身份证正反面&#xff1a; <…

IDEA 2022创建Spring Boot项目

首先点击New Project 接下来&#xff1a; (1). 我们点击Spring Initializr来创建。 (2). 填写项目名称 (3). 选择路径 (4). 选择JDK------这里笔者选用jdk17。 (5). java选择对应版本即可。 (6). 其余选项如无特殊需求保持默认即可。 然后点击Next。 稍等一会&#xff0c…

[Android]修改应用包名、名称、版本号、Icon以及环境判断和打包

1.修改包名 在Android Studio中更改项目的包名涉及几个步骤&#xff1a; 打开项目结构: 在Android Studio中&#xff0c;确保您处于Android视图模式&#xff08;在左侧面板顶部有一个下拉菜单可以选择&#xff09;。 重命名包名: 在项目视图中&#xff0c;找到您的包名&…

Mac M2/M3 芯片环境配置以及常用软件安装-前端

最近换了台新 Mac&#xff0c;所有的配置和软件就重新安装下&#xff0c;顺便写个文章。 一、环境配置 1. 安装 Homebrew 安装 Homebrew【Mac 安装 Homebrew】 通过国内镜像安装会比较快 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Ho…

msys2 + MSVC(VS2019)编译ffmpeg6.0源码

以前使用的v1.2版&#xff0c;很多功能和使用方法发生了变化&#xff0c;需要重新编译新的ffmpeg版。 编译环境: windows 10 , VS2019, MSYS2 1. msys2 下载安装 MSYS2 , https://www.msys2.org/ 2. msys2 环境配置打开 msys2 2.1 安装相关软件 然后输入以下命令安装&…

技术贴 | SQL 执行 - 执行器优化

本期技术贴主要介绍查询执行引擎的优化。查询执行引擎负责将 SQL 优化器生成的执行计划进行解释&#xff0c;通过任务调度执行从存储引擎里面把数据读取出来&#xff0c;计算出结果集&#xff0c;然后返回给客户。 在关系型数据库发展的早期&#xff0c;受制于计算机 IO 能力的…

【Python】AppUI自动化—appium自动化元素定位、元素事件操作(17)下

文章目录 前言一.Appium 元素定位1.定位方式种类2.如何定位2.1 id定位2.2 className定位2.3 content-desc 定位2.4 Android Uiautomator定位4.1 text定位4.2 text模糊定位4.3 text正则匹配定位4.4 resourceId定位4.5 resourceId正则匹配定位4.6 className定位4.7 className正则…

Centos7下mbr主引导记录演示

linux mbr主引导记录演示 dd if/dev/sda ofmbr.bin bs446 count1 dd if/dev/sda ofmbr.bin bs446 count1hexdump -C mbr.bin[rootlocalhost ~]# cd /boot/grub2 [rootlocalhost grub2]# ls [rootlocalhost grub2]# grub2-editenv list #默认引导内核查看 [rootlocalhost g…

VS项目属性变量

VS项目属性变量 $(SolutionDir) 获取解决方案的路径 $(Platform) 平台名字 → x86 / x64 $(ProjectName) 工程名字 $(Configuration) 当前的项目模式 → Debug / Release

用 Raspberry Pi 5 构建文件服务器(NAS)

系列文章目录 文章目录 系列文章目录前言一、软件设置二、存储器设置三、配置总结 前言 2023 年 11 月 13 日 本-埃弗拉德 这个 #MagPiMonday 周一&#xff0c;学习如何利用 Raspberry Pi 5 的新功能制作更好的 NAS。本教程是 MagPi 推出的 Raspberry Pi 5 特辑的一部分。 M.…

【教3妹学编程-算法题】K 个元素的最大和

3妹&#xff1a;“太阳当空照&#xff0c;花儿对我笑&#xff0c;小鸟说早早早&#xff0c;你为什么背上炸药包” 2哥 :3妹&#xff0c;什么事呀这么开发。 3妹&#xff1a;2哥你看今天的天气多好啊&#xff0c;阳光明媚、万里无云、秋高气爽&#xff0c;适合秋游。 2哥&#x…

深度解析NLP定义、应用与PyTorch实战

1. 概述 文本摘要是自然语言处理&#xff08;NLP&#xff09;的一个重要分支&#xff0c;其核心目的是提取文本中的关键信息&#xff0c;生成简短、凝练的内容摘要。这不仅有助于用户快速获取信息&#xff0c;还能有效地组织和归纳大量的文本数据。 1.1 什么是文本摘要&#x…

多篇论文介绍-DSConv-原文

论文地址 https://arxiv.org/pdf/1901.01928v1.pdf 目录 01 改进 YOLOv5的交通灯实时检测鲁棒算法 01 作用 02 模型介绍 02 基于改进YOLOv7一tiny 算法的输电线路螺栓缺销检测 01 作用 02 模型介绍 03 结合注意力机制的 &#xff39;&#xff2f;&#xff2c;&#xff…

μC/OS-II---互斥信号量管理1(os_mutex.c)

目录 背景&#xff1a;优先级反转问题互斥信号量管理互斥信号量创建互斥信号量删除互斥信号量获取/等待 背景&#xff1a;优先级反转问题 在高优先级任务等待低优先级任务释放资源时&#xff0c;第三个中等优先级任务抢占了低优先级任务。阻塞时间是无法预测的&#xff0c;可能…

dgl 的cuda 版本 环境配置(dgl cuda 版本库无法使用问题解决)

1. 如果你同时有dgl dglcu-XX.XX 那么&#xff0c;应该只会运行dgl &#xff08;DGL的CPU版本&#xff09;&#xff0c;因此&#xff0c;你需要把dgl(CPU)版本给卸载了 但是我只卸载CPU版本还不够&#xff0c;我GPU 版本的dglcu依旧不好使&#xff0c;因此吧GPU版本的也得卸载…