刷题经验和讲解整理

排列问题： 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的时候，一般可以猜排序算法。

分治和遍历：max node of binary tree

分治和遍历是两种常见的recursion写法，算法思想上，分治是把样本分成两部分（或者n个部分），每一个部分返回result，再把所有部分合成一个result，并且返回；而遍历，则是带一个容器，遍历所有element，不断更新容器里的内容。

用一个例子来说： max node of binary tree

遍历：这里用了一个preorder traversal，同时维护了一个pointer，指向最大的node
def traversal(self, root):
    res = None # 这个res就是那个容器，记录了最大的节点
    self.helper(root, res)
    return res
def helper(self, root, res):
     if not root:
        return
     if res and root.val > res.val:
        res = root
     self.helper(root.left, res)
     self.helper(root.right, res)

分治：函数本身就返回了这个最大的节点

def divideConcur(self, root):
     if not root:
         return root

     left = divideConcur(self, root.left)
     right = divideConcur(self, root.right)
     return self.maxNode(root, left, right) # maxNode返回三个节点，value最大的node

总结一下：
        1. 一般来讲分治法的function有return value，遍历（就是那个helper）不需要返回；
        2. 一般分治法是从下到上，比如在这道题里，是先找到最底层的最大值，然后逐层向上，最后到root的时候就找到答案了；遍历的顺序就比较随意了，总之就是便利所有数据之后，在容器内找到答案；
        3. 有些时候，分治法返回的value会比较复杂，这个时候需要自己define一个自己需要的容器；

分治的思路，在归并排序，快速排序中都有用到。真正情况下，要根据题来选择合适的算法。

谢谢分享，点个赞

二分法：sqrt（x）
当需用从O(n)或者O(n^2) 优化到O(logn)， O(nlogn)时，一般会考虑二分或者二分的思路。二分的思路一般都比较容易想到，但是难点是写二分的时候很容易写出bug，我自己总结的模板是这样的：（以sqrtx这道题为例）
def sqrt(self, x):
        def guess(num):
            if num * num < x:
                return -1
            elif num * num == x:
                return 0
            else:
                return 1

        left, right = 0, sys.maxint
        while left < right - 1:
            mid = left + (right - left) / 2
            g = guess(mid)
            if g == 0:
                return mid
            elif g < 0:
                left = mid
            else:
                right = mid

        if guess(right) <= 0:
            return right
        else:
            return left

这个模板几个点：
        1. 有一个guess函数。再简单的情况下不需要这个函数，直接在while循环中计算就可以了，但是如果有比较复杂的二分题目，最好还是写一个guess函数，这样可读性更高；
        2. while循环终止的条件是 left < right - 1，这样在终止循环的时候答案可能在mid，left和right三个值中出现，如果mid，就会直接返回；如果left或者right，那么会在跳出循环之后再看；
先看right还是先看left，取决于要求，比如找最大值，那就先看right；如果是找最小值，那就先看left。

BFS和其相关变形模板
BFS题目出现的概率很多，而且写法很简单，是一个需要掌握很好的算法。一般来讲BFS会用iterative的写法，这样可以避免stack overflow的问题，我自己总结的模板：

def BFS(self, graph, start)
        ans = []
        q = []
        visited = {}

        q.append(start)
        visited[start] = True  

        while q:
            temp = q.pop(0)
            ans.append(temp)
            for n in temp.neighbors:
                if n not in visited:
                    q.append(n)
                    visited[n] = True
        return ans

这里有关visited需要说明：
        1. visited是一个hashtable，它的第一个目的是判断当前node是否已经被访问；
        2. visited的维护一点要和q同步，每次把node加入到q时，也要加入到visited；
        3. visited的用法其实可以更加灵活，比如存入一些有关node信息，比如father （google onsite的一道followup用到了这个思想）

BFS的第一个变形是 level-by-level的BFS：
def BFS(self, graph, start)
        ans = []
        q = []
        visited = {}

        q.append(start)
        visited[start] = True  

        while q:
            size = len(q)
            for i in range(size):
                temp = q.pop(0)
                ans.append(temp)
                for n in temp.neighbors:
                    if n not in visited:
                        q.append(n)
                        visited[n] = True
        return ans
与之前不同是每次便利把同一层的node全部便利，这里用到了queue的FIFO特性。注意在for循环的时候一定要先得到q当前的size再loop，因为后面会把新node加入到q，q的size是一直变化的。

BFS的第二个变形是topological sorting。理论上topological sorting可以用BFS，也可以DFS。这里提供的是BFS的模板：


def topSortBFS(self, graph):
        indegree = {}
        ans = []
        for g in graph:
            for n in g.neighbors:
                if n not in indegree:
                    indegree[n] = 1
                else:
                    indegree[n] += 1

        q = []
        for g in graph:
            if g not in indegree:
                q.append(g)

        while q:
            temp = q.pop(0)
            ans.append(temp)
            for n in temp.neighbors:
                indegree[n] -= 1
                if indegree[n] == 0:
                    q.append(n)
        return ans

这里因为有indegree的存在，就不需要visited了（或者也可以理解为indegree是visited的变形）。如果以后碰到拓扑排序的题目，可以再详细分析，并revisited BFS

谢谢分享，点个赞

感谢LZ详细的解释，能不能加上几个推荐相关的练习的题目！！非常感谢！！

水锦鲤 发表于 2019-1-28 10:24
感谢LZ详细的解释，能不能加上几个推荐相关的练习的题目！！非常感谢！！

嗯 一点点来，我会尽量更新，也算是自己保持状态 哈哈～

感谢楼主分享，赞一个

amcw7777 发表于 2019-1-28 11:02
嗯 一点点来，我会尽量更新，也算是自己保持状态 哈哈～

谢谢LZ!!!!