首页 > 其他分享 >46.permutations 全排列

46.permutations 全排列

时间:2022-09-21 18:58:25浏览次数:79  
标签:vector 排列 nums 46 permutations back int used path

问题链接:46.permutations
依旧是用回溯法,与组合问题形成对比,组合问题每次只需要选i之后的数;排列则每次需要从0开始,但是不能重复,利用used[6] = {0}这个used数组来记录数是否已经进入path,进入了path就将used[i] = 1,回溯时used[i] = 0

#include <vector>
using std::vector;
class Solution {
  private:
    vector<int> path;
    vector<vector<int>> res;
    void track_back(vector<int> &nums, int index, int *used) {
        if (path.size() >= nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == 1)
                continue;
            used[i] = 1;
            path.push_back(nums[i]);
            track_back(nums, i + 1, used);
            path.pop_back();
            used[i] = 0;
        }
        return;
    }

  public:
    vector<vector<int>> permute(vector<int> &nums) {
        int used[6] = {0};
        track_back(nums, 0, used);
        return res;
    }
};

或者

class Solution {
  private:
    vector<int> path;
    vector<vector<int>> res;
    int used[6] = {0};
    void track_back(vector<int> &nums) {
        if (path.size() >= nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == 1)
                continue;
            used[i] = 1;
            path.push_back(nums[i]);
            track_back(nums);
            path.pop_back();
            used[i] = 0;
        }
        return;
    }

  public:
    vector<vector<int>> permute(vector<int> &nums) {
        int used[6] = {0};
        track_back(nums);
        return res;
    }
};

标签:vector,排列,nums,46,permutations,back,int,used,path
From: https://www.cnblogs.com/zwyyy456/p/16716769.html

相关文章

  • 46. Room
    46.Room46.1Room三角色介绍→→Room是SQLite数据库的抽象流畅易用的访问数据库。Entity:StudentDAO:DAODB:StudentDatabase注解46.2Room三角色编写引入依赖implem......
  • 排列&组合
    排列:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e3+5;#defineswap(a,b){inttemp=a;a=b;b=temp;}intdata[maxn];voidso(){   for(......
  • python3--重新排列单词间的空格
    class Solution:    def reorderSpaces(self, text: str) -> str:        count=text.count(' ')#字符串中空格的数量        li=text.s......
  • AcWing 4604. 集合询问
    https://www.acwing.com/problem/content/4607/哈希表题意:初始时空集{},进行t次操作,操作分为:+x,将一个非负整数x添加至集合中。注意,集合中可以存在多个相同的整......
  • 1592. 重新排列单词间的空格
    1592.重新排列单词间的空格给你一个字符串text,该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成,并且两个单词之间至少存在一个空格。......
  • Ubuntu Jenkins升级2.346.3后远程调用403解决方案(HTTP ERROR 403 No valid crumb was
       一般通过api调用Jenkinsjob出现403(HTTPERROR403Novalidcrumbwasincludedintherequest)报错,是因为新版本Jenkins为了安全,搞的一套crsf认证机制,具体的自......
  • 题解【P2466 [SDOI2008] Sue 的小球】
    题目传送门。一眼丁真,鉴定为原题。现将所有点按照\(x\)排序,区间\([l,r]\)的终点一定是\(l\)或\(r\),否则会跑冤枉路。设\(f_{i,j,0/1}\)表示在区间\([i,j]\)......
  • 46 | JAVA_IO_使用Files
    使用Files虽然Files是java.nio包里面的类,但他俩封装了很多读写文件的简单方法,例如,我们要把一个文件的全部内容读取为一个byte[],可以这么写:byte[]data=Files.readAllBy......
  • LeetCode 46 全排列
    classSolution{public:vector<vector<int>>res;vector<int>path;boolused[10];voiddfs(vector<int>&nums){if(path.size()==nu......
  • P3223 (排列组合)
     题目传送门题目大意:略题目分析:本题类似于当小球遇上盒子。[\(1\)]:我们可以假设所有老师均为男生,利用插板法,我们可知两个女生可以放入一个男生两侧,又因为每个人......