Leetcode969: 煎饼排序(medium, DFS)-CSDN博客

本文链接：https://blog.csdn.net/chenxy_bwave/article/details/123014543

1. 题目描述

给你一个整数数组 arr ，请使用煎饼翻转完成对数组的排序。一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0...k-1]（下标从 0 开始）
例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

示例 1：
输入：[3,2,4,1]
输出：[4,2,4,3]
解释：我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

示例 2：
输入：[1,2,3]
输出：[]
解释：输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。

提示：

1 <= arr.length <= 100
1 <= arr[i] <= arr.length, arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pancake-sorting

2. 解题分析

第一感是深度优先搜索。但是，这个并不只是判定能否到达目标状态（本题中目标状态即为升序排列的状态），而是要给出翻转序列，即需要给出搜索路径。

每次从所有可能的k值中挑选一个并进行相应的翻转，约束条件是不能连续两次用相同的k值，因为两次连续相同k值的翻转相互抵消了。直到找到一个有效的翻转序列，即k值序列。

题意要求翻转次数在 10 * arr.length 范围内，所以可以将10 * arr.length设置为搜索深度上限。不知道这个条件是不是需要。因为也许可能证明，“对于任意arr.length，一定可以在多少步以内将牌翻转到目标状态”。。。之类的。我有个有趣的猜想，不过页面（脑）容量太小写不下证明^-^。

深度优先搜索的几个要点：（1）栈；（2）已访问状态节点的维护；(3) 邻节点遍历

本题的深度优先搜索处理流程如下(python style psuedo code)：

dfs(card, pathHist):

if card == target:

return True #当前pathHist即为所求路径。在以下实现中用全局变量记录传递。

if len(pathHist) >= 10 * arr.length:

return False #表示搜索失败

for k in range(2,len(card)+1): #遍历邻节点. 1意味着什么都不做不必考虑

如果k与最进一次动作相同，跳过（因为会导致回到之前访问过的状态）

new_card = flip(card,k)

if new_card not in visited:

Add k to pathHist, and add new_card to visited

flag = dfs(new_card,path)

if flag: #表示搜索成功

返回True

从pathHist退出最后加入的k # 容易被漏掉！

3. 代码实现

from typing import List
import time

path    = []
class Solution:    
    def pancakeSort(self, arr: List[int]) -> List[int]:
        def flip(card, k):
            new_card = card.copy()
            for l in range(k//2):
                new_card[l], new_card[k-1-l] = new_card[k-1-l], new_card[l]
            return new_card

        visited = set()
        target  = [m+1 for m in range(len(arr))]
        # print(target)
        
        def dfs(card,pathHist):
            global path
            # print('dfs():', card, pathHist)
            
            if card==target:
                path = pathHist
                return True

            if len(pathHist) == 10*len(arr):
               # print('Fail:', pathHist, len(pathHist))
               return False #表示搜索失败
            
            for k in range(2,1+len(card)): #遍历邻节点, Note: 1 means no flipping!
                if len(pathHist)>0 and k==pathHist[-1]: # Repeat the same k has no meaning
                    continue
                new_card = flip(card,k)
                # print(card, k , new_card)

                if tuple(new_card) not in visited:
                    # Add k to path, and add new_card to visited
                    pathHist.append(k)
                    visited.add(tuple(new_card))
                    flag = dfs(new_card,pathHist)                      
                    if flag:
                        return True
                    pathHist.pop()         
                    
        flag = dfs(arr,[])
        return path

测试运行结果：

很遗憾，在leetcode提交中因超时而失败。以上最后一个testcase耗时长达7秒钟，难怪过不了。而且很明显这个解决方案给出的结果（所需要的次数远远超出了）例子中所给出的答案次数。这样的话看来这个问题更适合于用广度优先搜索来解决？那如何在来判断一个问题是适合于用深度优先搜索还是适合于用广度优先搜索来解决呢？

接下来考虑广度优先搜索的实现方案。