论文部分内容阅读
【摘 要】在学习算法刷题过程中,很多人选择leetcode这个平台来进行。本文对leetcode平台第46题全排列[1]进行了详细分析,并对[2]中给出的代码做了优化,最后用一行python代码实现了全排列功能。
【关键词】全排列; leetcode;python
引言
在美国互联网发展的过程中,美国企业面对着招聘需求增长,采用了写题为主的面试方法论。时至今日,像Google、FaceBook、Amazon等公司,依然保留和沿用着以写题为主的面试方法。于是,就有了Leetcode和中文版的Leetcode。
本文对Leetcode第46题全排列[1]进行了详细的分析,并给出了一行python改进解法。
1.Leetcode第46题内容介绍
46题:给定一个没有重复数字的序列,返回其所有可能的全排列。
示例: 输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
1.1题目分析
看完题目,以及给出的示例输入输出,可以发现这就是一个普通的全排列问题,输入一个整型的数组,输出是一个数组,同时数组中的每一个元素就是一个排列。
1.2解题思路
参考文献[3]和[4],“回溯”算法也叫“回溯搜索”算法, “回溯”指的是“状态重置”,可以理解为“回到过去”、“恢复现场”,是在编码的过程中,是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。 “全排列”就是一个非常经典的“回溯”算法的应用。我们知道,N 个数字的全排列一共有 N! 这么多个。
“全排列”问题的树形结构如下所示:
使用编程的方法得到全排列,就是在这样的一个树形结构中进行编程,具体来说,就是执行一次深度优先遍历,从树的根结点到叶子结点形成的路 就是一个全排列。
2.编码步骤:
(1)首先这棵树除了根结点和叶子结点以外,每一个结点做的事情其实是一样的,即在已经选了一些数的前提,我们需要在剩下还没有选择的数中按照顺序依次选择一个数;
(2)递归的终止条件是,数已经选够了,因此我们需要一个变量来表示当前递归到第几层,我们把这个变量叫做 depth;
(3)这些结点实际上表示了搜索(查找)全排列问题的不同阶段,为了区分这些不同阶段,我们就需要一些变量来记录为了得到一个全排列,程序进行到哪一步了,在这里我们需要两个变量:
(4)在非叶子结点处,产生不同的分支,这一操作的语义是:在还未选择的数中依次选择一个元素作为下一个位置的元素,这显然得通过一个循环实现。
3.代码的编写
由于编写代码采用的python语言,可以充分利用python的精简的风格和特殊的语法糖,直接给出一行python代码如下:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return [ p[:i] + [nums[0]] + p[i:]
for i in range(len(nums))
for p in self.permute(nums[1:])
] or [[]]
該代码对文献[2]中的代码进行了简化,是本文的一个精简的改进。
由于是Leetcode中提交的形式,所以这个代码在普通的环境中是无法执行的。
4.小结
本文用一行python代码实现了leetcode46题全排列,并且对文献[2]的代码进行了精简的改进。
参考文献
[1] https://leetcode-cn.com/problems/permutations/
[2] https://leetcode.com/problems/permutations/discuss/18241/One-Liners-in-Python
[3] 胡松涛。 图解LeetCode初级算法(Python版). 北京:清华大学出版社,2020.
[4]https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
【关键词】全排列; leetcode;python
引言
在美国互联网发展的过程中,美国企业面对着招聘需求增长,采用了写题为主的面试方法论。时至今日,像Google、FaceBook、Amazon等公司,依然保留和沿用着以写题为主的面试方法。于是,就有了Leetcode和中文版的Leetcode。
本文对Leetcode第46题全排列[1]进行了详细的分析,并给出了一行python改进解法。
1.Leetcode第46题内容介绍
46题:给定一个没有重复数字的序列,返回其所有可能的全排列。
示例: 输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
1.1题目分析
看完题目,以及给出的示例输入输出,可以发现这就是一个普通的全排列问题,输入一个整型的数组,输出是一个数组,同时数组中的每一个元素就是一个排列。
1.2解题思路
参考文献[3]和[4],“回溯”算法也叫“回溯搜索”算法, “回溯”指的是“状态重置”,可以理解为“回到过去”、“恢复现场”,是在编码的过程中,是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。 “全排列”就是一个非常经典的“回溯”算法的应用。我们知道,N 个数字的全排列一共有 N! 这么多个。
“全排列”问题的树形结构如下所示:
使用编程的方法得到全排列,就是在这样的一个树形结构中进行编程,具体来说,就是执行一次深度优先遍历,从树的根结点到叶子结点形成的路 就是一个全排列。
2.编码步骤:
(1)首先这棵树除了根结点和叶子结点以外,每一个结点做的事情其实是一样的,即在已经选了一些数的前提,我们需要在剩下还没有选择的数中按照顺序依次选择一个数;
(2)递归的终止条件是,数已经选够了,因此我们需要一个变量来表示当前递归到第几层,我们把这个变量叫做 depth;
(3)这些结点实际上表示了搜索(查找)全排列问题的不同阶段,为了区分这些不同阶段,我们就需要一些变量来记录为了得到一个全排列,程序进行到哪一步了,在这里我们需要两个变量:
(4)在非叶子结点处,产生不同的分支,这一操作的语义是:在还未选择的数中依次选择一个元素作为下一个位置的元素,这显然得通过一个循环实现。
3.代码的编写
由于编写代码采用的python语言,可以充分利用python的精简的风格和特殊的语法糖,直接给出一行python代码如下:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return [ p[:i] + [nums[0]] + p[i:]
for i in range(len(nums))
for p in self.permute(nums[1:])
] or [[]]
該代码对文献[2]中的代码进行了简化,是本文的一个精简的改进。
由于是Leetcode中提交的形式,所以这个代码在普通的环境中是无法执行的。
4.小结
本文用一行python代码实现了leetcode46题全排列,并且对文献[2]的代码进行了精简的改进。
参考文献
[1] https://leetcode-cn.com/problems/permutations/
[2] https://leetcode.com/problems/permutations/discuss/18241/One-Liners-in-Python
[3] 胡松涛。 图解LeetCode初级算法(Python版). 北京:清华大学出版社,2020.
[4]https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/