专栏首页小浩算法小白真能看一篇文章就学会全排列算法吗?

小白真能看一篇文章就学会全排列算法吗?

今天是小浩算法 “365刷题计划” 第97天 。为大家分享如何用算法来求全排列!话不多说,直接看题!

01

PART

全排列是啥

什么是全排列?从 n 个不同元素中任取 m(m≤n)个元素,按照一定的顺序排列起来,叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m=n 时所有的排列情况叫全排列。

比如 [1,2,3] 全排列共有 6 种:

02

PART

全排列题目

然后把上面的全排列稍微改改,就变成了一道算法题。。。

全排列问题:给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

03

PART

题解分析

这种由基础数学知识改编而成的题目,在面试时还是很受欢迎的。因为作为面试官,可以用这种题目,来显示自己的博学。(谬论)

假如我们不是做算法题,而是做数学题。我们会一个位置一个位置的来考虑,先写出以1开头的排列,再写出以2开头的排列,最后写出以3开头的排列。

这种思路是不是很像深度优先(DFS)的求解过程呢?


1、我们先选择 1,然后为 1 的第二位选择 2,此时 1 的 第三位只能选择 3。

2、然后完成了上面的步骤,我们需要回退到 1,因为只有 1 这里还存在别的选择 1-3,然后填写 1-3 后,只有 1-3-2 一种选择。

3、此时我们需要从 1-3-2,回退到 1-3,再回退到 1,再回退到 根节点,然后重新选择 2。

4、后面的流程相似,我就不一步步的描述了。

当然,如果不省略其回溯过程,就是下面这个样子:


上面分析是分析完了,但是仍然不妨碍你继续懵逼。。。“题目中不是给我的是一个数组吗?作为一个合格的算法小白,我特么根本就不知道 DFS 在这里面咋用啊!!”本来想扔完代码就走,想了想还是决定讲一下。

我们把代码先丢出来(注意,这个代码不是最优的,这样写只是易于大家理解。比如我们还可以通过置换的方式来进行优化,又或者其他的优化方法。但是都大同小异,核心是回溯的过程):

 1//JAVA
 2class Solution {
 3    List<List<Integer>> ans = new ArrayList<>();
 4
 5    public List<List<Integer>> permute(int[] nums) {
 6        dfs(nums, new ArrayList<>());
 7        return ans;
 8    }
 9
10    private void dfs(int[] nums, List<Integer> tmp) {
11        System.out.println(Arrays.toString(nums) + "," + tmp);
12        if (tmp.size() == nums.length) {
13            ans.add(new ArrayList<>(tmp));
14        } else {
15            for (int num : nums) {
16                if (!tmp.contains(num)) {
17                    tmp.add(num);
18                    dfs(nums, tmp);
19                    tmp.remove(tmp.size() - 1);
20                }
21            }
22        }
23    }
24
25}

假若 nums 为 [1,2,3],会有下面的输出:

其实这个代码还是很容易理解的,他干了个啥事?就是当我们按顺序去枚举每一位时,我们要把已经选择过的数字排除掉(第16行代码),比如我们上面选择三个数字:

  • 在枚举第一位的时候,就有三种情况
  • 在枚举第二位的时候,就只有两种情况(前面已经出现的一个数字不可以再出现)
  • 在枚举第三位的时候,就只有一种情况(前面已经出现的两个数字不可以再出现)

整个代码其实就干了这么一件事!而 第12行 的代码,其实就是说当枚举到最后一位的时候,这个就是我们要的排列结果,所以我们要放入到全排列结果集中。

那这里还有一个很重要的代码,其实是 第19行,这一步其实是干啥!说白了就是在回到上一位时,我们要就把上一次的选择结果撤销掉。不然如果你之前选过了,后面不就不能继续用了么。

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

04

PART

啰嗦一下

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

这是最简单的一道全排列题目,注意我在上面的题解中,并没有引入什么状态、路径、选择列表、结束条件之类的专业术语,甚至我连回溯的概念都没有提及。

之所以这样讲,我是希望咱可以从最简单的人类思考出发,而不是去套用一些框架之类的东东。。。。当然,至于更多的概念和回溯框架的东西,我会在后面更为复杂的题目中为大家引入。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • 漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

    今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ(进阶版)。话不多说,直接看题:

    程序员小浩
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • 如果未来手机变成隐形眼镜,人类会不会虚拟现实不分?

    很多人都有自己坚持每天做的事情,可能是每天晨跑,可能是每天写日记,可能是每天写代码,而我,决定每天在知乎提一个脑洞很大的问题。

    挖数
  • 2018-07-19 如何重构“箭头型”代码如何重构“箭头型”代码

    原文地址:https://coolshell.cn/articles/17757.html

    Albert陈凯
  • 美国失业人数突破2200万!这个动态图我用Python画出来了

    【导语】:今天我们聊聊美国失业人数,Python技术部分可以直接看第二部分。公众号后台,回复关键字“失业人数”获取完整数据。

    CDA数据分析师
  • 3分钟找书指南

    iOSDevLog
  • AI技术三大应用领域:智能医疗、自动驾驶、智慧营销产业发展现状分析

    “So tomorrow, if AI can shape healthcare, it has to work through the regulations...

    SIGAI学习与实践平台
  • 「R」t 检验

    你想要检验来自两个总体的样本是否有不同的均值(显著性差异),或者检验从一个总体抽取的样本均值和理论均值有显著性差异。

    王诗翔呀
  • 三层架构之我见 —— 不同于您见过的三层架构。

           我从02年开始了编程的工作,开始接触一些简单的网站,下半年写了个小的自助建站程序(asp和asp.net),比较简陋没有使用。03年开始正式做网站...

    用户1174620

扫码关注云+社区

领取腾讯云代金券