剑指Offer JavaScript-递归循环专题

青蛙跳台阶

1. 题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

2. 思路分析

跳到 n 阶假设有 f(n)种方法。

往前倒退，如果青蛙最后一次是跳了 2 阶，那么之前有 f(n-2)种跳法; 如果最后一次跳了 1 阶，那么之前有 f(n-1)种跳法。

所以：f(n) = f(n-1) + f(n-2)。就是斐波那契数列。

3. 代码

这里利用缓存模式（又称备忘录模式）实现了代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const fibonacci = (() => {
    let mem = new Map();
    mem.set(1, 1);
    mem.set(2, 1);

    const _fibonacci = (n) => {
        if (n <= 0) {
            throw new Error("Unvalid param");
        }

        if (mem.has(n)) {
            return mem.get(n);
        }

        mem.set(n, _fibonacci(n - 1) + _fibonacci(n - 2));
        return mem.get(n);
    };

    return _fibonacci;
})();

/**
 * 测试代码
 */

let start = new Date().getTime(),
    end = null;

fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);

start = end;
fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);

数值的整次方

1. 题目描述

题目：实现函数 double Power（double base, intexponent），求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题

2. 思路分析

简单思路：最简单的做法是循环，但是要考虑异常值的检验。比如指数是负数，底数为 0。

优化思路：书上提供了一种复杂度为 $O(logN)$ 的做法。比如我们要求 32 次方，那么只要求出 16 次方再平方即可。依次类推，是递归函数的结构。

递推公式如下：

$$
a^n=\left{
\begin{aligned}
a^{n/2}*a^{n/2} ; n为偶数\
a^{(n - 1)/2}*a^{(n - 1)/2} ; n为奇数
\end{aligned}
\right.
$$

需要注意的是，如果幂是奇数，例如 5 次方，可以先计算 2 次方，结果平方后（4 次方），再乘以自身（5 次方）。按照此思路处理。

代码实现-简单思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 *
 * @param {Number} base
 * @param {Number} exp
 */
function pow(base, exp) {
    // 规定0的任何次方均为0
    if (!base) {
        return 0;
    }
    let result = 1,
        absExp = Math.abs(exp);

    for (let i = 0; i < absExp; ++i) {
        result *= base;
    }

    // 对于指数小于0的情况，求其倒数
    if (exp < 0) {
        result = 1 / result;
    }

    return result;
}

/**
 * 以下是测试代码
 */

console.log(pow(2, -2));
console.log(pow(2, 2));
console.log(pow(2, 0));
console.log(pow(0, -9));

代码实现-优化思路

在 Js 中整数除 2 不会自动取整，可以使用Math.floor()。但更好的做法是使用>>位运算。

判断奇数可以用%2判断。但更好的做法是和1进行&运算后（除了最后 1 位，都被置 0 了），判断是不是 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 求base 的 exp次幂，其中exp永远是正数
 * @param {Number} base
 * @param {Number} exp
 */
function unsignedPow(base, exp) {
    if (exp === 0) {
        return 1;
    } else if (exp === 1) {
        return base;
    }

    let result = pow(base, exp >> 1);
    result *= result;
    if (exp & (1 === 1)) {
        result *= base;
    }

    return result;
}

/**
 * 求 base的exp次幂
 * @param {Number} base
 * @param {Number} exp
 */
function pow(base, exp) {
    if (!base) {
        return 0;
    }

    let absExp = Math.abs(exp);

    return exp < 0 ? 1 / unsignedPow(base, absExp) : unsignedPow(base, absExp);
}

/**
 * 以下是测试代码
 */

console.log(pow(2, 2));
console.log(pow(2, 0));
console.log(pow(0, -9));
console.log(pow(2, -2));

打印从1到最大的n位数

1. 题目描述

题目：输入数字 n，按顺序打印出从 1 最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。

2. 思路分析

主要的坑点在：大数的溢出。当然，es6 提供了BigInt数据类型，可以直接相加不用担心溢出。

除此之外，这题显然是要我们模拟“大数相加”：将最低位加 1，然后每次检查是否进位，如果不进位，直接退出循环；如果进位，需要保留进上来的 1，然后加到下一位，直到不进位或者超出了我们规定的范围。

3. 代码实现

js 中不方便操作字符串中指定位置的字符，因此用数组对象来模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 用数组模拟大数相加操作
 * @param {Array} arr
 * @return {Boolean} true, 超出arr.length位最大整数; false, 没有超出arr.length位最大整数
 */
function increase(arr) {
    let length = arr.length,
        over = 0; // 记录前一位相加后的进位数

    for (let i = length - 1; i >= 0; --i) {
        arr[i] = arr[i] + over;

        if (i === length - 1) {
            arr[i] += 1;
        }

        if (arr[i] >= 10) {
            // 如果第n位进位，说明超出了n位最大数字
            if (i === 0) {
                return true;
            }

            arr[i] = arr[i] - 10;
            over = 1;
        } else {
            break;
        }
    }

    return false;
}

/**
 *
 * @param {Number} n
 */
function printMaxDigits(n) {
    if (n <= 0) {
        return;
    }

    let arr = new Array(n).fill(0);
    while (!increase(arr)) {
        console.log(arr);
    }
}

/**
 * 测试代码
 */
printMaxDigits(2);
printMaxDigits(3);
printMaxDigits(10);

顺时针打印矩阵

1. 题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

2. 思路分析

既然是顺时针打印，其实就是由外向内一圈圈打印，将过程分为 2 步：

第一步：printMatrix函数，确定要打印的圈的左上角坐标（比较简单）

第二步：printMatrixInCircle函数，根据左上角坐标，顺时针打印这一圈的信息。这个过程又分为四步：左上 -> 右上 -> 右下 -> 左下 -> 左上。

3. 代码实现

如果觉得，函数printMatrixInCircle的条件判断不清楚，可以配合下面这张图一起看：

5cfcfe24760b637950.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * 打印从 (start, start) 与 (endX, endY) 围成的一圈矩形
 * @param {Array} arr
 * @param {Number} cols
 * @param {Number} rows
 * @param {Number} start
 */
function printMatrixInCircle(arr, cols, rows, start) {
    let endX = cols - start - 1,
        endY = rows - start - 1,
        result = "";

    // 从 左上 到 右上 打印一行
    for (let i = start; i <= endX; ++i) {
        result = result + " " + arr[start][i];
    }

    // 从 右上 到 右下 打印一行
    if (start < endY) {
        for (let i = start + 1; i <= endY; ++i) {
            result = result + " " + arr[i][endX];
        }
    }

    // 从 右下 到 左下 打印一行
    if (start < endX && start < endY) {
        for (let i = endX - 1; i >= start; --i) {
            result = result + " " + arr[endY][i];
        }
    }

    // 从 左下 到 左上 打印一行
    if (start < endX && start < endY - 1) {
        for (let i = endY - 1; i >= start + 1; --i) {
            result = result + " " + arr[i][start];
        }
    }

    console.log(result);
}

/**
 * 打印的外层函数, 主要用于控制要打印的圈
 * @param {Array} arr
 */
function printMatrix(arr) {
    if (!Array.isArray(arr) || !Array.isArray(arr[0])) {
        return;
    }

    let start = 0,
        cols = arr[0].length,
        rows = arr.length;

    while (cols > start * 2 && rows > start * 2) {
        console.log(`第${start + 1}层: `);
        printMatrixInCircle(arr, cols, rows, start);
        ++start;
    }
}

/**
 * 以下是测试代码
 */

printMatrix([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]);

printMatrix([
    [1, 2, 3, 4],
    [4, 5, 6, 7],
    [8, 9, 10, 11],
]);

数组中出现次数超过一半的数字

1. 题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。

由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。

2. 思路分析

数组中有一个数字出现的次数超过数组长度的一半，说明它出现的次数比其他所有数字出现次数的和还要多。

在遍历的过程中保存两个变量：一个数字 + 一个次数。遍历到每个元素都会更新次数，元素 = 数字，加次数；否则，减次数；如果次数为 0，当前元素赋值给数字。

需要注意的是，最后结果不一定符合条件，比如数组 [1, 2, 3]，结果是 3。所以要再统计一下最后数字的次数，是否有一半那么多。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 检查指定元素的次数是否大于等于长度一半
function checkMoreThanHalf(nums = [], target) {
    let times = 0;
    nums.forEach((num) => num === target && ++times);
    return times * 2 >= nums.length;
}

// 计算出数组元素
function moreThanHalfNum(nums = []) {
    if (!Array.isArray(nums) || !nums.length) {
        return null;
    }

    let times = 1,
        result = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        if (times === 0) {
            times = 1;
            result = nums[i];
        } else if (result === nums[i]) {
            ++times;
        } else {
            --times;
        }
    }

    return checkMoreThanHalf(nums, result) ? result : null;
}

/**
 * 以下是测试代码
 */

console.log(moreThanHalfNum([3, 1, 3, 2, 2])); // output: null
console.log(moreThanHalfNum([1, 2, 3, 2, 2, 2, 5, 4, 2])); // output: 2

最小的k个数

1. 题目描述

输入 n 个整数，找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。

2. 思路分析

利用“快速排序”的中的 partition 操作：返回 index，小于 index 对应元素的元素都放在了左边，大于 index 对应元素的元素都放在右边。

利用这个特性，只要我们的 partition 返回值是 k - 1，那么数组中前 k 个元素已经被摆放到了正确位置，直接遍历输出即可。

由于不需要排序全部，整体的时间复杂度是 O(N)。但美中不足的是：要在原数组操作，除非用 O(N)的空间来做拷贝。除此之外，针对海量动态增加的数据，也不能很好处理。这种情况需要用到“最大堆”，请前往《堆》章节查看。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function partiton(arr = [], start, end) {
    const length = arr.length;
    if (!length) {
        return null;
    }

    let v = arr[start],
        left = start + 1,
        right = end;

    while (1) {
        while (left <= end && arr[left] <= v) ++left;
        while (right >= start + 1 && arr[right] >= v) --right;

        if (left >= right) {
            break;
        }

        [arr[left], arr[right]] = [arr[right], arr[left]];
        ++left;
        --right;
    }

    [arr[right], arr[start]] = [arr[start], arr[right]];
    return right;
}

function getKthNumbers(nums = [], k) {
    if (k <= 0) {
        return null;
    }

    const length = nums.length;
    const result = new Array(k);
    let start = 0,
        end = length - 1;
    let index = partiton(nums, start, end);
    while (index !== k - 1) {
        if (index > k - 1) {
            // 前k个元素在 [start, index] 下标范围内
            // 要进一步处理，缩小区间
            end = index - 1;
            index = partiton(nums, start, end);
        } else {
            // [start, index]都属于小于k的元素，但不是全部
            // 剩下要处理的区间是 [index + 1, end]
            start = index + 1;
            index = partiton(nums, start, end);
        }
    }

    for (let i = 0; i < k; ++i) {
        result[i] = nums[i];
    }

    return result;
}

/**
 * 以下是测试代码
 */

console.log(getKthNumbers([4, 5, 1, 6, 2, 7, 3, 8], 4)); // output: [2, 3, 1, 4]
console.log(getKthNumbers([10, 2], 1));

和为s的两个数字

1. 题目描述

输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，输出任意一对即可。

2. 解题思路

如果这个数组不是递增的，就得用哈希表来解决，空间复杂度是 O(N)。

但是题目条件是“递增数组”，因此可以使用“双指针”的思路来实现：即一个指针指向开头，另一个指向结尾。

比较指针对应的 2 个元素的和与给定数组 s：

  • 元素和 > s: 后指针向前移动
  • 元素和 < s: 前指针向后移动
  • 元素和 = s: 返回指针对应的 2 个元素

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 *
 * @param {Array} data
 * @param {Number} sum
 */
function findNumsWithSum(data, sum) {
    if (!Array.isArray(data) || data.length <= 1) {
        return [null, null];
    }
    let i = 0,
        j = data.length - 1;
    while (i < j) {
        let now = data[i] + data[j];
        if (now === sum) {
            return [data[i], data[j]];
        } else if (now > sum) {
            --j;
        } else {
            ++i;
        }
    }

    return [null, null];
}

/**
 * 以下是测试代码
 */

// 输出：[ 4, 11 ]
console.log(findNumsWithSum([1, 2, 4, 7, 11, 15], 15));

和为s的连续正数序列

1. 题目描述

输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含有两个数）。例如输入 15，由于 1 ＋ 2 ＋ 3 ＋ 4 ＋ 5 ＝ 4 ＋ 5 ＋ 6 ＝ 7 ＋ 8 ＝ 15，所以结果打印出 3 个连续序列 1 ～ 5、4 ～ 6 和 7 ～ 8。

2. 思路分析

和前面题目很相似，这里也是“双指针”的思路。不同的地方有 2 个点：

  • 指针是从第 0 个和第 1 个位置开始的（下面称为 a 和 b）
  • 这里要计算指针范围内的所有元素和（题目要求是“连续序列”）

每次移动 a、b 之前，都要计算一下当前[a,b]范围内的所有元素和。如果等于 s，打印并且 b 右移；如果小于 s，b 右移；如果大于 s，a 右移。

至于为什么相等的时候 b 右移而不是 a 右移？因为 a 右移会漏掉情况，而且指针可能重叠。比如对于数组 [1, 2, 2]，给定 s 是 3。

3. 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 打印指定数组的起始下标内的所有元素
 *
 * @param {Array} data 打印数组
 * @param {Array} seq [start, end] 数组打印元素的起始下标
 */
function print(data, seq) {
    const [start, end] = seq;
    for (let i = start; i <= end; ++i) {
        process.stdout.write(data[i] + ", ");
    }
    process.stdout.write("\\n");
}

/**
 * 打印出递增数组中，所有和为s的元素
 *
 * @param {Array} data 递增数组
 * @param {Number} sum 和
 */
function findSequenceWithSum(data, sum) {
    let small = 0,
        big = 1,
        cur = data[small] + data[big];
    const middle = (data.length + 1) >> 1;
    while (small < middle) {
        if (cur <= sum) {
            cur === sum && print(data, [small, big]);
            ++big;
            cur += data[big];
        } else {
            cur -= data[small];
            ++small;
        }
    }
}

/**
 * 测试代码
 */

// 输出：
// 2, 3, 4,
// 4, 5,
findSequenceWithSum([1, 2, 3, 4, 5, 6, 7, 8], 9);

n个骰子的点数

1. 题目描述

把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能的值出现的概率。

2. 思路分析

递归的思路就是组合出所有情况，然后每种情况记录出现次数，最后除以 6^n 即可。其中，6^n 就是所有情况的总数。

书中提出的方法是使用循环来优化递归，递归是自顶向下，循环是自底向上，思考起来有难度。

技巧性很强，准备 2 个数组，假想每次投掷一个骰子，出现和为 n 的次数，就是之前骰子和为 n-1, n-2, …, n-6 的次数和。依次类推，每次存储结果都和之前的数组不同。

3. 算法实现

注释中都有详细说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const gMaxValue = 6; // 每个骰子的最大点数

/**
 *
 * @param {Number} number 骰子的个数
 */
function printProbability(number) {
    if (number < 1) {
        return;
    }

    const probabilities = [
        new Array(gMaxValue * number + 1),
        new Array(gMaxValue * number + 1),
    ];
    let flag = 0;

    // 初始化
    for (let i = 0; i < gMaxValue * number + 1; ++i) {
        probabilities[0][i] = probabilities[1][i] = 0;
    }

    // 第一次掷骰子，出现的和只有有 gMaxValue 种情况，每种和的次数为 1
    for (let i = 1; i <= gMaxValue; ++i) {
        probabilities[flag][i] = 1;
    }

    // 之后是从第 2 ~ number 次掷骰子
    //
    for (let k = 2; k <= number; ++k) {
        // 第k次掷骰子，那么最小值就是k
        // 不可能出现比k小的情况
        for (let i = 0; i < k; ++i) {
            probabilities[1 - flag][i] = 0;
        }

        // 可能出现的和的范围就是 [k, gMaxValue * k + 1)
        // 此时和为i的出现次数，就是上次循环中骰子点数和为
        // i - 1, i - 2, ..., i - 6 的次数总和
        for (let i = k; i < gMaxValue * k + 1; ++i) {
            probabilities[1 - flag][i] = 0;
            // 这里的j是指：本骰子掷出的结果
            for (let j = 1; j < i && j <= gMaxValue; ++j) {
                probabilities[1 - flag][i] += probabilities[flag][i - j];
            }
        }

        flag = 1 - flag;
    }

    // 全部情况的总数
    const total = Math.pow(gMaxValue, number);
    for (let i = number; i < gMaxValue * number + 1; ++i) {
        console.log(`sum is ${i}, ratio is ${probabilities[flag][i] / total}`);
    }
}

/**
 * 测试代码
 * 6个骰子，所有和出现的可能性
 */
printProbability(6);

扑克牌的顺子

1. 题目描述

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。

2 ～ 10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王可以看成任意数字。

2. 思路分析

难度不大，可以将大小王看成数字 0，可以在任何不连续的两个数字之间做填充。

首先将原数组排序，然后统计任意数字（0）的出现次数。再遍历之后的数字，找出不相邻数字之间总共差多少个数字。

最后比较 0 的出现次数和总共差多少个数字，两者的大小关系。

注意：连续两个相同的数字是对子，不符合要求。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 *
 * @param {Array} numbers
 */
function isContinuous(numbers) {
    numbers.sort();
    const length = numbers.length;

    let zeroNum = 0;
    for (let i = 0; i < length && !numbers[i]; ++i) {
        ++zeroNum;
    }

    let interval = 0;
    for (let i = zeroNum + 1; i < length - 1; ++i) {
        if (numbers[i] === numbers[i + 1]) {
            return false;
        }
        interval += numbers[i + 1] - numbers[i] - 1;
    }

    return interval <= zeroNum;
}

/**
 * 测试代码
 */
console.log(isContinuous([3, 8, 0, 0, 1])); // false
console.log(isContinuous([8, 10, 0, 6, 0])); // true

圆圈中最后剩下的数字

1. 题目

0,1,…,n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

2. 思路分析

这个其实是经典的“约瑟夫环”问题。常用解法就是“循环取余”。每次都把下标移动 m 个位置，然后移除当前元素。直到只剩最后一个元素。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {Number} n 0, 1, 2, ..., n-1 一共n个数字
 * @param {Number} m 被删除的第m个数字(从0计算)
 */
function lastRemain(n, m) {
    // 生成 [0, 1, ... , n-1] 的列表
    const nums = new Array(n);
    for (let i = 0; i < n; ++i) {
        nums[i] = i;
    }

    // 逐步移除第m个数字
    let start = 0;
    while (nums.length > 1) {
        start = (start + m) % nums.length;
        nums.splice(start, 1);
    }

    return nums.shift();
}

/**
 * 测试函数
 */
console.log(lastRemain(5, 2));