终于也来开贴打卡了...

零零散散两个月lc 刷了114
速度实在是太慢了

求监督 求拍醒

（米国现在是不是看人在加拿大就不理了.. 有的被秒拒 其他的还没有回信 很丧心

（顺便求也在找工作的小伙伴

68 Text Justification  #airbnb  
没看discussion 提交了几遍过的
主要是不太知道怎么分配空格
first find how many space slot, and the number of spaces need to fill the line to reach maxWidth
number of space / space slot 得出每个词后面放多少空格 然后用 mod 比mod小的多加一个空格

最后一行直接用 " ".join() 然后再加上remaining spaces
看了discussion， 最后一行可以用 .ljust() 不过自己也不太了解api 作罢

212 word search II
trie + dfs
最后一个node存word 方便放进res

1. class Trie(object):
   
2.     def __init__(self):
   
3.         self.children = {}
   
4.         self.word = ""

复制代码

可以把board[row][col] set成 # to mean visited

补充内容 (2018-10-4 03:08):
又把text justification做了一遍
又忘记handle divide by zero的case了！！！！

202 Happy Number #airbnb #easy
用dict去看有没有出现以前有过的数字
看了discussion，重复三个call 看第一个和第三个一样不一样 那样就O(1) space

160 Intersection of two linked list #airbnb #easy
O(1)space完全懵逼
看了solution
你追我赶的解法.. 看来easy还是要多刷一刷

219 Contains Duplicate II #airbnb #easy
题目看了好几遍 因为做了以前那道
since the number is equal just using a hashmap to store and update the indices and check if indices difference

108 convert sorted array into bst #airbnb #easy
就是binary search

190 reverse bit #airbnb #easy
bit manipulation 不太记得了..
先挖个坑 回来再看

补充内容 (2018-10-3 03:32):
只是 & last bit  然后shift往上加就挺简单的
discussion里面有几个bit一起shift的 基本上就是swap bits
左右16个bits 换一下
然后8个bits 换一下 以此类推
用到 n>>16 | n << 16
0xff00ff00 >> 8 | 0x00ff00ff <<8

补充内容 (2018-10-3 03:32):
只是 & last bit  然后shift往上加就挺简单的
discussion里面有几个bit一起shift的 基本上就是swap bits
左右16个bits 换一下
然后8个bits 换一下 以此类推
用到 n>>16 | n << 16
0xff00ff00 >> 8 | 0x00ff00ff <<8

76. Minimum Window Substring Hard
Sliding Window  
Move the right pointer until containing all the characters
then move the left pointer until its invalid

751. IP to CIDR #Easy
又是bit manipulation..

238        Product of Array Except Self    #Medium
看到要求就懵逼了，觉得有可能是dp但是没仔细往下想
小伙伴提醒了一下是dp， 最后纠结出来了
一开始用了两个dp array 然后优化成了一个

10. Regular Expression Matching Hard
dp+ backtracking
难点在于*
edge case:  s= "aaaa" p = "a*a"
dp[i, j] 如果s[i] p[j] match or p[j] == “." 先算一个first match, i has to be smaller than len(s)
然后看下一个是不是*
如果是* dp[i, j]  = dp[i, j+2] or (firstmatch and dp[i+1, j])  covers the case "abc" "c*abc" 和 "aaabc" "a*bc", "abc" "a*abc"
如果下一个不是* dp[i,j] = dp[i+1, j+1]
base case 如果 j == len(p) 如果把 p走完了，return i == len(s)

378. Kth Smallest Element in a Sorted Matrix #Medium
本来想拿bst做 但是把自己绕进去了= =
heapq 把first row 放进去
然后loop k 拿一个 放一个拿出来的数字的next row number

1. heaqp.heappush(list, ele)
   
2. heapq.heappop(list)
   

复制代码

ele 可以是 tuple, 第一个数字是用来compare的 第二个可以存点东西

397. Integer Replacement #Medium
没忘bit manipulation 想 好像discussion都是用math 和bit manipulation做的
直接用recursion 加memorization 做了..
回来再研究一下bit manipulation
真是弱项啊啊啊

airbnb的变形
        If a number is odd, the next transform is 3*n+1
        If a number is even, the next transform is n/2
        The number is finally transformed into 1.
        The step is how many transforms needed for a number turned into 1.
        Given an integer n, output the max steps of transform number in [1, n] into 1.


补充内容 (2018-10-3 04:56):
bit manipulation的做法
如果最后一个bit是0 就 >> 1
如果是3或者 n+1 的 1 比 n -1 的多
n -= 1
else
n += 1
数有多少1bit python api: Integer.bitCount(n+1)

pon123 发表于 2018-10-1 07:15
76. Minimum Window Substring Hard
Sliding Window  
Move the right pointer until containing all the ...

751
- transform string ip to number
- translate back
- num ^ -num to get right most 1-bit


补充内容 (2018-10-3 04:54):
int.bit_length()
Return the number of bits necessary to represent an integer in binary, excluding the sign and leading zeros

146 LRU cache #Hard
老题了 hash + double LinkedList
hash用来O(1) 找node return value
double linkedlist 是每个get/set 去把node 挪到最前面
put 的时候有可能是已经存在的key或者是新key
从map里面把key delete掉 是 del map[key]