LeetCode打卡

这5天没有刷题。自从上次简历被拒后我又进了MERN Stack坑，开始做一个flash card小app， 希望能给递简历增加一些把握 当前进度是数据库设计完成，把前后台全部初步搭好能顺畅通信，然后能发布上Azure。由于之前的项目经历太偏后端逻辑层和数据层，每到涉及前端的时候就卡的厉害。归根结底还是css，html基础差，以及审美差。目前自己的小项目还处于主页相当丑的阶段，打算接下来连同刷题每天推进一点点，推进多少就改多少简历。

进度：310道。
几个要注意的点：
- Map中只能用Integer等object， 如果没有转换成int直接比较的话，一定要用equals替换==，这个中招太多次了！！
- Palindrom类题，多想想有没有解法涉及对称性/两头性，从外向内包围，从内向外突围两个方向都想想。

进度：312.
426. Convert Binary Search Tree to Sorted Doubly Linked List
733. Flood Fill

今天Labor Day和同学出去浪了一整天，只来得及刷2天。明天继续

楼主加油！

进度仍旧312。但今天复习了。
142. Linked List Cycle II
287. Find the Duplicate Number
一个算法，都是 Floyd's Tortoise and Hare，用快指针和慢指针。
核心思路是讲环前面的路径长设置为a，环长为b，慢指针经过intersection（I）后，再移动的距离为c，到达的点为S。
快慢相交，意味着 2(a+c) = a + b + c  =>   b = a + c
那如果某个指针从S点出发，移动a格，必然会到I点。
想让它移动a格，只需要另外设置一个指针在起始点，和S点的指针一起移动。
它们移动a格会相交于I。

心得：之前在Linked List里也看到一道带Cycle的题，但是最终求的东西不太一样，记忆中好像也是通过快慢指针做。反正Cycle题两种，一种是指针，一种是数组里的数值即为下标指针（第二种在题目描述里，数值上会有一定暗示）。求什么并不一定。但需要通过快慢指针（暗含2倍关系），设几个未知数建立方程式。应该不管求什么都能从方程式里得到有用信息。
可能拓展方向：不仅2倍，可能3倍关系等都能转化为有用信息。理论上只要方程成立，应该能获取各种不同信息，下次需要往方程和双指针方向想！！

今日进度: 329

最近几天开始，每天一场Virtual Contest和Google Doc Mock Interview，然后依次看Discussion学习大家简洁的写法，也开始贡献自己的解法了。我发现写英文题解和自己Mock自己很有助于锻炼用英语描述自己的解法，一开始不论说还是写都有点磕磕绊绊，相信长期坚持下来会对自己面试时的表达能力有所改变。
加油，又是奋斗的一天！

今日进度: 330

昨晚没睡好严重影响今天效率和思维了。模拟面试感觉自己解释东西很混乱。而且犯了一下小错误导致没有及时调出来。
需要补充的知识点: Probability +Random + 几何代数词汇。
明天开始模拟面试和比赛都切换回C++以适应新面试公司的要求。

今日进度: 343

整理一下这几天的题。感觉自己还是需要每天整理，特别容易漏..

发现一波结合快慢指针和单调栈或纯单调栈能O(n)时间内出答案，且代码能长的像，利于标准化的题目...
84. Largest Rectangle in Histogram
85. Maximal Rectangle
221. Maximal Square
739. Daily Temporature
907. Sum of Subarray Minimums
Codeforces - 509(Div.2)-D Glinder
--------------------------------------------------------
其中好几道在第一次做的时候都使用了binary search，后来发现只要有别的指针维护好单调栈什么时候进栈即可，或者出栈的时候更新答案。
也有像Daily Temporature这样凑好的情况，不需要第二个指针。
总结：凡是有单调性可用binary_search的题目，都往单调栈+双指针+或者出栈时处理信息方向想。
单调性的方向往往和范围的限定有关，如果要求某段区间（上限下限），或者像Glinder那样在推导dp状态时，出现了<=, >=, <, >一般都可以试试搞一个单调vector
------------------------------------------------------------------
480. Sliding Window Median
295. Find Median from Data Stream           
priority_queue比较容易想到，但multiset和双指针结合这种思路还挺难想到的。
201. Bitwise AND of Numbers Range
自己想到的是从后往前挨个处理一个个"1"，然后答案里见到了直接处理range前缀不同处的唯一那个(0,1) pair。
觉得以后要认真思考是不是有必要1个个处理有效位，有没有一个关键点像pivot一样重要（一般容易发生在极左或极右处）

补充单调栈/队列的题目:
239. Sliding Window Maximum
862. Shortest Subarray with Sum at Least K
都维护一个单调队列，弹从尾巴弹，取数值从头取。
区别是：239的队列源自固定长度的sliding window
862的队列是因为需要查看 比当前数值-K的数。

今天面JingChi了。这几天从单纯刷LC，改为LC+各种oj。
这两天补充练习了以下知识点。
1. DP + 微积分 or DP + 概率/期望
------------------------------------------------------------------------
poj1160 => DP + 滚动数组优化
1160距离平方+邮局可建在任何地方版。多一步求导找0点。
1160距离平方+邮局必须建在村庄位置版。二分查找最佳位置附近的村庄。
期望DP:
poj2096 - 期望DP经典题, 注意处理边界，逆序。
hdu4405-同理

2. 简单DFS/BFS：
LC102 - vertically print a tree

3. 图论/欧拉回路/并查集/dijkstra:
JingChi考得比较综合（例如走象棋、字符接龙），考虑面试会换题，就多练了几道。
poj2387 - 入门Dijkstra
hdu1213 - 入门并查集
hdu1878 - 无向图欧拉路径，需要度数为偶数，且连通（并查集判断）

4. 计算器:
LC Calculator III

补充：今天面完后发现准备的一个都没考到，考了LC两道题，题目不难，就是现场心态不太好错了好多细节，觉得对我来说mock比刷题重要了，面试竟然会这么影响发挥的吗....  真的是紧张星人。。。