关于算法:烧饼排序

34次阅读

共计 1800 个字符,预计需要花费 5 分钟才能阅读完成。

读完本文,你能够去力扣拿下如下题目:

969. 煎饼排序

———–

烧饼排序是个很有意思的理论问题:假如盘子上有 n 面积大小不一 的烧饼,你如何用一把锅铲进行若干次翻转,让这些烧饼的大小有序(小的在上,大的在下)?

构想一下用锅铲翻转一堆烧饼的情景,其实是有一点限度的,咱们每次只能将最下面的若干块饼子翻转:

咱们的问题是,如何应用算法失去一个翻转序列,使得烧饼堆变得有序

首先,须要把这个问题形象,用数组来示意烧饼堆:

如何解决这个问题呢?其实相似上篇文章 递归反转链表的一部分,这也是须要 递归思维 的。

一、思路剖析

为什么说这个问题有递归性质呢?比如说咱们须要实现这样一个函数:

// cakes 是一堆烧饼,函数会将前 n 个烧饼排序
void sort(int[] cakes, int n);

如果咱们找到了前 n 个烧饼中最大的那个,而后设法将这个饼子翻转到最底下:

那么,原问题的规模就能够减小,递归调用 pancakeSort(A, n-1) 即可:

接下来,对于下面的这 n - 1 块饼,如何排序呢?还是先从中找到最大的一块饼,而后把这块饼放到底下,再递归调用 pancakeSort(A, n-1-1)……

你看,这就是递归性质,总结一下思路就是:

1、找到 n 个饼中最大的那个。

2、把这个最大的饼移到最底下。

3、递归调用 pancakeSort(A, n - 1)

base case:n == 1 时,排序 1 个饼时不须要翻转。

那么,最初剩下个问题,如何设法将某块烧饼翻到最初呢

其实很简略,比方第 3 块饼是最大的,咱们想把它换到最初,也就是换到第 n 块。能够这样操作:

1、用锅铲将前 3 块饼翻转一下,这样最大的饼就翻到了最下面。

2、用锅铲将前 n 块饼全副翻转,这样最大的饼就翻到了第 n 块,也就是最初一块。

以上两个流程了解之后,根本就能够写出解法了,不过题目要求咱们写出具体的反转操作序列,这也很简略,只有在每次翻转烧饼时记录下来就行了。

二、代码实现

只有把上述的思路用代码实现即可,惟一须要留神的是,数组索引从 0 开始,而咱们要返回的后果是从 1 开始算的。

// 记录反转操作序列
LinkedList<Integer> res = new LinkedList<>();

List<Integer> pancakeSort(int[] cakes) {sort(cakes, cakes.length);
    return res;
}

void sort(int[] cakes, int n) {
    // base case
    if (n == 1) return;
    
    // 寻找最大饼的索引
    int maxCake = 0;
    int maxCakeIndex = 0;
    for (int i = 0; i < n; i++)
        if (cakes[i] > maxCake) {
            maxCakeIndex = i;
            maxCake = cakes[i];
        }
    
    // 第一次翻转,将最大饼翻到最下面
    reverse(cakes, 0, maxCakeIndex);
    res.add(maxCakeIndex + 1);
    // 第二次翻转,将最大饼翻到最上面
    reverse(cakes, 0, n - 1);
    res.add(n);

    // 递归调用
    sort(cakes, n - 1);
}

void reverse(int[] arr, int i, int j) {while (i < j) {int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++; j--;
    }
}

通过方才的具体解释,这段代码应该是很清晰了。

算法的工夫复杂度很容易计算,因为递归调用的次数是 n,每次递归调用都须要一次 for 循环,工夫复杂度是 O(n),所以总的复杂度是 O(n^2)。

最初,咱们能够思考一个问题​:依照咱们这个思路,得出的操作序列长度应该为​ 2(n - 1),因为每次递归都要进行 2 次翻转并记录操作,总共有 n 层递归,但因为 base case 间接返回后果,不进行翻转,所以最终的操作序列长度应该是固定的 2(n - 1)

显然,这个后果不是最优的(最短的),比如说一堆煎饼 [3,2,4,1],咱们的算法失去的翻转序列是 [3,4,2,3,1,2],然而最快捷的翻转办法应该是 [2,3,4]

初始状态:[3,2,4,1]
翻前 2 个:[2,3,4,1]
翻前 3 个:[4,3,2,1]
翻前 4 个:[1,2,3,4]

如果要求你的算法计算排序烧饼的 最短 操作序列,你该如何计算呢?或者说,解决这种求最优解法的问题,外围思路什么,肯定须要应用什么算法技巧呢?

无妨分享一下你的思考。

正文完
 0