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

今天要出去玩，所以就随便做了四道题hh
374.Guess Number Higher or Lower（E）：不能更简单的binary search，直接跳过
910. Smallest Range II（M）：这道题我想了好久，就是给一个数组然后对每个数组进行+K或者-K操作，求得到新数组最大最小值的差的最小值，我看了下给定数组范围是1 ～ 10000，所以想着复杂度应该要控制在o（n）或者o（logn），估计o（n2）都不行hh，但是我觉得还是应该要从最容易的bruce force开始，最后是对数组排序，得到差值，然后从最小的值开始进行操作，检查差值能否变小，复杂度是o（nlogn），主要是排序的原因，瞄了眼讨论区貌似还有o（n）的解法，就是不用排序，但是没来得及细看了
687. Longest Univalue Path：这道题我乍一看还挺简单的dfs，其实还是需要想的，因为有特殊的情况，就是树分叉了以后不能再被算进parent的路径里面了，所以一直有test报错，最后发现了之后才通过
450. Delete Node in a BST：在二分树里面删一个指定node，找到指定node挺简单的，删除我选的是把删除节点的右边的分叉放到删除节点的左分叉的最右边，这样能够保证二分树的性质不变，复杂度是o（h）

哈哈，圣诞节前一天来更新一发，今天就做了3题
878. Nth Magical Number（H）：这题感觉和别的hard题不太一样，最后写出来的代码并不复杂，思路也没什么困难，用binary search就能解决，但是里面有些细节还是要仔细考虑的，包括数的范围之类的，我用的长整形
948. Bag of Tokens（M）：这道题我一开始想的复杂了，以为贪心不行，想了很久以后发现贪心可以，而且如果不能用贪心的话貌似就只能brute force了，我用brute force试了一下，数组稍微长一点时间就爆炸，最后用的贪心解决的
314. Binary Tree Vertical Order Traversal（M）：这道题非常有意思，我觉得挺好的，要得到一颗树的vertical order，最后代码也挺复杂的，我用了2个list和1个treemap做的

圣诞节也来更新一发哈哈
955. Delete Columns to Make Sorted II（M）：这道题用贪心的话不难解，但是我花了很久想是不是能用贪心解决，感觉不太好证明贪心的解法就是最优解，虽然答案就是贪心。我这里用的hashset来存的位置，我看了下讨论区用的数组，确实应该用数组会更好。
592. Fraction Addition and Subtraction（M）：又是很麻烦的字符串处理，但是感觉这种题目做多了也感觉不错了，这次差点秒掉了，虽然最后还是有点问题，但是小改一下就过了哈哈
925. Long Pressed Name（E）：比较简单的字符串比较，跳过
845. Longest Mountain in Array（M）：这道题挺好的，是数组里面的two pointer类，我一开始是每个index都重算一次，速度很慢，后来用了优化解法，不用每次都更新，最后速度在80%

今日更新
128. Longest Consecutive Sequence（H）：是一道比较简单的hard题，在数组里面找最长的连续数，我用了两个hashset来做的，速度在60%
945. Minimum Increment to Make Array Unique（M）：把数组sorted以后就很好解决了，由于要排序，时间复杂度是o（nlogn），貌似还有o（m + n）的解法
775. Global and Local Inversions（M）：最后看来是最简单的题，但是我却花了最久的时间，陷入了分开找global 和 local inversions的误区，忽略了global inversions实际上包含了local inversions，下次做题不能一上来就敲代码了，得先思考一下
536. Construct Binary Tree from String（M）：字符串处理，没别的好说，就是细心就行，最后基本上是秒掉了，除了一个空字符串的情况没考虑到

今日打卡
244. Shortest Word Distance II（M）：题目是会一开始给一个数组存着很多可能重复的单词，要写一个函数来输入两个单词，得到两个单词的最短距离，然后这个函数会被调用很多次。我一开始是把复杂度都堆在了构造上，o（N2）的复杂度，可以让找距离的复杂度变成o（1）。发现跑不过测试，原因是数组长度太长，o（N2）跑不完，只能把复杂度分开到构造和调用的函数上了，把两个都变成o（n）的复杂度才通过。最后速度是80%
454. 4Sum II（M）：很简单， 从四个数组中分别取出一个数，得到四个数加起来为0的所有组合的数量，我是用hashmap先存两个数组所有加起来数的数量，然后再将另外两个数组加进来，最后为0就是所有组合的数量，速度是80%
311. Sparse Matrix Multiplication（M）：稀疏矩阵的乘法，由于线代太久没碰了，做起来有点生疏哈哈，想清楚以后比较简单，由于是稀疏矩阵，所以我一开始把矩阵处理了下，把不是0的数和位置存进Hashmap，最后只对hashmap进行操作就行了，速度不是很快，在50%
496. Next Greater Element I（E）：比较简单，我一开始还想有没有o（N）的解法，想了半天发现好像没有，就写了个简单的o（N2）去测试，结果速度是90%，就没管了哈哈

我也在Boston，刷题准备面试中，题目没你刷的多但工作比你久一点，有兴趣加微信一起讨论刷题吗？

感觉刷题真是很难坚持，楼主加油

Laojiang 发表于 2018-12-30 05:54
我也在Boston，刷题准备面试中，题目没你刷的多但工作比你久一点，有兴趣加微信一起讨论刷题吗？

可以呀，我发你私信了

codexpage 发表于 2018-12-30 06:25
感觉刷题真是很难坚持，楼主加油

是呀哈哈，我这几天忙着做project都没时间更新了

好久没有更新了，并不是去玩了hh，主要是寒假忙着做project准备春季的career fair，寒假做了两个full stack的项目
一个是用react + redux做前端，nodejs + express + mongodb做的后端，做了一个类似于论坛一样的网站，然后为了丰富这个project，用websocket给这个网站加上了online chat的功能，现在还在完善中，做完了准备用docker部署到ec2上
另一个也是一个网站，post二手物品，技术栈与第一个相同，react + redux的前端，nodejs + express + mongodb后端，这个网站我想了很多种方法处理图片，一开始是存储到本地，后来又改成了存进mongodb，最后是采用的上传到amazon s3上，然后图片使用url存储，感觉这样更好处理，API设计也比较清晰，同样还在完善中

现在手上ongoing的项目是用java spring做一个backend，这个项目比较复杂，估计career fair之前肯定做不完，只能慢慢来了