最近在刷 LeetCode 的数据结构，在此记录一下，欢迎大家提供其它解法！
一、数组
1. 寻找数组中心索引
给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个
// 我的
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function (nums) {
if (nums.length === 0) return -1;
if (nums.length === 1) return 0;
const sum = nums.reduce((pre, current) => pre + current);
for (let i = 0; i < nums.length; i++) {
let leftSum = 0;
let rightSum = 0;
for (let j = 0; j < i; j++) {
leftSum += nums[j];
}
rightSum = sum - leftSum - nums[i];
if (leftSum === rightSum) {
return i;
}
}
return -1;
};
// 用时更短
var pivotIndex = function (nums) {
let sum = 0;
nums.forEach((num) => (sum += num));
let leftSum = 0;
for (i = 0; i < nums.length; i++) {
if (sum - nums[i] - leftSum == leftSum) {
return i;
} else {
leftSum += nums[i];
}
}
return -1;
};
2. 搜索插入的位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target || target < nums[i]) {
return i;
}
}
return nums.length;
};
二分查找
var searchInsert = function (nums, target) {
const n = nums.length;
let left = 0,
right = n - 1,
ans = n;
while (left <= right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};
3. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例：
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function (intervals) {
if (intervals.length === 0) return [];
// 1. 将数组按左边界排序
const sortInterval = intervals.sort((a, b) => a[0] - b[0]);
const arr = [sortInterval[0]];
for (let i = 1; i < intervals.length; i++) {
// 当后一项的左边界大于前一项右边界，不需合并
if (arr[arr.length - 1][1] < intervals[i][0]) {
arr.push(intervals[i]);
// 如果后一项的右边界<=前一项右边界 就跳过不动 反之则进行上述方法合并
} else if (arr[arr.length - 1][1] < intervals[i][1]) {
arr[arr.length - 1][1] = intervals[i][1];
}
}
return arr;
};
4. 旋转矩阵
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到？
示例：
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
思路：先将矩阵转置，然后将每一行倒序 reverse
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
for (i = 0; i < matrix.length; i++) {
for (j = i + 1; j < matrix.length; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
matrix[i] = matrix[i].reverse();
}
return matrix;
};
5. 零矩阵
编写一种算法，若 M × N 矩阵中某个元素为 0，则将其所在的行与列清零。
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
let xClear = new Set(), // 存储需要清除的行索引
yClear = new Set(); // 存储需要清除的列索引
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === 0) {
xClear.add(i);
yClear.add(j);
}
}
}
// 清除行
for (let i of xClear) {
for (let j = 0; j < matrix[i].length; j++) {
matrix[i][j] = 0;
}
}
// 清除列
for (let j of yClear) {
for (let i = 0; i < matrix.length; i++) {
matrix[i][j] = 0;
}
}
};
二、字符串
1. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
输入: ["flower","flow","flight"]
输出: "fl"
var longestCommonPrefix = function (strs) {
const len = strs.length;
const newStrs = strs.map((i) => {
return i.split("");
});
if (len === 0) return "";
if (len === 1) return strs[0];
const commonPrefix = [];
// 以第一个来对比
for (let i = 0; i < newStrs[0].length; i++) {
if (strs.every((item) => item[i] === newStrs[0][i])) {
commonPrefix.push(newStrs[0][i]);
} else {
break;
}
}
return commonPrefix.join("");
};
2. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
- 暴力解法
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
function isPalidrome(str) {
const len = str.length;
const middle = parseInt(len / 2);
for (let i = 0; i < middle; i++) {
if (str[i] !== str[len - i - 1]) {
return false;
}
}
return true;
}
let res = "";
let maxStr = 0;
const len = s.length;
// 枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串
for (let i = 0; i < len; i++) {
for (let j = i + 1; j <= len; j++) {
const tempStr = s.substring(i, j);
if (isPalidrome(tempStr) && tempStr.length > maxStr) {
maxStr = tempStr.length;
res = tempStr;
}
}
}
return res;
};
解法2：动态规划 - B
状态定义
dp[i,j]：字符串s从索引i到j的子串是否是回文串
true： s[i,j] 是回文串
false：s[i,j] 不是回文串
转移方程
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
s[i] == s[j]：说明当前中心可以继续扩张，进而有可能扩大回文串的长度
dp[i+1][j-1]：true
说明s[i,j]的**子串s[i+1][j-1]**也是回文串
说明，i是从最大值开始遍历的，j是从最小值开始遍历的
特殊情况
j - i < 2：意即子串是一个长度为0或1的回文串
总结
dp[i][j] = s[i] == s[j] && ( dp[i+1][j-1] || j - i < 2)
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
let n = s.length;
let res = "";
let dp = Array.from(new Array(n), () => new Array(n).fill(0)); // n x n 的二维数组
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
if (dp[i][j] && j - i + 1 > res.length) {
res = s.substring(i, j + 1);
}
}
}
return res;
};
3. 翻转字符串里的单词
输入：" hello world! "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
var reverseWords = function (s) {
return s
.split(" ")
.filter((i) => i !== "")
.reverse()
.join(" ");
};
4.双指针技巧
经典问题：反转数组中的元素。比如数组为 ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']，反转之后变为 ['e', 'd', 'o', 'c', 't', 'e', 'e', 'l']。
思考：使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。
function reverseString(s) {
let i = 0,
j = s.length - 1;
while (i < j) {
// const temp = s[i];
// s[i] = s[j];
// s[j] = temp;
[s[i], s[j]] = [s[j], s[i]]; // 不使用中间变量
i += 1;
j -= 1;
}
return s;
}
5. 数组拆分
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
示例：
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
我们需要形成数组元 素的配对，使得这种配对中最小的总和最大。因此，我们可以查看选择配对中最小值的操作，比如 (a,b)(a,b) 可能会产生的最大损失 a-ba−b (如果 a > ba>b)。
如果这类配对产生的总损失最小化，那么总金额现在将达到最大值。只有当为配对选择的数字比数组的其他元素更接近彼此时，才有可能将每个配对中的损失最小化。
考虑到这一点，我们可以对给定数组的元素进行排序，并直接按排序顺序形成元素的配对。这将导致元素的配对，它们之间的差异最小，从而导致所需总和的最大化。
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function (nums) {
// sort() 不传函数，默认按 ASCII 码排序
const sortNum = nums.sort((a, b) => a - b);
let sum = 0;
for (let i = 0; i <= nums.length - 2; i += 2) {
sum += nums[i];
}
return sum;
};
6. 两数之和 II - 输入有序数组
给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
// i < j , numbers[i]+numbers[j] = target, 返回[i+1, j+1]
for (let i = 0; i < numbers.length - 1; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] === target) {
return [i + 1, j + 1];
}
}
}
};
二分查找：
- 从 numbers 取出一个元素 numbers[i]，在 numbers 中 i 之后的元素中查找 target - numbers[i]
- 查找到之间返回，不然依次从 numbers 中取后面一个元素
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let len = numbers.length;
for (let i = 0; i < len; i++) {
// number[i] + targetNum = target
const targetNum = target - numbers[i];
// left=i+1, right=len-1
let left = i + 1,
right = len - 1;
while (left <= right) {
let mid = parseInt((right - left) / 2) + left; // mid 需要放在 while 循环里面，每次重新计算
if (numbers[mid] === targetNum) {
return [i + 1, mid + 1];
} else if (numbers[mid] > targetNum) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return [-1, -1];
};
双指针：
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
每次计算两个指针指向的两个元素之和，并和目标值比较。
如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。
如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let left = 0,
right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] === target) {
return [left + 1, right + 1];
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
right--;
}
}
};
7. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
双指针解法:
当 nums[j] 与给定的值相等时，递增 j 以跳过该元素。只要 nums[j] != val，我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。
/**
* 双指针解法
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function (nums, val) {
let i = 0,
j = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== val) {
nums[i] = nums[j];
i++;
}
}
return i;
};
8. 最大连续 1 的个数
给定一个二进制数组， 计算其中最大连续 1 的个数。
示例：
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function (nums) {
return Math.max(
...nums
.join("")
.split(0)
.map((i) => i.length)
);
};
遍历：
用一个计数器 count 记录 1 的数量，另一个计数器 maxCount 记录当前最大的 1 的数量。
当我们遇到 1 时，count 加一。
当我们遇到 0 时：
将 count 与 maxCount 比较，maxCoiunt 记录较大值。
将 count 设为 0。
返回 maxCount
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function (nums) {
let max = 0,
count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
max = count > max ? count : max;
count = 0;
} else {
count++;
}
}
return max;
};
9. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
滑动窗口：
// 子数组长度：[1, s]
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (s, nums) {
const len = nums.length;
let right = nums.length; // 子数组的右下标
// 遍历子数组所有可能长度
for (let i = 0; i < len; i++) {
// left 为子数组的左下标 [left, right) 子数组不包括右下标
for (let left = 0; left < len - i; left++) {
right = left + i;
if (right <= len) {
let sum = 0;
const sonArr = nums.slice(left, right);
sonArr.forEach((i) => (sum += i));
if (sum >= s) {
return sonArr.length;
}
} else {
break;
}
}
}
return 0;
};
const minSubArrayLen = (s, nums) => {
let minLen = Infinity;
let i = 0;
let j = 0;
let sum = 0;
while (j < nums.length) {
// 主旋律是扩张，找可行解
sum += nums[j];
while (sum >= s) {
// 间歇性收缩，优化可行解
minLen = Math.min(minLen, j - i + 1);
sum -= nums[i];
i++;
}
j++;
}
return minLen === Infinity ? 0 : minLen; // 从未找到可行解，返回0
};
10. 杨辉三角
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
思路：判断如果不是该列数组的首位或者最后一位，则值为 a[i-1][j-1] + a[i-1][j] ，否则值为 1
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function (numRows) {
const res = [];
for (let i = 0; i < numRows; i++) {
// 生成第 i 行
const lineArr = [];
for (let j = 0; j <= i; j++) {
// j 列
if (j > 0 && j < i) {
lineArr.push(res[i - 1][j - 1] + res[i - 1][j]);
} else {
lineArr.push(1);
}
}
res.push(lineArr);
}
return res;
};
11. 杨辉三角 2
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function (rowIndex) {
const arr = [];
for (let i = 0; i <= rowIndex; i++) {
const lineArr = [];
for (let j = 0; j <= i; j++) {
if (j > 0 && j < i) {
lineArr.push(arr[i - 1][j - 1] + arr[i - 1][j]);
} else {
lineArr.push(1);
}
}
arr.push(lineArr);
}
return arr[arr.length - 1];
};
12. 反转字符串
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序
在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function (s) {
return s
.split(" ")
.map((i) => {
return i.split("").reverse().join("");
})
.join(" ");
};
13. 删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
/**
* @param {number[]} nums
* @return {number}
*/
// 排序数组
var removeDuplicates = function (nums) {
let j = 0;
if (!nums.length) return 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[j]) {
j++;
nums[j] = nums[i];
}
}
return j + 1;
};
Set 中的元素是唯一的，可用于去重(占用空间)。
[...new Set(nums)].length;
//或者
new Set(nums).size;
14. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
1.必须在原数组上操作，不能拷贝额外的数组。 2.尽量减少操作次数。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let i = -1;
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== 0) {
// const temp = nums[j];
// nums[j] = nums[i + 1];
// nums[i + 1] = temp;
[nums[i + 1], nums[j]] = [nums[j], nums[i + 1]]; // 不使用中间变量
i++;
}
}
return nums;
};
注：题目来自 LeetCode ，其中部分解法与思路来自力扣官方和评论，大家可以去 LeetCode上看更加详细多样的解答。
