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

miaoyuhang 发表于 2019-2-7 10:07
拖更了拖更了，选了门硬核数据结构，作业偏理论，所以赶作业去了，几天零零散散做了几题
703：Kth Largest ...

lz太强了……都是M或H阶段了，我还停留在从E到M阶段ORZ，以后要以lz为榜样…

要相信实习肯定能找到，多寻找机会吧！

莫涯泉水 发表于 2019-2-7 13:49
lz太强了……都是M或H阶段了，我还停留在从E到M阶段ORZ，以后要以lz为榜样…

要相信实习肯定能找到， ...

没有没有，我现在做hard还是特别头疼
谢谢鼓励，一起加油

今天稍划水，好吧，是特别划水，做了1M3E
430. Flatten a Multilevel Doubly Linked List（M）：思路比较清晰，可以选择用循环也可以用dfs，我用的是循环
520. Detect Capital：比较简单，我这里为了快速做完就没有考虑代码的简洁，直接用三个bool表示三种不同的情况
653. Two Sum IV - Input is a BST：比较简单，和two sum类似，只是这里的输入是一个bst，用dfs遍历树就行了
371. Sum of Two Integers：这题比较有意思，不用+或者-操作符来得到两个数的和，感觉应该可以算到m题，如果对位操作不熟的话，还是要想很久的，我没有很好的思路，最后是看的讨论区，是这样的，2进制位上的加减情况只有四种：11，10，01，00，后三种都可以用异或来得到结果，11要通过&来得到结果而且要往前进一位，那么原来的两个数a和b的和就变成a ^ b + (a & b) << 1，这样还是不能得到结果，因为会用到+，所以要按着这个思路继续吸取，这时候a和b就变成了a ^ b和(a & b) <<1，可以递归做下去，最后的情况就是第二项不可能无限进位下去，当第二项为0的时候就是一个数加0，直接返回第一个数就行，这样就可以通过不用+和-来计算两个数的和

昨天刚参加career fair，今天就收到一家公司的interview，这一段时间好好准备下，看能不能拿到一个实习

今日更新， 刚收到twitter的oa，找个时间做了，不知道能不能收到interview，然后career那家公司说要给我发个任务，让我一天内做完，最近事情越来越多了
今天做了3e，2m，1h，感觉还行，hard题思路还是不太ok，要继续努力刷题
707. Design Linked List（E）：比较简单，自己设计一个linkedlist，之前上61b把linkedlist和arraylist都写过一遍， 这里写成双向节点比较好，速度更快
557. Reverse Words in a String III（E）：比较简单的字符串处理，用stringbuilder的reverse就行，自己写个reverse函数也可以
299. Bulls and Cows（M）：这道题看着比较简单，不过还是有点麻烦，因为对应的位置的digit消掉后，就不能对应其他位置，其他位置的相同digit也只能使用一次，我这里是先循环secret数组一遍，把所有字母和对应的数量放进hashmap，再循环guess，找对应位置是不是一样，一样就将map里面的数量减一，最后再循环一遍guess，看其他位置的情况
594. Longest Harmonious Subsequence（M）：和299类似，找最大最小刚好为1的最长subsequence，这里我先循环一遍数组，把数字和对应的数量存入hashmap，然后再遍历一遍数组，看n(i)和n(i+1)的sum以及n(i)和n(i-1)的sum，找最大的sum返回就行了
807. Max Increase to Keep City Skyline（M）：比较简单的m题，理解了意思就行，就是二维数组上每个点有个建筑，数字代表建筑高度，现在要把各个点的建筑高度增高，然后保证从四个面看效果和之前是一样的，其实就是对每个点看它对应的行和列最大值，不超过两者中的最小值就不会影响看的效果，先遍历一遍数组得到各行各列的最大值，然后再遍历一遍数组，求增高的总和返回就行
282. Expression Add Operators（H）：感觉还是比较难的一题，没什么很好的意思，看的讨论区，做完又觉得还是挺简单的，还是要继续刷题。会给一串数字，可以任意使用"+","-","*"，求所有最后结果符合target的string，这里的方法是用的dfs，由于数字没限制位数，每次调用函数都要从当前起始位开始loop，数字的位数不同，除非第一位是0，然后dfs的过程中有些要注意的地方就是'*'这个符号有优先级，所以4 + 1 * 2应该是6而不是10，所以在dfs的过程中，要把前面的数字带上，这样如果是用的'*',sum要先减去前面的数字，再加上前面的数字乘以新的数字，其他就没有什么了

今日晚更，做了3E3M
350. Intersection of Two Arrays II（E）：比较简单，但是follow up值得仔细思考，没有sorted的情况下我是用的hashmap，因为速度会比先sort再解快，sorted情况下可以用two pointer来解，这样能节省空间，如果某一个数组的长度明显小于另一个数组，那么以小数组来建立hashmap是比较好的，如果两个数组都比较大而且对空间有限制，那么可能还是得先sort再解
339. Nested List Weight Sum（E）：比较简单，和之前做过的那道341. Flatten Nested List Iterator类似，但是341更难，这里只用求nestedlist深度和数的sum，用dfs是比较好的
973. K Closest Points to Origin（E）：topk的变种？需要重写priority queue的comparator，其他的比较简单，维持最大堆的数量在K就行
518. Coin Change 2（M）：dp还是难的，没有很好的思路，虽然之前也做过类似的题目，最后看的讨论区，思路是这样的，构建一个二维数组dp[i][j],i表示会用到前i种硬币，j表示钱的数量，那么就会有dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]，其实这是个knapsack问题，就是说可以选择用第i种硬币，也可以选择不用，如果不用，那么就是dp[i - 1][j]，表示只用前i - 1种硬币，如果用第i种硬币，那么就是dp[i][j - coins[i]]，表示从j - coins[i]这个数量再加上当前coin的数量而来
723. Candy Crush（M）：有点类似于之前写的那个wordbrain的游戏，但是明显简化很多，行列有3个或3个以上相同的数字就能消掉，一轮过后，数字下落填补消掉的空白，求最后无法再继续的结果，这里我一开始用hashset存的所有行列的情况，先遍历一遍数组找到所有可以消的坐标存到hashset中然后再遍历一轮将set中坐标设为0，最后再处理下落。后来发现不用hashset，把要消掉的坐标的值设为负数就行，判断用绝对值来判断，负数不会影响判断结果，最后把所有负数设为0
362. Design Hit Counter（M）：我用的treemap，如果当前treemap的最小值与gethit的timestamp超过300，就把最小值remove，hit总值减去最小值对应的hit数，然后继续，直到差值不超过300为止

今天做了五道题，1H2M2E
364. Nested List Weight Sum II（M）：比较简单，之前做过很多道类似的题目，像339. Nested List Weight Sum，341. Flatten Nested List Iterator，比较难的是341，用stack进行nestedlist的一维化，其他的都是比较简单的dfs，我这里是先求得最大的depth，然后再进行dfs求得结果
460. LFU Cache（H）：虽然是道hard题，但思路还是比较明确的，不过还是有点麻烦，之前做个类似的题，146. LRU Cache，432. All O`one Data Structure（H），我这里用到了两个hashmap，一个treemap，然后还是双向链表，我感觉这里可能空间复杂度还要优化一下。  有个问题就是，treemap严格来说应该是o(logn)的复杂度，但是我一直当成o(1)来做，似乎也没啥问题，我在网上看别人说hashmap和treemap的时间复杂度差不多
692. Top K Frequent Words（M）：比较简单，感觉topk的问题一般用最小堆或者最大堆都能做，这里需要重写下comparator，然后最后结果要求是频率相同的按字典序，只要在comparator中相等的情况下加一个string的compareTo比较就行了
860. Lemonade Change（E）和783. Minimum Distance Between BST Nodes（E）都比较简单，我就不讲啥了

昨天做了题忘了更新了，今天一起来更新
25. Reverse Nodes in k-Group（H）：思路很简单， 做起来比较麻烦，我用了很多个变量，这样只用遍历一遍就能把nodes都反转了，如果不想用太多变量可以稍微增加一点时间复杂度
905. Sort Array By Parity（E）：很简单，可以用two pointer来做
947. Most Stones Removed with Same Row or Column（M）：不太好做，一开始题意就没太理解清楚，后来才知道就是很多石头分布在二维平面上，可以选择从里面挑走一块石头，挑走的这块石头必须在他的同一行或者同一列上还有一块石头，求可以挑走的石头的最大个数，这道题如果是想挑石头的具体方法的话就会很难，但是从disjoint set的角度去想就很简单，假设所有能够相连的石头是一个集合，那么就会有n个不相关集合，不管怎么样，这些集合最后都会剩一个石头，那么总会有方法来挑石头使得每个集合都剩一个石头，那么最后的结果就是石头的个数-集合的数量，可以用dfs来做也可以用并查集来做
681. Next Closest Time（M）：由于只有四个位置，四个值，所以可以直接brute force，把所有可能的情况都遍历一遍，快一点可以把小时大于24，分钟大于60的情况去除掉
528. Random Pick with Weight（M）：和之前做过的一道题比较像，会给一个数组s，根据s[i]的值来随机得到一个index，index的概率和s[i]成正比，解法有两个，可以遍历s数组用treemap记录累加的值和对应的index，得到随机数然后看它在treemap里面的上一个值，也可以用一个数组来存住s对应累加值，用binary search找到随机数对应的index
609. Find Duplicate File in System（M）：比较简单的字符串处理，注意用"("分离要写成string.split("\\(")
844. Backspace String Compare（E）：我用的stack，比较简单
713. Subarray Product Less Than K（M）：类似于sliding window，保证中间的数的乘积不超过k

今日更新，1H + 2M + 1E
713. Subarray Product Less Than K（M）：和two sum类似，比two sum稍难，要求3 sum的所有可能，最简单的思路是brute force，o(n3)，应该是tle，没有试，进一步的想法是用hashmap存住所有sum - A[i]的情况，加上一个prefix的hashmap，存住一个数前面的所有数，这样只用遍历一边就能直接在另一边找有没有对应的数使得prefix + A[i] + sum - A[i] = sum，更进一步的话，由于A[i] <= 100，可以不用hashmap，直接用数组找所有情况，这样数很多的情况下也只要循环100次
709. To Lower Case（E）：很简单，不用tolowercase的话就把大写字母-'A'+'a'就可以
921. Minimum Add to Make Parentheses Valid（M）：做过很多parentheses的题目，基本思路就是保存'('的值，遇到')'比'('多的时候就结果+1，最后再加上剩余的')'的数量
759. Employee Free Time：感觉是比较简单的hard题，用一个最小堆按时间开始顺序存住所有的时间段，每次得到堆顶的结束时间，poll出来以后再和新的堆顶开始时间比较，开始时间比结束时间小的话就是大家都有空的时间，每次都更新结束时间就行

939. Minimum Area Rectangle（M）：感觉很好的一道题，给N个二维坐标，要求其中四个点围成的边与x轴、y轴都平行的矩形最小面积，我最后的方法是先遍历数组，用一个hashset存住坐标，为了让这里的坐标唯一化，需要将横坐标乘以40000再加上纵坐标，乘以40000是因为所有点的横纵坐标都小于40000。然后用一个嵌套循环遍历两个点的组合情况，当两个点横纵坐标都不相同的时候，找对应的矩形的另外两个点，如果存在的话，就和结果进行比较。
697. Degree of an Array（E）：先用一个循环得到所有相同数的最小和最大坐标以及degree，存到hashmap中，然后得到最大degree，第二次循环hashmap，得到满足最大degree的最大最小坐标差值的最小值
251. Flatten 2D Vector（M）：这题有点奇怪，说要用iterator做，但是我的输入是一个二维数组，然后我看别人的输入是二维列表，然后我就把输入改成了二维列表，具体实现就是用两个iterator，一个存的是列表，一个存的是Integer，每次Integer iterator迭代完后，将第一个iterator的下一个值给它，这里要注意空的情况
285. Inorder Successor in BST（M）：这里傻了，用的treeset来做的，做复杂了，其实用recursion很简单，如果是当前root比给定的p要小，那p就在root的右边，root和root左边的数就不用管了，如果root比给定的p要大，那就会在root的左边，但这时候root也是符合要求的值，所以要用recursion先得到左边子树的情况，如果左边子数没有符合要求的值，结果就是root，如果有符合要求的值，因为在root左边，肯定比root小，就返回recursion得到的结果就行了

补充内容 (2019-2-17 00:47):
昨天很晚写的，放在今天更了

刚刚做了骨骼的oa，一道是奇偶jump的问题，一道是求party最大人数
奇偶jump的思路就是先构建一个二维数组，得到当前index奇数偶数跳的时候应该跳到的下一个地方，然后再对原数组就行循环，对每一个数进行一次dfs，看能不能跳到最后一个数，能的话结果+1，不知道能不能通过隐藏test
party最大人数和leetcode那道meeting room比较像，我的做法是先用二维数组将参与和离开时间绑定，然后再根据参与时间sort数组，构建一个按离开时间排序的堆，循环数组，如果堆顶的数小于数组当前index的参与时间，就将堆顶的元素poll出来知道堆顶的值大于参与时间，最后返回堆能维持的最大size就可以了