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

从排序数组中删除重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例1
给定数组 nums = [1,1,2]
​
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
​
你不需要考虑数组中超出新长度后面的元素。
示例2
给定 nums = [0,0,1,1,1,2,2,3,3,4],
​
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
​
你不需要考虑数组中超出新长度后面的元素。
说明
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
const len = removeDuplicates(nums);
​
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (let i = 0; i < len; i++) {
print(nums[i]);
}

方法一

思路
我们先遍历数组，若发现相同的相邻项，将该元素删除。此时数组的长度也会发生变化，我们需要把 i - 1，保证遍历顺序不会出错。最后，再返回数组的长度。
详解
  1. 1.
    遍历数组里的元素；
  2. 2.
    判断该元素的相邻项是否与之相同；
  3. 3.
    若相同，则删除该元素，同时将数组长度减一，继续遍历；
  4. 4.
    待遍历结束时，返回数组的新长度。
代码
const removeDuplicates = function (nums) {
// 遍历数组
for (let i = 1; i < nums.length; i++) {
// 若该元素的相邻项与之相同，则删除该元素
if (nums[i - 1] === nums[i]) {
nums.splice(i - 1, 1);
// 因删除该元素后，数组长度会减一，故 i 也需要减一
i--;
}
};
return nums.length;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    共执行了 n 次，因此时间复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外的空间，因此空间复杂度为
    O(1)O(1)
    。

方法二

思路
我们用 count 来记录不重复的下标数量，第一个数必定不是重复的，即 nums[0] 肯定是不重复的，所以从第二项（即 nums[1]）开始，遍历数组，判断该下标的值跟不重复的数组最后一个元素 nums[count] 是否相同，如果不相同，将该元素值赋值给 nums[count + 1] ，然后 count++，继续遍历。待遍历结束时，我们可以通过 count 数量来判断不重复元素个数，因为 count 是从 0 开始的，故返回的新数组的长度为 count + 1。
比如原数组为 [0,0,1,1,1,2,2,3,4]，经过遍历会变成类似 [0,1,2,3,4,x,x,x,x] 的结构，此时 count = 4，返回新数组长度 count + 1 = 5。
详解
  1. 1.
    创建字段 count，用来记录不重复的下标数量，初始值为 0；
  2. 2.
    因数组的第一个元素（即 nums[count = 0]）必定是不重复的，故从数组第二项开始（即 nums[1]）开始，遍历数组里的元素；
  3. 3.
    判断数组当前元素是否与 nums[count] 相等，若不同，得知当前元素并未重复，将该元素值赋值给 nums[count + 1] ，然后 count++，继续遍历；
  4. 4.
    待遍历结束，我们可以通过 count 数量来判断不重复元素个数，因为 count 是从 0 开始计数的，故返回的新数组的长度为 count + 1。
代码
const removeDuplicates = function (nums) {
let count = 0;
// 遍历数组
for (let i = 1; i < nums.length; i++) {
// 若该下标的值跟不重复的数组最后一个元素不相同，则该值添加到不重复数组后一位
if (nums[count] !== nums[i]) {
nums[count + 1] = nums[i];
count++;
}
};
// 因为 count 是从 0 开始的，故返回的数组长度加一
return count + 1;
};

复杂度分析

  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

方法一 奇技淫巧

思路
我们可以把数组转化成数字加一，然后再转成数组
详解
利用数数的 join 方法，转成数字。
在提交代码时发现有 6145390195186705543 溢出的情况，使用 BigInt 来解决。
加一之后使用 toString方法，转换成字符，最后 split 成数组。
BigInt 是 JavaScript 中的一个新的原始类型，可以用任意精度表示整数。使用 BigInt，即使超出JavaScript Number 的安全整数限制，也可以安全地存储和操作大整数。
代码
/**
* @param {number[]} digits
* @return {number[]}
*/
const plusOne = function (digits) {
return (BigInt(digits.join('')) + 1n).toString().split('');
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    复杂度与输入数组的长度线性相关，为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外空间，复杂度为
    O(1)O(1)
    ​

方法二 进位相加

思路
我们可以模拟加法的操作
1 2 3
+ 1
-------
1 2 4
详解
在实际情况中，加一有且只有以下两种情况：
  • 9 加一进位
  • 其他数字加一
先把个位的数加一，如果没有进位就直接推出循环。
如果进位了，再把十位的数加一，个位数设置为0，如此循环，，直到判断没有再进位就退出循环返回结果。
9 9
+ 1
-------
1 0 0
对于 9、99 这种情况，需要进行补位
代码
const plusOne = function (digits) {
for (let i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10; // 9 + 1 = 10 ---> 0 判断有没有进位
if (digits[i] !== 0) {
return digits; // 最后没有进位直接返回
}
}
digits.splice(0, 0, 1);
return digits;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    复杂度与输入数组的长度线性相关，复杂度为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外空间，复杂度为
    O(1)O(1)
    ​

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2：
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

方法一

思路
定一个滑动窗口，滑动窗口内所有的价格从后向前是递减，如若不是则调整下标，满足该条件。前一个下标从后向前遍历，两个下标初始位置为数组最后一个。如果遇到价格不是递减，则相减得出利润差，并移动两个下标到新的起点。如此遍历直到第一日。
详解
  1. 1.
    初始化滑动窗口的两个下标，前下标从后向前遍历。
  2. 2.
    如果遇到价格不是递减的情况，则相减得出利润差，并移动两个下标到新的起点。
  3. 3.
    如此遍历直到第一日。
代码
const maxProfit = (prices) => {
// 总利润
let num = 0;
// 滑动窗口后一个下标
let aftOff = prices.length - 1;
// 滑动串口前一个下标
let offset = prices.length - 1;
while (offset > 0) {
// 价格递减则移动前一个下标，否则计算出利润差并移动两个下标到新的起点
if (prices[offset] > prices[offset - 1]) {
offset -= 1;
} else {
num += prices[aftOff] - prices[offset];
offset -= 1;
aftOff = offset;
}
}
// 价格递减到第一日情况的逻辑补充
if (aftOff !== offset) {
num += prices[aftOff] - prices[offset];
}
return num;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    假设
    nn
     为给定数组的长度，while 循环执行了
    nn
     次，因此，时间复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
     该解法中，申请了常数个变量，因此，空间复杂度为
    O(1)O(1)
    。

方法二

思路
遍历每日的价格，从第二天起，如果每日的价格都比前一日的价格高，则相减得出利润差，累加在总利润上，直到遍历到最后一日。
详解
  1. 1.
    从前向后遍历数组，从第二个开始
  2. 2.
    如果当前日的价格比前一日的价格高，则相减得出利润差，累加在总利润上。
  3. 3.
    遍历到最后一日，退出循环，返回总利润
代码
const maxProfit = function (prices) {
// 总收益
const totalBenefit = 0;
// 当前日下标
const offset = 1;
const len = prices.length;
while (offset <= len - 1) {
// 如果当日价格比前一天价格高，则相减得出收益
const curPrice = prices[offset];
const prePrice = prices[offset - 1];
if (curPrice > prePrice) {
totalBenefit += curPrice - prePrice;
}
offset += 1;
}
return totalBenefit;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明
  1. 1.
    必须在原数组上操作，不能拷贝额外的数组。
  2. 2.
    尽量减少操作次数。
注意事项
  1. 1.
    由于题目要求必须在原数组上操作，数组的 filter Api 或是 sort 算法，都是不必考虑的。
  2. 2.
    切记不要边遍历数组边修改数组长度，如：splice，push，pop等。

方法一 双指针

思路
创建两个指针 i 和 j，j 来记录非零元素的下标。遍历遇到一个非零元素时，就把 j 往右挪
遍历结束后，j 指向了最后一个非零元素的下标，再把剩余地址填充 0 即可
详解
  1. 1.
    i 用于遍历数组，j 来记录非零元素的下标
  2. 2.
    当发现 num[i] !== 0 时，说明找到非零元素，把第 j 和 i 指向的两个元素交互位置，再把 j 往右挪
  3. 3.
    遍历结束把剩余的地址填充 0
const moveZeroes = function (nums) {
let j = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
nums[j] = nums[i];
j++;
}
}
// 遍历完了，把尾部的元素填充 0 即可
nums.fill(0, j, nums.length);
};

复杂度分析

  • 时间复杂度：
    O(n)O(n)
    ​
    算法包括一次遍历，运行次数与数组长度一致，所以时间复杂度为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    额外空间包括若干个常量

方法二 双指针优化

思路
方法一进行了两次循环，还能进一步优化，只循环一次。
详解
思路与方法 1 极其相似，依次用非零元素与零元素交换即可，优点在于一步到位，不用再次填充 0。 1. 用 j 记录非零元素的下标，初始为 0 2. 依次用非零元素与 j 对应元素交换位置，每次交换后，j 加 1，j 对应元素就被替换成了 0（除初始值） 3. 零元素不用处理，会被替换或者保持不变。
const moveZeroes = function (nums) {
let j = 0;
let temp = '';
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
};

复杂度分析：

  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
以前
旋转数组、只出现一次的数字、两数之和、旋转图像
下一个
两个数组的交集、一周中的第几天、有效的数独、除资深以外数组的乘积和存在重复元素
最近更新 2yr ago
复制链接
大纲
从排序数组中删除重复项
加一
买卖股票的最佳时机 II
移动零