数组扁平化

使用递归实现数组扁平化

Array.prototype.flat = function() {
    var arr = [];
    this.forEach((item, index) => {
        if (Array.isArray(item)) {
            arr = arr.concat(item.flat());
        } else {
            arr.push(item);
        }
    });
    return arr;
}
let arr = [[2, 3], 4, 5, [6, [7, 8]]];
console.log(arr.flat()); //[2, 3, 4, 5, 6, 7, 8]

递归扩展：爬楼梯

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

function climbStairs(n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}
console.log(climbStairs(5)); // 5

递归扩展：二分查找

二分查找，是在一个有序的序列里查找某一个值。

function binarySearch(arr, target, low = 0, high = arr.length - 1) {
    if (low > high) return `没有找到${target}`;
    let n = Math.floor((low + high) / 2);
    let current = arr[n];
    if (current === target) {
        return `找到了${target}, 在第${n+1}个`;
    } else if (current < target) {
        return binarySearch(arr, target, n + 1, high);
    } else if (current > target) {
        return binarySearch(arr, target, low, n - 1);
    }
    // return `没有找到${target}`;
}
let arr = [1, 3, 5, 6, 9, 11, 35, 55];
console.log(binarySearch(arr, 9)); // 找到了9, 在第5个
console.log(binarySearch(arr, 7)); // 没有找到7

Donate