万年历网站做,通栏网站,外包制作app软件要多少钱,公众平台官网登录入口目录 一、13. 罗马数字转整数
贪心
二、16. 最接近的三数之和
排序指针 三、17. 电话号码的字母组合
dfs#xff08;深度优先搜索#xff09;
四、19. 删除链表的倒数第 N 个结点
1.模拟
2.前后同步指针
五、20. 有效的括号
栈
六、21. 合并两个有序链表
1.递归
…目录 一、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, val0, nextNone):
# 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, val0, nextNone):
# 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, val0, nextNone):
# 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, val0, nextNone):
# 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
完
感谢你看到这里一起加油吧
