每周刷题202010_19_25

前言

本周碰到的最多的是处理字符串序列，处理链表，用到的最多的是双指针。目前对于很多边界条件，有点面向测试用例编程的感觉

比较含退格的字符串
重排链表
二叉树的最近公共祖先
长按键入
二叉树的序列化与反序列化
组合两个表
第二高的薪水
划分字母区间
回文链表
视频拼接
第N高的薪水
分数排名
数组中的最长山脉

题解

• 比较含退格的字符串
  对字符串进行还原然后比较是否相等，这里的 # 代表删除符，如果碰到就删除前一个字符，对应的就是 s.pop。还要考虑字符删没了的情况，此时直接跳过，不在删除

• 重排链表
  一碰到这个问题，就想到双指针和快慢指针，链表本身无法通过索引获取，所以先把每个节点放到数组里，然后开始双指针遍历。emmn，到写代码的时候双指针遍历就不太会了。。双指针要考虑边界问题和结束条件。这里还算简单，只要看着示例就能写出来。 L0→L1→…→Ln-1→Ln => L0→Ln→L1→Ln-1→L2→Ln-2→…

  i, j = 0, len(nodes) - 1
  while i < j:
  	node[i].next = node[j]
  	i += 1
  	if i == j:
  		break
     node[j].next = node[i]
     j -= 1
  node[i].next = None   		

  • 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
    这个做过两遍了，一直没太看懂。大致意思，就是p, q 分别在左右子树两端，那么祖先肯定是 root

  • 长按键入
    双指针，确定判断指针移动的条件，确认边界

    • 确定指针移动条件，指向 name 的头指针i，指向 typed 的头指针j，指针位置值相等，
    • 确认边界，i 指针不用管，只会小于等于 j 指针，当 j 指针到尾部时，遍历结束，或者在遍历的过程中发现一个字符不匹配，就 break 跳出循环

• 二叉树的序列化与反序列化
  这个写的比较屎，只超过了 7% 的用户，用的 BFS 遍历，然后在还原回去，提交了多次，实现了真正的面向测试用例编程🤣。需要注意的是，序列化过程中，叶子节点会产生多余的 None

• 回文链表
  比较值的逆序与顺序元素，相等既为回文

• 视频拼接
  动态规划，自底之上，1 至少需要多少个拼接，2从1的基础上至少需要多少个拼接

• 数组中的最长山脉
  动态规划，山顶左侧单调递增，山顶右侧单调递减。每一个元素都有可能是山顶，所以需要求出其可以向左侧拓展多少，向右侧拓展多少