高级农民
- 积分
- 1062
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2016-9-18
- 最后登录
- 1970-1-1
|
介于FB tag已经基本刷完，而且刚好也上了20道，现在距离二面也只有一周了，所以现在基本上以分析、总结、归类为主，遇到某个类型的相似题目，可以顺便刷一刷
integer to roman / roman to integer
* 13. Roman to Integer (easy)
* 从index 0到length-2
* 如果current char >= next char, sum+= current
* 如果current char < next char, sum -= current
* 一个table对应roman 和 integer
* 12. Integer to Roman (medium)
* return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
* M是千，C是百，X是十，I是一
* 273. Integer to English Words (hard)
* 像这个系列的题一样，得有一个table或者几个list去存数字到英文的值，本题中存三个list，**注意不包含"zero"，因为“zero”是特殊情况，只有当数为0的时候才会用到**
* 小于二十: 1~19
* 十: 10~90
* 千: 1000, 100,000, 100,000,000
* 因为这个方法是O(1)的，所以不需要用StringBuilder
* 在主方法里面检查thousands
* 在helper方法里面检查小于二十，十和百（加上"Hundred”）
add two (string/binary/number)
* 67. Add Binary (easy)
* 首先run time不是O(1)，而是linearly related to the size of two input strings, 所以用StringBuilder
* 从右往左加
* 这种"add"类的题目，都需要存一个**carry**, 一个**sumOfCurrentDigit**
* 每次iteration开始时，`sumOfCurrentDigit = carry`
* 每次iteration中，`sumOfCurrentDigit += digit1 和 digit2`
* result的`currentDigit = sumOfCurrentDigit % radix(进制)`
* `carry = sumOfCurrentDigit / radix(进制)`
* 2. Add Two Numbers [linkedlist] (medium)
* 思路和67 add binary基本一致
* 每次iteration中，sumOfCurrentDigit += digit1 和 digit2
* 每次iteraton结束之前
* result的currentDigit = sumOfCurrentDigit % radix(进制)
* carry = sumOfCurrentDigit / radix(进制)
* 因为要新建一个LinkedList，所以需要新建一个dummy，然后node = dummy，最后return dummy.next
* 445. Add Two Numbers II (medium)
* 和2. add two number的区别是most significant digit comes first，这样的话在建dummy的时候，建成null即可，然后每次都新建一个newHead，让newHead.next = dummy；同样最后还要check一下sum是否为1，如果是1的话，再加一个val为1的newHead
* 415. Add Strings (medium)
* 和67. add binary基本一样，只是换了进制而已
* 43. Multiply Strings (medium)
* num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]
* if(sb.length() != 0 && p != 0) sb.append(p)，这样能够把开头的0去掉
subarray
* 325. Maximum Size Subarray Sum Equals k (medium)
* sum list, hash map，思路类似two sum
* 1. Two Sum (easy)
* hash map
* 209. Minimum Size Subarray Sum (medium)
* 2 pointer: O(n)
* 用start和end创造一个subarray的window
* start = 0, end = 0, min = Integer.MAX_VALUE, sum = 0
* `while (end < nums.length)`
* 正常情况下sum < k，这时候end++, 更新sum: sum += nums[end]
* 如果sum >= k了，那么start++, 更新sum: sum -= nums[start]
* binary search : O(nlgn)，其中binary search是O(lgn), helper method是O(n)
* 用一个helper叫windowExists的方法，把主方程里的mid当成size来搜索
substring (sliding window)
* 209. Minimum Size Subarray Sum (medium)
* 2 pointer: O(n)
* 用start和end创造一个subarray的window
* start = 0, end = 0, min = Integer.MAX_VALUE, sum = 0
* `while (end < nums.length)`
* 正常情况下sum < k，这时候end++, 更新sum: sum += nums[end]
* 如果sum >= k了，那么start++, 更新sum: sum -= nums[start]
* 76. Minimum Window Substring (hard) 【不用hash map的方法，用hash map的话更具有普适性】
* two pointers: start and end to represent a window.
* Move end to find a valid window.
* When a valid window is found, move start to find a smaller window.
* 不要用hash map存pattern的char，用int[128]就行了，因为unicode 0~127就包含了基本的拉丁字母和符号了，hash map反而更复杂
* map里存的是window中待include的char的数量
* counter: the number of chars of pattern to be found in text
* (while end < text.length())从end = 0 到 text.length()扫描：
* if 扫描的endChar对应map的值>0，将它的值-1, counter--
* 让map里对应的endChar的value-1，（map中对应的char如果是pattern的char，不会<0，如果不对应则会<0）
* end++，相当于window变大，所以待include的数量减少
* (while counter == 0)，说明在这个[start, end]区间内有一个valid window
* update minLength与minStart
* 让map里对应的startChar的value+1，（如果map里对应的char是pattern的char，此时它的数量会>0）
* if 该value > 0, counter++
* start++，相当于window变小，所以待include的数量增加
* 159. Longest Substring with At Most Two Distinct Characters (hard)
* 套用substring类的题目的模板
* 区别是，因为只有text，没有pattern，往map里put的时候，可以放在第一个while loop里面
* if (map.get(c1) == 1) counter++; // new char
* 340. Longest Substring with At Most K Distinct Characters (hard)
* 159的follow-up
* 把159中的`while (counter > 2)`换成`while (counter > k)`就好了
* 3. Longest Substring Without Repeating Characters (medium)
* 思路同159，340，只需要换三行就行了
* if (map.get(c1) > 1) counter++; // 把之前的 == 1 换成 > 1
* while (counter > 0) { // 换成 > 0
* if (map.get(c2) > 0) counter--; // 换成 > 0
* 438. Find All Anagrams in a String (easy)
* sliding window，基本同76一样，只需要改一点点
* 30. Substring with Concatenation of All Words (hard)
*
meeting rooms & intervals
* 252. Meeting Rooms (easy)
* use lambda expression to sort the intervals by start time
* start time at index i should be no less than end time at index (i+1)
* 253. Meeting Rooms II (medium)
* 找到最少需要几个meeting room
* 方法一：分别sort start time和end time
* loop over starttime list，需要两个var: rooms, endTimePointer
* 每当startime[i] < endTime[endTimePointer], rooms++ 【starttime[i]是新的meeting, endTime[endTimePointer]是旧的meeting】
* else endTimePointer++
* 方法二：sort start time，用min heap存end time
* loop over intervals (with sorted start time)
* 如果intervals[i].starttime >= interval_polled.endtime【intervals[i].starttime是新的meeting, heap.poll()是旧的meeting】，这时需要merge end time: interval_polled.end = intervals[i].end
* else heap.offer(intervals[i]);
* heap.offer(interval_polled)
* 56. Merge Intervals (medium)
* sorting
* make a new list, compare sorted intervals with new list and do merging
* 57. Insert Intervals (hard)
* 把所有endtime < newInterval.starttime的interval加到result中
* 把所有overlapping intervals和newInterval merge成一个新的newInterval，替代之前的newInterval，加到result中（用较小的starttime和较大的endtime）
* 把其他starttime > newInterval.endtime加到result中去
heap
* 23. Merge K Sorted List (hard)
* heap，对于stream，或者一直改变的structure的sorting，用heap，本题中每个list都在不停的改变
* 对所有的node : lists，如果node不为null，就offer到heap上
* while (heap不空)
* append heap.poll()的第一个node到tail上，在把第二个node开始（即tail = tail.next之后的tail.next）offer到heap上
* |
|
楼主: floydc
狗仔卡
楼主
