坐标波士顿，决定开个刷题贴激励下自己

今天开始恢复刷题了，今天上午做了三道题
132. Palindrome Partitioning II（H）：这道题目思路还是比较简单的，就是把一个string分割成palindrome string，求最小分割，用dp解决，一开始做的方法用了n3的复杂度，能刚刚过，后来改进了一下，变成n2的复杂度，先得到各个substring是否是palindrome string，再用dp求最小分割
918. Maximum Sum Circular Subarray（M）：这道题目应该是53. Maximum Subarray的变种，53题之前做过，学会了一种o（n）的方法叫kadane算法，就是遍历一遍将元素累加，看结果是否小于0，小于0就重新开始累加，这个题目也是同样的思想，但是不同的是这里是首尾连接的，所以这里的累加要加一个负数的累加，然后大于0就重新累加，思路就是整个array的sum减去中间某个subarray的sum就是某个首尾连接的subarray的sum
621. Task Scheduler（M）：这道题想了很久很久，有时候思路真的需要改变，不能钻进死胡同，我一直想的是如何安排各个task，而不是想着怎么找到需要的插空，如果用后者来想的话就很简单了，只要知道最小的个数肯定要大于task的总和，然后先安排出现频率最高的task，如果中间能插满，那最后的结果就是task的总和，如果插不满，那最后个数就是安排频率最高的task的长度

今天稍微偷个懒哈哈，因为打算补下没做的高频题，所以从easy开始刷起，今天刷了四道easy题
771. Jewels and Stones：非常简单，可以用hashset做，但是速度会慢一点，快一点可以用数组存46个字母
461. Hamming Distance：很简单，位操作，先将两个数异或，再得到位为1的数目
617. Merge Two Binary Trees：很简单，dfs求解就ok
448. Find All Numbers Disappeared in an Array：由于要求是不能有额外space，而且要求时间复杂度是o（N），想了比较久，最后是绕了一下由于位置和数组的值是对应的，所以要先循环一遍将值对应的位置负一下，最后再循环一遍数组，看哪些位置非负，就是不存在的数值，但是第一次要用abs处理一下

今天也是轻松的一天，差不多要把高频easy题刷完了，马上要进入medium不分了
437. Path Sum III（E）：这道题不用hashmap的话确实是easy，就是简单的dfs，但是速度只有50%，用hashmap的话感觉难度应该是medium偏难了，不太好想，hashmap我是看的讨论区还想了一会儿才弄懂的，这里是用hashmap记录走过的path的长度所有可能的总值，这些path都是从root开始，然后用num记录从root开始到当前node的path的长度，这样用num - hashmap
中某个数，就是当前node的所有可能的preflix，只要看preflix中是否有可能有给的sum target就行，这样复杂度是o（n），每个node只用遍历一遍
538. Convert BST to Greater Tree（E）：这题比较简单，就是先遍历tree的右子树，得到一个需要加上的val，再把root的val加上得到的val，val更新，继续访问tree的左子树，感觉表述的不太好，但大概就是这个意思hh
543. Diameter of Binary Tree（E）：之前做过类似的题哈，我这里返回的是数组，一个数表示的不经过当前节点的最长path，一个是要经过当前节点的最长path，最后取最大值就行
572. Subtree of Another Tree（E）：我以为这题会有很巧妙的解法，但是用个简单的dfs试了一下，发现速度是95，就没关注了

miaoyuhang 发表于 2019-1-17 01:11
好久没有更新了，并不是去玩了hh，主要是寒假忙着做project准备春季的career fair，寒假做了两个full stack ...

楼主很强啊 请问是怎么找的项目呢

5222464 发表于 2019-1-20 06:17
楼主很强啊 请问是怎么找的项目呢

em，论坛网站的项目我是在udemy上面看到的，我跟着一起做的，然后我把它改进了下，你要是有兴趣我可以把udemy链接发给你，另一个二手物品的网站我是按照第一个网站设计的过程自己设计的，java的项目不太方便说hh，其实我感觉那两个网站项目功能还是有点简单，可能以后会慢慢改进

miaoyuhang 发表于 2019-1-20 06:20
em，论坛网站的项目我是在udemy上面看到的，我跟着一起做的，然后我把它改进了下，你要是有兴趣我可以把u ...

行啊 求链接

5222464 发表于 2019-1-20 06:21
行啊 求链接

发给你了

今天有些事情哈，所以更得晚一点，后天就开学了，开学估计就没法每天更新了
今天做了三道题，高频题果然都很好，思考了很多hh
438. Find All Anagrams in a String（E）：我一开始写了一个brute force的解法，过是能过哈哈，速度惨不忍睹，后来改进了下用了sliding window，其实我觉得叫动态伸缩比较贴切哈哈，最后速度在90
581. Shortest Unsorted Continuous Subarray（E）：虽然最后做出来比较简单，但是做的过程中还是花了很多时间思考，最后我用两个循环，一个用来找上边界，一个找下边界，不过也可以把两个循环合并一下，速度不会差太多，最后速度在90
406. Queue Reconstruction by Height（M）：这道题首先思路花了很久想，最后想法对了，就是先安排高个子，因为高个子不会影响矮个子的结果，但是先安排矮个子会对高个子产生影响，但是写起来挺麻烦的，最后没想到合适的方法，最后看了讨论区发现自己基础还是要加强，就用array sort和linkedlist就能实现插空，但是array sort要重新写下comparator

今天也是忙碌的一天，匆匆做了3道题然后更新一哈，虽然是三题，但也花了蛮久的时间
347. Top K Frequent Elements（M）：经典的top k问题，一般是用最小堆来做，一开始用的最小堆，发现速度只有50%，想了想好像有不用最小堆的解法，时间复杂度是o（N），肯定比最小堆的o（NLogN）快，具体实现就先遍历存下各数以及出现的频率，然后建立一个list数组，再遍历一遍，将各个频率都放到数组里面，最后再遍历数组得到结果
287. Find the Duplicate Number（M）：这道题我花了蛮久的，没想出来，最后发现思路还是很简单的，就是用二分查找，这里虽然数组不是排序的，但是还是能用二分查找的，因为是1 ～ N的数填到一个长度为N的数组里面。结果还有一种方法是用two pointers，我看了下和之前做过的linkedlist一题很像，但是没太看懂，但是今天没啥时间了就没继续研究了，标记了一下改天好好想一下
394. Decode String（M）：比较复杂的字符串处理，由于涉及到嵌套结构，所以用了stack，虽然做了比较久但还是解决了。

lz方便分享一下udemy做的第一个project吗 感觉有点意思