记录一些经典算法

[akeymo]

记录日常看文章时遇到的经典算法。

洗牌算法

将一组有序的数组随机打乱。

思路： 从末位开始（也可以从首位），从还未排序的数字中随机取一个数（也可以取到自身），与当前数交换位置，依次排序直到剩最后一位。

function shuffle(array) {
    let m = array.length;
    let i, t;

    while (m) {
        // 随机取一个交换的数，也可以是本身
        i = Math.floor(Math.random() * m--);

        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }

    return array;
}

[akeymo]

数组拍平

使用递归思想解

let a = [1, 2, 3, [1, 3, [1, 2]], [1, 5]]

function flat(a = []) {
    let result = [];
    a.forEach((item) => {
        if (Array.isArray(item)) {
            result = result.concat(flat(item, []));
        } else {
            result.push(item);
        }
    })

    return result; // [1, 2, 3, 1, 3, 1, 2, 1, 5]
}

除了递归方法外，还有一个骚操作就是先利用toString()方法将数组转为字符串，然后利用split(',')重新转为数组，最后用map()将字符串转为数字。

function flat(arr) {
    const result = arr.toString().split(',').map(item=>+item);
    return result;
}

[akeymo]

判断是否是完全二叉树

所谓完全二叉树，就是深度为h的二叉树，所有叶子节点都出现在h或者h-1层，并且最后一层的叶子节点都集中在最左边。

如果进行广度优先遍历，那么在队列中，null值都会集中在队列的最末端并且中间不会有节点值，通过这个特性可以用来判断一棵树是否是完全二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function isCompleteBinaryTree(root) {
    if (root === null) return root;
    let cur = root;
    const queue = [];

    while (cur !== null) {
        queue.push(cur.left);
        queue.push(cur.right);
        cur = queue.unshift();
    }

    return queue.filter(Boolean).length === 0;
}