python做题日记（9）

第二十一题

        第二十一题是合并两个有序链表，合并后的链表仍然需要保持有序，因为在合并之前已经是两个有序链表，因此在合并时只需要遍历比较两个链表中的下一结点数值，将其中较小的一个结点添加到新的列表中。如果有任何一个链表已经遍历完成，将另一链表的剩余结点直接接到新链表后面，最后返回新链表的头结点。

class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 创建一个虚拟头结点，方便操作dummy = ListNode()current = dummy# 遍历两个链表，取较小的节点接到新链表后面while list1 and list2:if list1.val < list2.val:current.next = list1list1 = list1.nextelse:current.next = list2list2 = list2.nextcurrent = current.next# 剩余的节点直接接到新链表后面current.next = list1 if list1 else list2return dummy.next

第二十二题

        第二十二题是括号生成问题，给定生成括号的对数，生成所有合理的组合方式。对于括号生成问题，本质上是多层嵌套的组合问题，每一步都要作出选择，并且每一步的选择都会影响后续的选择。在这里选择采用递归的方法解决这个问题，因为整个过曾像一棵决策树，递归可以自动遍历所有分支。每一层递归代表当前已经放了多少个括号，下一层递归就是在这个基础上再放一个括号。递归的终止条件是左右括号都已经用完。排列括号的条件是：如果还有左括号可以用，就可以放左括号，如果右括号剩余数量大于左括号时，才能放右括号。因此形成如下代码：

class Solution:def generateParenthesis(self, n: int) -> list[str]:res = []def backtrack(path: str, left: int, right: int):# 终止条件：左右括号都用完if left == 0 and right == 0:res.append(path)return# 只要还有左括号可以用，就可以放左括号if left > 0:backtrack(path + '(', left - 1, right)# 右括号剩余数量大于左括号时，才能放右括号if right > left:backtrack(path + ')', left, right - 1)backtrack('', n, n)return res