fucking-algorithm

fucking-algorithm copied to clipboard

文章链接点这里：烧饼排序算法

评论礼仪 见这里，违者直接拉黑。

是不是简化版汉诺塔？

是不是简化版汉诺塔？

我看到一半也想起汉诺塔了

done

应该是优先反转有序的部分

js

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var pancakeSort = function (arr) {

    // 在n个中找到最大的 然后铲起它 翻转其上的所有饼 这样他就到了最上面 然后翻转所有饼 这样最大的就到了最下面
    // 在对n-1个饼 进行此过程 直到n==1 返回 已经排好序了 
    // 以上思想很容易想到递归 在每次翻转的时候记录翻转序列中最大的数字

    let res = [];
    mysort(arr.length);
    function mysort(n) {
        let maxCakeIndex = 0, maxCake = 0;
        if (n == 1) return; // 就一个煎饼 不用翻转
        // 找到最大的煎饼 记录下索引
        for (let i = 0; i < n; i++) {
            if (arr[i] > maxCake) {
                maxCake = arr[i];
                maxCakeIndex = i;
            }
        }


        // 翻转 使得最大的煎饼在上面
        myreverse(0, maxCakeIndex);
        res.push(maxCakeIndex + 1);

        // 翻转 使得最大的煎饼到下面
        myreverse(0, n - 1);
        res.push(n);
        // console.log(arr);

        mysort(n - 1); // 
    }
    function myreverse(i, j) {
        while (i < j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    return res;



};

最后那个思考题，是不是可以双向BFS来解，起点终点都有了，要求最短路径。

我看开头就想起了汉诺塔，但是这题用递归有些过于复杂了，用冒泡排序每次把最大值沉底应该会快一些

哈哈哈看到這個題目真的好好笑