刷题打卡～西雅图刷题求组队

在职。干的也很开心。但是由于某些原因觉得是时间跳槽了。如果有西雅图的小伙伴愿意一起组队刷题偶尔探讨下题目也是欢迎欢迎哈～一起刷题累了还可以一起打个王者哈哈～带你飞～
如果有人想问问我现在的公司想要内推，我也很愿意内推你哈～

之前的账号被盗了，现在积分都没有了。求大家看到帖子给我点大米。给大米的小伙伴都有超级棒的offer

前一周终于看完了cc150基本的那些。现在正式开始刷题。顺道把这个帖子可以写成一个我的跳槽贴。

楼主你好，我在西雅图也在刷题。欢迎跟我组队！

捕鱼大神 发表于 2019/03/22 14:13:43
不太懂235 和236的区别。。。做法难道不是一样的么。。。
235        Lowest Common Ancestor of a Binary Search Tree
236        Lowest Commo...

235因为是BST完全可以根据数值大小关系确定位置，时间复杂度其实应该O(depth)，236只能硬找，复杂度O(n)

我懒了很多天了。。不能这样下去了。。今天继续来打卡。。

373        Find K Pairs with Smallest Sums
pq.

380        Insert Delete GetRandom O(1)
381        Insert Delete GetRandom O(1) - Duplicates allowed
差不多的两道题。最精妙的就是如何用o（1）从list中移除一个数。把最后那个数和要移除的数互换，然后移除最后一个数。

384        Shuffle an Array
不太知道这种random一个数，然后互换两个数。这种shuffle的做法是不是真的平均分配机会了。前面的数被重复shuffle了。

449        Serialize and Deserialize BST
没救了我居然在这道题debug了一个小时。对自己失望。感觉自己的做法和discussion里面都不一样。但既然beat了95%的submission。应该还可以吧。。还用了binary search

刷了一晚上心好累。leetcode居然999题了。然而我在美国这五年大概就刷了两百题左右（其中140题是当初三年前毕业找工作刷的。。50题大概是去年也想着跳槽刷的。。这中间可能还重复了无数题）。而且我觉得leetcode的test case做的比原来好了。

下面来写点今天的刷题总结。

224， 227 两题basic calculator
一看就是stack题。总的来说就是，记住pre number和pre sign，根据当前的状态来决定。 1+1 <=> (0+)1+1
要记得算数字，不都是个位数。

336 palindrome pairs
一看吓哭了。然后发现是挺简单的。用hashset来做。
1. ‘abc' needs 'cba'  2. 'aba' needs ''"  3. 'cacba' needs 'ab' 4. 'bacac' needs 'ab'
lc讨论区有trie的做法。我看不下去了。明天来看懂吧。

68 text justification
这道题明显题目写的不明确。比如现在有‘a', 'b' maxwidth = 5. 到底’a**b*'正确还是‘a***b’正确？？？ 假设不是最后一行。
有没有大神看到帮我解决一下。
["This", "is", "an", "example", "of", "text", "justification."]
16
expected: ["This    is    an","example of text","justification.  "]
output:    ["This    is    an","example of text ","justification.  "]

捕鱼大神 发表于 2019-3-6 14:43
刷了一晚上心好累。leetcode居然999题了。然而我在美国这五年大概就刷了两百题左右（其中140题是当初三年前 ...

刚刚写完总结。突然知道68我错在哪里了。终于通过了！写总结果然是有用的！

捕鱼大神 发表于 2019-3-6 14:43
刷了一晚上心好累。leetcode居然999题了。然而我在美国这五年大概就刷了两百题左右（其中140题是当初三年前 ...

准确来说1004道了宝宝

今日份的打卡。

10. regular expression
第一次觉得这题目可以理解了。。。以前总觉得太复杂都直接跳过。。。
关键在于要理清所有的分类。以及dp。
1. ---a    ---a 或 ---.  (看---和---就可以了。)
2. ---a   --b* (b*只能当作空)
3. ---a   --.* 或 --a* （.*或者a* 可以为空，可以为a, 可以为多个a）

773 sliding puzzle
这个题一看就是，啊我知道，肯定要bfs，要queue，要来一个visited的set。然后我就一脸懵逼了。这如何把每一步状态存起来呢。又如何比较呢。
看了讨论区某个人利用string的解法，惊为天人。好厉害这都能想到！然后又看了一个人的解答是自己写了个class定义这个object，感觉这个人更牛逼也更通用到遇到别的数据结构的类似题。定义object的时候记得要override equals和hashcode。
反正是一题有意思的题目。不难。

198， 213， 337 house robber 一系列
198 213 我都用dp了。213的想法真是赞。逆向思维了。你要找要rob的房子，那我看看哪些不要rob。既然是个圈，要么第一个房子不能rob，要么最后一个房子不能rob。来两次198计算就好了。
337我觉得要是能直接改class就好了。给各个node加个exclusive sum和inclusive  sum。

现在才十点半。。在考虑要不要看个系统设计的东西。。还是打个王者荣耀上个分。。然后去睡觉。。

王者刷题同求带飞

SpartanGiraffe 发表于 2019-3-7 15:04
王者刷题同求带飞

好哇好哇！要不要私信我微信。

今天就刷了两道题，但是刷的生无可恋。。。leetcode到底有没有debug模式，哪位大神告诉我一下怎么用。。。

787 Cheapest Flights Within K Stops
被这道题折磨死了。花了一个小时就用来debug。bfs/dfs
我用了bfs，因为看到了中转次数限制。
来一个map。city -》 flights。 city 就是id了，flight 是 src， dst， cost
来一个queue。放当前状态。根据当前状态来推出后面的状态。这里我们需要src city， dst city， total cost， stop count来知道从src到dst的价格和中转次数。这样根据dst的航班我们可以继续延续下一个状态。这道题既然src是固定，就不需要了。
判断状态是否是最终。dst和count。
记得要剪枝叶优化。如果坐这个flight会让cost超过已知的最低价，那就不要在走了。
----- 网上有个大神用了priorityqueue来寸这个状态，cost最小的在最上面。然后一旦找到第一个是到dst的状态的时候，就是最低价了。用这个做法，你还能来拿到top n的解法呢。我在想flight booking网站是这么算的么？要是有专门研究这种算法的大神可以回复跟我探讨一下？

756 Pyramid Transition Matrix
题目读了三遍我都没看懂在说什么。可能是我英语太差。于是我搜了下中文版的解释。这个解说和解法都炒鸡赞，分享给大家http://www.cnblogs.com/grandyang/p/8476646.html
hashmap映射，dfs, 递归实现。dp这个也是很赞了，但我自己还没写过。