66. Plus One
Easy题。学会了python的reversed操作。for i in reversed(xrange(len(digits)))作者: bibaboo0 时间: 2017-1-27 05:01:01
317. Shortest Distance from All Buildings
这是一道hard题。用bfs的方法做，感觉复杂度挺高的。一开始超时了。后来答案的启发下，稍微剪枝了一下，就通过了，虽然只击败了36%的人。作者: bibaboo0 时间: 2017-1-27 06:56:06
305. Number of Islands II
Hard题。自己写了一个union-find类之后就很好做了。另外就是python的这个操作：for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]。。。真心太方便了。
提交之后直接ac，还是蛮爽的。作者: bibaboo0 时间: 2017-1-29 11:53:00
289. Game of Life 难度medium
python黑魔法之ngbs = sum( 1 for a in xrange(max(0,i-1),min(i+1+1,m)) for b in xrange(max(0,j-1),min(j+1+1,n)) if (a!=i or b!=j) and (board[a]==1 or board[a]==3))
int整数可以代表好几bit的信息。作者: bibaboo0 时间: 2017-2-1 04:10:20
231. Power of Two
Easy题，不解释。作者: bibaboo0 时间: 2017-2-8 11:05:07
422. Valid Word Square
Easy题，不过数据index溢出的情况考虑还是挺烦人的。作者: bibaboo0 时间: 2017-2-8 11:30:00
408. Valid Word Abbreviation
Easy题。在处理含数字的字符串的时候，一定要考虑数字可不可能不止一位、数字能不能以0开始等等多种情况。这一题就是没考虑这两种情况，错了两次。作者: bibaboo0 时间: 2017-2-8 11:41:05
374. Guess Number Higher or Lower
Easy题，二分搜索。作者: bibaboo0 时间: 2017-2-8 11:49:06
326. Power of Three
Easy题。普通的做法是用recursion或者loop。看discussion发现一种聪明的做法是用：3的19次方（整数范围最大的power of 3) mod 一下这个数。如果能整除就返回true。同样的思路可以用在其他所有数的power上面。作者: bibaboo0 时间: 2017-2-8 11:49:38
448. Find All Numbers Disappeared in an Array
Easy题。看答案看到一种很聪明的做法：
for e in nums:
nums[abs(e) - 1] = -abs(nums[abs(e) - 1])
return [i + 1 for i, e in enumerate(nums) if e > 0]作者: bibaboo0 时间: 2017-2-9 09:42:02
447. Number of Boomerangs
Easy题。6行python代码解决，有点小开心。至此google easy题全部结束。作者: bibaboo0 时间: 2017-2-9 13:07:02
第二轮运气比较好，遇到一个中国人大哥，大哥直接让我讲中文了。也不废话啰嗦，上来直接就出题。题目是给定一个list of interger，找出其中surpassers的总数。surpasser的定义是对于i,j if i < j and A[i]<A[j], then j is a surpasser of i. 也就是一个pair，后面的数index和值都比前一个大。这个题目brute force的方法很好想，就是一个二重循环，复杂度n方。大哥开始问如何优化，说最优解是nlogn。我想半天没想出来，要大哥提醒。大哥说有两种方法，一种是二叉树插入，还有一种是merge sort的变体。大哥提醒我了之后我还是没想明白，只能再次求教。后来总算明白了merge sort的方法，其实就是分治，分成left right，两边count，再count横跨两边的pair，最后把三个数加起来。知道了算法我就开始写，写的还挺快的，但是中间又出了问题：count横跨两边的pair的时候，我用了一个二层循环，这样一来就不是nlogn了，大哥让我算一下复杂度，我算出来是n方。那么怎么才能nlogn呢？我又卡壳了。在大哥提醒下，我在divide and conquer的时候，一边count 一边排序，这样上层拿到的就是一个有序list，就可以用O(n)的时间计算pair，这样复杂度就nlogn了。大哥开始问我空间复杂度的问题，我说是nlogn。最后大哥说最优的merge sort可以只用O(n)的空间。面试结束。感觉这题比上一题要更难一些，两次思路都没想到，感觉不太妙。作者: bibaboo0 时间: 2017-2-27 15:03:45
253. Meeting Rooms II 难度Medium
这题之前跟同学讨论过，没想出来方法。今天看了答案，理解了半天，豁然开朗。其实如果脱离了算法、编程这些，如果你就是一个房间管理员，这个其实很好解决，就是根据meeting的先后顺序，先来了就先分配房间，走了房间就空出来，没有空房间了就再开一个新的，就这么简单。如果非要说算法的话应该可以归类为贪心算法吧。作者: bibaboo0 时间: 2017-3-1 03:43:14
127. Word Ladder 难度medium
一开始超时。后来利用字符串的字母个数限制，将一个维度的复杂度降低到常数级才通过。
for i in xrange(len(w1)):
for cha in 'abcdefghijklmnopqrstuvwxyz':
。。。
这个循环大概有上百次，但毕竟还是常数级。再大的常数级都比O(N)要好。这是一个真理。作者: bibaboo0 时间: 2017-3-1 04:32:21