今天继续整理hot100题。
目录
10、有效的括号
题目内容
给定一个只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
?
示例 1：
输入：s = "()"
输出：true
示例?2：
输入：s = "()[]{}"
输出：true
示例?3：
输入：s = "(]"
输出：false
题解
一般思路，栈顶元素匹配即可。?
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
const arr = [];
for (let i = 0; i < s.length; i++) {
switch (s[i]) {
case "(":
arr.push(s[i]);
break;
case "{":
arr.push(s[i]);
break;
case "[":
arr.push(s[i]);
break;
case ")":
if (arr.pop() !== "(") {
return false;
}
break;
case "}":
if (arr.pop() !== "{") {
return false;
}
break;
case "]":
if (arr.pop() !== "[") {
return false;
}
break;
default:
return false;
}
}
if (arr.length > 0) {
return false;
}
return true;
};
11、合并两个有序链表
题目内容
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。?
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
?
题解
一般思路，直接按照顺序遍历添加即可。?
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
let res = null;
if (list1.val <= list2.val) {
res = list1;
list1 = list1.next;
} else {
res = list2;
list2 = list2.next;
}
let pos = res;
while (list1 && list2) {
if (list1.val <= list2.val) {
pos.next = list1;
list1 = list1.next;
} else {
pos.next = list2;
list2 = list2.next;
}
pos = pos.next;
}
if (list1) {
pos.next = list1;
}
if (list2) {
pos.next = list2;
}
return res;
};12、括号生成
题目内容
数字 n?代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
?
题解
容易观察到，如果想得到匹配的字符串，左括号的数量一定要>=右括号的数量，那么递归解决即可。注意边界条件，left和right最多是等于0，绝不能小于0。而等于0时，一定要返回一个包含空字符串的数组，这个是最根本的字符串，否则将无法得到任何一个字符串。
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
return getStrings(n, n);
};
// 传入左括号和右括号的个数
function getStrings(left, right) {
let arr = [];
if (left < 0 || right < 0) {
return arr;
}
if (left === right) {
if (left === 0) {
arr.push("");
} else {
// 此时只能放入左括号
let sub = getStrings(left - 1, right);
arr = arr.concat(sub.map((item) => "(" + item));
}
} else if (left < right) {
// 此时可以放入左括号，也可以放入右括号
let sub1 = getStrings(left - 1, right);
arr = arr.concat(sub1.map((item) => "(" + item));
let sub2 = getStrings(left, right - 1);
arr = arr.concat(sub2.map((item) => ")" + item));
}
return arr;
}13、下一个排列
题目内容
整数数组的一个 排列??就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
?
题解
这道题需要仔细观察规律，花费了我一定的时间。我的具体思路如下：
首先研究一下什么叫按字典顺序排列。简单来说，就是让整个数字最小限度地增大，就是下一个排列。
因此，如果最后两位是升序的数字，直接交换它们，就可以得到下一个排列。
否则，说明从后往前是先变大，直到达到一个转折点，在转折点之前是从后往前递减的。如果这个转折点是0，说明，整个数组就是从前往后递减的，那么直接反转数组即可。
如果转折点不是0，说明我们可以根据转折点前后的数字做一些文章。如果想要让数字变大，由于转折点及其后面的数字都是从前往后递减的，交换它们并不能使数字变大。所以，我们考虑，转折点前面的第一个数字p，和，转折点及其后面的数字。在转折点及其后面的数字中，从后往前，找到第一个比p大的数字q，q一定是比p大且最小的数字。
然后，p和q交换位置，这样数字就一定会变大。要想使变动最小，则需要把q后面所有数字按照升序排列，拼接在q的后面即可。这样得到的，就是正确的答案。
注意，力扣不支持数组的concat方法，所以只能使用push(...ls)。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
// 12345 < 12354 < 12435 < 12453 < 12534 < 12543 < 13245 < 13254 < 13425
// 考察最后两位
let n = nums.length;
if (nums[n - 2] < nums[n - 1]) {
// 如果最后两位是升序，则直接交换即可
let temp = nums[n - 1];
nums[n - 1] = nums[n - 2];
nums[n - 2] = temp;
} else {
// 否则，说明最后两位是降序
// 需要找到第一个转折点
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i < 0) {
// 说明整个数组都是降序，直接倒过来成升序即可
nums.reverse();
} else {
// 找到第一个转折点是i+1处
// 应该把从后往前数，第一个比nums[i]大的放在nums[i]处，其余的升序放在后面
let j = n - 1;
while (j >= i + 1 && nums[j] <= nums[i]) {
j--;
}
let temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
// i后面的升序排列
let tempList = nums.slice(i + 1, n);
tempList.sort((a, b) => a - b);
nums.splice(i + 1);
nums.push(...tempList);
}
}
};
官方思路更加高效，有兴趣可以去看看。?
13、最长有效括号
题目内容
给你一个只包含 '('?和 ')'?的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
?
题解
这道题很难！！！
一开始，我是想使用类似map记录前n项和的方法来解，但是发现无法控制字符串中间的内容是否合法。后来仔细想了想，可以使用动态规划。
具体思路就是，用数组arr记录以第i个字符结尾，符合条件的最长子串。从前往后判断，如果是左括号或者第一个字符，则arr[i]记为0。如果是有括号，再分两种情况：
如果第i-1个字符是左括号，那么直接令arr[i]=arr[i-2]+2，因为这样就可以把前面的衔接上了。当然，如果i-2<0，arr[i]=2。
如果第i-1个字符是右括号，这样思考。到第i-1个字符，它应该组成了arr[i-1]这么长的子串。我们需要越过这些字符：从第i-1个字符往前推arr[i-1]个字符，这样就可以跳过以第i-1个字符结尾的字符串，看前面的字符是否能够与第i个字符配对。这个字符就是第i-1-arr[i-1]个字符，如果它是左括号，那么就可以跟第i个字符组成长度为arr[i-1]+2的合法字符串。那么，arr[i]=arr[i-1-arr[i-1]-1]+arr[i-1]+2。
在这里要注意边界情况。如果i-1-arr[i-1]<0，或者i-1-arr[i-1]处是右括号，说明没有左括号与第i个字符配对，所以arr[i]=0。或者，如果i-1-arr[i-1]-1<0，那么说明第i-1-arr[i-1]个字符就是第一个字符，那么arr[i]就直接等于arr[i-1]+2。
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
// 动态规划
let n = s.length;
// 以第i个字符结尾的最长子串长度
const arr = new Array(n).fill(0);
let res = 0;
for (let i = 0; i < n; i++) {
if (i === 0 || s[i] === "(") {
arr[i] = 0;
} else {
if (s[i - 1] === "(") {
arr[i] = i - 2 >= 0 ? arr[i - 2] + 2 : 2;
} else {
// 第i-1处是右括号，其组成的子串长度是arr[i-1]
// 那么，要看i-1往左走arr[i-1]步的字符是不是左括号
if (i - 1 - arr[i - 1] >= 0 && s[i - 1 - arr[i - 1]] === "(") {
arr[i] =
i - 1 - arr[i - 1] - 1 >= 0
? arr[i - 1 - arr[i - 1] - 1] + arr[i - 1] + 2
: arr[i - 1] + 2;
}
}
}
res = Math.max(res, arr[i]);
}
return res;
};14、搜索旋转排序数组
题目内容
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为?[4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回?-1?。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例?2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
?
题解
说到底，这还是一个二分查找。只是需要分清楚，target和middle各在哪个部分，从而根据target和nums[middle]以及它们的位置去改变left和right的值。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
let n = nums.length;
let left = 0,
right = n - 1;
// 看target在左半边还是右半边，左true右false
let flag = target > nums[n - 1] ? true : false;
while (left <= right) {
let middle = parseInt((left + right) / 2);
if (nums[middle] === target) {
return middle;
}
if (flag) {
// 在左半边
if (nums[middle] < target) {
// 如果nums[middle]比target小，那么middle可能在左半边，也可能在右半边
if (nums[middle] <= nums[n - 1]) {
// middle在右半边
right = middle - 1;
} else {
// middle在左半边
left = middle + 1;
}
} else {
// 如果nums[middle]比target大，那么middle一定中左半边
right = middle - 1;
}
} else {
// 在右半边
if (nums[middle] < target) {
// 如果nums[middle]比target小，那么middle一定在右半边
left = middle + 1;
} else {
// 如果nums[middle]比target大，那么middle可能在左半边，也可能在右半边
if (nums[middle] <= nums[n - 1]) {
// middle在右半边
right = middle - 1;
} else {
// middle在左半边
left = middle + 1;
}
}
}
}
return -1;
};15、在排序数组中查找元素的第一个和最后一个位置
题目内容
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回?[-1, -1]。
你必须设计并实现时间复杂度为?O(log n)?的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例?2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
?
题解
我的想法很粗暴，找到一个target的位置，往两边跑，找到所有target即可。。。
官方思路是先找第一个等于target的位置，再使用同样的算法找到第一个大于target的位置。有兴趣可以再试试。?
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let n = nums.length;
let left = 0,
right = n - 1;
while (left <= right) {
let middle = parseInt((left + right) / 2);
if (nums[middle] === target) {
let l = middle - 1,
r = middle + 1;
while (true) {
if ((l < 0 || nums[l] !== target) && (r > n || nums[r] !== target)) {
break;
}
if (l >= 0 && nums[l] === target) {
l--;
}
if (r < n && nums[r] == target) {
r++;
}
}
return [l + 1, r - 1];
} else if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return [-1, -1];
};16、组合总和
题目内容
给你一个 无重复元素 的整数数组?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
输出: []
?
题解
典型的完全背包组合问题，外层遍历candidates，内层升序遍历target即可。
我有个疑问在于，dp[i]=dp[i].concat(tempList)是成功的，但之前验证过，力扣有时候不支持concat方法，这里为什么又可以了？此外，dp[i].push(...tempList)的结果是错的，为什么呢？它与concat理论上应该是一致的才对呀？？？?
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
// 完全背包问题，组合问题
// 外层循环nums，内层升序遍历target
let dp = new Array(target + 1).fill([]);
dp[0] = [[]];
for (let candidate of candidates) {
for (let i = 1; i <= target; i++) {
if (i >= candidate) {
let tempList = JSON.parse(JSON.stringify(dp[i - candidate]));
tempList = tempList.map((item) => {
item.push(candidate);
return item;
});
// dp[i].push(...tempList);
dp[i] = dp[i].concat(tempList);
}
}
}
return dp[target];
};17、全排列
题目内容
给定一个不含重复数字的数组 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]]
?
题解
一直想写一下全排列算法，直到今天遇到了这道题。
我的思路就是，使用递归，每次取一个还没有取过的数字。这就需要，使用一个数组visited来记录是否取过该位置的数字，还要使用step记录这次递归是取第几个数字。当step===nums.length时，说明取到最后一个数字，只需要把没有取过的那个数字放入结果数组，返回即可。
否则，说明不是最后一个数字。那么，先找出所有没取过的数字们，记为raw。依次取raw中的数字，记为当前数字，并在visited中标记该数字已经取过，然后递归进行第step+1次调用。这样，得到子数组，然后在子数组的每个数组最前面，加入当前数字。再把刚刚标记过的当前数字置为没有取过，再取下一个当前数字即可。
最终，通过递归，得到了正确答案。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
// 是否取过该数字
let visited = new Array(n).fill(false);
return getRes(nums, visited, 1);
};
// 取第step个数字
function getRes(nums, visited, step) {
let res = [];
if (step === nums.length) {
// 取最后一个数字
let pos = visited.findIndex((item) => !item);
res.push([nums[pos]]);
return res;
}
// 找到还没有取过的数字
let raw = [];
for (let i = 0; i < visited.length; i++) {
if (!visited[i]) {
raw.push(i);
}
}
for (let pos of raw) {
visited[pos] = true;
let subRes = getRes(nums, visited, step + 1);
let temp = subRes.map((item) => {
item.unshift(nums[pos]);
return item;
});
res = res.concat(temp);
visited[pos] = false;
}
return res;
}?
18、旋转图像
题目内容
给定一个 n?×?n 的二维矩阵?matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：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]]
题解
这道题不是很难，只需要找到前后数组的映射关系即可。
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
const copy = JSON.parse(JSON.stringify(matrix));
const n = matrix.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[i][j] = copy[n - 1 - j][i];
}
}
};19、字母异位词分组
题目内容
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
题解
这道题我没有什么好办法。官方题解给出了两种思路：第一个是对每个字符串进行排序，把排序结果相同的放入同一个集合里面，这个比较简单，不必多说。
第二个是，记录每个字符串中，26个字母出现的次数，存为长度26的数组。此时，JavaScript语言特性帮了大忙（在题解后面细说）。若把一个数组作为普通Object对象的键，那么会先调用这个数组的toString方法，形成一个字符串，然后作为键，存入对象。只有两个完全相同的数组的toString才是完全相同的，因此，使用数组作为对象的键可以保证唯一性！
这样就可以，把符合某数组的字符串存入该数组对应的集合中，最终直接返回对象的values即可。
这道题告诉我们，优秀的语言特性及其原理是很重要的！
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
// 统计每个字符串中，每个字母出现的次数，保存在长度为26的数组中
// 记录每种出现次数对应的字符串
const map = {};
for (let str of strs) {
const arr = new Array(26).fill(0);
for (let i = 0; i < str.length; i++) {
arr[str[i].charCodeAt() - "a".charCodeAt()]++;
}
if (map[arr]) {
map[arr].push(str);
} else {
map[arr] = [str];
}
}
return Object.values(map);
};这里说一下为什么数组可以作为对象的键。
我们知道，JavaScript的普通Object对象的键，只能是字符串或Symbol。因此，其他类型作为键的时候，都会转化为字符串。比如obj={a:1}，实际上是obj={'a':1}。同样，其他类型作为键会是这样：
const arr1 = [1, 2],
arr2 = [1, 2];
const map = {};
map[arr1] = 1;
function f1() {}
function f2() {}
map[f1] = 2;
map[f2] = 3;
const obj = { a: 1 };
map[obj] = 4;
console.log(Object.keys(map));
// [ '1,2', 'function f1() {}', 'function f2() {}', '[object Object]' ]对于数组、函数和Object对象，作为对象的键时，都会先调用自己的toString转化成字符串。?不同的数组和函数，toString的结果都不一样，因此具有唯一性。但Object对象，其toString结果都是'[object Object]'，因此，不论使用多少个Object对象作为键，都是操作'[object Object]'这个字符串的。
20、最大子数组和
题目内容
给你一个整数数组 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
题解
最基础的动态规划了，没什么可说的。?
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let n = nums.length;
// 到第i个数字为止，最大连续数组和
const arr = new Array(n).fill(0);
let res = -Infinity;
for (let i = 0; i < n; i++) {
if (i === 0) {
arr[0] = nums[0];
} else {
if (arr[i - 1] >= 0) {
arr[i] = nums[i] + arr[i - 1];
} else {
arr[i] = nums[i];
}
}
res = Math.max(res, arr[i]);
}
return res;
};