写点什么

算法题每日一练:全排列

作者:知心宝贝
  • 2023-04-23
    江苏
  • 本文字数:1603 字

    阅读完需:约 5 分钟

算法题每日一练:全排列

一、问题描述

给定一个不含重复数字的数组 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]]
复制代码

考察

1.回溯算法2.建议用时20~35min
复制代码

三、问题分析

本题是开启回溯算法刷题的第4题,之前没有了解过可以看一下这篇题解,讲解比较详细。


算法题每日一练---第85天:组合


这一题和之前刷的组合题目回溯类型是不一样的,组合是不要求顺序,比如[1,2,3]和[2,1,3]是相同的,而对于排列来说确实不同的。所以高中学的排列组合,排列讲究顺序、组合讲究元素


下面我们来讲解一下排列:


第一式:函数初始

我们要初始化一个函数来承载回溯,函数里面的参数如何确定呢?


首先,要传入给定的数组信息,目标值,初始遍历的下标。


    vector<int>t;    int visit[10]={0};//判断元素是否被存储    vector<vector<int>>v;void DFS(int n,vector<int>& nums)//函数初始
复制代码

第二式:终止条件

什么时候结束继续向下开始搜索的条件呢?


题目要求全排列,那当我们数组里面的元素等于 nums.size()不就行了?


if(t.size()==n)//终止条件{    v.push_back(t);    return;}
复制代码

第三式:剪枝优化

这一题不需要剪枝操作。

第四式:递归处理

for(int i=0;i<n;i++)//递归处理{   if(!visit[i])//是否被访问    {       visit[i]=1;//标记为1,存入数组       t.push_back(nums[i]);       DFS(nums.size(),nums);       visit[i]=0;//回溯       t.pop_back();    }}
复制代码


如上面的树形结构,这一题遍历我们需要从头开始遍历,循环的 i 不受数组元素初始下标的影响。


由于数组内的元素只能使用一次,我们要判断这个元素是否被使用过,用 visit[i]记录(为 0 没有使用,为 1 使用过)。


运算过程如下所示:


递归之前 => [1] 递归之前 => [1, 2] 递归之前 => [1, 2, 3] 递归之后 => [1, 2] 递归之后 => [1] 递归之前 => [1, 3] 递归之前 => [1, 3, 2] 递归之后 => [1, 3] 递归之后 => [1] 递归之后 => [] 递归之前 => [2] 递归之前 => [2, 1] 递归之前 => [2, 1, 3] 递归之后 => [2, 1] 递归之后 => [2] 递归之前 => [2, 3] 递归之前 => [2, 3, 1] 递归之后 => [2, 3] 递归之后 => [2] 递归之后 => [] 递归之前 => [3] 递归之前 => [3, 1] 递归之前 => [3, 1, 2] 递归之后 => [3, 1] 递归之后 => [3] 递归之前 => [3, 2] 递归之前 => [3, 2, 1] 递归之后 => [3, 2] 递归之后 => [3] 递归之后 => [] 输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
复制代码


模板


void DFS(变量)//函数初始{    if(条件1||条件2...)//终止条件    {         v.push_back(t);         return;    }    if (条件1||条件2...)//剪枝         return;    for(int i=cur;i<=n;i++)//递归处理    {        //选择当前数字        DFS(向下遍历);        //回退    } }
复制代码


冲冲冲!


四、编码实现

class Solution {public:    vector<int>t;    int visit[10]={0};//判断元素是否被存储    vector<vector<int>>v;    void DFS(int n,vector<int>& nums)//函数初始    {        if(t.size()==n)//终止条件        {            v.push_back(t);            return;        }        for(int i=0;i<n;i++)//递归处理        {            if(!visit[i])//是否被访问            {                visit[i]=1;//标记为1,存入数组                t.push_back(nums[i]);                DFS(nums.size(),nums);                visit[i]=0;//回溯                t.pop_back();            }        }    }    vector<vector<int>> permute(vector<int>& nums) {        DFS(nums.size(),nums);//传入数据        return v;    }};
复制代码

五、测试结果


发布于: 刚刚阅读数: 2
用户头像

知心宝贝

关注

公众号:穿越计算机的迷雾 2022-03-07 加入

生于尘埃 溺于人海 死于理想高台

评论

发布
暂无评论
算法题每日一练:全排列_数据结构_知心宝贝_InfoQ写作社区