合并链表与生成括号——LeetCode 21、22 题记
合并链表与生成括号——LeetCode 21、22 题记
今天刷的是一道关于链表操作的简单题目，一道关于括号的中等难度题目。可见链表、括号类题目还是频繁出现的，可以有针对性地练习下。
题目一
第 21 题 合并两个有序链表：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4思路
基于以往经验，这里就可以把两个链表同时放到一个遍历循环中，判断条件就是其中任意链表还没有结束，这样就可以一个循环遍历两条链表所有节点。在循环中，只要判断其中的链表是否结束、比较两链表节点值，取小的值作为节点来重新拼接就基本完成任务。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 新建个节点 0 作为起点
start = ListNode(0)
# 复制下该节点，这样就可以用复制的节点.next 作为返回结果了
start_copy = start
# 若两链表有非空，while 循环来遍历
while l1!=None or l2!=None:
# 若其中有链表已经为空，那么下一位都是另一链表内容了
if l1==None:
start.next = l2
l2 = l2.next
elif l2==None:
start.next = l1
l1 = l1.next
# 若两链表均非空
else:
# 取其中值较小的节点作为下一节点来拼接
if l1.val<l2.val:
start.next = l1
l1=l1.next
else:
start.next = l2
l2=l2.next
# 将赋值好的下一节点赋给 start 来进行下一遍历
start = start.next
# 复制起始节点的下一节点，即要求链表的开始
return start_copy.next提交答案
执行用时 : 52 ms, 在所有 Python3 提交中击败了 31.57% 的用户 内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 7.14% 的用户
第二题没能做出来，贴在这还得研究研究：
题目二
第 22 题 括号生成：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses思路
这话做得有点自闭，总感觉可以穷举，但怎么写都不对。穷举的思路就是 n 对括号生成的字符串长度是 2*n 位长，我们就把 n 对括号所能生成的所有字符串全列出来，按照对应左括号一定要先于右括号出现的规则来进行筛选即可。
这个穷举过程，因为 n 不确定，如果要穷举的话，目前我能想到的只有 n 层 for 循环来嵌套，但这个写不出来，纠结了好几个小时也写不出来。对于递归法，又理解得不到位，抓瞎了。
只看看题解区是怎么递归、回溯实现的了。
代码
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 定义递归过程中不断加括号的方法
def generate(A):
# 当判断长度足够时
if len(A) == 2*n:
# 检测符合括号对应的规则，添加到结果中
if valid(A):
ans.append("".join(A))
else:
# 以下就是同时兼顾到左右括号的递归实现了
# 向其中加入左括号
A.append('(')
# 继续调用自身
generate(A)
# 上一调用自身算是一分支，分支结束后删去新加的左括号，相当于回到分支开始前
A.pop()
# 在新分支中添加右括号
A.append(')')
# 继续开启新分支
generate(A)
# 新分支结束，删去新加的右括号
A.pop()
# 检测最终生成的括号列表是否符合规则
def valid(A):
# bal 用于计算左右括号数目
bal = 0
for c in A:
# 左括号为 +1
if c == '(': bal += 1
# 右括号为 -1
else: bal -= 1
# 如果出现负值，说明右括号先于对应的左括号出现，直接返回 False
if bal < 0: return False
# 最终只有和为 0 的才是左右括号匹配的情况
return bal == 0
# ans 用来存结果
ans = []
# 启动递归过程
generate([])
return ans
# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/这里要着重看下这段代码中如何在递归过程中兼顾左右括号两种情况：它先添加左括号，调用自身函数，相当于开启了加左括号的分支；此分支结束后，删去添加到左括号，重新添加右括号，再调用自身函数，开启又一新分支；最终分支结束时，再将添加的右括号删去。
初次接触，有些懵，但捋一捋过程，确实、这样就相当于不断分支分岔遍历到所有情况。
提交答案
不是自己亲手写的代码，都没有检测的欲望了。。没办法，谁让自己写不出来呢。
执行用时 : 108 ms, 在所有 Python3 提交中击败了 6.99% 的用户 内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 6.06% 的用户
优化
刚属于暴力产生所有左右括号的组合，最终检测生成的结果是否符合规则来筛选，自然会产生大量不合规的结果、浪费时间。那么相应的优化可以放到递归生成单一结果的过程中，在生成结果时就保证它是合规的，那么就可以规避掉后续不符合规则的诸多情况。
对于递归我仍然要消化，这里优化的代码也是搬运的题解区的回溯法代码：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
# 注意看参数中多了 left 和 right 用于记录左右括号个数
def backtrack(S, left, right):
# 如果长度达标，直接添加结果即可
if len(S) == 2 * n:
ans.append(''.join(S))
return
# 如果左括号个数小于 n
if left < n:
# 添加左括号
S.append('(')
# 调用自身函数时，把左括号个数更新
backtrack(S, left+1, right)
# 上一分支结束，还原下添加的括号
S.pop()
# 如果右括号个数小于 n
if right < left:
# 添加右括号
S.append(')')
# 调用自身函数，更新右括号个数
backtrack(S, left, right+1)
# 还原下新添加的括号
S.pop()
backtrack([], 0, 0)
return ans
#作者：LeetCode-Solution
#链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/优化后的表现：
执行用时 : 44 ms, 在所有 Python3 提交中击败了 58.40% 的用户 内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 6.06% 的用户
结论
第 21 和 22 题：关于链表的简单题，现在可以独立来解决了，但可能仍需配合着测试用例来进行调试；生成括号的这道中等难度题目，目前对递归法和回溯法仅停留在可以理解的阶段，我要多练习写写这类的代码。
写不出代码，很尴尬，也挺打击人，但又没办法，只能学着模仿、等熟练了再尝试独立写出来吧。