现在感觉刷题就像高考和考研完全拼记忆力

是不是，像我现在干脆背题了，每题记核心。
1 Two Sum
2 Add Two Numbers
42 Trapping Rain Water left[i]=max(left[i-1],height[i-1]); right[i]=
max(right[i+1],height[i+1]);
146 LRU Cache
5 Longest Palindromic Substring 2 个expand, expand(i,i),expand(i,i+1),每次最长的替换res
4 Median of Two Sorted Arrays 切刀法，log(min(m,n))，cut1/cut2/cutL/
cutR四个变量控制切的范围， L1>R2 切点右移 ,L2>R1 切点左移 ，相等时返回，奇
数偶数判断，奇数直接返回R1
200 Number of Islands DFS 中要设置 grid[i][j]='0';
3 Longest Substring Without Repeating Characters 进入for ，右加1，
while右大于1左减一left增1，范围小则替换res
53 Maximum Subarray
15 3Sum 最外层i循环，nums[i]==nums[i-1] continue去重，内层left,right左右指针，right从len-2起如果nums[right]==nums[right+1],right--,continue
20 Valid Parentheses hashmap配对，遍历每个字符，是keySet入栈，是
valueSet栈顶元素和目前配对的话弹出栈顶
21 Merge Two Sorted Lists
23 Merge k Sorted Lists list每个对头入pq,while(出对头cur，加到res链表的结尾，cur下结点不空则入pq)
238 Product of Array Except Self left=1,遍历2次，第一次从倒数第二个逆
向，res[i]=res[i+1]*nums[i+1]; 第二次从开头正向，res[i]*=left,left*=nums[i]
56 Merge Intervals 按start排序，第0个元素定义lastStart,lastEnd, 从第一个元素起遍历，如果cur.start<=lastStart,lastEnd=max(lastEnd,cur.end)，否则结
果加入（lastStart,lastEnd）,lastStart/lastEnd赋值为cur的对应。 别忘记最后一
次要将res中加一次new（lastStart，lastEnd）
206 Reverse Linked List 递归和非递归2种解法，递归：(head==null,head.
next==null返回)，second=head.next,head.next=null,res=rec(second),second.next=head,return rest，最后返回的是最后一个节点。 非递归解法，2个指针cur和second=cur.next，1个dummy,把当前节点插在dummy的后面头插法，往后遍历cur=second。
76 Minimum Window Substring 进入for ，右减1，如果右非负count减一，
while左为负，左加1left加1，count为0且范围小则记录替换
1007 Minimum Domino Rotations For Equal Row "无论怎么换位置，如果最后
可以让某一行的数字完全一样，每个位置上只有两个可能，这个数要么是A的，要么是B的。 那么，对第0个数字来说，要么是A[0], 要么是B[0]。
那么，不管在那一行，后面的数字要么和A[0]相同， 要么和B[0]相同， 否则就不能达到效果。
所以，
–遍历数组一次， 如果可以在A或者B里面在每个位置上都找到和A[0]相同的元素，那
么就可以把某一行全部变成A[0]
–再遍历数组一次， 如果可以在A或者B里面在每个位置上都找到和B[0]相同的元素，
那么就可以把某一行全部变成B[0]"
289 Game of Life count返回值进行设置 -1：died->will live, 设置 2:
lived->will die. count数周围活着细胞：1或2都是，最后update，-1设为1,2设置0
22 Generate Parentheses 记录DFS参数和调用关系，四种情况：1 left>right 返回， 2 left right均为0 res加s并返回 3 left>0 DFS(s+"(",left-1) 4right>0 DFS(s+")", right-1)
297 Serialize and Deserialize Binary Tree serialize: list.add(""+ data), deserialize时出队列的点，判断为空则不处理，字符串数组不为#则说明为左子树，构造左子节点，再把左子节点入队，i增加1
273 Integer to English Words 用递归实现 recurse(int n) if(n递归 recurse(n/比当前n 低一档 ) +“n 低一档”+recurse(n%n低一档）
301 Remove Invalid Parentheses 扫描整个字符串，一旦发现右括号比左括号
数量多，删除一个右括号。如果左括号比右括号多则做reverse处理（优化）。遍历s,
用cnt比较左和右括号多少进行正负。
33 Search in Rotated Sorted Array
253 Meeting Rooms II 将interval先start后end排序，0元素end入pq, 从1元素开始遍历，lastEnd为pq头，cur.start>=lastEnd则pq弹头，cur.end入pq
121 Best Time to Buy and Sell Stock min记录当前最小值（取最小和当前
price），当前price减去min如果大于maxprofit则替换后者。
560 Subarray Sum Equals K hashmap保存数组某个位置之前的数组和，map 初
始化为<0 1="">，然后遍历数组求和，这样当我们求到一个位置的和的时候，向前找sum-k是否在数组中，sum在map中个数增加1
49 Group Anagrams
11 Container With Most Water
609 Find Duplicate File in System
394 Decode String
54 Spiral Matrix
91 Decode Ways
269 Alien Dictionary
68 Text Justification
41 First Missing Positive bucket_sort。while(A[i]!=i+1){ swap( A[i], A[ A[i]-1 ] ) } ，记住while判断条件 和swap下标， break的2个条件：A[i]越界，A[i]==A[A[i]-1]
88 Merge Sorted Array 得到总元素个数N，从尾部开始同时遍历两个数组，大
的赋值给原数组。
138 Copy List with Random Pointer
336 Palindrome Pairs
973 K Closest Points to Origin
31 Next Permutation
332 Reconstruct Itinerary
7 Reverse Integer while(input!=0){res=res*10+input%10,input/=10}
380 Insert Delete GetRandom O(1)
85 Maximal Rectangle
17 Letter Combinations of a Phone Number
10 Regular Expression Matching
46 Permutations

牛逼，你可以的宝贝

爱你

Merge k Sorted Lists用pq干啥？ 看起来很fancy,真能大幅提高效率么？ K个list， 平均每个长度是n， 每个node至少要touch一遍，所以至少是O(nk)，然后PQ里的插入操作是logK, 就变成了O(nklogk).
简单利用merge 2 sorted list:
1. 把k个list分成 (0, 1), (2, 3)。。。 k /2个pair, merge pair
2. 重复1直到变成一个list

不fancy，但实现简单， 而且时间复杂度一样:
1. merge完连个list之后，list的平均长度会翻倍。
2. 所以，总共merge的次数
k/2 * n * 2 + k / 4 * (2 * n) * 2 + k / 8 * (4 * n) * 2 + ... k * n * 2

k * n * (1 + 1 +...1) => O(nklogk)

【 在 daSHXiWanGon (硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】
: 是不是，像我现在干脆背题了，每题记核心。
: 1 Two Sum
: 2 Add Two Numbers
: 42 Trapping Rain Water left[i]=max(left[i-1],height[i-1]); right[i]=: max(right[i+1],height[i+1]);
: 146 LRU Cache
: 5 Longest Palindromic Substring 2 个expand, expand(i,i),expand(i,i+1),
: 每次最长的替换res
: 4 Median of Two Sorted Arrays 切刀法，log(min(m,n))，cut1/cut2/cutL/: cutR四个变量控制切的范围， L1>R2 切点右移 ,L2>R1 切点左移 ，相等时返回，奇
: ...................

所以就像我说的，背题的会被录取，你这种现场分析，给出一个次优解，你这次面试就F了。
再仔细想想。我的一个一个节点往pq里送，时间复杂度多少。你的是多少。
我那个就是网上最优解。

【 在 dullview (dullview) 的大作中提到: 】
: Merge k Sorted Lists用pq干啥？ 看起来很fancy,真能大幅提高效率么？ K个list
，
: 平均每个长度是n， 每个node至少要touch一遍，所以至少是O(nk)，然后PQ里的插入操
: 作是logK, 就变成了O(nklogk).
: 简单利用merge 2 sorted list:
: 1. 把k个list分成 (0, 1), (2, 3)。。。 k /2个pair, merge pair
: 2. 重复1直到变成一个list
: 不fancy，但实现简单， 而且时间复杂度一样:
: 1. merge完连个list之后，list的平均长度会翻倍。
: 2. 所以，总共merge的次数
: k/2 * n * 2 + k / 4 * (2 * n) * 2 + k / 8 * (4 * n) * 2 + ... k * n * 2
: ...................

用pq很麻烦，而且有些语言还没有pq或者minheap，还得自己先写一个。两个时间复杂
度完是一样的。pq并没有带来时间复杂度级别上提升，还是停留在O(n * k * logK)上
，还要多耗内存。唉，不过刷题进去的面试官估计很难理解这个。一看你这种题居然不会用pq，估计心理就默默挂你了。所以我说好多面试官其实根本不理解自己问的题目。

【 在 daSHXiWanGon (硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】
: 所以就像我说的，背题的会被录取，你这种现场分析，给出一个次优解，你这次面试就
: F了。
: 再仔细想想。我的一个一个节点往pq里送，时间复杂度多少。你的是多少。
: 我那个就是网上最优解。
: ，

刷题考的是啥？ds+coding。算法都不是重点

你用的ds越fancy，代码写得越整洁，最后就越难黑你。

【 在 dullview (dullview) 的大作中提到: 】
: 用pq很麻烦，而且有些语言还没有pq或者minheap，还得自己先写一个。两个时间复杂
: 度完是一样的。pq并没有带来时间复杂度级别上提升，还是停留在O(n * k * logK)上
: ，还要多耗内存。唉，不过刷题进去的面试官估计很难理解这个。一看你这种题居然不
: 会用pq，估计心理就默默挂你了。所以我说好多面试官其实根本不理解自己问的题目。

What will be the space complexity of your approach?

【 在 dullview (dullview) 的大作中提到: 】
: 用pq很麻烦，而且有些语言还没有pq或者minheap，还得自己先写一个。两个时间复杂
: 度完是一样的。pq并没有带来时间复杂度级别上提升，还是停留在O(n * k * logK)上
: ，还要多耗内存。唉，不过刷题进去的面试官估计很难理解这个。一看你这种题居然不
: 会用pq，估计心理就默默挂你了。所以我说好多面试官其实根本不理解自己问的题目。

如果你想写的容易些，O(K）。如果你处理的很巧妙，可以不需要再花额外空间。

【 在 andy2008 (monkey) 的大作中提到: 】
: What will be the space complexity of your approach?

赞收藏了

【 在 daSHXiWanGon (硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】
: 是不是，像我现在干脆背题了，每题记核心。
: 1 Two Sum
: 2 Add Two Numbers
: 42 Trapping Rain Water left[i]=max(left[i-1],height[i-1]); right[i]=: max(right[i+1],height[i+1]);
: 146 LRU Cache
: 5 Longest Palindromic Substring 2 个expand, expand(i,i),expand(i,i+1),
: 每次最长的替换res
: 4 Median of Two Sorted Arrays 切刀法，log(min(m,n))，cut1/cut2/cutL/: cutR四个变量控制切的范围， L1>R2 切点右移 ,L2>R1 切点左移 ，相等时返回，奇
: ...................

I think a divide-and-conquer k-way merge works as good as a min-heap k-way
merge in most conditions.

【 在 daSHXiWanGon (硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】
: 所以就像我说的，背题的会被录取，你这种现场分析，给出一个次优解，你这次面试就
: F了。
: 再仔细想想。我的一个一个节点往pq里送，时间复杂度多少。你的是多少。
: 我那个就是网上最优解。
: ，

谁让你选没有pq 的语言呢，选难用的语言又不加分。

【 在 dullview (dullview) 的大作中提到: 】
: 用pq很麻烦，而且有些语言还没有pq或者minheap，还得自己先写一个。两个时间复杂
: 度完是一样的。pq并没有带来时间复杂度级别上提升，还是停留在O(n * k * logK)上
: ，还要多耗内存。唉，不过刷题进去的面试官估计很难理解这个。一看你这种题居然不
: 会用pq，估计心理就默默挂你了。所以我说好多面试官其实根本不理解自己问的题目。

【 在 daSHXiWanGon (硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】
: 所以就像我说的，背题的会被录取，你这种现场分析，给出一个次优解，你这次面试就
: F了。
: 再仔细想想。我的一个一个节点往pq里送，时间复杂度多少。你的是多少。
: 我那个就是网上最优解。
: ，

pq runtime 5ms的样子
d&c 2ms

pq短好记倒是真的

请问你怎么确定 面试官会认为pq是更好的解法？

如果是我被面试 我会直接问他 2种实现哪种他满意 但是最贱的是 8成他回答都一样 让我随意 结果他心里确实有个高下而嘴上不说 这是最贱的 可是在我眼里是真的都一
样没什么区别

所以窃以为面试比起天朝的高考/考研美国的sat gre标准化考试 严谨性差了很多 随意性多了很多

如果 k lists的 head nodes是存在一个array里的，那么可以在这个array上进行pq/
minheap的那些操作，这样也不需要额外空间的。。。

【 在 dullview (dullview) 的大作中提到: 】
: 如果你想写的容易些，O(K）。如果你处理的很巧妙，可以不需要再花额外空间。

时间复杂度应该是一样吧，每次pq内部进行heapfy也要算时间的。虽然你外部调用只用一句话。好比python list.sort()就把一组数给排序好，你不能说你排序是O(1)

【 在 daSHXiWanGon(硅谷白肥2020年健身成KOF97大门五郎) 的大作中提到: 】

: 所以就像我说的，背题的会被录取，你这种现场分析，给出一个次优解，你这次面试就

: F了。

: 再仔细想想。我的一个一个节点往pq里送，时间复杂度多少。你的是多少。

: 我那个就是网上最优解。

: ，

没有pq？太简单了现场换个语言自带pq的不就行了？谁脑抽了用c去面试还只会这一种
语言。

【 在 dullview (dullview) 的大作中提到: 】
: 用pq很麻烦，而且有些语言还没有pq或者minheap，还得自己先写一个。两个时间复杂
: 度完是一样的。pq并没有带来时间复杂度级别上提升，还是停留在O(n * k * logK)上
: ，还要多耗内存。唉，不过刷题进去的面试官估计很难理解这个。一看你这种题居然不
: 会用pq，估计心理就默默挂你了。所以我说好多面试官其实根本不理解自己问的题目。