LeetCode打卡

好久没来打卡了。打一发。

今日LC进度: 362。

最近MOCK比较多。有遇到难度简单的题，也有遇到完全没见过会懵逼的。总结一下最近的心得。
若面试中遇到毫无思路的新题：
首先：
保持镇定！镇定！镇定！
1）问清题目细节，收集信息。举例子去理解题目或是至少向对方展示理解题目的过程。
2）若能想到暴力解法。先讲为何选择这个解法，再描述，切忌因为是暴力解法，就讲的太过跳跃导致没有让对方明白自己的思路。这样会让面试官怀疑你是不是能找到正确答案。
3）好像想到最优解法，但有点儿模糊的。先讲为何想到这个，然后一定要在描述和写注释阶段理清思路，还要讲时空效率，如果开始写之后反悔，反复修改数据结构，容易弄晕面试官，特别是和对方使用语种不同的情况下。
4）有多个解法，但彼此trade off。一定要都说！要对比时空效率，选个好的去实现。
5）没啥具体解法。那就逐一分析题目关键词，去推测可能的数据结构。至少要一个个列举出来分析。不需要马上确定。

如果是正常题目：
1）写代码前写一个个step的注释，最好直接拷贝到代码区，或者在那上面直接写，注释可以保持和代码一起缩进，代码要写的尽量快！注释和代码不要间隔太远，容易漏掉注释里面说的步骤。或者是边写边说，越简单的题越忌讳漏掉步骤！
2） Header File最后记得加。
3）找几个测试例子，特别是边缘！！！测试自己的代码。
4）写完后优化，如果写的过程中就优化，一定要慢慢地打字讲清楚，因为切换思路的过程容易让对方不知道你在做什么。

不同面试的侧重点：
Google Doc Interview：侧重交流，即便最优解实现起来有难度，只要让面试官听懂，也可以写。比真正上机对bug free要求低一点。这个环境利于提出多种答案做trade off。
Coderpad上机类Interview：侧重实现，要留出足够时间实现一个doable的解，可以是暴力解。跑不出来会死得很惨。。

写一些普通BFS/优先队列BFS 心得。
1)"visited"set的更新放在压入队列前:
   - 这可以防止一个节点入队列两次。大部分普通BFS都是这种。
2)"visited"set的更新放在Pop出队列后:
  - 这允许一个结点进入队列两次，感觉更适用于优先队列BFS。
  - Dijkstra里，可使用dis数组比较当前优先队列里面的dis，省去这一步，本质上相当于pop后更新visited。
3)不使用"visited":
    - Topology Sort中由于只有当一个结点入度为0的时候才入队列, 一个结点入度为0只发生一次，所以不需要visited，入度数组顶替了visited set的功能。
   -  可以通过直接更新已有的数据（标记为0或者-1之类的)，节省visited空间（DFS二维矩阵时更常见)。缺点是修改了原始数据。

答案的更新:
1) Pop出队列的时候更新答案
- 适用于多起点，多结束点，执行步数会比做法2多，当答案出队列时，前一个层级的结点都已经被考虑完，适用于必须等一个层级的结点全部走完才能做决策的情况。
2) 找到立刻更新
- 比较适用于只有一个起点的情况，当答案出队列前，当前层级的结点并没有被考虑完。大部分普通BFS都是这种。

单调栈心得

    关于单调栈/队列的题，最后往往可以抽象为离当前操作值val最近的>(=)val或者<(=)val的值。如果是找离的最远的，可以转化为最近。比如查找最远的<=val的index，就能转化为找最近>val的值的index, 然后-1或+1（取决于哪个方向更靠近当前index）

1) 找>val的最近数值:
    假设Stack里存了两个index，i和j，i比较远，j离val的index近。那么如果我们还是选择了i对应的nums[i]，说明j对应的nums[j]太小了，只要nums[j]>=nums[i]，那肯定选j不选i，也就是说一个更大或相等的元素会把stack里已有的元素block掉，把这些没用的被blog的元素弹出，就会得到一个单调递减的栈。
    另外一种思维是确保栈里越新的元素符合条件希望越小（符合希望大的元素会block前面的元素）。 若让>val的希望变小，只能单调减。

2) 找>=val的最近数值 ~ 相当于>val-1:
    还是单调递减，让<=val的元素出栈，只是弹出时多查看下弹出元素是否=val，若等于，立刻更新答案。
    把单调递减改成单调不增，只弹出>val的，这样栈顶可能是一个=val的元素，这种做法会保留冗余元素，栈里可能有一排等于val的数值，其实只有最近的那个有效，但这个写法代码干净。

3) 升级:
    - 找最近的<val-k的，按’希望变小’原则，栈单调增。改用deque，从头取<val-k的元素，从尾巴插入val。
    - 找最近<val+k的，按’希望变小’原则，栈单调增，也就是>=val时弹出，弹出过程时可能出现符合条件的元素（跟前面讨论的>=val转化为>val-1的做法一致，>val-1可以看成>val-k的子情况，类似<val+k，都是弹出时解决)
    - 找<任意值，hmmm…目前只能想到单调栈上做binary search。

最近一直刷题和Mock感觉也不是办法，该想想办法给自己搞到更多真面试，可是简历还是被拒的飞起      日常丧。

今日进度: LC393。
今天面了景驰电面。难、凉、跪。follow up卡了很久，面试官提示下磕磕绊绊写了个跑的很慢的解答，然后在面试官提示下做了优化。反正。。。一切都在他的提示下搞的，被自己蠢哭了。从今天开始刷codeforces和poj，觉得leetcode不太满足他们的出题难度。。。ACM退役太久脑子没当年灵活了，哎，也有可能有心态影响吧，反正实力还太弱。

今天复盘了一下周赛，和一些矩阵、dp题。
周赛105：
1-LC917   两端双指针brute force
2-LC918   Maximum Sum Circular Subarray,  转化为sum前缀和求区间最小，单调增deque，从头顶取最小值即可。保持增是因为后面的元素Y会block掉前面>=Y的元素X。
3-LC919  模拟赛的时候太困写的很繁琐，总体思路是保持两个queue/vector，一个是父结点层，一个是未来的父结点层。讨论一下complete和In-complete两种情况。重写时用的是vector/index模拟queue，可以避免父结点层遍历完后还得把结点放回去。
4-LC920  一开始忽略了所有歌都要出现一次这个条件，之后用的dp。
dp[i][j]: i首歌，填满j个位置的方法数量。位置和歌的编号从1开始。
1) 位置j上的歌之前没出现
    i * dp[i-1][j-1]   (位置j上的歌一共i种可能，剩下(i-1)首歌要填充剩余(j-1)个位置)
2) 位置j上的歌之前出现过
    (i-K) * dp[i][j-1] (位置j上的歌一共i-K种可能, i首歌要填充j-1个位置)

LC84、85：
最早使用的是单调栈双向扫两遍的通解方法。重新尝试了单向法。最精妙的地方时计算不是发生在一个元素被压入栈前，而是发生在元素被弹出栈时。弹出元素Y的时候，查看前一个元素X(<Y的最近元素），同时因为Y是由某个<=Y的Z导致发生了弹出，所以Y的右半边也得到了考虑（相当于第二遍反向扫）。
之前我比较担心右半边发生的是<=而不是精确的<。但后来通过例子发现这不影响答案。

例如:   1 3 3 1
压入第二个3的时候导致前面的3弹出，此时计算的出来的矩阵面积为3，但其实以第1个3为高的矩阵最大是【3,3】（面积6）。
如果有这种高连续相等的情况，压入最后的1的时候，必然能得到矩阵面积6。因为单调栈单调递增，第1个3已经被第2个3导致弹出。
也就是说，若是按照双向扫描（两边查找<当前高的边界）理解这道题，一串连续相等的高，其实只有最右的高，被计算出了有意义的面积数值。
当然也可以把单向扫描法中压入栈的元素理解成exclusive右边界，面积理解为这个右边界以左的最大面积，这样理解的话，每一个时刻的面积值其实都是有意义的。相当于不断拓展右边界。
注意：最后需要加虚拟-1右边界，使得前面的元素发生弹出。

LC363
目前只想到了O(n^2mlogm)的解法，如果n比较大，可以选择换个方向O(m^2nlogn)
利用前缀和area[i][j](从matrix[0][0] ... matrix[i-1][j-1])
总觉得很慢还可以优化。。

LC621
使用一个banned队列记录当前不能实施的任务，在时间合理后更新priority queue， priority queue会把数量较大的任务前置。基本上来说是一种贪心做法。

LC 265. Paint House II
周日模拟面试的时候试了这道题。我定义的状态不太一样。解起来没问题，就是很难在白板上描述。
非常规定义:
//dp[i][j]: 涂第(i-1)个房子，不用颜色j的最小cost
//dp[i][j] = min(dp[i-1][k]) + costs[i-1][j];
注意处理只有1种颜色，1个房子的特殊情况-> cost[0][0]
时间效率优化：只需要记录最小值和第二小值。
用prev_id, prev_min, prev_min2还有now_id, now_min, now_min2分别标记上一行和当前行的最小值的列，最小值，和第二小值。
注意首行初始化！！
注意优化完时间后，可以把空间优化为O(1), 用dp表示dp[i][j]。

复盘一两周前做的比赛。拖延症严重。
下次要及时复盘！！！
Codeforces 514 Div.2
A - Cashier  普通模拟，一开始读题读漏了条件，做了些冗余操作
B - Forgery  把矩阵扫描一遍，只要能盖印就盖，最后对比结果矩阵和目标矩阵。算是贪心？
C - Sequence Transformation  n >= 4的时候，先消去奇数列，注意n=3这个边缘情况，不能消奇数列，应该消第一个第二个。不知道为啥比赛的时候老WA，感觉比赛时coding能力不稳定。
D - Nature Reserve。几何题，二分查找可行半径。注意:
1）long double binary search可以卡断！哪怕是1e17 被二分100次也非常非常小了！！（1e17/(2^100) =》 很小)
2）注意R的右边界不是1e7。直接在[0, 1e17]范围内找， 反正二分的系数是100。.
E - Split the Tree 比赛的时候没时间读这题题面。大意是一根树，上面的结点有数值，要切分成一段段path，每条path总和不超过S，结点数不超过L，问最少切割成几段path。
尝试了很多想法都失败，Div2-E大概是我目前的瓶颈吧，决定明早起来看tutorial再来更帖子。。

感想：
1). 减慢读题，举例子确认理解。codeforce不知道为啥题意比leetcode难理解很多，题意不完全理解会导致代码的混乱，甚至导致写一半发现理解错误。
2). 不用直接想最佳解法，想个可行的二分解法也可以。

今日要出门一天，回家看E…
最近严重的感觉到了瓶颈。这几次周赛模拟和正式比赛一直是前3道，一两百名左右。想要练成长期稳定输出第4题…只能用codeforces的模拟赛逼自己多动脑，日常刷lc hard，同时训练弱项-图论。
cf中容易碰到有新意不套路的题，对克服瓶颈很有帮助。
但愿几周内能见效，求点亮我捉急的智商QAQ

来自一亩三分地官方APP

621. Task Scheduler
358. Rearrange String k Distance Apart
767. Reorganize String
3道题一个套路，我自己做的时候用了priority_queue存可执行任务和一个queue存被ban的任务，实时地把queue里的avaliable任务取出（最多一个），然后在pq里查当前count最大的任务，然后再把刚执行的任务压入queue。后来看答案发现，可以以周期进行操作。就跟BFS时为了在外部更新level数值，而做的周期性操作一样。两种办法本质没什么区别，但周期性操作的方法存储的数据更少。
周期性操作的办法启发了第二种解法，可以尝试用任务填充周期。但我最开始忘考虑任务种类>周期的情况导致WA了。后来发现当任务种类>周期的时候，可以通过调整安排下所有任务。例如假设我们有A, B, C, D, E, F 6种任务，数量分别为5，5，3，3，3，3，n为3（周期4），那么一开始的ABCD可以排成下图。
ABCD
ABCD
ABCD
AB
AB
加入E之后，变成
ABCD
ABCD
ABCD
ABEE
ABE
这个时候必须交换某些位置，因为E的数量一定<=A,B,C,D的任务数量，E被安排进空档后，最多产生count(E)-1次重复，在本例子中，在第三行E产生了1个多余重复，但糟糕情况下可能产生(3-2)个，无论如何，需要处理的元素不会超过count(E)-1，那么C，D可以和E交换。且因为C和D的count都比(count(E)-1)大，每行都会有一个可以和E交换的任务。
交换后变成
ABED
ABCD
ABCD
ABEC
ABE
然后我们加入F
ABEDF
ABCDF
ABCD
ABEC
ABEF
这时候可以直接加在row后面.

打卡
本周在弄树
Invert Binary Tree
Binary Tree Level Order Traversal
236. Lowest Common Ancestor of a Binary Tree
Convert Sorted Array to Binary Search Tree