21.合并两个有序链表①题目②考点双指针 dummy 虚拟头节点③答案# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution(object): def mergeTwoLists(self, list1, list2): :type list1: Optional[ListNode] :type list2: Optional[ListNode] :rtype: Optional[ListNode] dummy ListNode(0) # cur 始终指向合并后链表的最后一个节点 cur dummy # 当两个链表都还有节点时进行比较 while list1 and list2: # list1 当前节点较小 if list1.val list2.val: cur.next list1 # list1 向后移动 list1 list1.next # list2 当前节点较小 else: cur.next list2 # list2 向后移动 list2 list2.next # cur 向后移动到刚刚添加的节点 cur cur.next # 循环结束后至少有一个链表为空 # 将另一个链表剩余部分直接接到结果后面 if list1: cur.next list1 else: cur.next list2 # dummy 是虚拟头节点真正的头节点是 dummy.next return dummy.next22.括号生成①题目②考点所谓“有效”需要满足左括号和右括号各有n个。任意位置之前出现的右括号数量不能超过左括号数量。最终所有左括号都能被右括号匹配。这道题主要考察回溯算法递归状态记录剪枝append()和pop()的配合如何保证生成结果合法③答案class Solution(object): def generateParenthesis(self, n): :type n: int :rtype: List[str] res [] # 保存所有合法的括号组合 path [] # 保存当前正在生成的括号组合 def backtrack(left, right): left已经使用的左括号数量 right已经使用的右括号数量 # 左右括号都使用了 n 个得到一个完整答案 if left n and right n: res.append(.join(path)) #将列表拼接成字符串 return # 左括号还没有用完可以添加左括号 if left n: path.append(() backtrack(left 1, right) # 撤销刚才添加的左括号 path.pop() # 右括号数量小于左括号数量时才能添加右括号 if right left: path.append()) backtrack(left, right 1) # 撤销刚才添加的右括号 path.pop() # 初始时左右括号都没有使用 backtrack(0, 0) return res23困难合并K个升序链表24.两两交换链表中的节点①题目②考点链表指针操作 虚拟头节点dummy③答案# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution(object): def swapPairs(self, head): :type head: Optional[ListNode] :rtype: Optional[ListNode] # 创建虚拟头节点方便处理原链表的头节点交换 dummy ListNode(0) dummy.next head # pre 指向当前准备交换的两个节点之前的节点 pre dummy # 后面至少存在两个节点时才能进行交换 while pre.next and pre.next.next: # 当前需要交换的第一个节点 first pre.next # 当前需要交换的第二个节点 second first.next # 第一步让 first 跳过 second first.next second.next # 第二步让 second 指向 first second.next first # 第三步让前面的节点 pre 指向交换后的 second pre.next second # first 现在是这一组交换后的最后一个节点 # 下一轮从 first 后面继续交换 pre first # dummy 是额外创建的虚拟节点真正的头节点是 dummy.next return dummy.next25.困难K个一组翻转链表26.删除有序数字中的重复项①题目②考点双指针思想在原数组中完成去重不创建新的结果数组“非严格递增排列”的数组通俗来说就是数组里的元素从左到右整体趋势是越来越大的但允许相邻的数字相等。③答案class Solution(object): def removeDuplicates(self, nums): :type nums: List[int] :rtype: int n len(nums) if n 2: return n k 1 last nums[0] for i in range(1, n): current nums[i] if current ! last: nums[k] current k 1 last current return k27.移除元素①题目②考点快慢指针使用两个变量i负责遍历整个数组可以理解为快指针k表示下一个“不等于val的元素”应该放置的位置可以理解为慢指针。③答案class Solution(object): def removeElement(self, nums, val): :type nums: List[int] :type val: int :rtype: int k 0 for i in range(len(nums)): if nums[i] ! val: nums[k] nums[i] k 1 return k空列表不能直接使用下标赋值28.找出字符串中第一个匹配项的下标①题目②考点逐个位置比较③答案class Solution(object): def strStr(self, haystack, needle): :type haystack: str :type needle: str :rtype: int m len(haystack) n len(needle) for i in range(m-n1): if needle haystack[i:in]: #中括号中必须填写下标或切片范围,这里不需要对 needle 进行切片直接比较整个 needle 即可 return i return -129.两数相除①题目②考点位运算 减法^ 是异或运算。只有两个条件不同时结果才是 True。核心语法range(start, stop, step)Python 的range()函数有三个参数start起始值31。循环变量shift的初始值是 31。stop结束值-1。注意stop是不包含在内的开区间。所以循环会在shift等于 0 时执行当shift变成 -1 时停止。step步长-1。表示每次循环后shift的值减 1。③答案class Solution(object): def divide(self, dividend, divisor): :type dividend: int :type divisor: int :rtype: int # 32 位有符号整数范围 MAX_INT (1 31) - 1 MIN_INT -(1 31) # 唯一可能发生正溢出的情况 # -2147483648 / -1 2147483648 # 超过了最大值 2147483647 if dividend MIN_INT and divisor -1: return MAX_INT # 判断最终结果是否为负数 negative (dividend 0) ^ (divisor 0) #^ 是异或运算。只有两个条件不同时结果才是 True # 先全部转换为正数进行计算 a abs(dividend) b abs(divisor) quotient 0 #商 # 从第 31 位一直检查到第 0 位 for shift in range(31, -1, -1): # 判断 b 左移 shift 位后是否不超过 a if a (b shift): # 从被除数中减去这一部分 a - b shift # 商中增加对应的值 quotient 1 shift # 如果两个数一正一负结果应该为负数 if negative: quotient -quotient return quotient30.困难串联所有单词的子串