加州 妹子一枚 监督自己每天⛽️刷题！！欢迎大家评论分享心得！！

ootsuka 发表于 2018-9-22 08:03
请问您觉得leetcode做多少题目才算是差不多可以去面试？

有的人刷了100个题就去面试了, 有的人刷了1000个题还在刷.
我觉得评判标准很简单, 你随机在leetcode上抽一个题或者地里看别人面经上的题, 你3分钟内都可以出思路你就算准备好了, implementation（写code） 都是熟能生巧.

9/24 Mon
Combination base DFS
求所有满足条件的组合
时间复杂度： O(答案总数 * 构造每个答案的时间) subsets(2^n * n) Permutation(n! * n)每个集合的平均长度O（n）
• 39. Combination Sum 时间(2^n)
在主方程中进行sort排序，在call dfs helper function. 在dfs helper function中首先要考虑递归的出口，那就是target<0 则表明不符合标准，要结束。第二个return case是当target==0时表明上一个完成的currList就是满足的答案，需要加到result中。值得注意的是加进去的时候需要wrap up type：
res.add(new ArrayList<>(currList))。 Backtracking （dfs）函数的重点是最后的for loop，表明同一深度可以面临着不同的选择，在for loop中再次call dfs 递归函数
• Difference btw 39 && 78 Subsets
        • Combination sum 中多了target来限制组合数的sum
        • Combination sum 中一个组合可以用重复的数字，subset一个数只能用一次
        • Combination sum 需要先对nums 进行sort
• 40 Combination Sum2  （Each number in candidates may only be used once in the combination.）
        • if(i > idx && candidates[i] == candidates[i - 1]) continue; 用来去重
• 131 Palindrome Partitioning
Input: "aab" Output:
[
  ["aa","b"],
  ["a","a","b"]
]
此题解法的特别之处： 没有idx来indicate处理到哪个地方，本题的backtracking是通过不断update传进来的string来标记处理到哪个地方的。dfs(s.substring(i+1), res, currList); 另外需要一个checkPalindrome 的helper函数

Permutation & graph related DFS
• 满足条件的permutation：时间与n!
• 46. Permutations (backtracking)
        • 与之前的backtracking不同的是：在dfs的helper function中不需要index，唯一的constrains是当currList的size==nums.length的时候，此时return即可。要注意的是，permutation不可以用相同的element所以在currList添加之前要check currList中是否已经存在currList了。最后记得remove the last one.
• 47. Permutations II (input array has duplicate)
        • 做法差别：一开始要记得sort array，多了一个boolean array来存各个element的使用情况。传到dfs helper function中的for loop环节：首先查如果当前元素被使用过则跳过；如果该元素不是第一个元素并且和上一个元素相等，上一个也没有使用的情况下，也跳过，其余情况则添加到当前list中，重要：在每次添加和移除的过程中，boolean【】 used函数也要相应变化
• 681. Next Closest Time
        Input 是表示时间的string，求下一个可能的时间是多少？只能用input中出现的数字来排列组合，一个char可以用多次。
        • 如何生成左右可能的时间解？将input string中的char分别存下来，用四个for loop来iterate所有的解
        • 如何保证存下来的时间是没有duplicate的？需要一个set的data structure来存所有的解
        • 如何来sort解？需要list这个data structure，那么list.addAll(set)来存set的值
        • 特别：list是用 Collections.sort(list)来写的
        • 不能随便就return要检查得到的idx是否是最后一个，如果是，那么return第一个解
题目不难，大思路就是要生成所有的解，进行从小到大的排序，得到input time所在的顺序，return排在它下一个的解就行了

9/25 Searching and Sorting
• Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.
        • 一个list n个元素，那么建立一个它的Pq: time complexity = O(nlogn)
• Count word by freq using hashMap: O(n)
• 针对n个元素，找出top k frequency 的元素并输出的问题，有三种方法：
        • Sort by frequency + pick top k element: 时间 O(nlogn) + space O(n)
        • priorityQueue/min Head (692) time O(nlogk) + space O(k)
        • Bucket sorting: time O(n)
                ○ Space: O(n) array -> O(k) hashtable



• 692. Top K Frequent Words O(nlogK)
这道题用到了固定size的priorityqueue/heap的知识和reversely add 的小技巧
PriorityQueue/Head O(nlogk) time O(nlogk), space O(n)
        • Step1: build hashMap to count the freq for each key O(n)
        • Step2: add each entry to min heap with maximum size = k O(nlogk)
                ○ priorityQueue的comparator的写法：entry.value from small to larger, 因为若要取出，则先删除掉小的entry；entry.key 字母顺序从大到小。
        • Step3: exact min from head reversely O(nlogk)
                ○ 这里用到的是list 作为返回的result，并且每次list.add(0, num)这样可以保证每次从前面加起来，那么最后所加的big value是排在前面的

加油加油 同5月毕业 刷题量比楼主还少…… 看楼主这么努力真的非常优秀了

祝楼主好运!大概300题就可以去面试了

Reflection2333 发表于 2018-9-26 14:28
加油加油 同5月毕业 刷题量比楼主还少…… 看楼主这么努力真的非常优秀了

谢谢你～

eins1179 发表于 2018-9-26 22:53
祝楼主好运!大概300题就可以去面试了

好的，谢谢你

9/26 Wed Searching and Sorting
347. Top K Frequent Elements
做法： bucket Sorting
• Step1: use hashMap to count the frequency for each element
• Step2: create a list array as buckets.  For Map's each key, get its frequency, insert into the buckets[frequency]
• Step 3: from buckets back to front, get k elements as most freqent element （找到一个buckets[i] 要先检查它是不是null，不是null才能寄到result list里面）
• 注意⚠️：list[] buckets = new list[n+1] //注意list要建立n + 1的长度，表示frequency最大是n，所有的数都一样

215. Kth Largest Element in an Array 找到数组中第k大的element
不难，但有多种方法
• Method1: sort the entire array and retrieve the n-k th element
        • Time complexity O(nlogk) + space O(1) Java uses Quicksort algorithm which has O(n log n) average complexity and is performed in-place, no extra space is needed.
• Method2: use priorityQueue with fixed size k to store elements, then peek the first element is the k the largest element in the array
        • Time complexity: O(nlogk) + space O(k) n个element，每次插入需要logK时间

Search for a Range
给一组递增的数组，找等于target数的一组index区间
分析：找到区间，就是用来找到等于target的第一个index和等于target的最后一个index。先用bianry search 来找到Starting index，end index 其实就是target的下一个元素的index - 1
做法： 写一个binary search 的helper函数，用来找到等于target的index。在主函数中先得到left bound再得到helper(nums, target + 1) - 1作为right bound


253. Meeting Rooms II 和merge Interval 很相似
做法： 将start time 和 end time 进行分离分别存在int array 中进行排序。设一个endIdx从0开始的variable。进行for loop，如果start[i] < end[endIdx] 那么count++，否则就endIdx ++
240. Search a 2D Matrix II
We can rule out one row or one column each time, the time complexity is O(m+n).
Binary search , row = 0开始col = matrix[0].length - 1开始, 在while loop中查看matrix[row][col] 与target的大小关系


280. Wiggle Sort  vs 324. Wiggle Sort II
280不难 in-place sort 即可。 324需要点小技巧
153 Find Minimum in Rotated Sorted Array （操作index）
Use index as search space. 不同的是这里是rotated sorted array, 那么用一个target = nums[n]来存一下，因为是rotated,所以小于target 才算做是small number。用binary search，如果中间的值小于target，end = mid, 说明在最小值还应该在mid的左边，让end = mid
142. Linked List Cycle II && 287 Find the Duplicate Number
大致思路都是一样的，用快慢两个指针先来找到第一次会和的地方，再需要一个从头开始的指针，再同步走到相遇的地方，便是结果。当时！！两个的写法有差，因为一个是在数组上进行，一个是在linkedList上

【总结】
Binary Search--> figure out the "Search Space"
Two kinds of "Search Space"
        • Index: generally used for sorted array
        • Range: used for unsorted array
Binary Search: O（logn）题目说比O（n）更优的方法几乎只能是O(logn)
        • 第一类：套模版
        • 第二类：OOXX 即找到符合条件的第一个or最后一个
        • 第三类：Half Half 即每次保留一半

9/27 Thurs Dynamic Programming
121 Best Time to Buy and Sell Stock & 122. Best Time to Buy and Sell Stock II
• 121 只能有一次transaction：return的是在array中找出最大的卖出价格 - array中最小的买入价格
• 122 可以有多次transactions： return的maxProfit = Sum ( 所有正的profitable price difference)
        那么需要 prices[i] - price[ I - 1]即可
• 198. House Robber
要讨论length == 0 和length == 1的return情况，因为dp是从I = 2 开始讨论的
• 322. Coin Change
给定的几个硬币，求能组合出amount的最少数量。求最少可能的一般用DP
Time complexity O(n * amount) Space O(amount)
设一个长度为amount + 1的dp数组，dp[0] = 0. 在dp中一般需要长度为amt + 1 因为index需要从0 ～amount，长度得+1. 每一位arrays.fill（Integer.max_value) 所以dp数组需要用array of long
分析：做dp题目时首先要知道四要素：
                ○ 状态： 即dp数组中的每一位代表的什么意思
                ○ 初始状态：又是要讨论dp【0】，dp【1】
                ○ 转移方程
                ○ Return value
• 300. Longest Increasing Subsequence 好题目
        同样的做法，设一个int array并且先将每一位都fill成1，进入for loop，用两个指针一前一后地来查看

152. Maximum Product Subarray
做法稍微简单一点的dp，不需要int array来当dp，全程只需要maxPro，minPro, res 来不断update保存即可。原因，input数组中有正有负。所以不仅要存储maxPro还需要存储minPro，有时候num是负数，那么乘以一个负数会变成大的正数。

楼主好棒！每天的内容好充实，要向你学习。加油加油，付出一定会带来收获！