高算1是介绍性的,讲的是前向型指针
1. Kth Smallest Number in Sorted Matrix: 用 heap来做,并且用visited来保存访问过的位置,不过这题和leetcode的668. Kth Smallest Number in Multiplication Table,很类似但是leetcode这题如果用heap的话就会TLE,需要用binary search来做。那道题的条件更强
2. Minimum Size Subarray Sum: 找动态窗口的一般首先考虑前向型指针
3. Longest Substring Without Repeating Characters: 同上解
4. Longest Substring with At Most K Distinct Characters: 前向型指针的模版,基本思路就是先挪j,一直到j不能动为止,再缩减i
for i in range(len(nums)):
while j < len(nums) and valid(j, hash, counter, etc...):
modify hash, counter, etc.
calculate result
revise hash counter, etc,
5. Kth Smallest Sum In Two Sorted Arrays:类似于1, 一道用heap和visited来做的题
6. Kth Largest in N Arrays: 还是用heap来做
7.Two Sum - Less than or equal to target: 这道题用two pointer,只是在某一个pointer做循环的时候要考虑range的效应比如说 A[i] + A[j] <= target 那么所有 A[i] + A[k] k in i+1...j 都 <= target
8. Kth Smallest Numbers in Unsorted Array: 这道题是quick select
9.Triangle Count: 和第7题一样,只是利用了一下triangle的性质
10. Minimum Window Substring: 前向型指针的题,去leetcode手写一遍
11. Kth Largest Element: 和第八题一样,只是转换一下大小index就可以了