高频面试题LeetCode 31:递归、回溯、八皇后、全排列一篇文章全讲...

来源：TechFlow

作者：梁唐

今天我们讲的是LeetCode的31题，这是一道非常经典的问题，经常会在面试当中遇到。在今天的文章当中除了关于题目的分析和解答之外，我们还会详细解读深度优先搜索和回溯算法，感兴趣的同学不容错过。

题目

Next Permutation

难度

Medium

描述

实现C++当中经典的库函数next permutation，即下一个排列。如果把数组当中的元素看成字典序的话，那下一个排列即是字典序比当前增加1的排列。如果已经是字典序最大的情况，则返回字典序最小的情况，即从头开始。

Implement next permutation , which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be [in-place](http://en.wikipedia.org/wiki/In- place_algorithm) and use only constant  extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

样例

1,2,3 -> 1,3,2
3,2,1 -> 1,2,3
1,1,5 -> 1,5,1

介绍和分析

如果对C++不够熟悉的同学可能不知道next permutation这个库函数，这个库函数可以生成下一个字典序的排列。

举个例子，比如样例当中1 2 3这三个元素，我们把它所有的排列列举出来，一共是6种：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

这6种排列的字典序依次增加，而next permutation呢则是根据当前的排列返回下一个排列。比如我们输入1 2 3，返回1 3 2，我们输入3 1 2，返回3 2 1。而如果我们输入字典序最大的，也就是3 2 1时，则从头开始，返回字典序最小的1 2 3.

暴力

老规矩，我们第一优先级思考最简单的暴力解法。

最简单粗暴的方法是什么，当然是将所有的排列全部列举出来，然后根据字典顺序排序，根据要求筛选，最后返回答案。

说起来很简单，但是实现的话一点都不容易。首先，我们怎么获取所有的排列呢？这个问题最简单的方法是通过递归实现深度优先搜索。我单单这么说，对搜索算法不够熟悉的同学可能理解不了。没关系，我们一步一步来推导。我们先把原问题放一放，来看一道经典的搜索问题：八皇后问题。

八皇后问题

八皇后问题是假设我们有一张8*8的国际象棋的棋盘，我们要在棋盘上放置八个皇后，使得这些皇后之间彼此相安无事。

众所周知，在国际象棋当中皇后比较牛X，可以横竖以及对角线斜着走。也就是说如果将两个皇后放在同行或者同列以及同对角线，那么就会出现皇后之间互相攻击的情况，也就不满足题目要求了。

                            root
                             /
                            1
                           /
                          2
                         /
                        3
                       /
                      4
                     /
                    5
                   / \
                  6   7
                 / \
                7   8
               /     \
              8       7

模板代码

def A():
     do_something()
     B()
     do_something()

def A():
     do_something()
     A()
    do_something()

def dfs():
for choice in all_choices():
        record(choice)
        dfs()
        rollback(choice)

def dfs(depth):
if depth >= 8:
return
for choice in all_choices():
        record(choice)
        dfs(depth+1)
        rollback(choice)

def dfs(n, queens, record):
# 记录答案与控制递归深度
if n >= 8:
# 由于Python当中传递的是引用，所以这里需要copy
# 否则当后面queens pop的时候，会影响record当中记录的值
        record.append(queens.copy())
return

for i in range(8):
# 判断是否同列
if i in queens:
continue
# 判断是否同对角线
        flag = False
for j in range(len(queens)):
if abs(n - j) == abs(i - queens[j]):
                flag = True
break
if flag:
continue
# 递归与回溯
        queens.append(i)
        dfs(n+1, queens, record)
        queens.pop()

def dfs(permutation, array, origin):
"""
    origin记录原排列
    mini  记录答案，即大于原排列的最小排列
    """
# 由于Python引用机制，在函数内部修改，外部不会生效
# 所以需要用全局变量来记录答案
global mini
# 当所有元素都已经放入permutation
if len(array) == 0:
# 判断是否合法，并且是最小的
if permutation > origin and permutation < mini:
# 因为后面permutation会执行pop
# 所以这里需要copy
            mini = permutation.copy()
# 如果还有元素没有放入
for i in array.copy():
        array.remove(i)
        permutation.append(i)
        dfs(permutation, array, origin)
        array.append(i)
        permutation.pop()

贪心

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
        Do not return anything, modify nums in-place instead.
        """
# 长度
        n = len(nums)
# 记录图中i-1的位置
        pos = n - 1
for i in range(n-1, 0, -1):
# 如果降序破坏，说明找到了i
if nums[i] > nums[i-1]:
                pos = i-1
break

for i in range(n-1, pos, -1):
# 从最后开始找大于pos位置的
if nums[i] > nums[pos]:
# 先交换元素，在进行翻转
                nums[i], nums[pos] = nums[pos], nums[i]
# 翻转[pos+1, n]区间
                nums[pos+1:] = nums[n:pos:-1]
return

# 如果没有return，说明是最大的字典序，那么翻转整个数组
        nums.reverse()

推荐阅读

全部文章分类与整理（算法+数据结构+计算机基础），持续更新

【吐血整理】那些让你起飞的计算机基础知识：学什么，怎么学？

普普通通，我的三年大学

写公众号15个月以来，这一路上的学习与收获

历经两个月，我的秋招之路结束了！

2020 第一篇原创 | 我是如何让自己变的更加优秀的？