删除链表节点与有效的括号——LeetCode 19、20 题记
删除链表节点与有效的括号——LeetCode 19、20 题记
一道中等难度、一道简单题目，但感觉现在做题还是太依赖已有知识点，对新学到的方法很难应用，看来还要结合着特定方法集中练习下。
题目一
第 19 题 删除链表的倒数第N个节点：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路
之前在 第二题：两数之和 中曾接触过链表在 Python 中的表示，正如提交代码中注释部分所示，自定义 ListNode 作为链表节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None题目中给的例子 1->2->3->4->5，删除倒数第二个节点，也就是倒数第三个节点 node_3.next = node_5 = node_3.next.next
所以问题的关键是拿到整个链表长度、定位到倒数第 n+1 个节点。我没能实现一趟扫描，用了两趟：第一轮扫描拿到链表长度；第二轮扫描定位倒数节点。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 先通过 while 循环拿到链表长度
temp = head
l=1
while temp.next!=None:
temp = temp.next
l+=1
# 如果删除倒数第n个节点、n为链表长度，也就是删除第一个节点，那么直接返回第二个节点即可
if n==l:
return head.next
# 通过新一轮 while 循环定位到倒数第 n+1 节点
new_start = head
i = 2
# 例如 l=5,n=2,需要i定位到3
while i<=l-n:
new_start=new_start.next
i+=1
# 倒数第 n+1 节点的下一位，跳过倒数第 n 位
new_start.next = new_start.next.next
return head提交答案
执行用时 : 48ms, 在所有 Python3 提交中击败了 33.57% 的用户 内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 5.41%的用户
表现勉强，想到题目中进阶那条：你能尝试使用一趟扫描实现吗？完全没有思路。
优化
啥也不说了，观摩题解走起。首先是一份运用递归算法的题解。我们先熟悉下递归算法：
递归就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。 递归常用来解决结构相似的问题。所谓结构相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。递归有两个基本要素： （1） 边界条件：确定递归到何时终止，也称为递归出口。 （2） 递归模式：大问题是如何分解为小问题的，也称为递归体。 递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 https://blog.csdn.net/SeeTheWorld518/article/details/47957183
再结合着题目看代码：
class Solution:
def removeNthFromEnd(self, head, n):
# 定于全局变量，因为要调用子函数，保证变量通用
global i
# 空链返回 None
if head is None:
i=0
return None
# 下一位开始的子链，即对第二位开始应用自身函数
head.next = self.removeNthFromEnd(head.next,n)
# 因为会不断调用对下一位实施自身函数，所以 i 这里是从最后一位开始自增
i+=1
# i与n相等时，通过返回head.next 跳过倒数第n节点
return head.next if i==n else head
#作者：adamch0u
#链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/python-di-gui-by-adamch0u/类似递归的思路目前还只是能结合着实例看得懂，之后得集中几道题目专门琢磨琢磨。
题目二
第 20 题 有效的括号：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例
输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false
输入: "{[]}"
输出: true思路
根据题目要求，我们要记录字符串从左到右出现左括号的顺序，若右括号先于相应类型左括号出现、或出现顺序与记录的左括号顺序不匹配，均返回 False。
这里我们可以用一个列表来记录左括号，那么最后加到列表中的就是需要最先检测匹配的。自从解题以来，开始越来越多使用字典，这次也不例外，可以直接通过字典来完成同一类型左右括号的绑定，具体细节看代码。
代码
class Solution:
def isValid(self, s: str) -> bool:
# 将左括号设为key值，对应的右括号设置为相应 value
dic = {"(":")","{":"}","[":"]"}
# 列表用来记录左括号出现顺序
record = []
# 遍历字符串，逐位检测
for c in s:
# 如果该位是右括号
if c in dic.values():
# 如果此时记录左括号的记录非空，即出现过左括号
if record:
# 如果此右括号与最新记录的左括号匹配
if c == record[-1]:
# 将记录中最晚的左括号数据删掉
record.pop()
# 若不匹配，直接返回 False
else:
return False
# 如果没有左括号记录，先出现右括号直接返回 False
else:
return False
# 如果该位是左括号
if c in dic.keys():
# 将左括号在字典中对应的值添加到列表中记录
record.append(dic[c])
# 最终，检测记录列表是否为空，为空则右括号已经与左括号全部匹配完毕
return record==[]提交答案
表现出乎意料地好：
执行用时 : 32 ms, 在所有 Python3 提交中击败了 91.25% 的用户 内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 5.22% 的用户
翻看了几个题解，基本与我们的思路是一致的，但讲解时都不约而同地提到了栈，也就是其先入后出的特点，即我们利用列表匹配最末位的方法。怎么说呢，学 Python 这点挺不好的，链表啊、栈啊这些并没有直接的对应类型或概念，没法直接对应。
结论
第 19 和 20 题：第一个中等难度，虽然结合着具体情况分析找到了规律、通过两轮扫描完成任务，但明显不太符合题目对于一轮扫描的预期，所以之后要学习、练习下递归法；第二个题目用到了栈，虽然对这些概念掌握不多，但基于题目要求和对列表的把握也能体会到其用法。
到这里也暴露出自己对这些概念或者方法理解的缺失，逮到机会要多补补。