Shymean_V0.8.0

最近重新翻阅《剑指offer》第二版，同时将里面的题目使用JavaScript实现，本文主要整理相关题目及思路、代码实现等，方便回顾。

<!--more-->

本文可能会非常长

1. 面试基础知识

包含语言、数据结构和算法等

1.1. 3 找出数组中的重复数字

题目 1

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例如：如果输入长度为 7 的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。

// 思路1：使用hash表，记录已经遍历过的元素，内存O(n)，时间O(n)
function solution(arr) {
    var map = {};
    for (var val of arr) {
        if (!map[val]) {
            map[val] = true;
        } else {
            return val;
        }
    }
    return -1;
}

// 思路2：题目给出了一个限制：所有数字都在0 ~ n-1的范围内,
// 如果没有重复的数字，则排序后数字i将出现在arr[i]处；由于存在重复的数字，则某些索引值arr[i]处没有值，而某些arr[i]包含多个值
// 通过这个特性，可以将空间复杂度降低为O(1)
// 具体算法步骤为：从头遍历数组，对于每个索引i处的元素m，判断i === m,
//  如果是，则遍历下一个元素
//  如果不是，则判断 arr[m] === m ： 如果不相等，则把arr[i]处的值m与arr[m]处的值交换，把m放在arr[m]处；如果相等，则表示i与m处均出现了m值，说明m是一个重复出现的值
// 对于[2,3,1,0,2,5,3]
// 变化过程为 [1,3,2,0,2,5,3] -> [3,1,2,0,2,5,3] -> [0,1,2,3,2,5,3] -> [0,1,2,3,2,5,3] 发现arr[4] = 2 与arr[2]相同，则找到了重复出现的值

function solution(arr) {
    // 数据校验
    if (!arr || !arr.length) return -1;
    for (let v of arr) {
        if (v < 0 || v > arr.length - 1) {
            return -1;
        }
    }

    for (let i = 0; i < arr.length; ++i) {
        while (arr[i] !== i) {
            var m = arr[i];
            if (arr[m] !== m) {
                var tmp = arr[m];
                arr[i] = tmp;
                arr[m] = m;
            } else {
                return m;
            }
        }
    }
}

var arr = [2, 3, 1, 0, 2, 5, 3];
var res = solution(arr);
console.log(res);

题目 2

在一个长度为 n+1 的数组里所有数字都在 1~n 的范围内，所有数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。

// 与3_1类似，但是题目要求不能修改数组， 一种办法是使用hash表，接下来研究不使用额外空间的解法
// 如果没有重复数字，则在1~n中只有n个数字，目前数组超过了n个数字，则肯定有重复的。基于这个思路，将数组分成两部分 1~m 与 m+1 ~ n，如果前部分数组中在1~m区间的个数超过m，则表示该部分包含重复数字；后部分的逻辑同理，这样就是一个二分查找的过程，只是在每次查找过程中需要遍历数组统计数量
// 例如：[2,3,5,4,3,2,6,7]  长度为8， 分为1 ~ 4 和 5 ~ 7之间，
// 在第一次二分判断中，数组中在1~4范围的个数有5个，则表示包含重复数字，继续二分 1~2 和 3~4
// 在第二次二分判断中，在1~2范围内的个数有2个，无法确定是否包含重复的数字；在3~4范围内有3个数组，表示肯定包含重复的数组
// 最后，统计3的个数，数量大于1，直接返回

// 最终空间复杂度为O(1)，时间复杂度比hash解法更高，为O(nlogn)，相当于时间换空间，这道题还要求在写代码之间理解出题人的具体意图，然后再考虑使用对应算法

function solution(arr) {
    var len = arr.length;

    var start = 1;
    var end = len - 1;
    while (start <= end) {
        var m = ((end - start) >> 1) + start;
        var c = count(start, m);
        if (end === start) {
            if (c > 1) {
                return start;
            } else {
                break;
            }
        }

        if (c > m - start + 1) {
            end = m;
        } else {
            start = m + 1;
        }
    }
    return -1;

    function count(start, end) {
        var count = 0;
        for (var val of arr) {
            if (val >= start && val <= end) {
                count++;
            }
        }
        return count;
    }
}

var arr = [2, 3, 5, 4, 3, 2, 6, 7];
var res = solution(arr);
console.log(res);

1.2. 4 二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

// 思路1： 二维数组遍历，时间O(r*c)，空间O(1)

// 思路2：由于该二维数组排列比较特殊，每次选择二维数组的**右上角**与目标元素进行比较，然后移除掉行或者列，缩小查找范围
// 以下面的例子来研究， 如果目标元素为7
// 第一次右上角元素 9 > 7 ，且9是所在列最小的元素，则可以直接移除掉该列
// 第二次右上角元素 8 > 7, 同理移除该列
// 第三次右上角元素 2 > 7，有2是所在行最大的元素，则可以直接移除掉该行
// 第四次右上角元素 4 > 7 ，同理移除该行
// 第五次 右上角元素 7 == 7 ，找到目标元素，返回true

function solution(matrix, n) {
    var row = matrix.length;
    if (!row) return false;
    var col = matrix[0].length;

    var r = 0;
    var l = col - 1;

    while (r < row && l >= 0) {
        var rt = matrix[r][l];
        if (rt === n) {
            return true;
        } else if (rt > n) {
            l--;
        } else {
            r++;
        }
    }
    return false;
}

// 思路3： 同理，我们每次选择左下角的元素lb进行比较也是可以的，
// 当lb < n时，lb是所在列最大元素，则直接移除该列
// 当lb > n时，lb是所在行最小元素，可以直接移除该行

// 收获：当我们需要解决一个复杂问题的时候，可以从一个具体的问题入手，通过简单分析具体的例子，尝试寻找普遍的规律

var matrix = [
    [1, 2, 8, 9],
    [2, 4, 9, 12],
    [4, 7, 10, 13],
    [6, 8, 11, 15],
];
var n = 7; // true
// n = 5
var res = solution(matrix, n);
console.log(res);

1.3. 5 替换空格

实现一个函数，把字符串中每个空格替换成'%20'。突然想起之前遇见的一个面试题：为什么要对 url 进行 URLEncode 编码~

// 思路：实现起来比较简单，但是要考虑字符串的特殊性，诸如包装对象等
function solution(str) {
    return str.split(" ").join("%20");
}

function solution(str) {
    var ans = "";
    for (var i = 0; i < str.length; ++i) {
        var ch = str[i];
        ans += ch === " " ? "%20" : ch;
    }
    return ans;
}
// 在某些场景下会要求我们在字符串本身进行替换，然而JS的字符串是基础类型，所以这里实现一种在数组上原样替换的
function solution(str) {
    var arr = str.split(""); // 根据题意，将数组中将所有的 ' ' 替换成'%' '2' '0'三个位置
    var count = 0;
    for (var ch of arr) {
        if (ch === " ") {
            count++;
        }
    }
    var cur = arr.length - 1;
    var len = arr.length + count * 2; // 替换所有空格后数组的长度
    // 从后向前依次添加
    for (let i = len - 1; i >= 0; --i) {
        let ch = arr[cur];
        if (ch === " ") {
            arr[i] = "0";
            arr[i - 1] = "2";
            arr[i - 2] = "%";
            i -= 2;
        } else {
            arr[i] = ch;
        }
        cur--;
    }
    return arr.join("");
}

题目 2

一道扩展题，有两个排序数组 A1 和 A2，实现函数将 A2 的所有数字插入到 A1，且所有数字仍旧是排序的

与字符串替换空格的题目思路基本相似，从后向前依次将 A2 的数字插入到 A1 中，同时挪动 A1 后面的数字，这样可以在 O(n1 + n2)的情况下实现

1.4. 6 倒序打印链表

// 思路1，通过额外的数据结构依次保存每个节点，然后倒序输出，空间O(n)，时间O(n)
function solution(head) {
    var arr = [];
    while (head) {
        arr.push(head);
        head = head.next;
    }
    // 栈先进后出，倒序打印
    while (arr.length) {
        var node = arr.pop();
        console.log(node.val);
    }
}
// 思路2，基于思路1的栈实现，可以使用递归，通过系统的函数调用栈来打印，实现起来非常简洁，但是需要注意递归过深时额外的系统开销
function solution(head) {
    if (!head) return;
    solution(head.next);
    console.log(head.val);
}

1.5. 7 重建二叉树

根据前序遍历和中序遍历的结果重建二叉树，假设树中不包含重复数字

// 思路：根据前序遍历和中序遍历的特点，可知 preorderList[0] 为根节点root，
// 然后在中序遍历的列表中找到inorderList.indexOf(root)索引值为idx，则inorderList.slice(0, idx)为左子树，然后根据左子树的长度确定前序遍历的右子树列表；
// 同理可以得到右子树的前序遍历和中序遍历列表，通过递归构建左子树和右子树，最后完成整个树的构建
function solution(preorderList, inorderList) {
    if (!preorderList.length) return null;
    var rootVal = preorderList[0];
    var idx = inorderList.indexOf(rootVal);
    var lInorderList = inorderList.slice(0, idx);
    var rInorderList = inorderList.slice(idx + 1);

    var lPreorderList = preorderList.slice(1, lInorderList.length + 1);
    var rPreorderList = preorderList.slice(lInorderList.length + 1);

    var root = new Node(rootVal);
    root.left = solution(lPreorderList, lInorderList);
    root.right = solution(rPreorderList, rInorderList);

    return root;
}

1.6. 8 中序遍历顺序的下一个结点

给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。

// 思路1：先中序遍历，然后找到node在遍历列表中的索引值，根据索引值的下一个节点，需要空间O(n)
function solution(root, node) {
    var arr = [];
    inorder(root);
    var idx = arr.indexOf(node);
    return idx < arr.length - 1 ? arr[idx + 1] : null;

    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        arr.push(node);
        inorder(node.right);
    }
}

// 思路2：由于每个节点保存了父节点的引用，因此在中序遍历中
// 如果node存在右子节点，则下一个节点就是他的右子树最左侧叶子节点
// 如果node不存在子节点，判断node是否为父节点的左子节点
//      如果是，则返回父节点
//      如果不是，则需要逐步判断父节点的父节点...当父节点作为其父节点的左节点时，则直接返回父节点的父节点；如果不是，则继续向上查找

function solution(root, node) {
    if (node.right) {
        return findLeftLeafNode(node.right);
    }
    var parent = node.parent;
    if (!parent) return null;

    if (node === parent.left) {
        return parent;
    } else {
        var cur = parent;
        while (cur && cur.parent) {
            if (cur === cur.parent.left) {
                return cur.parent;
            } else {
                cur = cur.parent;
            }
        }

        return parent ? parent.left : null;
    }

    function findLeftLeafNode(node) {
        if (!node.left || !node.right) {
            return node;
        }
        return node.left
            ? findLeftLeafNode(node.left)
            : findLeftLeafNode(node.right);
    }
}

1.7. 9 用两个栈实现队列

用两个栈实现队列

// 思路：使用stack1和stack2，在入队列的时候，stack1.push(元素)，
// 当出队列时，由于先加入的元素需要先出去，因此可以将stack1的元素依次弹出并push到stack2中
// 此时stack2的栈顶元素就是最先进入队列的元素，直接pop即可
// 至此，就可以完成使用两个栈实现队列的功能
function solution() {
    var stack1 = [];
    var stack2 = [];

    function enqueue(val) {
        stack1.push(val);
    }
    function dequeue() {
        if (!stack2.length) {
            while (stack1.length) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    return {
        enqueue,
        dequeue,
    };
}

同理，根据这个思路，可以通过两个队列来实现一个栈

function solution(){
    var queue1 = []
    var queue2 = []

    function push(val){
        queue1.push(val)
    }
    function pop(){
        // 轮流使用queue1和queue2
        if(queue1.length) {
            while(queue1.length > 1){
                queue2.push(queue1.shift())
            }
            queue1.shift() // 将 queue1最后的元素删除
        }else if(queue2.length){
            while(queue2.length > 1){
                queue1.push(queue2.shift())
            }
            queue2.shift() // 将 queue2最后的元素删除
        }
    }

    return {
        push,
        pop
    }
}

1.8. 10 求斐波那契数列的第n项

求斐波那契数列的第n项，

// 思路1:递归
function solution1(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    return solution(n - 1) + solution(n - 2);
}
// 优化1：上面的递归存在大量的重复运行计算，可以保存某项的计算结果
function solution(n) {
    var memo = {};
    return fb(n);
    function fb(n) {
        if (n === 1) return 1;
        if (n === 2) return 2;
        if (memo[n]) return memo[n];

        var ans = fb(n - 1) + fb(n - 2);
        memo[n] = ans;
        return ans;
    }
}

// 思路2：另外一种思路是从下向上计算
function solution(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    var dp = [0, 1,2]
    for (var i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
// 优化2： 上面需要O(n)的空间来保存每一项的计算结果，实际上中间项的变量是不需要保存的，我们只需要保存前两项的结果就可以了
function solution(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    var a = 1
    var ans = 2
    for (var i = 3; i <= n; ++i) {
        var tmp = ans
        ans += a
        a = tmp
    }
    return ans
}

// 复杂度为O(logn)的数学解法
// 1 1
// 1 0  ^ n-1 矩阵的乘方

题目2 青蛙跳台阶

青蛙跳台阶，一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

// 思路到达最后一级台阶有两种路径，
// 1.从倒数第二个台阶跳一步
// 2.从倒数第三个台阶跳二步
// 因此问题简化为到n-1级台阶的跳法和到n-2级台阶的跳法，即最终答案为：solution(n) = solution(n-1) + solution(n-2)
// 所以实际上是斐波拉契数列的变种

1.9. 11 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

// 思路1：求数组的最小值，直接遍历,O(n)，这种思路没有理由旋转数组的特性
function solution(arr) {
    return Math.min(...arr);
}

// 思路2：由于数组是某个非递减排序数组，则其旋转数组可以分成两个非递减子数组，两个数组的分界点就是最小元素，
// 所以一种方法是找到arr[i] < arr[i-1]时，对应的arrr[i]就是最小值
function solution(arr) {
    for (var i = 1; i < arr.length; ++i) {
        if (arr[i] < arr[i - 1]) {
            return arr[i];
        }
    }
    return arr[0];
}

// 思路3：利用上面的特性，实际上并不需要按顺序查找，前半部分子数组的值基本上是大于等于后半部分子数组的值，因此可以使用二分
// 比如[3,4,5,1,2] ，初始化时l = 0, r = 4
// 第一次 m = 2 arr[m] > arr[l] 说明m一定在左子数组，此时需要将l移动到m处
// 第二次 l = 2, r = 4, m = 3, arr[m] < arr[r]，说明此时m一定在右侧子数组
// 依次比较，直到l与r的索引值相差为1的时候，表示两个数组的连接处，此时arr[r]即为结果

function solution(arr) {
    var len = arr.length;
    var l = 0;
    var r = len - 1;

    var m = 0

    // 处理数组均为增序的情况，则可以跳过循环直接返回首元素
    while (arr[l] >= arr[r]) {
        if(r - l === 1) {
            m = r
            break
        }
        m = ((r - l) >> 1) + l;
        if(arr[m] >= arr[l]){
            l = m
        }else if(arr[m] <= arr[r]){
            r = m
        }
    }
    return arr[m]
}

// 思路3： 特殊情况如[1,0,1,1,1]，无法判断m属于左边还是右边，此时只能通过顺序查找最小值

1.10. 12 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

// 如下面矩阵包含bfce、但是不包括abfb
// a b t g
// c f c s
// j d e h

// 思路：利用回溯法，从首字符开始找到符合要求的坐标，然后向周围判断是否可以继续查找下一个字符
function solution(matrix, target) {
    var row = matrix.length;
    if (!row) return -1;
    var col = matrix[0].length;

    // 记录是否访问到某个坐标
    var visited = new Array(row);
    for (var i = 0; i < row; ++i) {
        visited[i] = new Array(col).fill(false);
    }

    for (var i = 0; i < row; ++i) {
        for (var j = 0; j < col; ++j) {
            if (find(i, j, 0)) {
                return true;
            }
        }
    }
    return false;

    function find(i, j, index) {
        if (index === target.length) return true;

        if (i < 0 || i >= row || j < 0 || j >= col) return;

        if (visited[i][j]) return false;

        visited[i][j] = true;
        if (matrix[i][j] === target[index]) {
            // 四个方向都没找到，则重置visited并返回false
            if (
                !find(i - 1, j, index + 1) &&
                !find(i, j - 1, index + 1) &&
                !find(i, j + 1, index + 1) &&
                !find(i + 1, j, index + 1)
            ) {
                visited[i][j] = false;
                return false;
            }
            return true;
        }
        return false;
    }
}

var arr = [
    ["a", "b", "t", "g"],
    ["c", "f", "c", "s"],
    ["j", "d", "e", "h"],
];
var res = solution(arr, "bfce");
var res = solution(arr, "abfb");

1.11. 13 机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够达到多少个格子？

例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

// 思路，从0,0开始通过回溯统计所有可以到达的地方
function solution(m, n, k) {
    // 记录是否访问到某个坐标
    var visited = new Array(m);
    for (var i = 0; i < m; ++i) {
        visited[i] = new Array(n).fill(false);
    }
    var ans = 0;
    walk(0, 0)
    return ans
    function walk(i, j) {
        if (i < 0 || i >= m || j < 0 || j >= n) return;
        if(visited[i][j]) return  
        if (!check(i, j)) return;
        visited[i][j] = true
        ans++;
        walk(i + 1, j);
        walk(i - 1, j);
        walk(i, j + 1);
        walk(i, j - 1);
    }

    function check(i, j) {
        let arr = [...i.toString(), ...j.toString()];
        let sum = arr.reduce((acc, item) => {
            return acc + parseInt(item, 10);
        }, 0);
        return sum <= k;
    }
}


// 总结：通常物体或人在二维放个运动这里问题都可以通过回溯法解决

1.12. 14 剪绳子

给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1,m>1），每段绳子的长度记为 k[0], k[1], k[2], …, k[m]。请问 k[0] * k[1] * k[2] * … * k[m] 可能的最大乘积是多少？

例如，当绳子的长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

// 思路：动态规划
// dp[n] = max([i from 0 to n ... dn[n-i]*dp[i]])
function solution(n) {
    if (n <= 0) return 0;
    var dp = [0, 1, 2, 3];
    for (var i = 4; i <= n; ++i) {
        var ans = [];
        for (var j = 1; j < i; ++j) {
            ans.push(dp[j] * dp[i - j]);
        }
        dp[i] = Math.max(...ans);
    }
    return dp[n];
}

// 思路2：贪婪算法
// 通过数据论证，当n>=5时，2(n-2)>1*n 且3(n-3)>1*n，且3(n-3) > 2(n-2)，因此需要尽可能将绳子剪成长度为3;
// 当长度为4时，2*2 > 1 * 3，因此需要单独处理余数为4的情况
function solution(n) {
    if (n < 2) return 0;
    if (n === 2) return 1;
    if (n === 3) return 2;

    // 尽可剪成长度为3
    var timeOf3 = Math.floor(n / 3);

    // 最后长度为4，则不能剪成1*3, 而是剪成2*2
    if (n % 3 === 1) {
        timeOf3 -= 1;
    }
    var timeOf2 = Math.floor((n-timeOf3*3) / 2)
    // 所有子段乘积
    return Math.pow(3, timeOf3) * Math.pow(2, timeOf2)
}

console.log(solution(8)); // 18

1.13. 15 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

例如，把9表示成二进制是1001，有2位是1。因此如果输入9，则该函数输出2。

// 思路1；将数字转换成二进制，然后计算
function solution(n) {
    var str = n.toString(2);
    var ans = 0;
    for (var i = 0; i < str.length; ++i) {
        var ch = str[i];
        if (ch === "1") {
            ans++;
        }
    }
    return ans;
}

// 思路2：位运算，在负数的时候会出现死循环，因为负数右移时首位会存放符号1
function solution(n) {
    var ans = 0;
    while (n) {
        // 判断最后1位是不是1
        if (n & 1) {
            ans++;
        }
        n = n >> 1;
    }
    return ans;
}
// 思路3：从低位开始判断每一位，而非移
function solution(n) {
    var ans = 0;
    var flag = 1;
    while (flag) {
        // 判断最后1位是不是1
        if (n & flag) {
            count++;
        }
        flag = flag << 1;
    }
    return ans;
}
// 思路4，有几个n就循环几次
function solution(n) {
    var ans = 0;
    while (n) {
        ++ans;
        n = (n - 1) & n;
    }
    return ans
}

2. TDOO 接下来的章节