8.28 - 高算1

高算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就可以了

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容