6年后端 10月计划到500

几年前Java刷了250题。如今用Python3刷，计划10月达到500题。
按照 Neetcode视频里推荐的那种方式，用 Google Sheet记录题型，题目，link，以及3-5句话描述 essence。很适合每天回顾。
这次先刷 Leetcode 官方 Explore，觉得总结分类的挺好，觉得二分最后一节的几题还真挺难弄。
【10/9】 200题
* 719. Find K-th Smallest Pair Distance. XXX: 真正的二分搜索！济公学院: Generic二分: Find the turning point in an ordered boolean function f(v). 找 how many pairs in sorted array里 whose distance <= value是经典的双指针O(N)问题。
   * 看了 huahua 和其他的视频觉得还是不好理解，看了济公的觉得不错。结合 leet form里的好贴子模板：[Python] Powerful Ultimate Binary Search Template. Solved many problems



补充内容 (2021-10-12 01:23 +8:00):
主要参考资料：花花酱，Neetcode，9章，山景城一姐，济公学院，cspiration。当然还有forum的高分答案。并不是说哪个人的讲解分析是最好的，尤其是难题，所以要多看多理解。
题目分类：seanprashad/leetcode-patterns，Dmitry Babichev's Patterns, 锤子科技未来产品经理（1k+）
模板：CP4

补充内容 (2021-10-21 01:37 +8:00):
用 Notion DB整理 Leetcode 相关 article、video
* 书：《Competitive Programming in Python》《Competitive Programmer's Handbook》《CLRS》《Algs 4》《Algorithms-UCB》
* 视频：WilliamFiset，Eddie Woo证明，happygirlzt题解视频，图灵星球Turing Planet，etc


补充内容 (2021-10-21 01:54 +8:00):
时间管理技巧：Google Calender记录时间段 Todo/Done. 用VS Code的 Code Time自动 track coding时长

补充内容 (2021-10-23 04:14 +8:00):
Huifeng Guan 1000+题解分析视频和repo: wisdompeak/LeetCode.
2018.11.30 更新: 在十一月的一次LC周赛（本人的第81场周赛）中取得了第三名。同时这个月底签了狗家。



补充内容 (2021-10-23 08:45 +8:00):
<由数据范围反推算法复杂度以及算法内容> by yxc

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 `10^7～10^8` 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择:

1. n≤30, 指数级别, dfs+剪枝，状态压缩dp
2. n≤100 => O(n3)O(n3)，floyd，dp，高斯消元
3. n≤1000 => O(n2)O(n2)，O(n2logn)O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. n≤10^4 => O(n∗n√)O(n∗n)，块状链表、分块、莫队
5. n≤10^5 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分
6. n≤10^6 => O(n)O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000n≤10000000 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
7. n≤10^9 => O(n√)O(n)，判断质数
8. n≤10^18 => O(logn)O(logn)，最大公约数，快速幂
9. n≤10^1000 => O((logn)2)O((logn)2)，高精度加减乘除
10. n≤10^100000 => O(logk×loglogk)，k表示位数O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT

补充内容 (2022-01-19 06:47 +8:00):
尽早加入 community，例如 YouTuber: Programming Live with Larry 6.48K subscribers 的 Discord，看看别人是怎么在<30min 解决每次Weekly Contest，以及多快刷到 1k club, 分享拿到 Knight的喜悦，etc 都很能激励。很多人都在2021上岸 FLAG。

在数学教育家波利亚（George Polya）看来，任何一个问题都可以无限地探究下去。他在名著《怎样解题：数学思维的新方法》中写道：“没有任何一个题目是彻底完成了的。总还会有些事情可做；在经过充分的研究和洞察以后，我们可以将任何解题方法加以改进；而且无论如何，我们总可以深化我们对答案的理解。”这实际上点出了问题导向的学习的另一个益处，就是问题可以帮助我们形成长期的、一贯的思考路径。问题构成了学习的连续性。当没有问题引导时，可能我们常常只是零散、随性地去涉猎学习材料，去捕获一些不相干的知识。这种学习的结果是得到一盘知识的沙砾。而在问题牵引下的学习，则是连续不断地构筑着知识之间的联系，使它们以一种有意义的方式连缀在一起。
——《精进》

今天才到 550 题，回看当时立下的flag，颇为羞耻...上上次周赛晚到，结果只做了1题，掉了巨多分，然后第一次Bi-weekly睡过去了... 什么时候能上1700？

去年12月加入了 Programming Live with Larry 6.48K subscribers 的 Discord，还是要早点加入 community，看看别人是怎么在<30min 解决每次Weekly Contest，以及多快拿到 Knight的，都很能激励。很多人都在2021上岸 FLAG。

2022年1月的目标 做完 FB tag的 413题，solved到 700题。 以及看最近1个月的 Amazon面经题。

觉得每做多100题又有不同的感悟，尤其是 Medium+ ~ Hard题，考察的是 general Problem Solving Skill（在各类DSA熟悉的前提下）。毕竟人生就是在不断地做决策解决问题。

这里贴一下看到的不错的文章《你知道做数学题下手的套路是怎么锤炼出来的吗？》
--------------------------------------------------------------------- 复制开始 ---------------------------------------------------------------------

波利亚在《怎样解题》一书中，将解题过程大致分成四个步骤：“弄清问题”、“拟定计划”、“实现计划”和“回顾反思”。解题时只要按这个步骤去做，必能成功。我们如果能在平时的做题中不断实践和体会这个过程，必能很快就会发出和波利亚一样的感叹：“学数学是一种乐趣！”

我们把四个步骤中每个步骤解读、概括如下：
第一，弄清问题(审题，复述问题)
这个步骤简要地说就是：寻找问题的关键性元素(描述性的词语与数学表达式，包括条件中的，也包括结论中的)，明确条件与结论。

具体要弄清楚：未知元素有哪些？已知数据(指已知数、已知图形和已知等式等的统称)是什么？条件是什么？满足条件是否可能？它是否充分、必要？是多余的？或者矛盾？引入适当的符号，转换文字描述；把条件、结论写下来。能够画图的一定画图，不管是几何图形，还是反映各符号、描述之间关系的图形。

第二，改写可能的各描述形式，转换、变形问题描述
中心思想：陌生问题熟悉化。这个步骤是探索问题解决思路的关键！

尽可能多地改写条件、或者结论中出现的，或者在审题过程中转换得到的各种数学描述形式！以自己能够理解的，尽可能通俗地形式重新叙述问题。在改写的过程中探寻曾经熟悉的问题类型或者解题思路，组合各种改写形式，探索可能的解题思路方向。

这个步骤要求我们对教材中的内容、练习的基本概念、基本思想、基本方法和例题、练习非常熟悉，并能正确理解！教材、课堂学习是我们探索解题思路与方向的基础！

第三，探索可能的解题思路与解题步骤
组合出现的各种描述形式，尝试性地探索解题过程！这个过程是一个不断失败逐步走向成功的过程！一般不要理所当然地认为可以一步到位找到解题方法，只有在不断的尝试、探索中才能找到真正可能的解题思路与步骤！为保证解题过程的正确性，要保证探索过程有理有据！

第四，验算所得到的解，回顾反思、拓展思维与问题
基本原则与中心思想：练习不在多而再精，多理解、真掌握、能延伸、会拓广. 举一反三、触类旁通！


做完题后力争做到：

• ①题目主要检测哪方面的概念与知识；
• ②部分改变题目的条件，能导出什么新的结论；
• ③题目的解题方法是否带有普遍性，是否能成为一种程序化的解法；
• ④解题中所用的技巧是如何想出的；
• ⑤由题目的条件还能考虑哪些结论？
• ⑥对于其它可能的结论依据条件可以得出来吗？
  

--------------------------------------------------------------------- 复制结束 ---------------------------------------------------------------------


迟到n久的更新，谢谢大家支持&鞭策，继续通过 Leetcode 提高 Problem Solving Skill。
Youtube上面的 古城 & 济公学院的 Leetcode视频也在一直更新，学到很多！

坐等楼主更新，光是看记录都学习了很多，感谢

10/10 完成explore binary search，开始 BST，计划明日完成。
10/11 完成 explore BST。Explore只剩 graph，开了会员，开刷。同时计划了 21天刷400题表： 17gre.github.io/17GRE/，按照17天搞定GRE单词，一次多记，记忆曲线复习，每日总结思考。

10/12 Problem Solved 220. 冲了会员，补完 explore linked list, recursion II, Hashtable. 285. Inorder Successor in BST (Inorder search 的好题）
489. Robot Room Cleaner. (回溯之走迷宫 右手法则) 仙剑的黑雾迷宫。


补充内容 (2021-10-17 05:58 +8:00):
看了 CS 106B讲的 recursion和Backtracking很好。递归很重要，哪里都要用到：DP，Search，Graph/Tree. 可以说是最基本的tool了。

10/13 计划 240题。补完Queue & Stack，Binary Search。开刷 Explore Graph。


补充内容 (2021-10-17 05:57 +8:00):
完全理解才能真正把DSA作为 toolbox用：要深入理解、思考DSA本质，推论。
只有多做medium+hard题，通过灵活运用DSA才能逼迫我更深入的理解、掌握。

10/14 Explore Graph 的 1202. Smallest String With Swaps 的同一个 union的可以任意两两swap=> 可以union的排序。然后merge sort的merge，通过stack pop简化 k-list merge. 399. Evaluate Division. WangQiuc的 augment UF字字珠玑，学到挺多的。10/15 接着看CS 106B Summer 2015的 Recursion和Backtracking，

开始还是写解题报告，因为 Neetcode的 google sheet的2-3句核心思路还是适合熟练后的复习用。现在还处于各种思路，DSA不够通透理解的阶段，还是要详细记录，画画图，分分析。
结论就是 解题报告 + google sheet。

10/15 做 399. Evaluate Division 才发现前面的 UF真的练习模板题，都没有真正运用。到了这题看了WangQiuc的augment UF才学到了，medium+hard的题都是要灵活运用DSA作为toolbox，并不一定能直接运用。画图分析的时候别人就很简洁：研究一个例子就够来发现pattern，最多再举一两个其他来做edge cases。画图发现自己又忘了union只作用于root！而因为一进入union就要find，所以做了path compression. 而这题其实理解了UF就很好想，因为UF就是等价性，所以同一个root的话，augment就是node idx，以及相对于root的ratio。自然是在find里compression和Union的时候 update。类似的有BFS、DFS都是更新所有DS。

10/16 今天学习 MST - Kruskal即UF构成 group，然而还是那句话：think deeply on simple things (DSA). 只有深入理解原理才能运用。例如 1168. Optimize Water Distribution in a Village，其实就是加一个辅助线（single virtual house as the well). 就能用MST了，因为MST只能用于 无向图的 spanning tree，而对于节点有weight没法做。通过这一点想如何把节点的weight转化为edge。创造性的变形、augment就是多做题，多思考，把高手的技术、技巧学过来。

10/17 兴奋也痛苦，刚学完 UF、MST、又来一个新算法：Eulerian Path/Circuit. 学了 Hierholzer Algorithm。早知道早点买Leetcode会员了，他们的official solution确实讲的很通透，手把手无门槛入门教学，这样学算法比上课高效太多了。 毕竟上课过于完整，对于interview超纲了，当然时间够的话还是多看多学。Hierholzer思想就是通过post order traversal 的 backtrack来 connect disjoint circles。对于DFS、recursion、backtrack又有了新的认识。
---

时间管理工具：Google Calender记录时间段 Todo/Done. 用VS Code的 Code Time自动 track coding时长

10/18 因为昨天的 Eulerian Path又翻了好几本书，发现 CP的书都有讲 Hierholzer算法，是 classics graph algorithm。参见 WilliamFiset的 repo整理的很好，也建了一个 自己的DSA toolbox（包括classics 和 problem examples）Min Cost to Connect All Points 的 MST，要 stick to framework！MST Kruskal使用 UF，单元是 点id。这题给了list of coordinate，我一开始用 坐标作为UF的元素，写起来好麻烦，还容易搞混。看了OS也说了：用id！id！id！

10/19 第一次见 3色标记法，原来是CLRS的BFS/DFS template就是这样写的 color-variant DFS. 1059. All Paths from Source Lead to
* Destination。搞 Prim 也复习 Dijkstra。
* 为了 Eulerian cycle, 注册了 Coursera上面 UCSD的 Introduction to Discrete Mathematics for Computer Science Specialization，发现第一节课就是讲 《Tiling dominoes | Dynamic programming》，WilliamFiset也讲过。

同事刚拿了软+亚麻 L5
---
这些天被 Graph搞得有点崩溃了，做一题就是一个新的算法。感觉自己很废啊...
* 来地里看看其他同学努力上岸的thread来给自己打打鸡血！[其他] 经验贴：文科生从helloworld不会写到lc可以做hard题

《到底该如何刷 LeetCode？》胡小旭 - (618题 Airbnb）#为何我坚持不下来：如果你不知道该如何树立自己的强大的梦想，也许这个UP主会帮到你——《清华生保持高效率奋斗的五大因素 | 梦想如何让你的人生充满意义》

看《从零到谷歌程序员 2个半月550题》
150+310+90，对于前200和一些高频题，我刷了两遍以上或者更多。4月到7月20面试结束。
用 手账规划学习任务，而不仅仅记录时间，要不断正反馈。

Leetcode 题目总数
#1715  Jan 9, 2021
# 2127 Jan 3, 2022

楼主非常有毅力而且深入，希望看到更新，谢谢！

go2022 发表于 2022-1-13 14:22
楼主非常有毅力而且深入，希望看到更新，谢谢！

谢谢 我现在做到500多，发现每做100题都是一个新的自己。继续加油，希望1月可以做到700. 把FB tag做了。