leetcode js题解（随缘更新）
javascript 算法 leetcode
二分查找
https://leetcode-cn.com/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
let start = 0;
let end = nums.length - 1;
while (start <= end) {
let mid = Math.floor((end + start) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] > target) end = mid - 1;
if (nums[mid] < target) start = mid + 1;
}
return -1;
};第一个错误的版本
https://leetcode-cn.com/problems/first-bad-version/ 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
提示：
1 <= bad <= n <= 231 - 1/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function (isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function (n) {
let start = 0;
let end = n;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (isBadVersion(mid)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
};
};两数之和-输入有序数组
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let i = 0;
let j = numbers.length - 1;
while (i < j) {
if (numbers[i] + numbers[j] === target) return [i + 1, j + 1];
if (numbers[i] + numbers[j] > target) j--;
if (numbers[i] + numbers[j] < target) i++;
}
};仅含 1 的子串数
https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：
输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
示例 2：
输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：
输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成
示例 4：
输入：s = "000"
输出：0
提示：
s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5/**
* @param {string} s
* @return {number}
*/
var numSub = function (s) {
let MODULO = 1000000007;
function add(length) {
return (length * (length + 1)) / 2;
}
let count = 0;
let length = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] == 1) length++;
else {
length && (count += add(length));
length = 0;
}
}
length && (count += add(length));
return count % MODULO;
};搜索插入位置
https://leetcode-cn.com/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
let start = 0;
let end = nums.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (nums[mid] >= target) end = mid - 1;
if (nums[mid] < target) start = mid + 1;
}
return start;
};有序数组的平方
https://leetcode-cn.com/problems/squares-of-a-sorted-array/
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function (nums) {
let start = nums.length - 1;
for (let index in nums) {
if (nums[index] >= 0) {
start =
isNaN(nums[index - 1]) ||
Math.abs(nums[index]) < Math.abs(nums[index - 1])
? index
: index - 1;
break;
}
}
let end = Number(start) + 1;
let res = [];
while (start >= 0 || end <= nums.length - 1) {
if (start < 0) {
res.push(Math.pow(nums[end], 2));
end++;
continue;
}
if (end > nums.length - 1) {
res.push(Math.pow(nums[start], 2));
start--;
continue;
}
if (Math.abs(nums[start]) <= Math.abs(nums[end])) {
res.push(Math.pow(nums[start], 2));
start--;
} else {
res.push(Math.pow(nums[end], 2));
end++;
}
}
return res;
};使数组唯一的最小增量
https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/
给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。
示例 1:
输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
示例 2:
输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示：
0 <= A.length <= 40000
0 <= A[i] < 40000/**
* @param {number[]} nums
* @return {number}
*/
var minIncrementForUnique = function (nums) {
nums.sort((x, y) => x - y);
let queue = [];
let count = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
//如果相同 则放入队列
queue.push(nums[i]);
}
if (nums[i] - nums[i - 1] > 1) {
let tmp = nums[i - 1] + 1;
while (tmp < nums[i] && queue.length) {
count += tmp - queue.shift();
tmp++;
}
}
}
let last = nums[nums.length - 1] + 1;
while (queue.length) {
count += last - queue.shift();
last++;
}
return count;
};两个数组的交集 II
https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function (nums1, nums2) {
nums1.sort((x, y) => x - y);
nums2.sort((x, y) => x - y);
let res = [];
while (nums1.length && nums2.length) {
if (nums1[0] < nums2[0]) {
nums1.shift();
} else if (nums1[0] > nums2[0]) {
nums2.shift();
} else {
res.push(nums1[0]);
nums1.shift();
nums2.shift();
}
}
return res;
};