2024.6.28刷题记录

目录

一、13. 罗马数字转整数

贪心

二、16. 最接近的三数之和

排序+指针

 三、17. 电话号码的字母组合

dfs（深度优先搜索）

四、19. 删除链表的倒数第 N 个结点

1.模拟

2.前后同步指针

五、20. 有效的括号

栈

六、21. 合并两个有序链表

1.递归

2.迭代

---

一、13. 罗马数字转整数

贪心

class Solution:dict = {'I': 1, 'V': 5,'X': 10, 'L': 50,'C': 100, 'D': 500,'M': 1000}def romanToInt(self, s: str) -> int:# 贪心，若前面小于后面就相减n = len(s)ans = 0for i in range(n):if i == n - 1 or Solution.dict[s[i]] >= Solution.dict[s[i + 1]]:ans += Solution.dict[s[i]]else:ans -= Solution.dict[s[i]]return ans

二、16. 最接近的三数之和

排序+指针

又重新写了一遍这道题

class Solution:def threeSumClosest(self, nums: List[int], target: int):# 排序+ 指针nums.sort()if sum(nums[-3:]) <= target:return sum(nums[-3:])if sum(nums[:3]) >= target:return sum(nums[:3])ans1, ans2 = -math.inf, math.inf    # 左右区域n = len(nums)for i in range(n - 2):x = nums[i]if x + nums[-2] + nums[-1] <= ans1 or \x + nums[i + 1] + nums[i + 2] >= ans2:# 剪枝# 最大值小于等于左端点# 最小值大于等于右端点continuej, k = i + 1, n - 1while j < k:cur = x + nums[j] + nums[k]if cur == target:return targetelif cur > target:ans2 = min(ans2, cur)k -= 1else:ans1 = max(ans1, cur)j += 1return ans1 if target - ans1 < ans2 - target else ans2

 三、17. 电话号码的字母组合

dfs（深度优先搜索）

来自灵神题解（. - 力扣（LeetCode）），完全没想到。

MAPPING = "", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
# 元组class Solution:def letterCombinations(self, digits: str) -> List[str]:# dfsif not digits:return []n = len(digits)ans = []path = ['' for _ in range(n)]   # path长度固定为ndef dfs(i: int) -> None:nonlocal nif i == n:# 搜索到末尾ans.append(''.join(path))returnfor c in MAPPING[int(digits[i])]:path[i] = c # 覆盖dfs(i + 1)dfs(0)return ans

四、19. 删除链表的倒数第 N 个结点

1.模拟

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:# 模拟# 先求长度l = 0cur = headwhile cur:l += 1cur = cur.nextdummy = ListNode(next = head)   # 哨兵节点l -= n  # 指到指定节点的前一个节点cur = dummywhile l > 0:cur = cur.nextl -= 1cur.next = cur.next.next    # 更改连接return dummy.next

2.前后同步指针

来自灵神题解（. - 力扣（LeetCode））。很妙！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:# 前后同步指针left = right = dummy = ListNode(next = head)for _ in range(n):# 右指针先走n位right = right.nextwhile right.next:# 走到指定节点的前一个节点，这里是right.nextleft = left.nextright = right.nextleft.next = left.next.nextreturn dummy.next

五、20. 有效的括号

栈

class Solution:def isValid(self, s: str) -> bool:# 栈st = []hash = {')': '(', '}': '{', ']': '['}for c in s:if c in hash:# 右括号if not st or hash[c] != st[-1]:return Falsest.pop()else:# 左括号st.append(c)return not st   # 为空即对

六、21. 合并两个有序链表

1.递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 递归if not list1 or not list2:return list1 if list1 else list2if list1.val < list2.val:list1.next = self.mergeTwoLists(list1.next, list2)return list1else:list2.next = self.mergeTwoLists(list1, list2.next)return list2

2.迭代

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 迭代dummy = ListNode()cur = dummywhile list1 and list2:if list1.val <= list2.val:cur.next = list1cur = cur.nextlist1 = list1.nextelse:cur.next = list2cur = cur.nextlist2 = list2.nextcur.next = list1 if list1 else list2return dummy.next

完

感谢你看到这里！一起加油吧！