秋季新学期计划 - 刷题|补基础|准备面试

一、暑假学习情况和总结：四个月前定的假期计划勉勉强强算是基本完成，主要还是因为当制定的计划很不科学，使得很多没有必要、或者没有能力去学习到的内容被当作目标，而一部分本应该学习扎实的内容反而被忽略；不过还好有很多热的同学在帖子里给我留言建议，让我能够及时修改我的学习计划，使得最终我这段时间还是完成了一些学习内容。1）LC前400道题目按照分类列表已经全部做完，并且绝大部分题目写完后都有一定的回忆和总结，感觉现在做题算是不像原来那么盲目，有一点点感觉了；
2）OO Design / System Design这两个方面，通过看视频有了一些初步的了解，知道它们都是怎么一回事、出发点是什么、以及常见的案例；
3）Spring、SpringBoot以及包括maven、jdbc、hibernate等等其他一些工具，经过这段时间的跟着网课视频写代码，初步了解了一些核心的概念，并熟悉了基本开发及使用流程，通过一些面试后，感觉如果被问到这方面的话自己也算是有话可说了；
4）基本web开发，通过重新回顾网课和比较仔细地记笔记，使得自己对这一整套前后端开发流程以及各个层面之间的交互关系有了一定的了解，对前端的一些概念也做了一些总结从而加深了印象；
5）简历上把上学期从网上抄来的可以包装但是一问三不知的项目都抛弃掉，增加了两个自己稍微更理解一些的项目。


二、现状和存在的问题：虽然暑假的时候完成了一些内容，但是通过这段时间的学习仍然发现了自己的路线和规划存在着很大的问题，也发现了自己在很多地方仍然是非常的薄弱和欠缺；由于在校内转了新的专业，实际上就相当于多交了一部分学费换取了更多的学习准备时间，那就希望能够好好利用这多出来的时间，解决当前存在的各种问题才行。
1）英语听说能力，尤其是面试英语听说的准备，我感觉这方面真的没有完全准备好的时候，最好的锻炼方法还是得让自己有一个实习才行，现在能够在面试时跟人扯上一两个小时已经是极限，新学期需要多去学校的一些机构练英语；
2）BQ问题，我在上个月的一个电话面试的时候第一次被问到了BQ，因为完全没有准备过，结果被问到对原来工作经历最喜欢和最不喜欢的地方，实际上我回答的都是同样的内容，语无伦次，前后逻辑有硬伤；
3）Java语言特性，这部分其实自己有一定的了解，但大多浮于表面，比如问我GC究竟是怎么处理垃圾的具体过程，或者问我hash collision的具体处理办法，我就完全答不上来；
4）Java Web开发，只熟悉大致的流程，但是随便找出一些细节性问题问我，比如应该如何用JDBC处理sql dialect，如何对前端发来的query进行权限设置等待，本质上还是对简历内容的不了解，为了让简历好看而盲目添加自己并不掌握充分的内容；
5）OO Design类的问题，当前仅仅是机械被动学习知识点并不能举一反三，并没有真正动手对各种典型类别的实际问题进行设计练习，使得面试时被问到的最基础的Design问题都答不上来；
6）算法题目，虽然做了很多题，但是大部分都是参考别人的讨论，很多都没来得及复习并且很多都没有做到一题多解，理解思路以后自己在实现过程中如果代码出现了问题都很难自己解决，此外在做题的时候都是闷头做题一声不吭，没有做到用英语去叙述出来自己的解题思路。

三、新学期的目标方向和计划：在吸取总结了各种经验教训、跟其他基础扎实且热心的同学交流、并结合自己现在的阶段处境之后，我认为在新学期自己的准备大致内容应该分为做算法题、做设计题、学习CS基础知识、补习Java语言特知识、补习开相关的基础知识等；因此主要仍然是做各种题目和总结归纳，同时对Java的基础和开发方面的知识要加深理解，最后一定要挤出时间学习一些计算机基础知识；目标是希望能够多投简历多面试，最好能够找到明年春/夏的实习，即使找不到也能够积累更多的经验，同时把基础打扎实，这样就至少不算浪费时间了。
1）刷题：复习回顾假期完成的前400道题目，同时每天固定完成5个某大公司tag的题目，开始参加周末的contest；
2）OOD/SD：回顾之前看过的相关视频，阅读各种相关帖子、博客、教程，熟悉各种类型的例题并尽量练习；
3）计算机基础知识：主要包括计算机组成原理、操作系统、计算机网络，这三个部分感觉还是很有必要做一些初步了解的，因为在自己准备转码的过程中很多问题归根结底都属于这些方面，不求和科班同学一样的水平，但是一定要有基本的了解；
4）Java语言特性：主要是Java基础语法、Java面向对象、Java字符串、Java集合、Java异常、Java泛型、Java枚举、Java I/O、Java内存和GC、Java并发和多线程等等，这些太容易被问到，而且重点的地方会被问的非常细致；
5）Java服务端编程：首先是要熟悉JSP+Servlet+JDBC，然后熟悉MySQL的基本使用和常考知识点，接下来就是熟悉Spring、SpringMVC、Hibernate、SpringBoot、SpringCloud以及其他相关开发的操作流程和原理，把简历上涉及到的掌握即可；
6）Web开发：建立一个个人web作品的portfolio网站，如果有时间的话再去看完暑假没有来得及看完的进阶web课、学一个前端框架，并且把JS和CSS(BootStrap)相关的常考知识点进行整理总结；
7）BQ问题准备：根据在论坛各种帖子里搜集到的典型BQ问题，尽量每天写一个BQ问题并且加以练习，希望通过这种方式对BQ开始初步的准备，顺便练练口语。



补充内容 (2019-10-12 21:06):
到现在为止我不是那么想每一题都总结那么多了，因为现在也还是复习前400个题，总结之前都有，我感觉应该提高做题速度，多见见一些题目才对；因此我决定从这周末开始每天做10题，就做前400题中的比较重点的250个题

补充内容 (2019-10-21 11:41):
更新一下，我拿到了实习offer了，offer比较小，但是好像因为是在学校的平台上找的也没办法拒

补充内容 (2019-11-23 14:41):
其实已经好久没有系统刷题了所以帖子一直没更新，因为不得不接受实习所以其实接下来的计划也就全部改变了，这个帖子以后也就不会再更新了，下学期一边实习一边刷题然后完善各种技能，准备明年下半年的全职秋招

9.4 做题

621. Task Scheduler. 这个题目使用了Greedy的思路：先放好出现频次最多的那个task，这些频次最多的task的安放原则就是，它们之间均匀排列，每个之间的间隔就都是题目中规定的cooling区间数n；在安置好这个频次最多的task之后，其他的task就依次插入进这些频次最多的task的中间的间隔即可；就比如给定的char array是AABABC，并且n = 2的话，那么A的频次最高是3，因此按上面说的安排A：A ? ? A ? ? A，然后再安排两个B就这样放：A B ? A B ? A，最后是那一个C：A B C A B ? A，这样就可以看出，一共是剩下了一个间隔，那么这个间隔就是idle，因此这个task序列和冷却的结果就应该是7个task加上一个间隔也就是8；总结来说，首先找到出现频次最高的task，然后它的安排相当于划分出了这样的一个部分part = count(A) - 1，也就是两组间隔，而每一组间隔的数量都是给定的n；那么也就是说现在可以放置那些非最高频次的task的间隔数一共就是part * n；而还剩下的非最高频次的task的数量，就相当于是task的总数减去最高频次task的频次；那么idle的数量，其实就是当前一共的间隔数量，减去当前还剩下等待安排的task数量；最后返回的结果就是总共的task数量加上idle的数量；这个题目当然不会这么简单，比如一些情况需要考虑的就是，如果最高频次的task有多个怎么办（比如AABABBCC，出现了3个A和3个B），或者如果最高频次的task太多了怎么办（比如AABBCDCDEEFFG，除了G以外其他所有的task都是最高频次的，最高频次task的数量本身高于了给定的n）；这些特殊情况可以在discussion里面看着解决；当然这个题目除了greddy的方法之外还有用PriorityQueue和HashMap的方法，其实也是greedy的思路，先去找频次最大的字符来进行安置

560. Subarray Sum Equals K. 首先这个题目不能用two pointers，因为可能数组中有负数元素存在；这个题目的方法就是，想要找sum为k的subarray，实际上就是要确定在数组中是否存在一个(i, j)的subarray使得sum(i, j)正好等于k；而sum(i, j)正好等于sum(0, j) - sum(0, i - 1)，因此这个题目可以用prefix sum的方法；那么具体来说，在遍历数组的时候记录从起始位置到当前位置的sum，如果对于每一个为止的sum，都能立刻检查出sum - k是否在之前的位置的遍历中算出来的话就好了；这是因为，现在的位置j的sum(0, j)是sum，而现在希望看看是不是能够找到有一个从i到j的subarray它的sum(i, j)为k，那么实际上就是，只要能够找到一个i，使得从起始位置到它开始的sum(0, i - 1)正好等于sum - k就可以了，因为如果它存在，那么就意味着k存在；即，sum[i, j] = sum[0, j] - sum[0, i - 1]可以转化为sum[0, i - 1] = sum[0, j] - sum[i, j]，sum[0, j]是当前算出来的，sum[i, j]是给定的target，通过算出来sum[0, i - 1]后，能够找到它就可以了；那么怎么找到它呢？用HashMap，用这个map去记录每次遍历到一个位置的时候，从起始位置到当前位置的prefix sum就可以了；如果map中存在它，就说明有subarray是满足target条件的；那么key是prefix sum，value就是频次，因为存在负数的原因，可能一个prefix sum为某个数的subarray会出现很多次，那么也就意味着满足sum为sum[0, i - 1]的subarray其实就会有多个，这样valid的满足sum为sum[i, j]的subarray也会有很多个；所以每次找到prefix sum后，往结果中加入它在map中的value，也就是频次即可

953. Verifying an Alien Dictionary. 这个题目的关键还是，把给定的alien dict规定的字母顺序，和原有的字母都给map起来，就要建立起来一个，26个字母中的每个字符在新的alien dict中都排在第几位的map，比如在给定的"hlabcdefgijkmnopqrstuvwxyz"里面，字母h对应第0位，l对应第1位，a对应第2位这样；因此遍历order字符串，建立一个map；然后对于给定的words数组，从前到后把挨着的两个word进行比较；比较的方法就是两个String一个一个位置的字母进行检查，如果发现对应位置的两个字母不一样，然后就去看看是不是前一个word的当前字符在map中的顺序，比后一个word的当前字符的顺序考前就好了；如果考前就是true，否则就是false

426. Convert Binary Search Tree to Sorted Doubly Linked List. 把一个BST改成sorted的双向练表，其实就是考察BST的inorder和练表的各种操作；BST的inorder是排好顺序的，那么就肯定是在recursion里面，先用recursion function去弄好root.left的，然后对root进行某种操作，接下来再去弄root.right的；那么这个某种操作究竟是什么操作呢？其实就是把当前BST的node改成双向练表的node的转化；对于双向练表的node来说，其实，仍然是有左右指针，只不过不再指向左右子节点，而是指向前后节点；那么具体的转化操作就是，对于当前的node，它的左指针应该指向它的前一个节点，也就是跟他挨着的比他小的节点，而他的右指针就应该指向它的后一个节点，也就是跟他挨着的比他大的节点；因此这里的inorder操作时，recurion去处理left node的话，应该返回一个node，返回的这个node，应该和当前处理的当前node的关系，就应该是当前node的前一个node；也就是说，recursion处理的left子树后，返回的应该是在双向链表中的当前的node前一个node，其实按照sorted顺序也就应该是BST的当前node的左子树的最大的那个，也就是最右子节点；返回了这个pre节点以后，中间的操作就是，把当前节点的left指向pre，然后把pre的right指向当前节点；然后再去recursion处理当前node的右子树，处理完以后返回的节点，其实按照recursion方法的定义，就应该实际上是右子树的最右边节点，也就是当前node为root的tree的最大节点了，这个结果也就可以应用到其他上一层的recursion中；在处理完整个tree以后，还有注意收尾node也应该链接起来，即后一个node的left指向前一个node，前一个node的right指向后一个node

680. Valid Palindrome II. 这个题目就用左右指针相向而行，如果遇到不一样的字符，那么对于一般来说就应该直接返回false了；那么这个题目允许删除一个字符来继续尝试，那么实际上就相当于，对于这两个不一样的字符，要么删除左指针指向的字符以后继续验证，要么删除右指针指向的字符继续验证；如果删除左的，那么继续验证的时候实际上就是验证从left + 1位置一直到right位置的substring是不是一个Palindrome了，验证方法同样也是左右指针相向而行挨个验证是不是相同字符；如果删除右的话，那就验证从left到right - 1的位置进行验证了

9.4 做题

621. Task Scheduler. 这个题目使用了Greedy的思路：先放好出现频次最多的那个task，这些频次最多的task的安放原则就是，它们之间均匀排列，每个之间的间隔就都是题目中规定的cooling区间数n；在安置好这个频次最多的task之后，其他的task就依次插入进这些频次最多的task的中间的间隔即可；就比如给定的char array是AABABC，并且n = 2的话，那么A的频次最高是3，因此按上面说的安排A：A ? ? A ? ? A，然后再安排两个B就这样放：A B ? A B ? A，最后是那一个C：A B C A B ? A，这样就可以看出，一共是剩下了一个间隔，那么这个间隔就是idle，因此这个task序列和冷却的结果就应该是7个task加上一个间隔也就是8；总结来说，首先找到出现频次最高的task，然后它的安排相当于划分出了这样的一个部分part = count(A) - 1，也就是两组间隔，而每一组间隔的数量都是给定的n；那么也就是说现在可以放置那些非最高频次的task的间隔数一共就是part * n；而还剩下的非最高频次的task的数量，就相当于是task的总数减去最高频次task的频次；那么idle的数量，其实就是当前一共的间隔数量，减去当前还剩下等待安排的task数量；最后返回的结果就是总共的task数量加上idle的数量；这个题目当然不会这么简单，比如一些情况需要考虑的就是，如果最高频次的task有多个怎么办（比如AABABBCC，出现了3个A和3个B），或者如果最高频次的task太多了怎么办（比如AABBCDCDEEFFG，除了G以外其他所有的task都是最高频次的，最高频次task的数量本身高于了给定的n）；这些特殊情况可以在discussion里面看着解决；当然这个题目除了greddy的方法之外还有用PriorityQueue和HashMap的方法，可能是比较容易推广的办法

560. Subarray Sum Equals K. 首先这个题目不能用two pointers，因为可能数组中有负数元素存在；这个题目的方法就是，想要找sum为k的subarray，实际上就是要确定在数组中是否存在一个(i, j)的subarray使得sum(i, j)正好等于k；而sum(i, j)正好等于sum(0, j) - sum(0, i - 1)，因此这个题目可以用prefix sum的方法；那么具体来说，在遍历数组的时候记录从起始位置到当前位置的sum，如果对于每一个为止的sum，都能立刻检查出sum - k是否在之前的位置的遍历中算出来的话就好了；这是因为，现在的位置j的sum(0, j)是sum，而现在希望看看是不是能够找到有一个从i到j的subarray它的sum(i, j)为k，那么实际上就是，只要能够找到一个i，使得从起始位置到它开始的sum(0, i - 1)正好等于sum - k就可以了，因为如果它存在，那么就意味着k存在；即，sum[i, j] = sum[0, j] - sum[0, i - 1]可以转化为sum[0, i - 1] = sum[0, j] - sum[i, j]，sum[0, j]是当前算出来的，sum[i, j]是给定的target，通过算出来sum[0, i - 1]后，能够找到它就可以了；那么怎么找到它呢？用HashMap，用这个map去记录每次遍历到一个位置的时候，从起始位置到当前位置的prefix sum就可以了；如果map中存在它，就说明有subarray是满足target条件的；那么key是prefix sum，value就是频次，因为存在负数的原因，可能一个prefix sum为某个数的subarray会出现很多次，那么也就意味着满足sum为sum[0, i - 1]的subarray其实就会有多个，这样valid的满足sum为sum[i, j]的subarray也会有很多个；所以每次找到prefix sum后，往结果中加入它在map中的value，也就是频次即可

953. Verifying an Alien Dictionary. 这个题目的关键还是，把给定的alien dict规定的字母顺序，和原有的字母都给map起来，就要建立起来一个，26个字母中的每个字符在新的alien dict中都排在第几位的map，比如在给定的"hlabcdefgijkmnopqrstuvwxyz"里面，字母h对应第0位，l对应第1位，a对应第2位这样；因此遍历order字符串，建立一个map；然后对于给定的words数组，从前到后把挨着的两个word进行比较；比较的方法就是两个String一个一个位置的字母进行检查，如果发现对应位置的两个字母不一样，然后就去看看是不是前一个word的当前字符在map中的顺序，比后一个word的当前字符的顺序考前就好了；如果考前就是true，否则就是false

426. Convert Binary Search Tree to Sorted Doubly Linked List. 把一个BST改成sorted的双向练表，其实就是考察BST的inorder和练表的各种操作；BST的inorder是排好顺序的，那么就肯定是在recursion里面，先用recursion function去弄好root.left的，然后对root进行某种操作，接下来再去弄root.right的；那么这个某种操作究竟是什么操作呢？其实就是把当前BST的node改成双向练表的node的转化；对于双向练表的node来说，其实，仍然是有左右指针，只不过不再指向左右子节点，而是指向前后节点；那么具体的转化操作就是，对于当前的node，它的左指针应该指向它的前一个节点，也就是跟他挨着的比他小的节点，而他的右指针就应该指向它的后一个节点，也就是跟他挨着的比他大的节点；因此这里的inorder操作时，recurion去处理left node的话，应该返回一个node，返回的这个node，应该和当前处理的当前node的关系，就应该是当前node的前一个node；也就是说，recursion处理的left子树后，返回的应该是在双向链表中的当前的node前一个node，其实按照sorted顺序也就应该是BST的当前node的左子树的最大的那个，也就是最右子节点；返回了这个pre节点以后，中间的操作就是，把当前节点的left指向pre，然后把pre的right指向当前节点；然后再去recursion处理当前node的右子树，处理完以后返回的节点，其实按照recursion方法的定义，就应该实际上是右子树的最右边节点，也就是当前node为root的tree的最大节点了，这个结果也就可以应用到其他上一层的recursion中；在处理完整个tree以后，还有注意收尾node也应该链接起来，即后一个node的left指向前一个node，前一个node的right指向后一个node

680. Valid Palindrome II. 这个题目就用左右指针相向而行，如果遇到不一样的字符，那么对于一般来说就应该直接返回false了；那么这个题目允许删除一个字符来继续尝试，那么实际上就相当于，对于这两个不一样的字符，要么删除左指针指向的字符以后继续验证，要么删除右指针指向的字符继续验证；如果删除左的，那么继续验证的时候实际上就是验证从left + 1位置一直到right位置的substring是不是一个Palindrome了，验证方法同样也是左右指针相向而行挨个验证是不是相同字符；如果删除右的话，那就验证从left到right - 1的位置进行验证了

9.11 做题

416. Partition Equal Subset Sum. LC的discussion看这个：01-knapsack-detailed-explanation. 这个题目是0/1背包问题，用DP去做，问题的本质就是，给了一个集合，看看这个集合中是否能够挑出来一些数字，使得这几个数字的和正好等于给定的target；对于这个题目来说，那就是给的这个数组，找出是否存在其中的几个元素，使他们的和，正好等于数组全部元素的总和的一半；那么用DP的方法处理0/1背包问题的话，是需要一个二维的dp：dp[j]，i就表示给定数组的index，j则表示从0到target的累加和，那么dp[j]的物理意义就是，看看数组的前i个数字中，是否能找到若干个，使他们的和加起来等于j；那么最后要找到的就是，看看数组的所有数字中，是否能找到若干个，使他们加起来的和等于target；那么induction rule就是，对于当前的这个数组元素，如果不取的话，dp[j]就应该等于dp[i - 1][j]，如果取的话dp[j]就应该等于dp[i -1][j - nums]；因为不取的话其实就相当于没有这个数组元素一样，如果取的话，那么暂时的目标和j就应该减去取到的这个nums；因此就是dp[j] = dp[i - 1][j] || dp[i - 1][j - nums]

622. Design Circular Queue. 要求实现一个Queue但不是普通的queue，而是首尾相连的；那么就是说，FIFO的时候，比如现在有1，2，3，4这几个在queue中，如果pop的话就是从1开始，offer的话则是从4的后面；那么就希望是这样，pop一次变成了2，3，4这种，如果再offer5进去的话就变成这样5，2，3，4；那么如果再pop的话，或者单纯检查Queue最前面的元素的话，仍然是2；这就相当于一个Queue的数据结构，只不过有一个头指针和尾指针，如果在尾部offer完了，尾指针会自动跑到前面空余的地方去；因此maintain一个array，一个front指针和一个rear指针，同时记录当前Queue中的元素；如果offer的话，那就是在rear部分offer，rear要加1，然后array[rear]等于要被offer的数；当然由于需要首尾相连，因此rear不能单纯的加1，比如现在rear在3的位置，而0的位置被pop出去了，那么rear+1就会out of bound，因此rear再往后应该等于0才对，所以就是说，应该是rear = (rear + 1) % array.length，这样就可以循环进行了；那么对于pop的操作也是一样，只是对front操作就可以了；其他的API都很容易实现，利用count就好了，count就是offer的时候加1，pop的时候减1，验证是否为空为满就是count是否等于数组长度，或者是等于0

885. Spiral Matrix III. 这个题目可以算是矩阵操作题目，只要搞清楚从起始位置开始，到底一步一步是怎么走的，走多长、哪个方向就好了；这个题目就是，从起始位置开始，转着圈走，也就是先往左、再往下、再往右、再往上走，但是如果每次走的步长一样的话，那就一直原地不动了，所以每次走的步长有所不同：每当要往左走的时候，走的步长应该是上一次走的步长加1；每当要往右走的时候，步长也应该是上一步加1；只有这样才能不断扩大自己走的范围，最终完全覆盖住给定的矩阵；那么这种问题一般都是实现给一个二维固定数组，作为direction{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}；然后从当前点开始，一开始是往左走，走当前的步长，然后往下走；然后往右走的时候，当前步长加1，再接着往上走；就一直这么走，步长根据方向去看看是不是要改变，然后每次走到新的位置，都看看是不是在矩阵范围之内，如果是的话，把坐标添加进结果里面就好了

678. Valid Parenthesis String. 这个题目看上去有多种方法，iteraitve就可以做，不过代码很复杂，这里我先用recursion/DFS的方法做的；就是说现在的字符串有左括号、右括号、星星，星星可以作为左右括号用，也可以作为空；那么检查的方法就是，maintain一个count；如果遇到左括号，count++，表示现在有很多可以匹配的左括号；如果遇到右括号，count--，表示现在有一个右括号跟左括号匹配了；如果count在某一个步骤小于0的话，就说明左括号不够用了，肯定错；如果遇到星星，分三种情况讨论，也就是上面的三种；体现在recursion当中就是，下一步的recursion里面要么count增加了说明星星作为左括号，要么count减少了说明星星作为右括号，要么count不变说明星星为空，但是当前的index肯定要往前走的

489. Robot Room Cleaner. 这个题目是非常好的题，其实思路很直观，但是很难想像出这个代码应该是什么样子；就是给一个机器人，有四个API分别是向左转、向右转、前进、打扫；那么现在假设机器人在0-0位置上，首先0-0位置需要打扫，然后在一个Set里记录下来这个0-0；之后因为有四个方向，那么就做四次循环，每次循环指向一个方向，那么当然还是需要一个方向矩阵{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}；那么每次循环取一个方向，首先根据当前位置算出接下来要去的位置，也就是当前坐标加上当前的方向矩阵的pair；然后取Set里面看看，这个位置是不是已经visited过了，并且调用move走一下，如果走成功了说明没有障碍，并且robot实际已经到了前一个点了；到了新的点以后，在recursion调用当前的这个函数进行处理；处理好之后，robot在新的点要返回原来的位置，也就是转一百八十度，然后走，然后转一百八十度（这里是为返回原来的方向）；接下来在这次循环的最后，turnRight一下，因为需要改变方向；这里注意，并不是说，四次循环调用方向矩阵的pair就能自动改变方向了，只是用方向矩阵的四次循环，能够帮助提前算出来下一次的方向，从而方便去Set里面提前验证而已；真正改变方向的还是循环最后的turnRight；然后curDir也需要作为参数传入，因为并不是每一次都得是先向左，如果这个robot本来现在是想下的，那么这个方向也应该向下走才对

每天做五个题目+复习至少五个题目，然后在此基础上通过看视频和复习笔记来学习基础知识+语言知识+开发知识，希望能够坚持下来

9.4 做题

（刚刚打卡打不出来不知道为啥……

621. Task Scheduler. 这个题目使用了Greedy的思路：先放好出现频次最多的那个task，这些频次最多的task的安放原则就是，它们之间均匀排列，每个之间的间隔就都是题目中规定的cooling区间数n；在安置好这个频次最多的task之后，其他的task就依次插入进这些频次最多的task的中间的间隔即可；就比如给定的char array是AABABC，并且n = 2的话，那么A的频次最高是3，因此按上面说的安排A：A ? ? A ? ? A，然后再安排两个B就这样放：A B ? A B ? A，最后是那一个C：A B C A B ? A，这样就可以看出，一共是剩下了一个间隔，那么这个间隔就是idle，因此这个task序列和冷却的结果就应该是7个task加上一个间隔也就是8；总结来说，首先找到出现频次最高的task，然后它的安排相当于划分出了这样的一个部分part = count(A) - 1，也就是两组间隔，而每一组间隔的数量都是给定的n；那么也就是说现在可以放置那些非最高频次的task的间隔数一共就是part * n；而还剩下的非最高频次的task的数量，就相当于是task的总数减去最高频次task的频次；那么idle的数量，其实就是当前一共的间隔数量，减去当前还剩下等待安排的task数量；最后返回的结果就是总共的task数量加上idle的数量；这个题目当然不会这么简单，比如一些情况需要考虑的就是，如果最高频次的task有多个怎么办（比如AABABBCC，出现了3个A和3个B），或者如果最高频次的task太多了怎么办（比如AABBCDCDEEFFG，除了G以外其他所有的task都是最高频次的，最高频次task的数量本身高于了给定的n）；这些特殊情况可以在discussion里面看着解决；当然这个题目除了greddy的方法之外还有用PriorityQueue和HashMap的方法，其实也是先安排频次最大的task的思路

560. Subarray Sum Equals K. 首先这个题目不能用two pointers，因为可能数组中有负数元素存在；这个题目的方法就是，想要找sum为k的subarray，实际上就是要确定在数组中是否存在一个(i, j)的subarray使得sum(i, j)正好等于k；而sum(i, j)正好等于sum(0, j) - sum(0, i - 1)，因此这个题目可以用prefix sum的方法；那么具体来说，在遍历数组的时候记录从起始位置到当前位置的sum，如果对于每一个为止的sum，都能立刻检查出sum - k是否在之前的位置的遍历中算出来的话就好了；这是因为，现在的位置j的sum(0, j)是sum，而现在希望看看是不是能够找到有一个从i到j的subarray它的sum(i, j)为k，那么实际上就是，只要能够找到一个i，使得从起始位置到它开始的sum(0, i - 1)正好等于sum - k就可以了，因为如果它存在，那么就意味着k存在；即，sum[i, j] = sum[0, j] - sum[0, i - 1]可以转化为sum[0, i - 1] = sum[0, j] - sum[i, j]，sum[0, j]是当前算出来的，sum[i, j]是给定的target，通过算出来sum[0, i - 1]后，能够找到它就可以了；那么怎么找到它呢？用HashMap，用这个map去记录每次遍历到一个位置的时候，从起始位置到当前位置的prefix sum就可以了；如果map中存在它，就说明有subarray是满足target条件的；那么key是prefix sum，value就是频次，因为存在负数的原因，可能一个prefix sum为某个数的subarray会出现很多次，那么也就意味着满足sum为sum[0, i - 1]的subarray其实就会有多个，这样valid的满足sum为sum[i, j]的subarray也会有很多个；所以每次找到prefix sum后，往结果中加入它在map中的value，也就是频次即可

9.4 继续做题

953. Verifying an Alien Dictionary. 这个题目的关键还是，把给定的alien dict规定的字母顺序，和原有的字母都给map起来，就要建立起来一个，26个字母中的每个字符在新的alien dict中都排在第几位的map，比如在给定的"hlabcdefgijkmnopqrstuvwxyz"里面，字母h对应第0位，l对应第1位，a对应第2位这样；因此遍历order字符串，建立一个map；然后对于给定的words数组，从前到后把挨着的两个word进行比较；比较的方法就是两个String一个一个位置的字母进行检查，如果发现对应位置的两个字母不一样，然后就去看看是不是前一个word的当前字符在map中的顺序，比后一个word的当前字符的顺序考前就好了；如果考前就是true，否则就是false

426. Convert Binary Search Tree to Sorted Doubly Linked List. 把一个BST改成sorted的双向练表，其实就是考察BST的inorder和练表的各种操作；BST的inorder是排好顺序的，那么就肯定是在recursion里面，先用recursion function去弄好root.left的，然后对root进行某种操作，接下来再去弄root.right的；那么这个某种操作究竟是什么操作呢？其实就是把当前BST的node改成双向练表的node的转化；对于双向练表的node来说，其实，仍然是有左右指针，只不过不再指向左右子节点，而是指向前后节点；那么具体的转化操作就是，对于当前的node，它的左指针应该指向它的前一个节点，也就是跟他挨着的比他小的节点，而他的右指针就应该指向它的后一个节点，也就是跟他挨着的比他大的节点；因此这里的inorder操作时，recurion去处理left node的话，应该返回一个node，返回的这个node，应该和当前处理的当前node的关系，就应该是当前node的前一个node；也就是说，recursion处理的left子树后，返回的应该是在双向链表中的当前的node前一个node，其实按照sorted顺序也就应该是BST的当前node的左子树的最大的那个，也就是最右子节点；返回了这个pre节点以后，中间的操作就是，把当前节点的left指向pre，然后把pre的right指向当前节点；然后再去recursion处理当前node的右子树，处理完以后返回的节点，其实按照recursion方法的定义，就应该实际上是右子树的最右边节点，也就是当前node为root的tree的最大节点了，这个结果也就可以应用到其他上一层的recursion中；在处理完整个tree以后，还有注意收尾node也应该链接起来，即后一个node的left指向前一个node，前一个node的right指向后一个node

680. Valid Palindrome II. 这个题目就用左右指针相向而行，如果遇到不一样的字符，那么对于一般来说就应该直接返回false了；那么这个题目允许删除一个字符来继续尝试，那么实际上就相当于，对于这两个不一样的字符，要么删除左指针指向的字符以后继续验证，要么删除右指针指向的字符继续验证；如果删除左的，那么继续验证的时候实际上就是验证从left + 1位置一直到right位置的substring是不是一个Palindrome了，验证方法同样也是左右指针相向而行挨个验证是不是相同字符；如果删除右的话，那就验证从left到right - 1的位置进行验证了

9.4 继续做题

953. Verifying an Alien Dictionary. 这个题目的关键还是，把给定的alien dict规定的字母顺序，和原有的字母都给map起来，就要建立起来一个，26个字母中的每个字符在新的alien dict中都排在第几位的map，比如在给定的"hlabc..."里面，字母h对应第0位，l对应第1位，a对应第2位这样；因此遍历order字符串，建立一个map；然后对于给定的words数组，从前到后把挨着的两个word进行比较；比较的方法就是两个String一个一个位置的字母进行检查，如果发现对应位置的两个字母不一样，然后就去看看是不是前一个word的当前字符在map中的顺序，比后一个word的当前字符的顺序考前就好了；如果考前就是true，否则就是false

426. Convert Binary Search Tree to Sorted Doubly Linked List. 把一个BST改成sorted的双向练表，其实就是考察BST的inorder和练表的各种操作；BST的inorder是排好顺序的，那么就肯定是在recursion里面，先用recursion function去弄好root.left的，然后对root进行某种操作，接下来再去弄root.right的；那么这个某种操作究竟是什么操作呢？其实就是把当前BST的node改成双向练表的node的转化；对于双向练表的node来说，其实，仍然是有左右指针，只不过不再指向左右子节点，而是指向前后节点；那么具体的转化操作就是，对于当前的node，它的左指针应该指向它的前一个节点，也就是跟他挨着的比他小的节点，而他的右指针就应该指向它的后一个节点，也就是跟他挨着的比他大的节点；因此这里的inorder操作时，recurion去处理left node的话，应该返回一个node，返回的这个node，应该和当前处理的当前node的关系，就应该是当前node的前一个node；也就是说，recursion处理的left子树后，返回的应该是在双向链表中的当前的node前一个node，其实按照sorted顺序也就应该是BST的当前node的左子树的最大的那个，也就是最右子节点；返回了这个pre节点以后，中间的操作就是，把当前节点的left指向pre，然后把pre的right指向当前节点；然后再去recursion处理当前node的右子树，处理完以后返回的节点，其实按照recursion方法的定义，就应该实际上是右子树的最右边节点，也就是当前node为root的tree的最大节点了；在处理完整个tree以后，还有注意收尾node也应该链接起来，即后一个node的left指向前一个node，前一个node的right指向后一个node

680. Valid Palindrome II. 这个题目就用左右指针相向而行，如果遇到不一样的字符，那么对于一般来说就应该直接返回false了；那么这个题目允许删除一个字符来继续尝试，那么实际上就相当于，对于这两个不一样的字符，要么删除左指针指向的字符以后继续验证，要么删除右指针指向的字符继续验证；如果删除左的，那么继续验证的时候实际上就是验证从left + 1位置一直到right位置的substring是不是一个Palindrome了，验证方法同样也是左右指针相向而行挨个验证是不是相同字符

9.5 做题

（昨天突然蹦出来那么多重复的，发帖太长还要审核，真难看，不过只要好好打卡刷题学习就好了，今天上了一天的课，一共八九个小时，所以只能做两个题目，原谅自己一下

523. Continuous Subarray Sum. 这个题目就是用prefix sum做，和之前一个subarray sum的区别就是，那个题目允许有负数所以不能用two pointers；而这个题目则是不允许有负数，但是要求的是subarray的sum是否是给定target的倍数；具体来说，这里有一个math的技巧，就是如果到位置i为止的prefix sum为a，而到位置j为止的prefix sum为b，并且a % k正好等于b % k的话，那么就说明在i到j的这一段subarray就是所需要寻找的sum为k的倍数的subarray；那么根据这个技巧，只需要遍历整个数组并逐次记录prefix sum，然后如果k不为0的话，就用当前的这个prefix sum去对k取余；这个余数（不管它是不是0），都去一个map中寻找一下并获取对应的value；这个map需要预先建立起来，它的key就是每个位置上的prefix sum，而它的value则是对应位置的index；那么去map中寻找对应的用当前位置的prefix sum对k取余的余数，如果存在的话，检查一下在map中找寻到的存在的这个余数所对应的prefix sum的index是否和当前位置的index组成的subarray长度至少为2，如果是的话，那就说明，当前存在一个位置i（也就是从map中寻找到的存在的index），和一个位置j（也就是当前遍历时进行到的index），这两个index组成的subarray的sum是k的倍数，因为他们对应位置上各自的prefix sum对k取余的结果相等（根据之前的那个math技巧得到）

973. K Closest Points to Origin. 这个题目有多种方法可以进行解决，一种是最简单的先排序然后直接取sorted过的前k个（当然这里的排序不是简单的比大小，有的时候是比频率比如topK，这里则是比和原点的距离，即两个坐标点的平方和），一种是用Heap排序来做也就是maintain一个size为k的heap然后一个一个往里面offer，如果size超了就poll出去，然后最后遍历完整个数据结构以后剩下的就是K，最后一种是类似quick sort的quick selection；这个题目用的是Heap的方法，当然肯定是最后一种方法更快更好一些

9.6 做题

（今天做的题目也不多，还没上正轨

689. Maximum Sum of 3 Non-Overlapping Subarrays. 这个题目用的是DP的思路，基本方法就是，先记录下来prefix sum的数组，使得容易计算subarray的sum；接下来确定好，这三个subarray各自可能的起始index的范围：中间的那个subarray如果起始位置是i的话，那么实际上就是[i, i + k]，因为它是中间的那个，所以要给左边的那个subarray留出至少k个位置，并且要给右边的那个subarray流出至少k个位置，所以i > k且i + k < n - k，因此k < i < n - 2 * k；那么左边的subarray的范围就是从0开始一直到i；右边的subarray的范围就是从i + k开始一直到n；然后对于左边的subarray，从0~k开始，挨个算出每个范围内的subarray的sum(利用prefix sum来计算)，对于右边的也一样；这样左右两边到每个位置为止的起始index就算出来了；最后算中间的subarray，index就是从k开始到n-2*k，然后分别从之前算出来的left和right数组中找到当前i所可以取到的左右subarray的起始位置，加上这中间的i，一起算三个subarray的sum然后检查更新最后得到结果

785. Is Graph Bipartite. 用BFS做，对于一个点记录到一个集合，把它的相邻点generate出来记录到另一个集合；然后对所有的点都这么做，如果一个被generate出来的点已经被记录了，并且它所被记录的集合和generate出来它的点的集合一样，就说明一条边的两个点在同一个集合里了，这样就false了

438. Find All Anagrams in a String. 这个题目就是用滑动窗口和HashMap记录窗口中的字符数量；如果窗口的字符数量正好能让target string的字符数量利用HashMap进行完全匹配，那么就说明找到了，记录结果

9.7 简历

今天花了一天的时间把简历重新做好了，工作经历和假期新添加的project都写了上去，可以开始投了