刷题记录贴

开始baby step的刷题啦
用帖子记录下每日刷题经验

算法题的格式是

题目
1. 思路
2. test case
3. 遗漏点

first blood:
merge k sorted lists (small to big)
1. thoughts:
    overall: construct min priority queue to store smallest nodes
    1. iterate lists to store all nodes in pq
    2. while pq is not empty, pop the smallest nodes to output, push next node of the smallest node to pq (if there is any)
2. test case
    1. empty lists
    2. list with NULL nodes
    3. regular list

1249. Minimum Remove to Make Valid Parentheses
thoughts:
思路比较混乱，主要是因为不知道如何程序化的实现两个rule，另外就是对stack的理解不太深入
看了答案清楚了很多, 主要解法有两种
1. stack存(的index, 如果有)可以配对则pop; 如果遇到)时stack为空则)应该被remove; 如果scan一遍之后stack不为空则(应该被remove
2. 解法2很有意思, very philosophical, 就是说)可以再第一次scan的时候就被判断出来并且被remove; 那么如果把(和)取反而且把整个string reverse, 那我变成了你... 所以也可以通过一次scan把invalid的(也remove掉; 最后再把string reverse即可。坦白说这个解法就算想出来了也不是特别敢用, 不知道有没有比较严格的证明

#这个题目需要revisit

note:这个题目的主要问题是遗漏了test case: ()((
test case的完备对发现bug很重要

56. Merge Intervals
1. thoughts, track current interval,
if there is overlapping, update the interval and check next one
if there is no overlapping, push current interval to result and use next one as interval
push last one to result

2. note:
need to sort first, which simplified the problem to compare right border with left boarder with next interval
do not make assumption about input

3. test case:
empty interval
single interval
unsorted interval
sorted interval

4. followup question: how to decide 2 intervals have intersection?

Subarray Sum Equals K

想过bruteforce 但是大数据量过不了 看了答案发现需要用map 一年多前做过的题p都不记得。。。
思路是sum[j] - sum[i] = k, 因为是正序sum 所以i一定出现在j的左侧，所以j是否是sum为k的subarrary的end point是由他之前的elements决定的
next step是寻找可能的starting point, 因为sum[i] = k-sum[j], 所以只要满足i<j且sum[i] = k-sum[j]即可
这样满足条件的i可能有多个 -> do we care what i is? -> no
存<sum[i], occurence>即可

遗漏点：数据结构

2 extra steps when solving problem: dry run and input check

Product of Array Except Self

1. thoughts:
A. intuitively, get product of all elements, divide by each one -> this is forbidden
B. iterate from left to right to get product from left side, iterate from right to left to get the other side, multiply them

2. test case: [], [1], [0], [1,0,2]

record: one time pass!

another step: time complexity / space complexity analysis

Now the analysis is:

1. 思路
2. dry run
3. test case (input check)
4. time complexity / space complexity
3. 遗漏点

Verifying an Alien Dictionary

use map to record order

遗漏点: 对题意理解有误 两个词比较的时候 取得是第一个不同的char的对比结果, 而不要求整个word的letter在同一index都做到a[i]<b[i]
action item: clarify question by input examples

new protocol:
1. 思路
2. dry run
3. test case (input check)
4. time complexity / space complexity
5. 遗漏点
6. 如果需要revisit加#revisit