Appearance
第一部分
常见经典算法题，32题。
一、两数之和 简单
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
解法
1.暴力
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
js
var twoSum = function (nums, target) {
const len = nums.length;
let result = null;
for (let i = 0; i < len - 1; i++) {
for (let j = i; j < len; j++) {
if (nums[i] + nums[j] === target) {
result = [i, j];
break;
}
}
if (result) {
break;
}
}
return result;
};2.哈希表map
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
js
var twoSum = function (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [i, map.get(target - nums[i])]
}
map.set(nums[i], i)
}
};二、字母异位词分组 中等
题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
解法
排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
js
var groupAnagrams = function (strs) {
const map = new Map();
for (let str of strs) {
const arr = str.split('');
arr.sort();
const key = arr.toString();
const list = map.get(key) ? map.get(key) : [];
list.push(str);
map.set(key, list);
}
return [...map.values()]
};三、最长连续序列 中等
题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
题解
js
var longestConsecutive = function (nums) {
const numSet = new Set(nums); // 使用集合（Set）来去除数组中的重复元素，并方便后续查找
let result = 0;
for (const num of numSet) {
// 如果当前数字的前一个数字不在集合中，说明它可能是连续序列的起始数字
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentLength = 1;
// 不断查找后续数字，扩展连续序列长度
while (numSet.has(currentNum + 1)) {
currentNum++;
currentLength++;
}
result = Math.max(result, currentLength);
}
}
return result;
};四、移动零 简单
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
题解
解法一：双指针法（快慢指针）
js
var moveZeroes = function(nums) {
let slow = 0;
let fast = 0;
// 快慢指针同时从头开始遍历数组
while (fast < nums.length) {
// 如果快指针指向的元素不为0，将其赋值给慢指针指向的位置
if (nums[fast]!== 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
// 将慢指针后面的元素都置为0，也就是把0都移到末尾了
while (slow < nums.length) {
nums[slow] = 0;
slow++;
}
return nums;
};解法二：优化的双指针法（一次遍历）
js
var moveZeroes = function(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast]!== 0) {
// 当快指针指向非零元素时，交换快慢指针指向的元素
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
return nums;
};五、盛最多水的容器 中等
题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
题解
双指针
js
var maxArea = function(height) {
let left = 0;
let right = height.length - 1;
let max = 0;
while (left < right) {
let width = right - left;
let h = Math.min(height[left], height[right]);
let area = width * h;
max = Math.max(area, max);
if(height[left] > height[right]) {
right--;
} else {
left++;
}
}
return max;
};在每次计算完当前面积后，需要移动指针来探索其他可能构成更大面积的区间。这里通过比较 height[left] 和 height[right] 的大小来决定移动哪一个指针。如果左边的高度大于右边的高度，说明以右边这条垂线为限制因素（较矮），那么将 right 指针向左移动一位，去尝试寻找更高的垂线来增大面积；反之，如果左边的高度小于等于右边的高度，就将 left 指针向右移动一位。
六、三数之和 中等
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
题解
排序 + 双指针
js
function threeSum(nums) {
nums.sort((a, b) => a - b); // 对数组进行排序，方便后续去重和双指针操作
const result = [];
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
// 跳过重复的元素，避免出现重复的三元组
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let left = i + 1;
let right = n - 1;
while (left < right) {
const sumValue = nums[i] + nums[left] + nums[right];
if (sumValue === 0) {
result.push([nums[i], nums[left], nums[right]]);
// 跳过left指针后面连续相同的元素，保证三元组不重复
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
// 跳过right指针前面连续相同的元素，保证三元组不重复
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sumValue < 0) {
left++;
} else {
right--;
}
}
}
return result;
}七、接雨水 困难
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
题解
一、动态规划
要计算能接住多少雨水，关键在于找出每个位置左右两边柱子高度的最大值，然后根据这两个最大值中的较小值与当前位置柱子高度的差值来确定该位置能接住的雨水量，最后把所有位置能接住的雨水量累加起来就是总的接雨水量。
通过一个循环遍历整个柱子高度数组，对于每个位置i，能接住的雨水量等于该位置左右两边最大值（leftMax[i]和rightMax[i]）中的较小值减去当前位置柱子的高度height[i]。
js
var trap = function (height) {
const length = height.length;
const leftMax = new Array(length).fill(0);
const rightMax = new Array(length).fill(0);
let left = 0, right = 0;
for(let i = 0; i < length; i++) {
if(height[i] > left) {
left = height[i];
}
if(height[length - 1 - i] > right) {
right = height[length - 1 - i]
}
leftMax[i] = left;
rightMax[length - 1 - i] = right;
}
let res = 0;
for(let i = 0; i < height.length; i++) {
res += Math.min(leftMax[i], rightMax[i]) - height[i]
}
return res;
};二、单调栈
以下是使用单调栈来解决“接雨水”问题的JavaScript代码示例以及详细的原理讲解：
javascript
function trap(height) {
const stack = [];
let result = 0;
for (let i = 0; i < height.length; i++) {
while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
const top = stack.pop();
if (stack.length === 0) {
break;
}
const distance = i - stack[stack.length - 1] - 1;
const bounded_height = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
result += distance * bounded_height;
}
stack.push(i);
}
return result;
}原理解释
整体思路： 单调栈在解决这个问题时的核心思路是利用栈来维护柱子高度的单调递减顺序（从栈底到栈顶），通过不断比较当前柱子高度和栈顶柱子高度的关系，来确定可以接住雨水的区域，并计算相应的雨水量。
步骤拆解：
- 初始化单调栈： 首先创建一个空栈
stack，这个栈用来存储柱子的索引，方便后续通过索引去获取对应的柱子高度。同时初始化一个变量result用来累加计算得到的雨水量，初始值为0。 - 遍历柱子高度数组： 开始遍历输入的柱子高度数组
height，对于每个位置i（代表当前柱子），执行以下操作：- 维护单调栈性质（出栈操作及计算雨水量）： 当栈不为空并且当前柱子高度
height[i]大于栈顶元素对应的柱子高度（即height[stack[stack.length - 1]]）时，说明遇到了一个比栈顶柱子高的柱子，此时就有可能形成了可以接住雨水的低洼区域，需要进行出栈操作并计算相应的雨水量。 先将栈顶元素弹出，记为top，它代表了当前低洼区域中最右边的那个相对较低的柱子（在栈中是最后压入的那个较低柱子的索引）。如果弹出栈顶元素后栈为空了，说明这个位置左边没有其他更高的柱子来“拦住”雨水了，那就无法形成有效的接水区域，直接break跳出当前的while循环。 但如果栈还有元素，就可以计算当前能接住的雨水量了。计算距离distance，它表示当前低洼区域横向的宽度，计算方式是当前位置索引i减去栈顶元素（也就是当前低洼区域左边相邻的较高柱子的索引）再减去1（因为要去掉两边的柱子本身）。 然后计算有效高度bounded_height，它是当前柱子高度height[i]和栈顶柱子高度（即height[stack[stack.length - 1]]）这两者中的较小值减去刚刚弹出的栈顶柱子（top对应的柱子）的高度，这个有效高度就是该低洼区域在垂直方向上可以接住雨水的高度。 最后，将距离distance乘以有效高度bounded_height得到的雨水量累加到result变量中。 - 入栈操作： 不管是否进行了出栈及雨水量计算操作，都要把当前位置
i的索引压入栈stack中，这样可以继续维护栈的单调递减性质，为后续继续判断其他可能的接水区域做准备。
- 维护单调栈性质（出栈操作及计算雨水量）： 当栈不为空并且当前柱子高度
- 初始化单调栈： 首先创建一个空栈
例如，对于输入的柱子高度数组 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]，按照上述单调栈的处理逻辑，随着遍历的进行，栈中的元素会不断变化，并且在合适的位置计算并累加相应的雨水量，最终得到总的接雨水量。
单调栈方法在处理这类涉及到寻找左右边界来计算某个值（这里是雨水量）的问题时非常有效，它通过巧妙地利用栈的特性，避免了像之前双指针或者暴力解法那样大量的重复比较操作，时间复杂度一般可以优化到 $O(n)$，其中 n 是柱子高度数组的长度。
三、双指针
js
var trap = function (height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let res = 0;
while (left < right) {
leftMax = Math.max(height[left], leftMax);
rightMax = Math.max(height[right], rightMax);
if(height[left] < rightMax) {
res += leftMax - height[left];
left++;
} else {
res += rightMax - height[right];
right--;
}
}
return res;
};复杂度分析
时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
空间复杂度：O(1)。只需要使用常数的额外空间。
八、无重复字符的最长子串 中等
题目
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题解
滑动窗口
js
var lengthOfLongestSubstring = function(s) {
const map = new Map();
let max = 0;
let left = 0;
for(let right = 0; right < s.length ; right++) {
const char = s.charAt(right);
if(map.has(char) && map.get(char) >= left) {
left = map.get(char) + 1;
}
map.set(char, right);
max = Math.max(max, right - left + 1);
}
return max;
};九、找到字符串中所有字母异位词 中等
题目
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
题解
滑动窗口
关键在于创建两个长度为 26 的数组 pCount 和 windowCount，分别用于统计字符串 p 以及滑动窗口内每个小写英文字母出现的频次
js
var findAnagrams = function (s, p) {
const result = [];
const sLen = s.length;
const pLen = p.length;
if (sLen < pLen) {
return result;
}
const pCount = new Array(26).fill(0);
const windowCount = new Array(26).fill(0);
for (let i = 0; i < pLen; i++) {
pCount[p[i].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < pLen; i++) {
windowCount[s[i].charCodeAt() - 'a'.charCodeAt()]++;
}
if (arrayEqual(pCount, windowCount)) {
result.push(0);
}
for (let i = 0; i < sLen - pLen; i++) {
windowCount[s[i].charCodeAt() - 'a'.charCodeAt()]--;
windowCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()]++;
if (arrayEqual(pCount, windowCount)) {
result.push(i + 1);
}
}
return result;
};
var arrayEqual = function (arr1, arr2) {
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] !== arr2[i]) {
return false;
}
}
return true;
}十、和为k的子数组 中等
题目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
题解
一、暴力枚举
暴力枚举的核心思路就是通过两层循环来枚举所有可能的子数组，然后再通过内层的一个循环去计算每个子数组的元素之和，最后判断这个和是否等于给定的整数 k，如果等于，就将满足条件的子数组个数加 1，最终返回统计得到的个数。
js
var subarraySum = function (nums, k) {
let res = 0;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i ; j < nums.length; j++) {
sum += nums[j]
if (sum === k) {
res++;
}
}
}
return res;
};二、前缀和 + 哈希表优化
js
var subarraySum = function (nums, k) {
const map = new Map();
map.set(0, 1);
let sum = 0;
let res = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if(map.has(sum - k)) {
res += map.get(sum - k)
}
map.set(sum, (map.get(sum) || 0) + 1);
}
return res;
};const map = new Map()创建一个 Map 对象 map，用来记录前缀和及其出现的频次。例如，map 中的键是前缀和的值，对应的值是该前缀和出现的次数。
map.set(0, 1) 将前缀和为 0 的情况初始化为出现了 1 次。这是因为在计算子数组和的过程中，从数组开头到某个位置的前缀和刚好等于 k 时，相当于当前前缀和（也就是 k ）减去之前的前缀和（这里初始化为 0 ）等于 k，需要把这种情况考虑进去，所以先将 0 这个前缀和的频次设为 1。
let sum = 0 定义变量 sum，用于记录当前的前缀和，初始值设为 0，随着遍历数组，它会不断累加元素的值来更新前缀和。
十一、滑动窗口最大值 困难
题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
题解
一、自己的做法v1
js
var maxSlidingWindow = function (nums, k) {
const res = [];
let max = 0;
let maxCount = 0;
let left = 0, right = 0;
while (right - left < k && right < nums.length) {
if(max === nums[right]) {
maxCount++;
} else if(nums[right] > max) {
maxCount = 1;
max = nums[right];
}
right++;
}
res.push(max);
while (right < nums.length) {
const next = nums[right];
if(next > max) {
maxCount = 1;
max = next;
} else {
if(next === max) {
maxCount++;
}
}
if(nums[left] === max) {
if(maxCount === 1) {
const L = left + 1;
max = nums[L];
maxCount = 1;
for(let i = L + 1; i < L + k; i++) {
if(max === nums[i]) {
maxCount++;
} else if(nums[i] > max) {
maxCount = 1;
max = nums[i];
}
}
} else {
maxCount--;
}
}
res.push(max);
left++;
right++;
}
return res;
};二、自己的做法v2
用了单调递减队列但是存的是nums中的元素值而不是元素下标，且略显啰嗦。
js
var maxSlidingWindow = function (nums, k) {
const deque = [];
const res = [];
let sum = 0;
for (let index = 0; index < nums.length; index++) {
if(sum >= k) {
res.push(deque[0]);
if(deque[0] === nums[index - k]) {
deque.shift();
}
}
if (deque.length) {
while (deque[deque.length - 1] < nums[index]) {
deque.pop();
}
}
deque.push(nums[index])
sum++;
}
res.push(deque[0])
return res;
};三、单调递减队列
js
var maxSlidingWindow = function (nums, k) {
const res = [];
const deque = []; // 模拟单调递减队列，存放元素的索引
for (let i = 0; i < nums.length; i++) {
// 维护单调递减队列，移除队列中小于当前元素的索引（保证队列头部为当前窗口最大值索引）
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
// 检查队列头部元素是否超出当前窗口范围，如果超出则移除
if (deque[0] <= i - k) {
deque.shift();
}
// 当窗口大小达到k时，开始记录窗口最大值（即队列头部对应的元素）
if (i >= k - 1) {
res.push(nums[deque[0]]);
}
}
return res;
};十二、最小覆盖子串 困难
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
题解
滑动窗口(一)
js
var minWindow = function (s, t) {
if (s === '' || t === '' || s.length < t.length) {
return '';
}
let left = 0, right = 0;
const targetMap = new Map();
const windowMap = new Map();
let sumCount = 0;
let minLeft = 0, minRight = -1, minLength = Infinity;
for (let char of t) {
targetMap.set(char, (targetMap.get(char) || 0) + 1)
}
while (right < s.length) {
const char = s[right];
if (targetMap.has(char)) {
const charCount = (windowMap.get(char) || 0) + 1;
windowMap.set(char, charCount);
if (charCount === targetMap.get(char)) {
sumCount++;
}
}
while (left <= right && sumCount === targetMap.size) {
const char = s[left];
if (windowMap.has(char)) {
const charCount = windowMap.get(char) - 1;
windowMap.set(char, charCount);
if (charCount < targetMap.get(char)) {
sumCount--;
}
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minRight = right;
minLeft = left;
}
}
left++;
}
right++;
}
return s.slice(minLeft, minRight + 1);
};滑动窗口(二)
js
function minWindow(s, t) {
if (s === "" || t === "") {
return "";
}
// 用于统计t中每个字符出现的次数（目标字典）
const target = {};
// 用于统计滑动窗口中每个字符出现的次数（窗口字典）
const windowMap = {};
for (const char of t) {
target[char] = (target[char] || 0) + 1;
}
let left = 0;
let right = 0;
// 记录最小子串的左右边界以及长度
let minLeft = 0;
let minRight = 0;
let minLen = Infinity;
// 记录窗口中已经满足t中字符数量要求的字符种类数
let matchCount = 0;
while (right < s.length) {
const char = s[right];
// 将右移窗口纳入的字符加入窗口字典统计
windowMap[char] = (windowMap[char] || 0) + 1;
// 如果该字符在窗口中的数量达到了在t中的数量要求，匹配字符数加1
if (windowMap[char] === target[char]) {
matchCount++;
}
// 当窗口中已经包含了t中所有字符（匹配字符数等于t中不同字符的种类数）
while (matchCount === Object.keys(target).length && left <= right) {
// 如果当前窗口长度小于最小长度记录，更新最小长度及对应的子串边界
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minLeft = left;
minRight = right;
}
// 尝试收缩窗口左侧边界，将左侧字符移出窗口字典统计
const leftChar = s[left];
windowMap[leftChar]--;
// 如果移出后该字符在窗口中的数量小于在t中的数量要求，匹配字符数减1
if (windowMap[leftChar] < target[leftChar]) {
matchCount--;
}
left++;
}
right++;
}
return minLen === Infinity? "" : s.slice(minLeft, minRight + 1);
}十三、最大子数组和 中等
题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
题解
一、动态规划
js
var maxSubArray = function (nums) {
let max = nums[0];
// 创建一个长度和nums数组相同的新数组dp，用于保存状态，初始值都填充为0。这里的dp数组是用来通过动态规划的思想记录以每个位置结尾的子数组的最大和
let dp = new Array(nums.length).fill(0);
dp[0] = max;
for(let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(dp[i], max);
}
return max;
};十四、合并区间 中等
题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
题解
排序
js
var merge = function(intervals) {
if(intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
let cur = intervals[0];
let index = 1;
let res = [];
while (index < intervals.length) {
if(cur[1] >= intervals[index][0]) {
cur[1] = Math.max(cur[1], intervals[index][1]);
} else {
res.push(cur);
cur = intervals[index];
}
index++;
}
if(index === intervals.length) {
res.push(cur);
}
return res;
};十五、轮转数组 中等
题目
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [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]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
题解
一、原数组直接操作(代码量小但超时) unshift,pop
js
var rotate = function (nums, k) {
for (let i = 0; i < k % nums.length; i++) {
nums.unshift(nums.pop())
}
};二、原数组直接操作(不超时代码量巨小) unshift,splice
js
var rotate = function (nums, k) {
const round = k % nums.length;
nums.unshift(...nums.splice(-round , round));
};三、三次翻转
js
var rotate = function(nums, k) {
const n = nums.length;
// 对k取余，确保k在合理范围内（小于数组长度）
k %= n;
// 1. 先整体翻转数组
reverse(nums, 0, n - 1);
// 2. 翻转前k个元素，相当于把要旋转到后面的部分先翻转到前面合适位置
reverse(nums, 0, k - 1);
// 3. 翻转剩余的元素，即把原来在前面的部分翻转到后面合适位置，完成旋转效果
reverse(nums, k, n - 1);
};
// 定义一个辅助函数用于翻转数组指定区间内的元素
function reverse(arr, start, end) {
while (start < end) {
// 交换元素实现翻转
[arr[start], arr[end]] = [arr[end], arr[start]];
start++;
end--;
}
}四、使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)modn 的位置，最后将新数组拷贝至原数组即可。
js
var rotate = function (nums, k) {
const round = k % nums.length;
const newArr = new Array(nums.length);
for(let i = 0; i < nums.length; i++) {
newArr[(i + round) % nums.length] = nums[i];
}
for(let i = 0; i < nums.length; i++) {
nums[i] = newArr[i];
}
console.log(newArr, nums)
};十六、除自身以外数组的乘积 中等
题目
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
题解
一、动态规划(左右乘积列表)
先计算每个元素两边元素的乘积，再将两边相乘
js
var productExceptSelf = function(nums) {
const dp = new Array(nums.length).fill(1);
const dp2 = new Array(nums.length).fill(1);
const res = new Array(nums.length).fill(1);
dp[0] = 1;
dp2[nums.length - 1] = 1;
for(let i = 1; i < nums.length; i++) {
dp[i] = nums[i - 1] * dp[i - 1];
}
for(let i = nums.length - 2; i >= 0; i--) {
dp2[i] = nums[i + 1] * dp2[i + 1]
}
for(let i = 0; i < nums.length; i++) {
res[i] = dp[i] * dp2[i];
}
return res;
};二、优化(题解一)
空间复杂度优化,循环合并优化。
js
var productExceptSelf = function(nums) {
const res = new Array(nums.length).fill(1);
let leftProduct = 1;
for(let i = 0; i < nums.length; i++) {
res[i] *= leftProduct;
leftProduct *= nums[i];
}
let rightProduct = 1;
for(let i = nums.length - 1; i >= 0; i--) {
res[i] *= rightProduct;
rightProduct *= nums[i];
}
return res;
};三、双指针
对(题解二)的再次优化，只写一次循环。
js
var productExceptSelf = function(nums) {
const res = new Array(nums.length).fill(1);
let left = 0, right = nums.length - 1;
let lp = 1, rp = 1;
while (left < nums.length) {
res[left] *= lp;
res[right] *= rp;
lp *= nums[left++];
rp *= nums[right--];
}
return res;
};十七、缺失的第一个正数 困难
题目
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用 常数级别额外空间 的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
题解
一、哈希表
实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：
我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。
js
var firstMissingPositive = function (nums) {
const n = nums.length;
for(let i = 0; i < n; i++) {
if(nums[i] <= 0) {
nums[i] = n + 1;
}
}
for(let i = 0; i < n; i++) {
if(Math.abs(nums[i]) <= n) {
nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1])
}
}
for(let i = 0; i < n; i++) {
if(nums[i] > 0) {
return i + 1;
}
}
return n + 1;
};十八、全排列 中等
题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
题解
回溯
js
var permute = function(nums) {
const used = new Array(nums.length).fill(false);
const result = [];
const backtrack = (path) => {
if(path.length === nums.length) {
result.push([...path]);
}
for(let i = 0; i < nums.length; i++) {
if(!used[i]) {
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
used[i] = false;
}
}
}
backtrack([]);
return result;
};十九、子集 中等
题目
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的 子集 （幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
题解
一、递归和回溯
js
function subsets(nums) {
const result = [[]]; // 初始化结果集，包含空集
const backtrack = (start, subset) => {
for (let i = start; i < nums.length; i++) {
// 创建新的子集，加入当前元素
const newSubset = [...subset, nums[i]];
result.push(newSubset);
// 继续递归探索包含当前元素的后续子集情况
backtrack(i + 1, newSubset);
}
};
backtrack(0, []);
return result;
}二、迭代法实现子集枚举
记原序列中元素的总数为 n。原序列中的每个数字 a i 的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 a i 是否在子集中。例如，n=3 ，a={5,2,9} 时：
0/1 序列 子集 0/1 序列对应的二进制数
000 {} 0
001 {9} 1
010 {2} 2
011 {2,9} 3
100 {5} 4
101 {5,9} 5
110 {5,2} 6
111 {5,2,9} 7
可以发现 0/1 序列对应的二进制数正好从 0 到 2 ^ n −1。我们可以枚举 mask∈[0,2 ^ n −1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2 ^ n 个 mask，我们也就能构造出所有的子集。
js
var subsets = function(nums) {
const n = nums.length;
const result = [];
for(let i = 0; i < (1 << n); i++) {
const sub = [];
for(let j = 0; j < n; j++) {
if(i & (1 << j)) {
sub.push(nums[j])
}
}
result.push(sub);
}
return result;
};二十、电话号码的字母组合 中等
题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
题解
映射+递归
js
var letterCombinations = function (digits) {
const map = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z'],
}
let res = map[digits[0]] || [];
digits = digits.slice(1);
const backtrack = (str) => {
if (str.length === 0) {
return;
}
const arr = map[str[0]];
const newArr = [];
for(let i = 0; i < res.length; i++) {
for(let j = 0; j < arr.length; j++) {
const temp = [];
temp.push(res[i]);
temp.push(arr[j]);
newArr.push(temp.join(''));
}
}
res = newArr;
backtrack(str.slice(1))
}
backtrack(digits);
return res;
};二十一、组合综合 中等
题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
题解
一、回溯
js
var combinationSum = function (candidates, target) {
candidates.sort((a, b) => a - b);
const res = [];
const backtrack = (index, sum, currentArr) => {
for (let i = index; i < candidates.length; i++) {
const nextArr = [...currentArr, candidates[i]]
if(candidates[i] + sum > target) break;
if (candidates[i] + sum === target) {
res.push(nextArr);
break;
} else {
backtrack(i, sum + candidates[i], nextArr);
}
}
}
backtrack(0, 0, [])
return res;
};二十二、括号生成 中等
题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
题解
回溯
js
var generateParenthesis = function(n) {
const result = [];
const backtrack = (left, right, arr) => {
// 当左右括号都使用完n对时，得到有效括号组合，加入结果数组
if (left === n && right === n) {
result.push(arr.join(''));
return;
}
if (left < n) {
arr.push('(');
backtrack(left + 1, right, arr);
arr.pop(); // 回溯，撤销添加 '(' 的操作
}
if (right < left) {
arr.push(')');
backtrack(left, right + 1, arr);
arr.pop(); // 回溯，撤销添加 ')' 的操作
}
};
backtrack(0, 0, []);
return result;
};二十三、单词搜索 中等
题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
题解
递归
js
var exist = function (board, word) {
if (board.length === 0 || word.length === 0) {
return false;
}
const rowCount = board.length;
const colCount = board[0].length;
const start = word[0];
const startPos = [];
// 简化查找首字符起始位置的逻辑，使用单层循环
for (let row = 0; row < rowCount; row++) {
for (let col = 0; col < colCount; col++) {
if (board[row][col] === start) {
if(word.length === 1) {
return true;
}
startPos.push([row, col]);
}
}
}
const visited = new Array(rowCount).fill(0).map(() => new Array(colCount).fill(false));
const check = (row, col, index) => {
if(index === word.length) {
return true;
}
if (row <= -1 || col <= -1 || row === rowCount || col === colCount || visited[row][col] || board[row][col] !== word[index]) {
return false;
}
visited[row][col] = true;
const result = check(row + 1, col, index + 1) ||
check(row - 1, col, index + 1) ||
check(row, col + 1, index + 1) ||
check(row, col - 1, index + 1);
visited[row][col] = false;
return result;
}
let flag = false;
for (let i = 0; i < startPos.length &&!flag; i++) {
flag = check(startPos[i][0], startPos[i][1], 0);
if(flag) {
break;
}
}
return flag
};二十四、分割回文串 中等
题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
题解
递归
js
var isPalindrome = function (s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] === s[right]) {
left++;
right--;
} else {
return false;
}
}
return true;
};
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function (s) {
const result = [];
const split = (index, arr) => {
if (index === s.length) {
result.push([...arr])
return;
}
for (let i = index; i < s.length; i++) {
const str = s.slice(index, i + 1);
if (isPalindrome(str)) {
arr.push(str);
split(i + 1, arr);
arr.pop();
}
}
}
split(0, []);
return result;
};二十五、搜索插入位置 简单
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
题解
二分查找
js
var searchInsert = function(nums, target) {
let left = 0, right = nums.length - 1, ans = 0;
while (left <= right) {
ans = Math.floor((left + right) / 2);
if(nums[ans] === target) {
return ans;
}
if(nums[ans] > target) {
right = ans - 1;
} else {
left = ans + 1;
}
}
if(nums[ans] < target) {
return ans + 1;
}
return ans;
};二十六、四数之和 中等
题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
题解
排序 + 双指针
与三数之和类似。可以剪枝优化时间复杂度。
js
var fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
if(nums.length < 4) {
return [];
}
const ans = [];
for(let i = 0; i < nums.length - 3; i++) {
if(i > 0 && nums[i] === nums[i - 1]) {
continue;
}
if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if(nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
continue;
}
const sum = target - nums[i];
for(let j = i + 1; j < nums.length - 2; j++) {
if(j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if(nums[i] + nums[j] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
continue;
}
let left = j + 1, right = nums.length - 1;
while (left < right) {
const threeSum = nums[j] + nums[left] + nums[right];
if(threeSum === sum) {
ans.push([nums[i], nums[j], nums[left], nums[right]]);
left++;
right--;
while (nums[left] === nums[left - 1] && left < right) {
left++;
}
while (nums[right] === nums[right + 1] && left < right) {
right--;
}
} else if(threeSum < sum){
left++;
} else {
right--;
}
}
}
}
return ans;
};二十七、最小栈 中等
题目
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
题解
辅助栈
设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
js
var MinStack = function() {
this.stack = [];
this.minStack = [Infinity];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], val));
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop();
this.minStack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.minStack[this.minStack.length - 1];
};二十八、最长回文子串 中等
题目
给你一个字符串 s，找到 s 中最长的 回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
题解
一、中心扩展法
js
var longestPalindrome = function (s) {
if (s.length < 2) {
return s;
}
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
// 以单字符为中心扩展
let len1 = expandAroundCenter(s, i, i);
// 以相邻两个字符的间隙为中心扩展
let len2 = expandAroundCenter(s, i, i + 1);
let len = Math.max(len1, len2);
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.slice(start, end + 1);
};
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}二十九、每日温度 中等
题目
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
题解
单调栈
js
var dailyTemperatures = function (temperatures) {
const ans = new Array(temperatures.length).fill(0);
const stack = [0];
for (let i = 1; i < temperatures.length; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
ans[stack[stack.length - 1]] = i - stack[stack.length - 1];
stack.pop();
}
stack.push(i);
}
return ans;
};三十、跳跃游戏 中等
题目
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
题解
贪心
我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。
js
var canJump = function (nums) {
let max = 0;
for(let i = 0 ; i < nums.length; i++) {
if(max >= nums.length - 1) {
return true;
}
if(max >= i) {
max = Math.max(max, i + nums[i]);
}
}
return false;
};三十一、跳跃游戏 中等
题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
题解
一、动态规划
dp[i] 表示到达 i 处需要的最小跳跃数;
js
var jump = function (nums) {
const dp = new Array(nums.length).fill(Infinity);
dp[0] = 0;
let index = 0;
for (let i = 0; i < nums.length; i++) {
const max = i + nums[i];
for (let j = index; j <= max && j < nums.length; j++) {
dp[j] = Math.min(1 + dp[i], dp[j]);
if(j >= nums.length - 1) {
break;
}
}
if(max >= nums.length - 1) {
break;
}
index = max + 1;
}
return dp[nums.length - 1];
};二、正向查找
维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
js
var jump = function (nums) {
let step = 0, end = 0, maxPos = 0;
for (let i = 0; i < nums.length - 1; i++) {
maxPos = Math.max(maxPos, i + nums[i]);
if(i === end) {
step++;
end = maxPos;
}
}
return step;
};三十二、划分字母区间 中等
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
题解
一、贪心分组
代码按字符出现情况分割字符串s。先统计各字符频次，遍历s，依字符增减情况判断分组，无剩余字符时记录分组长度。
js
var partitionLabels = function(s) {
const charMap = new Map();
const existSet = new Set();
for(let char of s) {
charMap.set(char, (charMap.get(char) || 0) + 1);
}
let index = 0;
let str = '';
let ans = [];
while (index < s.length) {
const currentChar = s[index]
str += currentChar;
existSet.add(currentChar);
charMap.set(currentChar, charMap.get(currentChar) - 1);
existSet.forEach((char) => {
if(charMap.get(char) === 0) {
existSet.delete(char);
}
})
if(existSet.size === 0) {
ans.push(str.length);
str = '';
}
index++;
}
return ans;
};二、贪心
寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的
js
var partitionLabels = function(s) {
const lastIndex = new Array(26);
const ans = [];
const charCodeA = 'a'.charCodeAt(0);
for(let i = 0; i < s.length; i++) {
lastIndex[s[i].charCodeAt(0) - charCodeA] = i;
}
let currentCount = 0, end = 0;
for(let i = 0; i < s.length; i++) {
currentCount++;
end = Math.max(end, lastIndex[s[i].charCodeAt(0) - charCodeA])
if(i >= end) {
ans.push(currentCount);
currentCount = 0;
}
}
return ans;
};