目录
一、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 = 0
for 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:
# 剪枝
# 最大值小于等于左端点
# 最小值大于等于右端点
continue
j, k = i + 1, n - 1
while j < k:
cur = x + nums[j] + nums[k]
if cur == target:
return target
elif cur > target:
ans2 = min(ans2, cur)
k -= 1
else:
ans1 = max(ans1, cur)
j += 1
return 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]:
# dfs
if not digits:
return []
n = len(digits)
ans = []
path = ['' for _ in range(n)] # path长度固定为n
def dfs(i: int) -> None:
nonlocal n
if i == n:
# 搜索到末尾
ans.append(''.join(path))
return
for 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 = 0
cur = head
while cur:
l += 1
cur = cur.next
dummy = ListNode(next = head) # 哨兵节点
l -= n # 指到指定节点的前一个节点
cur = dummy
while l > 0:
cur = cur.next
l -= 1
cur.next = cur.next.next # 更改连接
return dummy.next2.前后同步指针
来自灵神题解（. - 力扣（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.next
while right.next:
# 走到指定节点的前一个节点，这里是right.next
left = left.next
right = right.next
left.next = left.next.next
return 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 False
st.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 list2
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list22.迭代
# 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 = dummy
while list1 and list2:
if list1.val <= list2.val:
cur.next = list1
cur = cur.next
list1 = list1.next
else:
cur.next = list2
cur = cur.next
list2 = list2.next
cur.next = list1 if list1 else list2
return dummy.next完
感谢你看到这里！一起加油吧！
