人肉翻墙-脱产刷题-记录帖

jiangqueque 发表于 2019-4-2 07:39
今天复习了DFS两道题。
1.word break
Gieve s = codecode,

做這類題目，還建議想清楚corner cases和time complexity。

我之前interview大廠的時候遇過word break, 由brute force做到dp，但跪了。feedback說我雖然做了optimal解，但time complexity & corner cases analysis答得不好。。。

摩拜大佬，祝早日上岸

有身份的话  问题不大诶 感觉

chan9118 发表于 2019-4-12 09:59
做這類題目，還建議想清楚corner cases和time complexity。

我之前interview大廠的時候遇過word break ...

是啊，我之前也是无脑写出来就算结束。
发现自己time complexity都分析不好。。
以后写每道题应该先想好用什么算法，时间复杂度，还有Corner case。。

多谢分享~~ ：）

04/10/19

1.Find kth smallest element in an array
2.sort colorsII
3.Interval Statistics
题目有点难理解。
Given an array of 01 and k. You need to count how many intervals meet the following conditions:
Both start and the end of the interval are 0 (allowing the length of the interval to be 1).
The number of 1 in the interval is not more than k.
Example
Given arr=[0,0,1,0,1,1,0], k=1, return 7.
也就是说，选择一些区间，左右都是0,要求他们之间的1的个数不能超过k个，问有几个这样的区间。
用two pointer来做，时间复杂度O（n）

4.一些easy题。

seawill77 发表于 2019-4-12 10:47
有身份的话  问题不大诶 感觉

谢谢鼓励！！借您吉言了：）

jackli31742 发表于 2019-4-12 10:21
摩拜大佬，祝早日上岸

不是什么大佬，每天踏踏实实“补课”哈哈。
谢谢鼓励~~

04/14/19

1.search in rotated array II
在一个包含重复数的倒装数组里寻找target
如，[2,2,3,3,4,1,1,1], target = 4
我想到的办法用Partition，
每次从中间将数组均分为两部分，每部分操作时间复杂度为O(1), 一共划分logn次，平均时间复杂度O(logn).
最差情况target在数组两边，时间复杂度为O(n)

有人的做法是，把mid数与start比，如果相等则start++直到不相等。不相等时则等于与seart in rotated array I 的题目。

04/15/19
1.find peak in an array
2.two sum
3.doing homework
4.longest substring without repeating charactors
hashmap+两根指针。
用fast指针往右边扫描，无重复则加入hashmap，如果有重复则将slow对应的字符在hashmap里删除，slow右移一位。
最长substring取fast-slow与最长的比较。

04/16/19

1.1779 Shortest Duplicate Subarray  
找最短包含重复数字的subarray长度。比如[1,1,2,3,2]，返回2，因为[1,1]为最短，[1,3,2,3]返回3，因为[3,2,3]最短。
用hashmap存无重复的数字及index, 遍历array是遇到重复的则计算当前subarray长度是不是比之前算的小。若是则更新hashmap对应的无重复数字及index。知道遍历完数组。
TC: O(n), SC : O(n)

2.1713 Unique Email Addresses  
给一组邮箱地址，判断无重复的地址有几个。'.'等价于没有，'+'后面到’@‘前等同于没有。
Jiang.queque@ll.com 和jiangqueque+12312@ll.com等同于 jiangqueque@ll.com。
Unorderd_set + string遍历。
TC: O(n), SC : O(n2)
可以优化的点，把邮箱后缀、前缀组合都保存到hashmap, 这样每次检查是否重复时可以省时间。空间换时间。

3. 88 Lowest Common Ancestor of a Binary Tree
求树中某两元素的共同最低的父节点。
先DFS求从顶到每个元素的path，再比较两个path最近一个相同节点。