侧边栏
《剑指Offer》题目整理
发布于 | 分类于 数据结构和算法
最近重新翻阅《剑指offer》第二版，同时将里面的题目使用JavaScript实现，本文主要整理相关题目及思路、代码实现等，方便回顾。
本文可能会非常长
面试基础知识
包含语言、数据结构和算法等
3 找出数组中的重复数字
题目 1
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如：如果输入长度为 7 的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。
js
// 思路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 的范围内，所有数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
js
// 与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);4 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
js
// 思路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);5 替换空格
实现一个函数，把字符串中每个空格替换成'%20'。突然想起之前遇见的一个面试题：为什么要对 url 进行 URLEncode 编码~
js
// 思路：实现起来比较简单，但是要考虑字符串的特殊性，诸如包装对象等
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)的情况下实现
6 倒序打印链表
js
// 思路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);
}7 重建二叉树
根据前序遍历和中序遍历的结果重建二叉树，假设树中不包含重复数字
js
// 思路：根据前序遍历和中序遍历的特点，可知 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;
}8 中序遍历顺序的下一个结点
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
js
// 思路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);
}
}9 用两个栈实现队列
用两个栈实现队列
js
// 思路：使用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,
};
}同理，根据这个思路，可以通过两个队列来实现一个栈
js
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
}
}10 求斐波那契数列的第n项
求斐波那契数列的第n项，
js
// 思路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级的台阶总共有多少种跳法（先后次序不同算不同的结果）
js
// 思路到达最后一级台阶有两种路径，
// 1.从倒数第二个台阶跳一步
// 2.从倒数第三个台阶跳二步
// 因此问题简化为到n-1级台阶的跳法和到n-2级台阶的跳法，即最终答案为：solution(n) = solution(n-1) + solution(n-2)
// 所以实际上是斐波拉契数列的变种11 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
js
// 思路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属于左边还是右边，此时只能通过顺序查找最小值12 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
js
// 如下面矩阵包含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");13 机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够达到多少个格子？
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
js
// 思路，从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;
}
}
// 总结：通常物体或人在二维放个运动这里问题都可以通过回溯法解决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。
js
// 思路：动态规划
// 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)); // 1815 二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。
例如，把9表示成二进制是1001，有2位是1。因此如果输入9，则该函数输出2。
js
// 思路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
}TDOO 接下来的章节
你要请我喝一杯奶茶？
版权声明：自由转载-非商用-保持署名和原文链接。
本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。
