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

哈哈，前几天把网站项目结了个尾部署到服务器上去了，感觉项目还是太过于简单了，需要继续更新，打算全部拆成微服务的模式，然后最近也在搭自己的一个blog，事情越来越多
今天终于找时间刷了下题，赶紧更新一下
341. Flatten Nested List Iterator（M）：看着很简单，做着也很简单，但是最后有corner case很恶心，我一开始用list做的，发现在null的情况下很麻烦，始终调试不好，最后看了下讨论区发现都是用stack做，于是改成用stack做了一下，不知道为啥就没问题，感觉有点诡异，有时间再看一下
280. Wiggle Sort（M）：看着以为有难度，做起来觉得蛮简单的，遍历一遍就能解决，因为对于偶数，就看后面的数是否小于当前数，不是就调换，对于奇数，就看后面的数是否大于当前数，不是就调换，前面的数就不用再管了，但是这是建立在大于等于和小于等于的情况，如果不能等于就会稍微麻烦一点，应该会是这题的follow up
297. Serialize and Deserialize Binary Tree（H）：比较麻烦，我一开始是一层一层的存的，从tree变成string简单，但是转换回去有点麻烦，于是改成递归存储，这样在转换回去的时候也能够递归的建树
884. Uncommon Words from Two Sentences（E）：比较简单，用hashmap和hashset就行

今日中午打卡，做了四道题 1H + 2M + 1E
289. Game of Life（M）：比较简单，由于要求是in-place，对空间复杂度有要求，于是第一个循环设立四个情况，0->1, 0->0, 1->1, 1->0，将四种情况用四个数代替，这样既知道原有的值的大小，以及第二次循环需要设成多少，第二次循环再把值重新设置一下就行
388. Longest Absolute File Path（M）：用string的一个内置函数就比较简单，不然就比较麻烦，做的过程中发现'\n'和'\t'原来只算作一个字符，还是基础太差
315. Count of Smaller Numbers After Self（H）：很麻烦，一开始思路就是普通的brute force，o（n2）的复杂度，tle了，然后用treemap试了一下，刚刚能过，但是也是o（n2）的复杂度，需要10000ms，最后看的讨论区用的归并排序或者自建一个bst，但是我觉得应该用归并排序好，bst不能保证树的平衡性，最坏情况也是o（n2），如果要手写一个自平衡树就更麻烦了，归并排序至少比较稳定，但是写归并排序本来就比较麻烦，而且这里还要改造一下，也算是复习一下排序的知识吧，最后时间是8ms，算是见识到n2和nlog之间的差距了....
760. Find Anagram Mappings（E）：很简单的一道题，用hashset做的

今日更新，今天做了5道题，1H,3M,1E
739. Daily Temperatures（M）：比较简单，给一个数组，得到一个新数组，新书组存的是给定数组对应位置右边最近的比自己大的数之间的位置差，我用的是stack，从右边开始遍历，到一个位置时看stack的top是否比这个位置的数小，如果小的话stack就pop，因为在当前位置的数比top的数更大的情况下，top的数以后肯定不会用到了，最后速度在40%，我看了下讨论区用数组做的，于是又用数组做了一下，思路一样，只是这次要创建一个游标，速度在80%
695. Max Area of Island（M）：记忆化存储 + dfs，比较简单，只要记住所有访问过的点就行，速度在90%
547. Friend Circles（M）：和上一题蕾丝，记忆话存储 + dfs，只是形式稍微不太一样，速度在80%
412. Fizz Buzz（E）：很简单，算是做题中的放松吧
146. LRU Cache（H）：很麻烦，现在hard题虽然思路差不多，但总是差一点，我一开始是用hashmap + linkedlist，但是用自带的linkedlist不行，因为在更新操作后没法用o（1）的时间将操作过的key放到最前面，看了讨论区是新建一个doublelinkedlist，自己做了一下，就是新建一个双向node，然后创建一个list由双向node组成，再创建一个头节点和尾节点，hashmap存的是key和双向节点，put的时候，就把双向节点插入list，操作需要更新就把node的前后节点连起来，再把node放到头部，删除就直接删除尾部节点，这样能够保证所有操作都是o（1），最后速度在70%

今日晚更，2H，1M，2E
421. Maximum XOR of Two Numbers in an Array（M）：o（N）的解法没想出来，最后研究了下讨论区自己写了下solution，思路是这样的，假设所有数最高位不超过第五位，由于10000> 01111，那么可以从最高位开始求最大的数，用贪心算法来解，从最高位开始，求到最低位，这样实际上时间复杂度是o（32N），也是o（N）了。另外一种解法是创造一个前缀树，思路是一样的。
344. Reverse String（E）：很简单
23. Merge k Sorted Lists（H）：要按顺序把n个list合并，其实还是很麻烦的，不过居然很快做出来了，我用的最小堆，存的是数组，数组存的是当前所有node的val以及这个val属于list数组的哪一个元素，最后复杂度应该是o（MlogN）
387. First Unique Character in a String（E）：很简单
10. Regular Expression Matching（H）：很麻烦，不太好做，字符串正则处理，我理解那个*理解了很久，试了几个case之后才知道*是和前面的字符绑定的，假设前面的字符是a，那么a*可以表示为空、a、aa、...、aaa...aaa，做的时候是用递归做的，当某一个字符的后面是*时，就把当前*所有可能影响的情况都试一遍，有一个正确就返回true，但是有一种情况a**，后面那个*匹配的应该是a还是*，我不太确定，这里我直接把*去比较了，最后通过了

今日晚晚更新，事情比较多所以晚上回来做了四道， 2H + 2E
273. Integer to English Words（H）：个人觉得虽然有点麻烦但还是一道比较简单的hard题，思路比较明确，只要注意过程中的一些细节就行
301. Remove Invalid Parentheses（H）：比较难的一道hard题，想了比较久，最后看了讨论区的思路，是这样的，先正向处理字符串，看有没有单的")"，有的话就必须从前面选一个")"去剔除，而且连续的")"只能选一个去剔除，避免重复操作，这样可以不用hashset来存，节省时间，然后选择一种剔除情况后，从后面的字符串开始，在正向处理完后，再把字符串反向处理一遍，这次剔除多的"("，思路是一样的，可以重复利用函数
482. License Key Formatting（E）：比较简单的字符串处理，没什么要注意的
811. Subdomain Visit Count（E）：稍微复杂一点的字符串处理，只要注意想要通过"."来分离string的话要用string.split("\\.")就行

我也在Boston，已经工作好几年，lc刷了两遍了正在第三遍（每遍大约4～500道），前几周去面试Boston某公司直接一道lc hard题的变种和一道lc上没有的题（大概算中等难度吧），给电脑得在电脑上跑出来结果，最关键是不能直接写出最优解，先得写出来暴力解法然后一步步优化成最优解才行，每种解法都要得出正确结果，最后优化出一道题，第二道题没优化完，只优化到次优解，就挂了，HR反馈说想找更stronger的候选人，搞得我信心大失。。。但还得继续努力才行，不如我们成立个刷题小组，三五个人最多，每天在群里更新刷题任务，然后一起讨论？当然，有时候项目太忙或者出去玩什么的就临时请个假（但正常情况下每天都刷），怎么样

infrared628 发表于 2019-2-2 01:54
我也在Boston，已经工作好几年，lc刷了两遍了正在第三遍（每遍大约4～500道），前几周去面试Boston某公司直 ...

加一个,算我一个

infrared628 发表于 2019-2-2 01:54
我也在Boston，已经工作好几年，lc刷了两遍了正在第三遍（每遍大约4～500道），前几周去面试Boston某公司直 ...

好呀，不过我现在每天上课，可能不太能保证每天都有时间

今日更新， 2H + 2E
269. Alien Dictionary（H）：很难，建立两个hashmap，一个存数和所有应该比这个数小的数，另一个存数和应该要比这个数大的数的数量，遍历一遍所有的string，根据字典规则更新两个hashmap，再从第二个hashmap中value为0的数开始，value为0代表这个数不依赖任何比它大的数，所以可以直接放入结果，当把一个数放入结果，根据第一个hashmap把所有应该比他小的数的依赖减一，重复步骤就能得到最后的结果，听起来就很绕。。
76. Minimum Window Substring（H）：我觉得不是很难，只是细节需要注意一下，思路就是sliding window，我这里是设了两个指针，当左右指针中间的所有字母（包括右指针）已经满足要求时，左指针往右移，直到中间的字母不满足要求为止，最后返回这个过程中左右指针最小的差值
349. Intersection of Two Arrays（E）：比较简单，我用的hashset
716. Max Stack（E）：比较简单，可以用stack + treemap，也可以用stack + pq，我两个都试了下，treemap快一点但空间会使用的比较多

周六出去了，实在找不到时间写，昨天晚上很晚做了四道题，今天来发一下，2H，2E
32. Longest Valid Parentheses（H）：和 301. Remove Invalid Parentheses（H）蕾丝，要找parentheses， 但是这题会稍微简单一点，我这里用的是stack，思路是每次遇到'('就push进stack里面，遇到')'就把栈顶元素pop出来，这样，最近的()就完成了配对，每一次都更新配对都更新一下最大长度，长度应该是当前的i减去pop后的新的栈顶元素，不过要注意stack
里面要始终放一个打底元素，刚开始的时候是-1,如果遇到')'比'('多的时候，代表前面的一段肯定不是valid的了，就把打底元素即使更新
432. All O`one Data Structure（H）：和LRU Cache的思路比较像，我用了Hashmap，treemap和doublelinkedlist，这题我最后时间是90%，空间是100%，感觉自己方法还不错，就写在了讨论区，https://leetcode.com/problems/al ... -easy-to-understand
415. Add Strings（E）：难度不大，注意细节就行，像最高位的进位什么的
706. Design HashMap（E）：自己大概设计一个hashmap，用数组加链表的形式，这里我做的过程中感觉还是挺好的，对hashmap稍微熟悉了一点，里面会用到hashcode()，有个小技巧，速度想要更快的话可以增加数组的容量，这样链表不会太长，我这里用了个100000的数组速度到了80%