pylist

30-Day LeetCoding Challenge

Week 1

• 136. Single Number
  • set()基础。秒杀，就是记得把中文输入法关了。
• 202. Happy Number
  • set()基础
  • 调用函数的时候记得不要忘了self.
  • while的开头和收尾， 目前好像没什么好的办法
• 53. Maximum Subarray
  • cumsum 的应用
  • 秒杀，因为做过原题
  • 计算max和min的时候，注意要不要包括当前点
    • 如果包括就先update再计算
    • 如果不包括就先计算再update
• 283. Move Zeroes
  • 同向快慢读写双指针
  • 虽然做过，不过还是死在了读题上
    • 题目要求保持先后顺序，结果我给反了过来
  • 其他挺简单的，仔细读题之后就秒杀了
• 122. Best Time to Buy and Sell Stock II
  • simulation
  • 秒杀，好像都没什么可说的
• 49. Group Anagrams
  • dict()的应用
  • 注意
    • string sort过之后是list
    • list不能作为dict的key
• Counting Elements
  • set基础运用
  • 没有漏出破绽，秒杀

Week 2

• 876. Middle of the Linked List
  • 倍速双指针
    • 注意快指针每循环移动一次，慢指针多个循环移动一次，这样不会出现越界太多的情况
    • 慢速指针在何时跟进可以用小的test case来特殊值法确定。用长度是 2 和 3 的linked list来尝试。
• 844. Backspace String Compare
  • 不是很顺利的一题
  • 这个题有两个思路
    • simulation，模拟按键把字符串生成出来，然后比较
    • pointer，不生成出来，而是挪动指针逐个比较
    • 很明显时间复杂度一样都是O(n)，然而指针更省空间。但是写指针的时候我没写出来。
  • 本题目犯的常规错误
    • 引用函数忘了加 self.
  • 关于指针的教训
    • 不要把两个指针的循环条件同时放入，while循环的条件，否则会非常麻烦。而是要为两个指针单独写while循环
    • while循环的条件要是搞不清楚的话，就直接写while True:然后中间break，如果发现条件比较清楚的时候再放回正确的位置，如果不能的话就不改了。
      • 死循环不是一个好的style，实在不行可以换成for一个大数
    • 一个循环只做一件事，这个非常重要。做完就要continue或者break或者return。否则会糊粥。
      • Style: 多个if重叠的时候，可以在if之后加入注释，注明如果可以运行到注释这行，需要达到的条件。
• 155. Min Stack
  • stack的进阶用法
  • 这个题因为有minimum所以让我想到了heap。而heap在pop的时候会非常之复杂。虽然trash list的策略确实可以AC，但是其实既浪费时间又浪费空间。
  • 常规错误
    • 不要把attribute和method起同一个名字
    • 用a[0]作为peek之前一定先判断list是否为空
    • 不要在某些语句的末尾加入无意义的冒号
      • 只要注意缩紧这个其实很容易避免
• 543. Diameter of Binary Tree
  • DC on binary tree
  • 二叉树上的分治在检查的时候一定注意：
    • combine的时候有没有充分利用左右获得的答案
• 1046. Last Stone Weight
  • heap
  • heapify has no out put, heap operations are inline
  • max heap 的 负号位置

    • h = [-s for s in stones]
      heapify(h)
      

    • push: heappush(h, -x)
    • pop: x = -heappop(h)
    • peek: -h[0]
• 525. Contiguous Array
  • cumsum 的应用
  • 注意 max 和 min 擂台的初始化
    • 根据题目要求，不一定要初始化到正负无穷
    • 比如这里 max 初始化到 0 就可以
• Perform String Shifts
  • circular shift
  • 看题，左右都能看反我也是服了

Week 3

• 238. Product of Array Except Self
  • 双向 cumsum ，这里是product，不过和sum差别不大
  • 循环还是分开写， 可以更清楚一些
• 678. Valid Parenthesis String
  • stack 进阶用法
  • dfs 会超时
  • 括号的配对原则
    • ( [ ) ] 也一样成立
  • 分析比较难的题，比较难总结，不过好歹是对了
• 200. Number of Islands
  • BFS， 其实很简单，小错一堆
  • 犯的常规错误
    • deque()初始化的时候，里面一定要放一个list。
      • 特别是每个元素都是tuple的时候，要放一个list of tuple
    • True大写
    • list of list 的双下标应该是 [i][j] 因为不是 numpy
    • 判断要不要放 q 里的时候，一定先看一下 qed 里面是不是已经有了。q 和 qed 一定共同进退
    • 一个输入参数一定看好格式，0 和 1 有可能是字符。
• 64. Minimum Path Sum
  • 简单的 DP
  • functools 库名称是有复数的
• 33. Search in Rotated Sorted Array
  • 二分法
  • 犯的错误
    • 二分法不是想当然的不是up就是low，还有找不到的时候
      • 最后返回的时候要判断两次，return 3 次
    • copy 的代码，一定要好像重新写一样，完整得读一遍，边读边改。因为很多细节都不一样，有可能会遗漏。
• 1008. Construct Binary Search Tree from Preorder Traversal
  • Binary search tree
    • 用二分法还原
  • 犯的错误
    • 检查拼写
• Leftmost Column with at Least a One
  • 打擂台 加 二分法

Week 4

• 560. Subarray Sum Equals K
  • cumsum 的进阶用法，inverse cumsum
  • 如果一堆关系搞不清，可以先写一个 class 用于理清关系
  • 如果一次想不清，可以先用成本高一些的方法看看大框架能不能行得通，如果行得通可以再 refine。比如这里不知道i有没有用，就先存着，后来发现只需要数目，就用计数器来替代list。
• 201. Bitwise AND of Numbers Range
  • 二进制数学，
    • 如果想清楚了，这个题目就是求 common prefix
  • 漏了一个计算条件，不知道算什么错误
• 146. LRU Cache
  • dict + double linked list 自定数据结构
    • previous node dictionary
  • 一定切记，定义新的数据格式的时候，要么新定义一个class，要么写好接口再用，否则很容易糊粥。
  • 又有一个拼写错误
• 55. Jump Game
  • simulation, 秒杀
• 1143. Longest Common Subsequence
  • DP， 两字符串，看hint之前没能自己想出来
  • dp 的精髓就是找到状态和转移方程
    • 两string的题一般是这种二维状态表
    • 转移方程很可能是这种向上向左的
• 221. Maximal Square
  • DP
  • 尼玛看题，看题，看题。第一次看成求和，第二次看成长方形我真是服了。
  • list of list deep copy:
    • left = [a + [] for a in matrix] + []
  • 这题有 insane empty test case
• First Unique Number
  • 自定义数据结构
    • set + deque
    • set 也可以换成dict计数器
  • 拼写
  • self.
  • 每个 condition 之间用 break，continue 或者 return 隔开

Week 5

• 124. Binary Tree Maximum Path Sum
  • Binary Tree DC
  • 虽然思考的时候卡壳了，不过写出来以后一遍过，可喜可贺
  • 这题的要点在于把每个节点都当作一条path的终点。而不是只考虑叶节点
  • 这题也是先用 list 想然后用 counter 优化
• Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
  • Binary tree traverse
  • 二叉树的travers 需要 dummy root
  • 递归之前需要判断左右节点的存在性
    • 这样就不像 DC 那样有两个 和 None 有关的返回条件了
      • 事实上一个都没有，全部的逻辑都在 return condition 部分