算法题
两数之和
给定一个整数数组 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]
以下是使用 JavaScript 实现的代码,解决“两数之和”问题:
代码实现:
function twoSum(nums, target) {
const numToIndex = new Map(); // 创建一个哈希表(使用 Map)
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]; // 计算差值
if (numToIndex.has(complement)) { // 如果差值在哈希表中
return [numToIndex.get(complement), i]; // 返回两个索引
}
numToIndex.set(nums[i], i); // 将当前元素及其索引存入哈希表
}
return []; // 如果没有找到,返回空数组(根据题目描述,这种情况不会发生)
}
示例运行:
const nums1 = [2, 7, 11, 15];
const target1 = 9;
console.log(twoSum(nums1, target1)); // 输出: [0, 1]
const nums2 = [3, 2, 4];
const target2 = 6;
console.log(twoSum(nums2, target2)); // 输出: [1, 2]
const nums3 = [3, 3];
const target3 = 6;
console.log(twoSum(nums3, target3)); // 输出: [0, 1]
代码说明:
- 哈希表:使用
Map
来存储数组中的元素及其索引。 - 遍历数组:通过
for
循环遍历数组,计算每个元素与目标值的差值complement
。 - 查找差值:检查差值是否在哈希表中,如果在,则返回对应的索引;否则将当前元素及其索引存入哈希表。
- 返回结果:如果找到满足条件的两个数,返回它们的索引;否则返回空数组。
复杂度分析:
- 时间复杂度:O(n),其中 n 是数组的长度。我们只需要遍历一次数组。
- 空间复杂度:O(n),哈希表在最坏情况下需要存储 n 个元素。
这个方法在 JavaScript 中同样高效且易于理解,适用于大多数情况。
详解
创建哈希表并将数组中的元素和索引存储在其中,是为了快速查找某个元素是否存在于数组中,并获取其索引。这是解决“两数之和”问题的关键步骤。下面详细解释为什么需要这样做,以及它是如何工作的。
为什么需要哈希表?
在“两数之和”问题中,我们需要找到两个数,使得它们的和等于目标值 target
。假设当前遍历到的元素是 nums[i]
,那么我们需要检查数组中是否存在另一个元素 complement = target - nums[i]
。
如果没有哈希表,我们需要在数组中逐个查找 complement
,这样的时间复杂度是 O(n)。对于每个元素,都需要遍历一次数组,总时间复杂度会达到 O(n²),效率很低。
而哈希表的作用是:
快速查找:哈希表可以在 O(1) 的时间内判断某个值是否存在。
存储索引:哈希表不仅可以存储元素的值,还可以存储其索引,方便直接返回结果。
哈希表是如何存储元素和索引的?
在代码中,哈希表(Map
或对象)的键是数组中的元素,值是该元素的索引。例如:
const numToIndex = new Map();
当我们遍历数组时:
对于当前元素
nums[i]
,计算complement = target - nums[i]
。检查
complement
是否在哈希表中:- 如果在,说明之前已经遍历过
complement
,直接返回它的索引和当前索引i
。 - 如果不在,将当前元素
nums[i]
及其索引i
存入哈希表。
- 如果在,说明之前已经遍历过
具体例子
假设数组是 nums = [2, 7, 11, 15]
,目标值是 target = 9
。
遍历过程:
第一次遍历(
i = 0
,nums[i] = 2
):- 计算
complement = 9 - 2 = 7
。 - 检查哈希表,发现
7
不存在。 - 将
2
和它的索引0
存入哈希表:numToIndex = {2: 0}
。
- 计算
第二次遍历(
i = 1
,nums[i] = 7
):- 计算
complement = 9 - 7 = 2
。 - 检查哈希表,发现
2
存在,且它的索引是0
。 - 返回结果
[0, 1]
。
- 计算
为什么不能提前存储所有元素?
如果我们在遍历之前就将所有元素和索引存入哈希表,那么在查找 complement
时,可能会找到当前元素本身。例如:
nums = [3, 3], target = 6
如果提前存储所有元素,哈希表会是 {3: 1}
(后面的 3
会覆盖前面的 3
)。当遍历到第一个 3
时,计算 complement = 6 - 3 = 3
,发现 3
在哈希表中,但它的索引是 1
,这会导致返回 [1, 0]
,而实际上正确答案是 [0, 1]
。
为了避免这种情况,我们采用边遍历边存储的方式:
- 每次只存储当前元素之前的元素,确保不会重复使用当前元素。
总结
哈希表的作用是:
- 快速查找:判断
complement
是否存在于数组中。 - 存储索引:方便直接返回结果。
- 避免重复使用元素:通过边遍历边存储的方式,确保不会重复使用当前元素。
通过这种方式,我们可以在 O(n) 的时间复杂度内解决问题,效率非常高。
两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
示例 2:
输入:l1 = [0], l2 = [0]
输出:[0]
示例 3:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
这个问题是经典的“两数相加”问题,涉及链表的操作。我们需要将两个逆序存储的链表表示的数字相加,并返回一个新的链表表示结果。以下是详细的解决思路和代码实现。
解决思路
- 逆序存储:链表中的数字是逆序存储的,例如
[2, 4, 3]
表示数字342
。 - 逐位相加:从链表的头部开始,逐位相加,同时考虑进位。
- 处理进位:如果某一位相加的结果大于等于 10,则需要将进位加到下一位的计算中。
- 创建新链表:将每一位的计算结果存储到新链表中。
- 边界条件:如果两个链表的长度不同,或者最后还有进位,需要额外处理。
代码实现 以下是 JavaScript 的实现:
- 辅助函数:将数组转换为链表
function arrayToList(arr) {
let dummyHead = new ListNode(0); // 虚拟头节点
let current = dummyHead;
for (const num of arr) {
current.next = new ListNode(num); // 创建新节点
current = current.next; // 移动指针
}
return dummyHead.next; // 返回链表的头节点
}
- 主函数:两数相加
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
function addTwoNumbers(l1, l2) {
let dummyHead = new ListNode(0); // 虚拟头节点
let current = dummyHead; // 当前节点
let carry = 0; // 进位
// 遍历两个链表
while (l1 !== null || l2 !== null) {
// 获取当前节点的值,如果链表已经遍历完,则值为 0
const x = l1 !== null ? l1.val : 0;
const y = l2 !== null ? l2.val : 0;
// 计算当前位的和(包括进位)
const sum = x + y + carry;
carry = Math.floor(sum / 10); // 计算新的进位
current.next = new ListNode(sum % 10); // 创建新节点
current = current.next; // 移动当前节点
// 移动链表指针
if (l1 !== null) l1 = l1.next;
if (l2 !== null) l2 = l2.next;
}
// 如果最后还有进位,添加一个新节点
if (carry > 0) {
current.next = new ListNode(carry);
}
return dummyHead.next; // 返回结果链表的头节点
}
- 辅助函数:将链表转换为数组(方便输出)
function listToArray(head) {
const result = [];
while (head !== null) {
result.push(head.val); // 将节点的值存入数组
head = head.next; // 移动指针
}
return result;
}
示例运行
示例 1:
const l1 = arrayToList([2, 4, 3]); // 数组转换为链表
const l2 = arrayToList([5, 6, 4]); // 数组转换为链表
const result = addTwoNumbers(l1, l2); // 计算结果
console.log(listToArray(result)); // 输出: [7, 0, 8]
示例 2:
const l1 = arrayToList([0]); // 数组转换为链表
const l2 = arrayToList([0]); // 数组转换为链表
const result = addTwoNumbers(l1, l2); // 计算结果
console.log(listToArray(result)); // 输出: [0]
示例 3:
const l1 = arrayToList([9, 9, 9, 9, 9, 9, 9]); // 数组转换为链表
const l2 = arrayToList([9, 9, 9, 9]); // 数组转换为链表
const result = addTwoNumbers(l1, l2); // 计算结果
console.log(listToArray(result)); // 输出: [8, 9, 9, 9, 0, 0, 0, 1]
代码解析
- 虚拟头节点:使用
dummyHead
作为虚拟头节点,方便处理链表的头部。 - 进位处理:通过
carry
变量记录进位,并在每次计算时更新。 - 链表遍历:使用
while
循环遍历两个链表,直到两个链表都遍历完。 - 结果链表:通过
current.next
创建新节点,并将结果存储到新链表中。 - 边界条件:如果最后还有进位,需要额外添加一个新节点。
复杂度分析
- 时间复杂度:O(max(m, n)),其中
m
和n
分别是两个链表的长度。 - 空间复杂度:O(max(m, n)),结果链表的长度最多为
max(m, n) + 1
。
这种方法既保持了算法的高效性,又提高了代码的可读性和易用性。
链表和数组是两种常见的数据结构,它们在存储和操作数据时有不同的特点和适用场景。下面我会详细解释链表的概念,以及为什么在这个问题中需要将数组处理成链表。
什么是链表?
链表(Linked List)是一种线性数据结构,由一系列节点(Node)组成。每个节点包含两部分:
- 数据域:存储数据(在这个问题中,存储的是数字的一位)。
- 指针域:指向下一个节点的地址(在 JavaScript 中,通常用
next
表示)。
链表的最后一个节点的 next
指向 null
,表示链表的结束。
链表的结构
class ListNode {
constructor(val, next = null) {
this.val = val; // 数据域
this.next = next; // 指针域
}
}
示例
假设有一个链表 [2, 4, 3]
,它的结构如下:
2 -> 4 -> 3 -> null
- 第一个节点的值是
2
,next
指向第二个节点。 - 第二个节点的值是
4
,next
指向第三个节点。 - 第三个节点的值是
3
,next
指向null
,表示链表结束。
链表 vs 数组
链表和数组的主要区别在于它们的存储方式和操作效率:
特性 | 数组 | 链表 |
---|---|---|
存储方式 | 连续的内存空间 | 非连续的内存空间(通过指针连接) |
访问元素 | O(1)(通过索引直接访问) | O(n)(需要从头遍历) |
插入/删除元素 | O(n)(需要移动其他元素) | O(1)(只需修改指针) |
空间灵活性 | 固定大小(需要预先分配内存) | 动态大小(按需分配内存) |
为什么这个问题要用链表?
在这个问题中,链表的使用是为了模拟数字的存储方式。题目要求:
- 逆序存储:数字的每一位是逆序存储在链表中的。例如,数字
342
存储为2 -> 4 -> 3 -> null
。 - 动态长度:链表的长度可以动态变化,适合处理任意长度的数字。
- 逐位相加:链表的节点结构非常适合逐位操作(从低位到高位相加)。
如果直接使用数组,虽然可以解决问题,但链表的特性更符合题目的描述,并且可以更好地模拟数字的逐位操作。
为什么需要将数组转换为链表?
在这个问题中,输入是以数组的形式给出的(例如 [2, 4, 3]
),但链表的操作更方便逐位相加。因此,我们需要将数组转换为链表:
- 输入格式:题目通常以数组的形式给出输入,因为数组更直观且易于测试。
- 链表操作:链表的节点结构更适合逐位相加和进位处理。
- 代码实现:将数组转换为链表后,可以直接使用链表的操作逻辑。
如果不使用链表,直接用数组可以吗?
可以,但需要额外处理逆序和进位的问题。以下是直接用数组实现的思路:
- 逆序数组:将数组反转,从低位到高位相加。
- 逐位相加:遍历数组,逐位相加并处理进位。
- 结果反转:将结果数组反转,得到最终答案。
示例代码(直接用数组实现):
function addTwoNumbersArrays(arr1, arr2) {
let result = [];
let carry = 0;
let i = 0;
// 逐位相加
while (i < arr1.length || i < arr2.length || carry > 0) {
const x = i < arr1.length ? arr1[i] : 0;
const y = i < arr2.length ? arr2[i] : 0;
const sum = x + y + carry;
result.push(sum % 10); // 当前位的值
carry = Math.floor(sum / 10); // 进位
i++;
}
return result;
}
// 示例
const arr1 = [2, 4, 3]; // 342
const arr2 = [5, 6, 4]; // 465
console.log(addTwoNumbersArrays(arr1, arr2)); // 输出: [7, 0, 8](表示 807)
- 链表:适合动态长度和逐位操作,符合题目的要求。
- 数组:可以直接操作,但需要额外处理逆序和进位。
- 转换原因:将数组转换为链表是为了更好地模拟数字的逐位相加过程。
如果你更喜欢直接用数组实现,也可以按照上述方法操作。链表的使用主要是为了更贴近题目的描述和数据结构的设计。
无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解法思路
要找到字符串中不包含重复字符的最长子串的长度,可以使用滑动窗口(Sliding Window)技术。滑动窗口是一种在数组或字符串中寻找满足特定条件的子数组或子串的高效方法。具体步骤如下:
- 初始化窗口和数据结构:使用两个指针(通常称为左指针和右指针)来表示当前窗口的左右边界。初始时,两个指针都指向字符串的开始位置。同时,使用一个哈希集合来记录当前窗口中的字符,以快速判断字符是否重复。
- 移动右指针:右指针逐个字符向右移动,将当前字符添加到哈希集合中。如果在添加时发现字符已存在于集合中,说明遇到了重复字符。
- 移动左指针:当遇到重复字符时,移动左指针,直到窗口中不再有重复字符为止。移动左指针时,从哈希集合中移除左指针指向的字符。
- 更新最长子串长度:在每次右指针移动后,检查当前窗口的大小是否大于已知的最大长度,如果是,则更新最大长度。
解决代码
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let charSet = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
};
代码解释
- 初始化:
charSet
是一个集合,用于存储当前窗口中的字符;left
指针初始化为 0,表示窗口的左边界;maxLength
用于记录最长子串的长度,初始化为 0。 - 滑动窗口:使用
right
指针遍历字符串。对于每个字符s[right]
,检查它是否已经在charSet
中:- 如果存在,则移动
left
指针,并从charSet
中移除s[left]
直到s[right]
不再存在于集合中。 - 将当前字符
s[right]
添加到charSet
中。
- 如果存在,则移动
- 更新最大长度:每次处理完
right
指针后,计算当前窗口的长度right - left + 1
,并与maxLength
比较,更新maxLength
为较大值。 - 返回结果:最终返回
maxLength
,即最长无重复字符子串的长度。
这种方法确保了在遍历字符串时,每个字符最多被访问两次(一次由 right
指针,一次由 left
指针),因此时间复杂度为 O(n),其中 n 是字符串的长度。空间复杂度为 O(min(m, n)),其中 m 是字符集的大小(即可能的不同字符数量)。
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
方法思路
要找到两个正序数组的中位数,并且要求时间复杂度为 O(log(m+n)),可以使用二分查找的方法。具体思路如下:
- 确保 nums1 是较短的数组:这样可以在较短的数组上进行二分查找,减少时间复杂度。
- 二分查找分割点:在较短的数组 nums1 中找到一个分割点 i,使得 nums1 和 nums2 的分割点 j 满足条件:i + j = (m + n + 1) / 2,并且 nums1[i-1] <= nums2[j] 和 nums2[j-1] <= nums1[i]。
- 处理边界情况:当分割点在数组的边界时,需要特殊处理,比如当 i=0 或 j=0 时。
- 计算中位数:根据数组长度的奇偶性,返回相应的中位数。
解决代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// 确保 nums1 是较短的数组
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
const totalLeft = Math.floor((m + n + 1) / 2);
let left = 0;
let right = m;
while (left <= right) {
const i = Math.floor((left + right) / 2);
const j = totalLeft - i;
const nums1LeftMax = i === 0 ? -Infinity : nums1[i - 1];
const nums1RightMin = i === m ? Infinity : nums1[i];
const nums2LeftMax = j === 0 ? -Infinity : nums2[j - 1];
const nums2RightMin = j === n ? Infinity : nums2[j];
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 找到正确的分割点
if ((m + n) % 2 === 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
}
} else if (nums1LeftMax > nums2RightMin) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0;
};
代码解释
- 确保 nums1 是较短的数组:通过交换数组,保证 nums1 的长度不超过 nums2,这样可以在较短的数组上进行二分查找,减少时间复杂度。
- 初始化变量:
m
和n
分别是两个数组的长度,totalLeft
是中位数左边的元素总数。 - 二分查找:在 nums1 上进行二分查找,找到合适的分割点
i
,使得 nums1 和 nums2 的分割点j
满足条件。 - 处理边界情况:当分割点
i
或j
在数组的边界时,使用Infinity
或-Infinity
来处理。 - 计算中位数:根据数组长度的奇偶性,返回相应的中位数。如果是奇数长度,返回左边最大值;如果是偶数长度,返回左边最大值和右边最小值的平均值。
这种方法确保了时间复杂度为 O(log(min(m, n))),满足题目要求。
最长回文子串
给你一个字符串 s,找到 s 中最长的 回文 子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
以下是使用JavaScript实现的最长回文子串查找的代码,采用中心扩展法,时间复杂度为O(n²),空间复杂度为O(1)。
代码实现
function longestPalindrome(s) {
if (s.length < 2) return s;
let start = 0;
let maxLength = 1;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
for (let i = 0; i < s.length; i++) {
const len1 = expandAroundCenter(i, i); // 奇数长度回文(如 "bab")
const len2 = expandAroundCenter(i, i + 1); // 偶数长度回文(如 "abba")
const currentMax = Math.max(len1, len2);
if (currentMax > maxLength) {
maxLength = currentMax;
start = i - Math.floor((maxLength - 1) / 2);
}
}
return s.substring(start, start + maxLength);
}
// 测试用例
console.log(longestPalindrome("babad")); // 输出 "bab" 或 "aba"
console.log(longestPalindrome("cbbd")); // 输出 "bb"
console.log(longestPalindrome("a")); // 输出 "a"
console.log(longestPalindrome("ac")); // 输出 "a" 或 "c"
console.log(longestPalindrome("aaaa")); // 输出 "aaaa"
代码解释
输入处理:
- 如果字符串长度小于2(空串或单字符),直接返回该字符串,因为其本身就是最长回文子串。
中心扩展函数
expandAroundCenter
:- 从给定的
left
和right
位置向两边扩展,直到字符不相等或越界。 - 返回当前回文子串的长度。
- 从给定的
遍历字符串:
- 对每个字符
i
,分别检查奇数长度和偶数长度的回文子串。 - 更新最长回文子串的起始位置
start
和长度maxLength
。
- 对每个字符
返回结果:
- 使用
substring
方法截取最长回文子串。
- 使用
复杂度分析
- 时间复杂度:O(n²),因为共有
2n-1
个可能的中心(每个字符和每两个字符之间的空隙),每个中心最多扩展O(n)
次。 - 空间复杂度:O(1),仅使用了常数个额外变量。
测试用例验证
输入 | 输出 | 说明 |
---|---|---|
"babad" | "bab" | 可以是"aba" |
"cbbd" | "bb" | 最长回文子串是"bb" |
"a" | "a" | 单字符本身就是回文 |
"ac" | "a" | 可以是"c" |
"aaaa" | "aaaa" | 整个字符串都是回文 |
这种方法高效且易于理解,适用于大多数情况下的最长回文子串查找问题。
整数反转
给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。
示例 1:
输入:x = 123
输出:321
示例 2:
输入:x = -123
输出:-321
示例 3:
输入:x = 120
输出:21
示例 4:
输入:x = 0
输出:0
方法思路
要反转一个32位有符号整数,需要注意以下几点:
- 处理符号:负数需要先转换为正数处理,反转后再恢复符号。
- 反转数字:通过循环取模和除法操作,逐步构建反转后的数字。
- 溢出检查:在每次构建新数字时,检查是否超出32位有符号整数的范围(即是否在[-2³¹, 2³¹ - 1]之间)。如果溢出,则返回0。
解决代码
function reverse(x) {
let reversed = 0;
const isNegative = x < 0;
x = Math.abs(x);
while (x > 0) {
const digit = x % 10;
reversed = reversed * 10 + digit;
x = Math.floor(x / 10);
// 检查溢出
if (reversed > Math.pow(2, 31) - 1) {
return 0;
}
}
return isNegative ? -reversed : reversed;
}
代码解释
- 初始化变量:
reversed
用于存储反转后的数字,isNegative
标记原始数字是否为负数。 - 处理绝对值:使用
Math.abs(x)
获取x
的绝对值,便于处理。 - 反转数字:
- 通过
x % 10
获取最后一位数字。 - 将
reversed
乘以10后加上该数字,实现数字反转。 - 通过
Math.floor(x / 10)
去掉x
的最后一位。
- 通过
- 溢出检查:每次更新
reversed
后,检查是否超过32位有符号整数的最大值(2³¹ - 1)。如果超过,直接返回0。 - 返回结果:根据原始数字的符号返回相应的反转结果。
这种方法确保在反转过程中实时检查溢出,符合题目要求,且时间复杂度为O(log(x)),空间复杂度为O(1)。
字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下:
空格:读入字符串并丢弃无用的前导空格(" ")
符号:检查下一个字符(假设还未到字符末尾)为 '-' 还是 '+'。如果两者都不存在,则假定结果为正。
转换:通过跳过前置零来读取该整数,直到遇到非数字字符或到达字符串的结尾。如果没有读取数字,则结果为0。
舍入:如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被舍入为 −231 ,大于 231 − 1 的整数应该被舍入为 231 − 1 。
返回整数作为最终结果。
示例 1:
输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
带下划线线的字符是所读的内容,插入符号是当前读入位置。
第 1 步:"42"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"42"(读入 "42") ^ 示例 2:
输入:s = " -042"
输出:-42
解释:
第 1 步:" -042"(读入前导空格,但忽视掉) ^ 第 2 步:" -042"(读入 '-' 字符,所以结果应该是负数) ^ 第 3 步:" -042"(读入 "042",在结果中忽略前导零) ^ 示例 3:
输入:s = "1337c0d3"
输出:1337
解释:
第 1 步:"1337c0d3"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"1337c0d3"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"1337c0d3"(读入 "1337";由于下一个字符不是一个数字,所以读入停止) ^ 示例 4:
输入:s = "0-1"
输出:0
解释:
第 1 步:"0-1" (当前没有读入字符,因为没有前导空格) ^ 第 2 步:"0-1" (当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"0-1" (读入 "0";由于下一个字符不是一个数字,所以读入停止) ^ 示例 5:
输入:s = "words and 987"
输出:0
解释:
读取在第一个非数字字符“w”处停止。
方法思路
实现 myAtoi
函数需要按照题目描述的步骤处理字符串:
- 去除前导空格:跳过字符串前面的所有空格字符。
- 处理符号位:检查接下来的字符是否是 '+' 或 '-',以确定最终数字的符号。
- 读取数字字符:从第一个非空格和非符号字符开始,连续读取数字字符,直到遇到非数字字符或字符串结束。
- 转换数字并处理溢出:将读取的数字字符转换为整数,并在转换过程中检查是否超出32位有符号整数的范围。如果超出,则返回相应的边界值。
解决代码
function myAtoi(s) {
let index = 0;
const n = s.length;
let sign = 1;
let result = 0;
const INT_MAX = Math.pow(2, 31) - 1;
const INT_MIN = -Math.pow(2, 31);
// 1. 跳过前导空格
while (index < n && s[index] === ' ') {
index++;
}
// 2. 处理符号位
if (index < n && (s[index] === '+' || s[index] === '-')) {
sign = s[index] === '-' ? -1 : 1;
index++;
}
// 3. 读取数字字符
while (index < n && s[index] >= '0' && s[index] <= '9') {
const digit = s[index] - '0';
// 检查溢出
if (result > Math.floor(INT_MAX / 10) ||
(result === Math.floor(INT_MAX / 10) && digit > INT_MAX % 10)) {
return sign === 1 ? INT_MAX : INT_MIN;
}
result = result * 10 + digit;
index++;
}
return sign * result;
}
代码解释
- 初始化变量:
index
用于遍历字符串,sign
存储数字的符号(默认为正),result
存储转换后的数字,INT_MAX
和INT_MIN
定义32位有符号整数的范围。 - 跳过前导空格:循环跳过字符串前面的所有空格字符。
- 处理符号位:检查当前字符是否是 '+' 或 '-',并相应地设置
sign
的值。 - 读取数字字符:循环读取连续的数字字符,并将其转换为整数。在每次转换时检查是否溢出:
- 如果
result
大于INT_MAX / 10
,或者等于INT_MAX / 10
且当前数字大于INT_MAX % 10
,则根据符号返回INT_MAX
或INT_MIN
。
- 如果
- 返回结果:将最终结果乘以符号位后返回。
这种方法确保在转换过程中实时检查溢出,并且严格按照题目要求的步骤处理字符串,时间复杂度为O(n),空间复杂度为O(1)。
正则表达式匹配
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。
示例 1:
输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:s = "ab", p = ".*"
输出:true
解释:"." 表示可匹配零个或多个('')任意字符('.')。
方法思路
实现正则表达式匹配的关键在于处理 '.'
和 '*'
这两个特殊字符。可以采用动态规划的方法来解决这个问题,具体步骤如下:
- 定义状态:使用一个二维数组
dp
,其中dp[i][j]
表示字符串s
的前i
个字符和模式p
的前j
个字符是否匹配。 - 初始化:
dp[0][0]
表示空字符串和空模式匹配,初始化为true
。处理模式p
中可能出现的'*'
的情况,即'*'
可以匹配零个前面的字符。 - 状态转移:
- 如果
p[j-1]
是'*'
,则需要考虑两种情况:- 匹配零个前面的字符:
dp[i][j] = dp[i][j-2]
。 - 匹配一个或多个前面的字符:如果
s[i-1]
和p[j-2]
匹配(p[j-2]
是'.'
或等于s[i-1]
),则dp[i][j] = dp[i-1][j]
。
- 匹配零个前面的字符:
- 否则,如果
s[i-1]
和p[j-1]
匹配(p[j-1]
是'.'
或等于s[i-1]
),则dp[i][j] = dp[i-1][j-1]
。
- 如果
- 返回结果:
dp[s.length][p.length]
即为整个字符串s
和模式p
是否匹配。
解决代码
function isMatch(s, p) {
const m = s.length;
const n = p.length;
const dp = new Array(m + 1).fill(false).map(() => new Array(n + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
代码解释
- 初始化
dp
数组:dp
是一个(m+1) x (n+1)
的二维数组,初始值全为false
。dp[0][0]
初始化为true
,表示空字符串和空模式匹配。 - 处理模式
p
中的'*'
:在初始化阶段,处理p
中'*'
可以匹配零个前面字符的情况,即dp[0][j] = dp[0][j - 2]
。 - 填充
dp
数组:- 如果当前字符匹配(
p[j-1]
是'.'
或等于s[i-1]
),则dp[i][j]
取决于dp[i-1][j-1]
。 - 如果当前字符是
'*'
,则考虑两种情况:匹配零个前面字符(dp[i][j-2]
)或匹配一个或多个前面字符(如果p[j-2]
匹配s[i-1]
,则dp[i][j]
取决于dp[i-1][j]
)。
- 如果当前字符匹配(
- 返回结果:最终结果存储在
dp[m][n]
中,表示整个字符串s
和模式p
是否匹配。
这种方法利用动态规划高效地解决了正则表达式匹配问题,确保了正确性和性能。
盛最多水的容器
给定一个长度为 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
方法思路
要找到能盛最多水的容器,关键在于选择两条垂直线,使得它们与x轴构成的容器面积最大。容器的面积由两条线之间的距离(宽度)和两条线中较短的那条线的高度决定。可以采用双指针法来高效解决这个问题:
- 初始化指针:使用两个指针,一个在数组的开始(
left
),一个在数组的末尾(right
)。 - 计算当前面积:当前容器的面积由
min(height[left], height[right]) * (right - left)
决定。 - 移动指针:比较
height[left]
和height[right]
,移动较短的那一侧的指针,因为移动较长的一侧的指针不会增加面积(高度由较短的线决定,而宽度在减少)。 - 更新最大面积:在每次计算后,更新记录的最大面积。
- 终止条件:当
left
指针不再小于right
指针时,遍历结束。
解决代码
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxArea = 0;
while (left < right) {
const currentHeight = Math.min(height[left], height[right]);
const currentWidth = right - left;
const currentArea = currentHeight * currentWidth;
maxArea = Math.max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
代码解释
- 初始化指针和最大面积:
left
指针初始化为0,right
指针初始化为数组的最后一个索引,maxArea
初始化为0。 - 循环计算面积:在
left
小于right
的条件下,计算当前容器的面积。面积由较短的高度和当前的宽度决定。 - 更新最大面积:每次计算完当前面积后,与
maxArea
比较,保留较大的值。 - 移动指针:移动高度较小的指针,因为只有移动较短的边才有可能在宽度减少的情况下找到更高的边,从而可能增加面积。
- 返回结果:当指针相遇时,循环结束,返回记录的最大面积
maxArea
。
这种方法确保了在O(n)的时间复杂度内解决问题,空间复杂度为O(1),非常高效。
罗马数字转整数
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的
规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。
示例 1:
输入: s = "III"
输出: 3
示例 2:
输入: s = "IV"
输出: 4
示例 3:
输入: s = "IX"
输出: 9
示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
方法思路
要将罗马数字转换为整数,可以按照以下步骤进行:
- 建立映射表:首先创建一个字典(或对象),将每个罗马字符映射到对应的数值。
- 遍历字符串:从左到右遍历罗马数字字符串。
- 处理特殊情况:检查当前字符与下一个字符的组合是否属于六种特殊情况(IV、IX、XL、XC、CD、CM)。如果是,则减去当前字符的值;否则,加上当前字符的值。
- 累加结果:根据上述判断,累加对应的数值,最终得到转换后的整数。
解决代码
function romanToInt(s) {
const romanMap = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
let result = 0;
for (let i = 0; i < s.length; i++) {
const currentVal = romanMap[s[i]];
const nextVal = romanMap[s[i + 1]];
if (nextVal > currentVal) {
result += nextVal - currentVal;
i++; // 跳过下一个字符,因为已经处理过
} else {
result += currentVal;
}
}
return result;
}
代码解释
- 建立映射表:
romanMap
对象存储了每个罗马字符对应的数值。 - 初始化结果变量:
result
初始化为0,用于存储最终的整数值。 - 遍历字符串:使用
for
循环遍历罗马数字字符串s
。 - 处理特殊情况:在每次迭代中,检查当前字符的值是否小于下一个字符的值。如果是,则根据特殊规则计算(如
IV
为5 - 1 = 4
),并跳过下一个字符;否则,直接加上当前字符的值。 - 返回结果:遍历结束后,返回累加的结果
result
。
这种方法确保了我们能够正确识别并处理罗马数字中的特殊情况,从而准确转换为对应的整数值。时间复杂度为O(n),其中n是字符串的长度,空间复杂度为O(1)。
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
方法思路
要找到字符串数组中的最长公共前缀,可以采用以下步骤:
- 检查边界条件:如果数组为空,直接返回空字符串。
- 初始化公共前缀:将第一个字符串作为初始的最长公共前缀。
- 遍历数组:从第二个字符串开始,逐个与当前的最长公共前缀进行比较,逐步缩短公共前缀,直到找到所有字符串的共同前缀或公共前缀为空。
- 返回结果:最终得到的公共前缀即为所求。
解决代码
function longestCommonPrefix(strs) {
if (strs.length === 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.substring(0, prefix.length - 1);
if (prefix === "") return "";
}
}
return prefix;
}
代码解释
- 边界条件检查:如果输入的字符串数组
strs
为空,直接返回空字符串""
。 - 初始化公共前缀:将数组的第一个字符串
strs[0]
作为初始的公共前缀prefix
。 - 遍历字符串数组:从第二个字符串开始,依次与当前的
prefix
进行比较:- 使用
indexOf
方法检查当前字符串是否以prefix
开头。 - 如果不是,则将
prefix
缩短一个字符(从末尾开始),直到当前字符串以prefix
开头或prefix
变为空字符串。
- 使用
- 返回结果:遍历结束后,
prefix
即为所有字符串的最长公共前缀。如果在过程中prefix
变为空字符串,则直接返回""
。
这种方法确保了我们能够高效地找到最长公共前缀,时间复杂度为O(S),其中S是所有字符串中字符的总数,空间复杂度为O(1)。
三数之和
给你一个整数数组 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 。
方法思路
要找到所有和为0的三元组,可以采用排序加双指针的方法:
- 排序数组:首先将数组排序,这样可以方便地跳过重复元素,并利用双指针来寻找和为零的三元组。
- 固定一个数:遍历数组,固定一个数
nums[i]
,然后使用双指针left
和right
分别指向i+1
和数组末尾。 - 双指针查找:计算三个数的和,如果和为零,记录下来;如果和小于零,移动
left
指针增加和;如果和大于零,移动right
指针减少和。 - 跳过重复元素:在遍历过程中,跳过重复的
nums[i]
、nums[left]
和nums[right]
,以避免重复的三元组。
解决代码
function threeSum(nums) {
const result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复的nums[i]
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复的nums[left]
while (left < right && nums[right] === nums[right - 1]) right--; // 跳过重复的nums[right]
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
代码解释
- 排序数组:使用
sort
方法对数组进行升序排序,以便后续的双指针操作。 - 遍历数组:外层循环固定
nums[i]
,内层循环使用双指针left
和right
查找另外两个数。 - 跳过重复元素:在固定
nums[i]
时,如果当前元素与前一个相同,则跳过以避免重复三元组。 - 双指针查找:
- 如果三数之和为零,记录该三元组,并移动指针跳过重复元素。
- 如果和小于零,移动
left
指针增加和。 - 如果和大于零,移动
right
指针减少和。
- 返回结果:最终返回所有满足条件的三元组数组。
这种方法确保了我们高效地找到所有不重复的三元组,时间复杂度为O(n²),空间复杂度为O(1)(不考虑结果存储空间)。
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = ""
输出:[]
示例 3:
输入:digits = "2"
输出:["a","b","c"]
方法思路
要生成电话号码数字对应的所有字母组合,可以采用回溯法(深度优先搜索)来解决:
- 建立数字到字母的映射:首先创建一个字典,将每个数字映射到对应的字母集合。
- 处理边界条件:如果输入字符串为空,直接返回空数组。
- 回溯法生成组合:使用递归方法,逐步构建所有可能的字母组合。每次递归处理一个数字,将其对应的字母添加到当前组合中,直到处理完所有数字,将当前组合加入结果列表。
解决代码
function letterCombinations(digits) {
if (digits.length === 0) return [];
const digitToLetters = {
'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']
};
const result = [];
function backtrack(index, currentCombination) {
if (index === digits.length) {
result.push(currentCombination);
return;
}
const currentDigit = digits[index];
const letters = digitToLetters[currentDigit];
for (const letter of letters) {
backtrack(index + 1, currentCombination + letter);
}
}
backtrack(0, '');
return result;
}
代码解释
- 建立映射表:
digitToLetters
对象存储了每个数字对应的字母集合。 - 边界条件处理:如果输入
digits
为空字符串,直接返回空数组[]
。 - 回溯函数:
backtrack
函数用于递归生成所有可能的字母组合。index
表示当前处理的数字位置,currentCombination
是当前已生成的字母组合。- 当
index
等于digits
的长度时,表示已经处理完所有数字,将当前组合加入结果列表。 - 对于当前数字对应的每个字母,递归调用
backtrack
函数,将字母添加到当前组合中,并处理下一个数字。
- 启动回溯:从第一个数字(
index = 0
)和空组合(''
)开始回溯。 - 返回结果:回溯完成后,返回所有生成的字母组合
result
。
这种方法确保了我们能够生成所有可能的字母组合,时间复杂度为O(3^N × 4^M),其中N是输入数字对应3个字母的个数,M是输入数字对应4个字母的个数,空间复杂度为O(N + M),主要用于存储结果和递归调用栈。
删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
方法思路
要删除链表的倒数第N个节点,可以使用双指针技巧:
- 初始化双指针:使用两个指针
fast
和slow
,初始时都指向链表的头节点head
。 - 移动快指针:先将
fast
指针向前移动N步,这样fast
和slow
之间相隔N个节点。 - 同时移动双指针:然后同时移动
fast
和slow
指针,直到fast
指针到达链表的末尾。此时slow
指针指向的节点就是要删除的节点的前一个节点。 - 删除节点:修改
slow.next
指针,跳过要删除的节点,直接指向下一个节点。 - 处理边界情况:如果要删除的是头节点(即
fast
移动N步后已经到达末尾),直接返回head.next
。
解决代码
function removeNthFromEnd(head, n) {
let dummy = new ListNode(0);
dummy.next = head;
let fast = dummy;
let slow = dummy;
// 快指针先移动n步
for (let i = 0; i < n; i++) {
fast = fast.next;
}
// 同时移动快慢指针,直到快指针到达末尾
while (fast.next !== null) {
fast = fast.next;
slow = slow.next;
}
// 删除倒数第n个节点
slow.next = slow.next.next;
return dummy.next;
}
代码解释
- 创建虚拟头节点:
dummy
节点用于简化边界条件处理,特别是当需要删除头节点时。 - 初始化指针:
fast
和slow
指针都初始化为指向dummy
节点。 - 移动快指针:
fast
指针先向前移动N步,使得fast
和slow
之间相隔N个节点。 - 同时移动双指针:
fast
和slow
同时移动,直到fast
到达链表末尾。此时slow
指向要删除节点的前一个节点。 - 删除节点:通过修改
slow.next
指针,跳过要删除的节点。 - 返回结果:返回
dummy.next
,即删除节点后的链表头节点。
这种方法确保了我们能够高效地删除倒数第N个节点,时间复杂度为O(L),其中L是链表的长度,空间复杂度为O(1)。
有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([])"
输出:true
方法思路
要判断一个字符串中的括号是否有效,可以使用栈的数据结构来处理:
- 初始化栈:创建一个空栈,用于存储遇到的左括号。
- 遍历字符串:逐个检查字符串中的字符。
- 处理左括号:遇到左括号('(', '{', '[')时,将其压入栈中。
- 处理右括号:遇到右括号(')', '}', ']')时,检查栈顶的左括号是否与之匹配。如果匹配,弹出栈顶元素;否则,字符串无效。
- 检查栈是否为空:遍历结束后,如果栈为空,说明所有括号都正确匹配,字符串有效;否则无效。
解决代码
function isValid(s) {
const stack = [];
const bracketMap = {
')': '(',
'}': '{',
']': '['
};
for (const char of s) {
if (char === '(' || char === '{' || char === '[') {
stack.push(char);
} else {
const top = stack.pop();
if (top !== bracketMap[char]) {
return false;
}
}
}
return stack.length === 0;
}
代码解释
- 初始化栈和映射表:
stack
用于存储左括号,bracketMap
定义了右括号到左括号的映射关系。 - 遍历字符串:对于每个字符,如果是左括号,压入栈中;如果是右括号,检查栈顶的左括号是否与之匹配。
- 匹配检查:如果栈顶的左括号与当前右括号不匹配,立即返回
false
。 - 栈空检查:遍历结束后,如果栈为空,说明所有括号正确匹配,返回
true
;否则返回false
。
这种方法确保了我们能够高效地判断括号字符串的有效性,时间复杂度为O(n),空间复杂度为O(n)。
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
方法思路
合并两个有序链表可以通过迭代的方式实现。我们维护一个指针,比较两个链表当前节点的值,将较小的节点连接到新链表中,并移动相应的指针。当一个链表遍历完毕后,将另一个链表的剩余部分直接连接到新链表的末尾。
解决代码
function mergeTwoLists(l1, l2) {
// 创建一个虚拟头节点,简化操作
const dummy = new ListNode(-1);
let current = dummy;
// 遍历两个链表
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// 将剩余的链表连接到新链表的末尾
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
代码解释
- 虚拟头节点:创建一个虚拟头节点
dummy
,这样可以避免处理空链表时的特殊情况。 - 初始化指针:
current
指针用于构建新链表,初始时指向dummy
。 - 比较节点值:在循环中,比较
l1
和l2
当前节点的值,将较小的节点连接到current
后面,并移动相应的链表指针。 - 处理剩余节点:当其中一个链表遍历完毕后,将另一个链表的剩余部分直接连接到新链表的末尾。
- 返回结果:最终返回
dummy.next
,即新链表的头节点。
这种方法的时间复杂度为 O(n + m),其中 n 和 m 分别是两个链表的长度。空间复杂度为 O(1),因为我们只是调整了指针的指向,没有使用额外的空间。