面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
旋转数组、只出现一次的数字、两数之和、旋转图像
从排序数组中删除重复项、加一、买股票的最佳时机和移动零
两个数组的交集、一周中的第几天、有效的数独、除资深以外数组的乘积和存在重复元素
字谜分组、三数之和、无重复字符的最长子串、矩阵置零和递增的三元子序列
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
旋转数组、只出现一次的数字、两数之和、旋转图像

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

方法一

思路
数据元素向右移动 1 个位置，相当于将数组元素的最后一项截取，然后放到第一项的位置，因此向右移动 k 个位置，就是循环执行上述操作 k 次。而当 k 为数组长度的倍数时，实际相当于没有移动，所以实际需要循环操作的次数为 k % l。
详解
  1. 1.
    首先计算出需要循环移动的次数；
  2. 2.
    通过数组的 unshift() 和 pop() 方法实现旋转，循环执行 k 次。
unshift() 方法将把它的参数插入数组的头部，并将已经存在的元素顺次地移到较高的下标处，该方法不会创建新数组，而是直接修改原数组。
pop() 方法将删除数组的最后一个元素，把数组长度减 1，并且返回它删除的元素的值。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
for (let i = 0; i < k; i++) {
nums.unshift(nums.pop());
}
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    循环遍历的次数取决于k的值，与k值呈线性关系，因此复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外的空间，因此复杂度为
    O(1)O(1)
    。

方法二

思路
方法一是将数组中的元素一个一个移动，我们还可以一次性将最后的 k % l 项全部截取，通过扩展运算符‘...’将截取的值放到数组的前边，实现旋转。
详解
  1. 1.
    首先还是计算出需要截取的数组元素的长度；
  2. 2.
    通过数组的 splice() 方法截取需要移动的元素，然后使用扩展运算符‘...‘将截取的元素当作参数，通过 unshift() 方法将截取的 元素放到数组的前边。
splice() 方法可删除从 index 处开始的零个或多个元素，然后返回被删除的项目。
数组的扩展运算符...相当于将数组展开,主要的使用场景是用于数组复制、合并等。
unshift() 方法的第一个参数将成为数组的 index 为0的新元素，如果还有第二个参数，它将成为 index 为1的新元素，以此类推。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
nums.unshift(...nums.splice(l - k, k));
};

复杂度分析：

  • 时间复杂度：
    O(1)O(1)
    。 采用一次性截取，所有方法都只执行了 1 次，因此复杂度为
    O(1)O(1)
    。
  • 空间复杂度：
    O(1)O(1)
    。没有申请额外的空间，因此复杂度为
    O(1)O(1)
    。

方法三

思路

先将原数组的所有元素整体往后移动 k 个位置，给需要旋转的元素预留出位置，然后通过替换和删除，实现数组的旋转。
详解
  1. 1.
    先将原数组原有的元素从最后一位开始，依次移动到（原下标 + k）的位置；
  2. 2.
    然后再从改变后的新数组的下标为 (k - 1) 的元素开始，依次将最后一位赋值给新数组下标为 (k - 1) 的元素，然后删除掉最后一位元素。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
for (let i = l - 1; i >= 0; i--) {
nums[i + k] = nums[i];
}
for (let j = k - 1; j >= 0; j--) {
nums[j] = nums[l + j];
nums.pop();
}
};
复杂度分析：
  • 时间复杂度：
    O(n)O(n)
    ​
    循环遍历的次数取决于数组长度，与数组长度呈线性关系，因此复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    数组进行了扩充，申请了n个空间，因此复杂度为
    O(n)O(n)
    。

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

方法一 分组查询法

思路
将数组遍历，并通过过滤的方法，将值相同的数归集为数组的一个元素，由于除了一个元素，其他元素都会出现两次，所有只要找到过滤的集合的长度为1的那个集合，该集合第一个元素即是该元素。
详解
  1. 1.
    遍历数组，由于需要返回值，这里使用map方法
  2. 2.
    使用过滤函数，过滤数组中值与当前遍历的元素的值相同的元素
  3. 3.
    现在得到了一个存在多个集合的数组，而数组中唯一值的那个元素的集合肯定值存在它自己
  4. 4.
    查询这个集合中长度只有1的集合，再取这个集合的第一个元素，即是只出现一次的数字
代码
const singleNumber = (nums) => {
const numsGroup = nums.map(num => nums.filter(v => v === num));
return numsGroup.find(num => num.length === 1)[0];
};
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    使用了 map 和 filter，嵌套遍历，故为
    O(n2)O(n^2)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    map方法创建了一个长度为
    nn
    的数组，占用了
    nn
    大小的空间。

方法二 异或比较法

思路
异或运算符可以将两个数字比较，由于有一个数只出现了一次，其他数皆出现了两次，类似乘法法则无论先后顺序，最后相同的数都会异或成0，唯一出现的数与0异或就会得到其本身，该方法是最优解，直接通过比较的方式即可得到只出现一次的数字。
详解
  1. 1.
    将数组的一个元素与下一个元素做异或比较，直接使用reduce方法
  2. 2.
    两两异或最后与所有元素都不相同，最后返回的值即是只出现一次的数字。
代码
const singleNumber = (nums) => {
return nums.reduce((accumulator, currentValue) => accumulator ^ currentValue);
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    仅用 reduce 方法遍历，一层遍历，故为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    空间复杂度为常量，占用空间没有随数据量
    nn
    的大小发生改变，故为
    O(1)O(1)
    。

两数之和

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例
给定 nums = [2, 7, 11, 15], target = 9
​
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一 暴力法

思路
遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。
详解
  1. 1.
    遍历每个元素 x
  2. 2.
    并查找是否存在一个值与 target - x 相等的目标元素。

代码

const twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] === target - nums[i]) {
return [i, j];
}
}
}
};
复杂度分析
  • 时间复杂度：
    O(n2)O( n^2 )
    ​
    对于每个元素，通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费
    O(n2)O( n^2 )
    的时间。
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额为的空间，所以空间复杂度为
    O(1)O(1)
    。

方法二 利用 map

思路
将每个元素的值和它的索引加到表中，检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中
详解
  1. 1.
    将每个元素的值和它的索引添加到表中
  2. 2.
    检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中
代码
const twoSum = function (nums, target) {
const lookup = {};
let res = [];
nums.some((v, i) => {
if (lookup[target - v] !== undefined) {
res = [lookup[target - v], i];
return true;
} else {
lookup[v] = i;
return false;
}
});
return res;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    我们只遍历了包含有 n 个元素的列表一次，在 map 中进行的每次查找只花费
    O(1)O(1)
     的时间, 因此总的复杂度为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    上述解法中，申请了大小为
    nn
     的空间，空间复杂度跟数字的个数 n 线性相关，因此为
    O(n)O(n)
    。

旋转图像

给定一个 n × n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度。
必须在原地旋转图像，需要直接修改输入的二维矩阵，不要使用另一个矩阵来旋转图像。
示例
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
​
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

方法一 四角旋转

思路
找到一个矩阵中对应点的旋转90度需要涉及到的四个位置的数字，然后将对应的四个数字按照顺时针90度的方法交换即可。
详解
  1. 1.
    根据输入得到矩阵的维数；
  2. 2.
    以左上角为（0，0）点，从左向右递增，从上向下递增建立矩阵；
  3. 3.
    将需要矩阵上需要交换的四个数字存放在一个临时数组中；
  4. 4.
    将原本位置上的数据按照数组中的数据进行替换。
代码
function rotate (matrix) {
const n = matrix.length; // n维矩阵
for (let i = 0; i < n; i++) {
for (let j = i; j < n - i - 1; j++) {
const a = [matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j], matrix[n - 1 - j][i]];
matrix[i][j] = a[3];
matrix[j][n - 1 - i] = a[0];
matrix[n - 1 - i][n - 1 - j] = a[1];
matrix[n - 1 - j][i] = a[2];
}
}
}
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
    O(n2)O(n^2)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    所占用空间不会随矩阵的维数而有所变化

方法二 正向对称

思路
先将矩阵沿左上角到右下角的对角线进行对称，然后将矩阵沿垂直中线对称即可。
详解
  1. 1.
    根据输入得到矩阵的维数；
  2. 2.
    以左上角为（0，0）点，从左向右递增，从上向下递增建立矩阵；
  3. 3.
    将矩阵沿左上角到右下角的对角线进行对称，以题目例子 1 为例即:
[
[1,4,7],
[2,5,8],
[3,6,9]
]
  1. 1.
    再将矩阵沿垂直中线进行对称。即:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
代码
function rotate (matrix) {
const n = matrix.length;
// 调换对角线元素
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 调换每行的左右元素
for (let k = 0; k < n; k++) {
for (let l = 0; l < Math.floor(n / 2); l++) {
const temp = matrix[k][l];
matrix[k][l] = matrix[k][n - 1 - l];
matrix[k][n - 1 - l] = temp;
}
}
}
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
    O(n2)O(n^2)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    所占用空间不会随矩阵的维数而有所变化

方法三 反向对称

思路
先将矩阵沿右上角到左下角的对角线进行对称，然后将矩阵沿水平中线对称即可。
详解
  1. 1.
    根据输入得到矩阵的维数；
  2. 2.
    将矩阵沿右上角到左下角的对角线进行对称，以题目例子 1 为例即:
[
[9,6,3],
[8,5,2],
[7,4,1]
]
  1. 1.
    将矩阵沿水平中线进行对称。即：
[
[7,4,1],
[8,5,2],
[9,6,3]
]
代码
function rotate (matrix) {
const n = matrix.length;
// 按对角线调换数字
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - 1 - i; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
matrix[n - 1 - j][n - 1 - i] = temp;
}
}
​
// 从头到尾交换每一行
for (let k = 0; k < Math.floor(n / 2); k++) {
const temp = matrix[k];
matrix[k] = matrix[n - 1 - k];
matrix[n - 1 - k] = temp;
}
}
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
    O(n2)O( n^2)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    空间与矩阵维数正相关
以前
数组
下一个
从排序数组中删除重复项、加一、买股票的最佳时机和移动零
最近更新 2yr ago
复制链接
大纲
旋转数组
只出现一次的数字
两数之和
旋转图像