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

XiaoyouZ 发表于 2019-2-20 14:48
加油加油

谢谢谢谢

好久没有更新了，暑假基本确定会去亚麻了，找个时间应该会重新开始更新吧，记录下刷题还有学习的状态，谢谢鼓励的朋友，一起加油

the same here...哭哭

继续更新，暑期实习要用python，所以打算以后简单做过的题用python写，难的没见过的先用python，另外大家知道有什么学习nlp的入门资料么，非常感谢
今天刷的题：
743. Network Delay Time(M):不是特别难，dijkstra's alg，我先用的queue，速度比较慢，可以用优先队列来优化
843. Guess the Word(H):比较难，没想出来，其实答案思路比较简单，首先要确定策略，策略就是首先要选符合要求的，比如猜了一个字符串，得到结果，可以用这个结果在字典中找所有候选字符串，然后在其中找字符重叠率高的，这样下一次可以确保淘汰更多的候选者，这样最后能最快的找到答案。
920. Number of Music Playlists(H)：很难得dp，大概思路是这样的：
dp[n][l][k]表示前l首歌放了n首不同的歌，k是重复歌曲之间的长度限制
dp[n - 1][l][k] 和 dp[n][l][k - 1] 不需要考虑，不符合条件
dp[n - 1][l - 1][k] 只需要把新的歌插到最后，这首歌可以是n首歌中任意一首
dp[n][l - 1][k] 这种情况稍微比较难想，最后一首歌不能是它前面的k首中的一首，由于前面k首歌肯定都是不同的歌，所以还剩n - k首
最后 dp[n][l][k] = dp[n - 1][l - 1][k] * n + dp[n][l - 1][k] * (n - k) 由于k不会影响结果，可以用一个二维数组来做dp
316. Remove Duplicate Letters(H)：相对来说比较简单，我用的是一个双向队列，思路类似于sliding window，遇到字典序小的情况把队列中小的元素都剔除出来，除非这个元素表示的字符已经超出了该字符最后一个位置的范围，队列中剩下的元素就是最后的结果
212. Word Search II(H)：和上学期最后做的那个proj类似，建立字典树来剪枝

更新一下，500题打个卡，很多题没有记录下来，说下最近做的几道题的思路
1032. Stream of Characters（H）：打比赛做的题目，用给定的字典构造一个trie，然后每次根据trie来找是否有相关的单词
277. Find the Celebrity（M）：感觉讨论区的思路特别好，由于celebrity的限制，可以先用一个循环找到一个可能的候选者，再用一个循环来验证这个候选者是否真的满足要求
115. Distinct Subsequences（H）：dp题，用dp[i][j]表示s的substring(0,i)和t的substring(0,j)的distinct subsequence个数，然后每次比较当前s.charAt(i)和t.charAt(j)，如果相等，那么代表dp[i-1][j-1]的情况都可以加上来，还要加上dp[i][j-1]，因为可以选择加上s.charAt(i)或者不加上，如果不想等那就只有dp[i][j-1]的情况
934. Shortest Bridge（M）：bfs，比较简单
863. All Nodes Distance K in Binary Tree（H）：这道题非常好，先用tree来构建一个无向图，再用bfs来找到距离为k的所有点
992. Subarrays with K Different Integers（H）：subarray用sliding window来做，但是这里要求所有可能的情况，所以有点麻烦，这里看了Lee大佬的思路，就是先求subarrays最多有K个different Integer的个数和subarrays最多有K-1个different Integer的个数，答案就是两者相剪，就是subarrays正好是K个different Integer的个数
224. Basic Calculator（H）：字符串处理，用stack来保存括号前的内容

更新一下今天写的几道题，
997. Find the Town Judge（M）：比较简单，和celebrity那道几乎一样，先找到一个candidate，然后再看candidate是否符合要求
990. Satisfiability of Equality Equations（M）：可以用union find，我这里是先把==连接的变量放到同一个集合中，再检查!=两端的变量是否在同一个集合
841. Keys and Rooms（M）：难度应该是easy，用dfs可以解
802. Find Eventual Safe States（M）：dfs，但是要处理一下有环的情况
1014. Best Sightseeing Pair（M）：思路和买卖股票那道题一样，用两个变量记录A[i]+i和A[j]-j，后者的更新通过前者来决定
1004. Max Consecutive Ones III（M）：可以用sliding window来做

今日打卡：
999. Available Captures for Rook（E）：简单递归
989. Add to Array-Form of Integer（E）：简单列表处理
998. Maximum Binary Tree II（M）：题目看懂了就比较简单，注意添加的index是放在列表的最后面，用递归就行
988. Smallest String Starting From Leaf（M）：这里有个陷阱，不能用bottom-top来做，会有个case过不了，在字符串比较时会出现一个逻辑错误，要用top-down来做
979. Distribute Coins in Binary Tree（M）：也是用递归，比较简单
987. Vertical Order Traversal of a Binary Tree（M）：这里我用的dfs，用map来存储相同vertical level的node

1003. Check If Word Is Valid After Substitutions：用stack来做，比较简单，遇到c就消掉stack里面的ab，最后看是否stack为空
986. Interval List Intersections：用two pointer来做，每次对两个pointer进行比较，把intersection加到结果里面
971. Flip Binary Tree To Match Preorder Traversal：写起来还是有点麻烦的，先看一般的顺序满不满足条件，不满足再试下flip的情况
contest
1037. Valid Boomerang：我是把情况都列了出来，其实只用这个等式就行((p[0][0] - p[1][0]) * (p[0][1] - p[2][1]) != (p[0][0] - p[2][0]) * (p[0][1] - p[1][1])
1038. Binary Search Tree to Greater Sum Tree：中序遍历，不过是从右边开始，遍历一个节点就把前面的和加到当前节点上
1039. Minimum Score Triangulation of Polygon：dp，具体思路就是选取图中两个点，从两个点距离为2开始，第三个点移动，找到最小的情况
1040. Moving Stones Until Consecutive II：看的Lee神的思路，大概就是分maximum和minimum来想，minimum就是找到距离为n的滑动窗口中，点最多的情况，最小的步数就是把其他不在窗口中的点移到窗口中，但是这里有个坑，由于“ move it to an unoccupied position so that it is no longer an endpoint stone.”的限制，当有一个endpoint在单独的位置，其他点连续时，应该结果是2不是1，因为这个endpoint不能直接移到另一个endpoint，应该先把连续的endpoint先移到中间
307. Range Sum Query - Mutable：学线段树做的题目，就是通过给定数组构造一个线段树然后调用update和findrange方法

1003. Check If Word Is Valid After Substitutions：用stack来做，比较简单，遇到c就消掉stack里面的ab，最后看是否stack为空
986. Interval List Intersections：用two pointer来做，每次对两个pointer进行比较，把intersection加到结果里面
971. Flip Binary Tree To Match Preorder Traversal：写起来还是有点麻烦的，先看一般的顺序满不满足条件，不满足再试下flip的情况
contest
1037. Valid Boomerang：我是把情况都列了出来，其实只用这个等式就行((p[0][0] - p[1][0]) * (p[0][1] - p[2][1]) != (p[0][0] - p[2][0]) * (p[0][1] - p[1][1])
1038. Binary Search Tree to Greater Sum Tree：中序遍历，不过是从右边开始，遍历一个节点就把前面的和加到当前节点上
1039. Minimum Score Triangulation of Polygon：dp，具体思路就是选取图中两个点，从两个点距离为2开始，第三个点移动，找到最小的情况
1040. Moving Stones Until Consecutive II：看的Lee神的思路，大概就是分maximum和minimum来想，minimum就是找到距离为n的滑动窗口中，点最多的情况，最小的步数就是把其他不在窗口中的点移到窗口中，但是这里有个坑，由于“ move it to an unoccupied position so that it is no longer an endpoint stone.”的限制，当有一个endpoint在单独的位置，其他点连续时，应该结果是2不是1，因为这个endpoint不能直接移到另一个endpoint，应该先把连续的endpoint先移到中间
307. Range Sum Query - Mutable：学线段树做的题目，就是通过给定数组构造一个线段树然后调用update和findrange方法

啊 楼主 你还在刷题吗 请问你有什么刷题小组吗