刷题经验和讲解整理

18年找工作刷了挺多题，而且自己也喜欢总结和分享。年前签完公司之后，我一直在帮身边有些在准备面试的朋整理算法题的思路和一些经典题。我觉得可以在这里单独发一个贴子写上自己的经验，一方面不断的复习，另一方面对大家都有所帮助。另外我另一个有关分布式系统设计的帖子最近几个月没有更新，因为时间花在毕业的事情上，以后我还会把自己学到的相关知识放上来和大家讨论～
祝大家新年快乐～

有一些在网课博客上经常能看见的经验，我想起来会随时补充：
        1. 根据数据规模选择算法：这个在网上看见过很多次，很有用处。考虑计算机是1 GHz，程序的overhead大概是100，也就是说计算机每秒能够运算10^ 6 到 10^7 次。一般来讲超过1秒的程序会超时，所以可以根据数据规模简单判断可以选用的算法：
                a. N > 10^5， 需要log(n)算法，主要是二分法
                b. 1000 < N < 10000， 一般是O(n)，也是个人感觉难题集中的地方，算法多变性很多，比如指针，dp
                c. 1000 < N < 5000, 这个时候可能会出现O(nlogn)算法，一般就是排序
                d. 100 < N < 1000， 这是允许 O(n^2) 算法，两次遍历数据，或者DP
                e. 10 < N < 100， 基本看到这个数据量就是NP问题了，组合O(2^n) 或者排列O(n!)

谢谢楼主的总结，很实用。有些自己的建议，供讨论。
1. Pythonic.
1) Python没有integer overflow, 所以我们不需要写mid = start + (end-start)/2，而是简单地 mid = (start + end) // 2
2) Python里int也没有最大值，所以其他语言的sys.maxint一般写成float("inf")
2. 二分法. left < right – 1的终止条件是left和right直接相邻，左left，右right，没有mid这第三个值出现(此时的mid等于left)。
3. BFS. Temp=q.pop(0)这一步时间复杂度是O(n)吧。如果改用collections.deque，然后temp = queue.popleft(),这样就approximately in O(1)了。

排列问题： subset
Subset是全排列的基础题目，完全掌握并不断复习非常有必要。问题是给一个数组，求出数组的所有subset
这里有一些我自己的概念的理解，如果有不对希望大家指正。
        1. 有关iterative 和 recursive：只是程序写法的问题，不代表DFS一定是recursive，BFS一定是iterative。比如DFS也可以用recursive来写；
        2. 有关DFS和BFS：也只是遍历的方法，不代表排列一定是DFS，比如排列也可以用BFS；另外遍历不只是只有DFS和BFS，比如二叉树inorder遍历就和这两种都没有关系；


题目：nums为非空排序数组， 要求return所有subset。比如[1,2,3], 答案是
[
  [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []
]
def solution(self, nums):
        res = [] # res 用来存储答案
        subset = [] # subset用来存储subset，相当于一个cache
        self.setset(res,nums)
        return res
       
解法1: 属于recursive的遍历DFS，遍历到最后一位的时候把subset记录在答案里，subset就是便利的时候携带的笔记本。
def subset1(self,subset,res,index,nums):
        if index == len(nums):
                res.append(subset[:])
                return
        subset.append(nums[index])
        self.subset1(subset,res,index+1,nums) # 这种情况就是用第idx个数字
        subset.pop(-1)
        self.subset1(subset,res,index+1,nums) # 这种情况就是不用idx
       
解法2: 在进行到index的时候把subset记录在res里，这个思路有点类似于Divide and concur，divide的两组分别是index之前和之后。
def subset2(self,subset,res,index,nums):
        res.append(subset[:])
        for i in range(index,len(nums)):
                subset.append(nums[i])
                self.subset2(subset,res,i+1,nums)
                subset.pop(-1)
               
解法3: iterative的排列写法，如果面试被问到需要掌握，注意这里一定要排序nums，因为用temp[-1] < nums[i]来找index
def subset3(self,res,nums):
        stack = []
        stack.append([])
        while stack:
                temp = stack.pop()[:]
                res.append(temp)
                for i in range(len(nums)):
                        if not temp or temp[-1] < nums[i]:
                                #相当于没有用temp[-1]到 第i-1个数字
                                subset = temp[:]
                                temp.append(nums[i])
                                stack.append(subset)
        return res
       
需要注意的点：
        1. copy的时候不能简单的res.append(subset)，那样只会copy pointer。这里需要deep copy，res.append(subset[:]) 或者更复杂的情况需要res.append(copy.deepcopy(subset))
        2. recursive需要出口，不然会死循环
        3. BFS的tricky点在于找开始插入的地址，用not temp or temp[-1] < nums[i] 判断。
       
排列的时间复杂度，一般来讲是O(2^n)，因为每一位数字都有用和不用两种可能，根据计算时间的讨论，10^6 > 8^6  > (2^3)^6 = 2 ^ 18。所以在n < 20的时候，一般可以猜排序算法。

沙发！！！

Quick sort 和 partition（快速排序法）：

class quickSort(object):

def __init__(self, nums):

self.A = nums

self.sort(0, len(self.A)-1)

def sort(self, start, end):

if start >= end:

Return

l, r =start, end

pivot = self.A[ l + (r-l)/2 ]

while l <= r:  

while l <= r and self.A[l] < pivot:

l += 1

while l <= r and self.A[r] > pivot:

r -= 1

if l <= r:

self.A[l],  self.A[r] = self.A[r],  self.A[l]

l += 1

r -= 1

self.sort(start, r)

self.sort(l, end)

快速排序的核心思想是partition，就是先找到一个pivot，然后把数组中小于pivot的数字放到左边，大于pivot的数字放在右边，一次partition之后，达到[start, r] 的数字小于pivot，同时[l, end]的数字大于pivot。然后再次调用sort函数，继续分别对这两个区间进行排序。

在while l  <= r 中的操作，目的是找到小于pivot的第一个l， 和大于pivot的第一个r，然后swap这两个数的值。

以下几点值得留意：

• 快速排序的平均时间复杂度是O(nlogn), 最差情况是O(n^2)，最差情况发生在每一次pivot都选成了区间内的最大/最小值。所以选择pivot实际上是一个很重要的问题，我的code里面是选取了中间位置的数值，还有一些其他方法，比如选取随机数，以及选取第一个数字，最后一个数字，中间数字这三个数字的平均值等等；我在面试的时候被问过这样的问题；
  
• 当nums[i]     ==     pivot情况的处理：我的code选择不动。原因是尽量让pivot左右两边的数值一样多。如果是让小于等于的数字去左边（或者大于等于pivot的数字去右边），容易让左边（或者右边）有更多的numbers；
  
• 跳出while循环的时候，实际上l已经在r的右边了，所以再继续recursion的时候，区间是[start,     r] 和 [l, end]，这里容易出bug。（如果没有理解可以自己过一下[3,2,14,5]这个例子，会卡在[0,1]死循环）。
  

面试真题：我没有直接被问到过快速排序，但是我有过两道面试题是用到partition了，Kth Largest Element in anArray这道题，大家可以试一下。

Merge sort 和 k路归并
class mergeSort(object):
        def __init__(self, nums):
                self.A = nums
                size = len(self.A)
                self.temp = [0 for _ in range(size)] self.sort(0,size-1)
        def sort(self, start, end):
                if start >= end:
                        return
                mid = start + (end-start)/2
                self.sort(start, mid)
                self.sort(mid+1, end)
                self.merge(start, end)
        def merge(self, start, end):
                mid = start + (end-start)/2
                l, r = start, mid+1
                index = start
                while l <= mid and r <= end:
                        if self.A[l] < self.A[r]:
                                self.temp[index] = self.A[l]
                                index += 1
                                l += 1
                        else:
                                self.temp[index] = self.A[r]
                                index += 1
                                r += 1
                while l <= mid:
                        self.temp[index] = self.A[l]
                        index += 1
                        l += 1
                while r <= end:
                        self.temp[index] = self.A[r]
                        index += 1
                        r += 1
                for i in range(start, end+1):
                        self.A[i] = self.temp[i]
归并排序的核心思想是把两个已经排序好的数组，归并成一个排序好的数组，在程序里，这两个数组分别是nums[start:mid] 和 nums[mid+1:end]。
程序里用l， r 分表表示两个数组的index，然后比较nums[l], nums[r]同时把比较小的数字放进缓存数组，最后再分别看两个数组是否有剩下的数字。最后一步把缓存数组（已经排好序的数字）替换原数组，以达到排序。

一个比较重要的点：
归并排序需要一个额外的空间来缓存，当整个排序好之后再用最后一个for循环来替换初始值。如果不用这个额外空间的话，会出现没有被扫描的数直接被in-place替换掉的情况。

Follow up 相关延展：
        1. k路归并。归并排序实际上是一种2路归并，把两个排序数组归并成一个；有一个非常有名的问题，是把k个排序好的数组归并成一个；
        2. 区间归并：如何merge interval？ 比如[1, 3] + [2,5] = [1, 5]，也是一个比较高频的题目。

谢谢你的经验

很有用！ 谢谢分享～

棒！期待更多的

双指针：同向双指针和相向双指针
双指针一般是用来作为O(n)时间扫描一次数据就能找到答案的算法。现在已经很少单独面试中用到了（我就面试过一次同向双指针），而是作为题中的一部分，比如merge  sort的时候用两个index来标记，是同向双指针；quick sort 是相向双指针。而这两种双指针最直接的应用是经典题目 sum two
        1. Sum two in sorted array: 相向双指针：
        def sumTwo(self, nums, target):
                idx1, idx2 = 0, len(nums)-1
                while idx1 < idx2:
                        sum = nums[idx1] + nums[idx2]
                        if sum == target:
                                return [idx1, idx2]
                        elif sum < target:
                                idx1 += 1
                        else:
                                idx2 -= 1
                               
        2. Diff two in sorted array: 同向双指针：
        def  diffTwo(self, nums, target):
                idx1, idx2 = 0, 0
                while idx2 < len(nums):
                        diff = nums[idx2] - nums[idx1]
                        if diff == target:
                                return [idx1, idx2]
                        elif diff < target:
                                idx2 += 1
                        else:
                                idx1 += 1
                               
实际情况中不会这么理想，很多难点都在细节和不同的要求中，但是核心就是这种感觉。
Follow up 相关延展：
        1. 扫描线法：思路实际上是同向双指针
        2. 单调栈：思路也是同向双指针
        3. Merge sort and quick sort