class Solution:
    """
    @params s1, s2, s3: Three strings as description.
    @return: return True if s3 is formed by the interleaving of
             s1 and s2 or False if not.
    @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
    """
    def isInterleave(self, s1, s2, s3):
        # write your code here
        if s1 is None or s2 is None or s3 is None:
            return False
        if len(s1) + len(s2) != len(s3):
            return False
        # 初始边界s1行s2列的false
        interleave = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        interleave[0][0] = True
        for i in range(len(s1)):
            interleave[i + 1][0] = s1[:i + 1] == s3[:i + 1]
        for i in range(len(s2)):
            interleave[0][i + 1] = s2[:i + 1] == s3[:i + 1]

        for i in range(len(s1)):
            for j in range(len(s2)):
                interleave[i + 1][j + 1] = False
                if s1[i] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] = interleave[i][j + 1]
                if s2[j] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] |= interleave[i + 1][j]
        return interleave[len(s1)][len(s2)]

class Solution:
    """
    @param nums: The integer array
    @return: The length of LIS (longest increasing subsequence)
    """
    def longestIncreasingSubsequence(self, nums):
        # write your code here
        if nums is None or not nums:
            return 0
        dp = [1] * len(nums) # 边界初始条件
        for curr, val in enumerate(nums):
            for prev in xrange(curr):
                if nums[prev] < val:  # 如果之前的元素大于等于curr，则dp[curr]为初始的1
                    dp[curr] = max(dp[curr], dp[prev] + 1) #状态转移方程
        return max(dp)

class Solution:
    # @param s: A string s
    # @param dict: A dictionary of words dict
    def wordBreak(self, s, dict):
        if len(dict) == 0:
            return len(s) == 0
            
        n = len(s)
        f = [False] * (n + 1)
        f[0] = True  # 初始边界
        
        maxLength = max([len(w) for w in dict]) #先计算字典中最大长度，减少复杂度
        for i in xrange(1, n + 1):
            for j in range(1, min(i, maxLength) + 1): #不必遍历i之前的所有j
                if not f[i - j]:
                    continue
                if s[i - j:i] in dict:
                    f[i] = True
                    break # 有一个满足即可判断下一个f[i+1]
        return f[n]

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    def minimumTotal(self, triangle):
        rows = len(triangle)
        dp = [[0] * len(triangle[row]) for row in range(rows)] 
        for i in range(len(triangle[rows - 1])):
            dp[rows - 1][i] = triangle[rows - 1][i] #初始边界
        for i in range(rows - 2, -1, -1):
            for j in range(i + 1):
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j] #状态转移方程
        return dp[0][0]

class Solution:
    """
    @param grid: a list of lists of integers.
    @return: An integer, minimizes the sum of all numbers along its path
    """
    def minPathSum(self, grid):
        for i in range(len(grid)): 
            for j in range(len(grid[0])):
                if i == 0 and j > 0:
                    grid[i][j] += grid[i][j-1] # 第一行，只在左边
                elif j == 0 and i > 0:
                    grid[i][j] += grid[i-1][j] # 第一列，只在右边
                elif i > 0 and j > 0:
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1])  # 由上面和左面的最小路径决定
        return grid[len(grid) - 1][len(grid[0]) - 1]

class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def climbStairs(self, n):
        # write your code here
        if n == 0:
            return 1
        if n <= 2:
            return n
        result=[1,2]
        for i in range(n-2):
            result.append(result[-2]+result[-1])
        return result[-1]

class Solution:

    def uniquePaths(self, m, n):
        paths = [[0] * n for i in range(m)] #初始边界
        # initial rows
        paths[0][0] = 1
        for x in range(1, m):
            paths[x][0] = paths[x - 1][0] #边界
        # initail columns
        for y in range(1, n):
            paths[0][y] = paths[0][y - 1] #边界

        for x in range(1, m):
            for y in range(1, n):
                paths[x][y] = paths[x -1][y] + paths[x][y - 1]
        return paths[m - 1][n - 1]

class Solution:
    """
    @param word1: A string
    @param word2: A string
    @return: The minimum number of steps.
    """
    def minDistance(self, word1, word2):
        n, m = len(word1), len(word2)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            f[i][0] = i # 边界
        for j in range(m + 1):
            f[0][j] = j # 边界

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j] + 1, f[i][j - 1] + 1)
                    # equivalent to f[i][j] = f[i - 1][j - 1]
                else: #分别代表替换，插入，删除
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
                        
        return f[n][m]

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

class Solution(object):
    # DP
    def isMatch(self, s, p):
        dp = [[False for i in range(0,len(p) + 1)] for j in range(0, len(s) + 1)]
        dp[0][0] = True
        for i in range(1, len(p) + 1):
            if (p[i - 1] == '*'):
                dp[0][i] = dp[0][i - 2]
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if s[i - 1] == p[j - 2] or p[j - 2] == '.':
                        dp[i][j] |= dp[i-1][j]
                else:
                    if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                        dp[i][j] = dp[i - 1][j - 1]
    
        return dp[len(s)][len(p)]

    # 懒癌版
    def isMatch(self, s, p):
        # '$'字符规则代表匹配字符串的末尾，匹配返回一个Match 对象，否则返回None
        return re.match(p + '$', s) != None

1         3     3       2    1
 \       /     /       / \    \
  3     2     1       1   3    2
 /     /       \                \
2     1         2                3

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    # @paramn n: An integer
    # @return: A list of root
    def generateTrees(self, n):
        # write your code here
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

class Solution:
    """
    @param nums: An array of integers
    @return: An integer
    """
    def maxProduct(self, nums):
        if not nums:
            return None
            
        global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            if num > 0:
                curt_max = max(num, prev_max * num)
                curt_min = min(num, prev_min * num)
            else:
                curt_max = max(num, prev_min * num)
                curt_min = min(num, prev_max * num)
            
            global_max = max(global_max, curt_max)
            prev_max, prev_min = curt_max, curt_min
            
        return global_max

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

class Solution:
    """
    @param s: A string
    @param p: A string includes "?" and "*"
    @return: A boolean
    """
    def isMatch(self, s, p):
        # write your code here
        n = len(s)
        m = len(p)
        f = [[False] * (m + 1) for i in range(n + 1)]
        f[0][0] = True

        if n == 0 and p.count('*') == m:
            return True

        for i in range(0, n + 1):
            for j in range(0, m + 1):
                if i > 0 and j > 0:
                    f[i][j] |= f[i-1][j-1] and (s[i-1] == p[j-1] or p[j - 1] in ['?', '*'])

                if i > 0 and j > 0:
                    f[i][j] |= f[i - 1][j] and p[j - 1] == '*'

                if j > 0:
                    f[i][j] |= f[i][j - 1] and p[j - 1] == '*'
        return f[n][m]

class Solution:
    """
    @param A: An array of non-negative integers
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber(self, A):
        if not A:
            return 0
        if len(A) <= 2:
            return max(A)
            
        f = [0] * len(A)
        f[0], f[1] = A[0], max(A[0], A[1])
        
        for i in range(2, len(A)):
            f[i] = max(f[i - 1], f[i - 2] + A[i])
        return f[len(A) - 1]
        
# 使用滚动数组版本
class Solution:
    """
    @param A: An array of non-negative integers
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber(self, A):
        if not A:
            return 0
        if len(A) <= 2:
            return max(A)
            
        f = [0] * 3
        f[0], f[1] = A[0], max(A[0], A[1])
        
        for i in range(2, len(A)):
            f[i % 3] = max(f[(i - 1) % 3], f[(i - 2) % 3] + A[i])
            
        return f[(len(A) - 1) % 3]

class Solution:
    """
    @param k: an integer
    @param prices: an integer array
    @return: an integer which is maximum profit
    """
    def maxProfit(self, k, prices):
        # write your code here
        size = len(prices)
        if k >= size / 2:
            return self.quickSolve(size, prices)
        dp = [None] * (2 * k + 1)
        dp[0] = 0
        for i in range(size):
            for j in range(min(2 * k, i + 1) , 0 , -1):
                dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
        return max(dp)

    def quickSolve(self, size, prices):
        sum = 0
        for x in range(size - 1):
            if prices[x + 1] > prices[x]:
                sum += prices[x + 1] - prices[x]
        return sum

'A' -> 1
'B' -> 2
...
'Z' -> 26

class Solution:
    # @param {string} s a string,  encoded message
    # @return {int} an integer, the number of ways decoding
    def numDecodings(self, s):
        # Write your code here
        if s == "" or s[0] == '0':
            return 0

        dp=[1,1]
        for i in range(2,len(s) + 1):
            if 10 <= int(s[i - 2 : i]) <=26 and s[i - 1] != '0':
                dp.append(dp[i - 1] + dp[i - 2])
            elif int(s[i-2 : i]) == 10 or int(s[i - 2 : i]) == 20:
                dp.append(dp[i - 2])
            elif s[i-1] != '0':
                dp.append(dp[i-1])
            else:
                return 0

        return dp[len(s)]

def numSquares(self, n):
        # write your code here
        dp = []
        import sys
        for i in range(n+1):
            dp.append(sys.maxint)
        i = 0
        while i * i <= n:
            dp[i*i] = 1
            i += 1

        
        for i in range(n+1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i-j*j] + 1)
                j += 1
        return dp[n]

class Node():
    #节点类
    def __init__(self,data = -1):
        self.data = data
        self.left = None
        self.right = None
class Tree():
    #树类
    def __init__(self):
        self.root = Node()
 
    def add(self,data):
        # 为树加入节点
        node  = Node(data)
        if self.root.data == -1:        #如果树为空，就对根节点赋值
            self.root = node
        else:
            myQueue = []
            treeNode = self.root
            myQueue.append(treeNode)
            while myQueue:              #对已有的节点进行层次遍历
                treeNode = myQueue.pop(0)
                if not treeNode.left:
                    treeNode.left = node
                    return
                elif not treeNode.right:
                    treeNode.right = node
                    return
                else:
                    myQueue.append(treeNode.left)
                    myQueue.append(treeNode.right)
 
    def pre_order_recursion(self,root):     #递归实现前序遍历
        if not root:
            return
        print root.data,
        self.pre_order_recursion(root.left)
        self.pre_order_recursion(root.right)
 
    def pre_order_stack(self,root):         #堆栈实现前序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:
            while node:       #从根节点开始，一直寻找他的左子树
                print node.data,     # 先序，进栈前就要读取了
                myStack.append(node) # 先存进栈，以后还需要它的右节点
                node = node.left
            node = myStack.pop()    #while结束表示当前节点node为空，即前一个节点没有左子树了
            node = node.right       #开始查看它的右子树
 
    def in_order_recursion(self,root):      #递归实现中序遍历
        if not root:
            return
        self.in_order_recursion(root.left)
        print root.data,
        self.in_order_recursion(root.right)
 
    def in_order_stack(self,root):        #堆栈实现中序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:     #从根节点开始，一直寻找它的左子树
            while node:
                myStack.append(node) 
                node = node.left
            node = myStack.pop() # 中序，弹出来后才读取
            print node.data,
            node = node.right
 
 
    def post_order_recursion(self,root):     #递归实现后序遍历
        if not root:
            return
        self.post_order_recursion(root.left)
        self.post_order_recursion(root.right)
        print root.data,
        
    def post_order_stack(self, root):  # 堆栈实现后序遍历（非递归）
        # 先遍历根节点，再遍历右子树，最后是左子树，这样就可以转化为和先序遍历一个类型了，最后只把遍历结果逆序输出就OK了。
        if not root:
            return
        myStack1 = []
        myStack2 = []
        node = root
        while myStack1 or node:
            while node:
                myStack2.append(node)
                myStack1.append(node)
                node = node.right
            node = myStack1.pop()
            node = node.left
        while myStack2:
            print myStack2.pop().data,
 
    def level_order_queue(self,root):       #队列实现层次遍历（非递归）
        if not root :
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print node.data,
            if node.left:
                myQueue.append(node.left)
            if node.right:
                myQueue.append(node.right)
                
if __name__ == '__main__':
    #主函数
    datas = [2,3,4,5,6,7,8,9]
    tree = Tree()          #新建一个树对象
    for data in datas:
        tree.add(data)      #逐个加入树的节点
 
    print '递归实现前序遍历：'
    tree.pre_order_recursion(tree.root)
 
    print '\n堆栈实现前序遍历'
    tree.pre_order_stack(tree.root)
 
    print "\n\n递归实现中序遍历："
    tree.in_order_recursion(tree.root)
 
    print "\n堆栈实现中序遍历："
    tree.in_order_stack(tree.root)
 
    print '\n\n递归实现后序遍历：'
    tree.post_order_recursion(tree.root)
 
    print '\n堆栈实现后序遍历：'
    tree.post_order_stack(tree.root)
 
    print '\n\n队列实现层次遍历：'
    tree.level_order_queue(tree.root)！

#  二分查找
def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low < height:
        mid = (low+height)/2
        if array[mid] < t:
            low = mid + 1

        elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]
    return -1


if __name__ == "__main__":
    print BinarySearch([1,2,3,34,56,57,78,87],57)

'''
深度优先遍历： 是一种用于遍历树或者图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都被搜索过了。搜索将回溯到节点v的那条边的起始节点。直到已发现从源节点可达的所有节点为止。如果还存在未发现的节点，则选择其中一个作为源节点并重复上述过程，整个进程反复进行直到所有节点都被访问为止.

广度优先遍历：从根节点开始，沿着树的宽度遍历树的节点，如果所有节点都被访问，则算法终止
'''
class Graph(object):
    def __init__(self, nodes, sides):
        # nodes表示用户输入的点，int型，sides表示用户输入的边，是一个二元组(u, v)
        # self.sequence是字典，key是点，value是与key相连的边
        self.sequence = {}
        # self.side是临时变量，主要用于保存与 指定点v 相连接的点
        self.side = []
        for node in nodes:
            for side in sides:
                u, v = side
                if node == u:
                    self.side.append(v)
                elif node == v:
                    self.side.append(u)
            # 第二层主要是遍历属于这个点的所有边，然后将点和边组成字典
            self.sequence[node] = self.side
            self.side = []
        # print self.sequence
        # {1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7], 4: [2, 8], 5: [2, 8], 6: [3, 7], 7: [3, 6], 8: [4, 5]}
 
    def dfs(self, node0):
        # order里面存放的是具体的访问路径，已经遍历的了
        queue, order = [], []
        queue.append(node0)
        while queue:
            v = queue.pop()  # 取出最后一个，为上一个刚加入节点的连接节点
            order.append(v) # 深度优先先加入，注意这个order的加入顺序
            for w in self.sequence[v]: # 两边
                # 不在order表示没被遍历，
                if w not in order and w not in queue:
                    queue.append(w)
        return order
    
    # bfs同理
    def bfs(self, node0):
        queue, order = [], []
        queue.append(node0)
        order.append(node0)
        while queue:
            v = queue.pop(0)  # 层次遍历按迅速取出
            for w in self.sequence[v]:
                # if w not in order and w not in queue:
                if w not in order
                    order.append(w) # 没被遍历就直接将两边加入order
                    queue.append(w)
        return order
 
 
def main():
        nodes = [i+1 for i in xrange(8)]
        sides = [(1, 2),
                 (1, 3),
                 (2, 4),
                 (2, 5),
                 (4, 8),
                 (5, 8),
                 (3, 6),
                 (3, 7),
                 (6, 7)]
 
        G = Graph(nodes, sides)
        print G.dfs(1)
        print G.bfs(1)
 
 
if __name__ == '__main__':
    main()

# 分析 a b c d e f g d 此时从最近重复的前一个字符d的后一位开始记，即e标记为start。此时继续取下一个数， 例如a，它的前一个字符下标为d[s[i]]=0，若d[s[i]]<start，则不需要更新start,否则更新start。新的无重复子串变为e f g d a
class Solution:
    """
    @param: s: a string
    @return: an integer
    """
    def lengthOfLongestSubstring(self, s):
        # write your code here
        res = 0
        if s is None or len(s) == 0:
            return res
        d = {} # 存储某个元素最后一次出现的下标
        tmp = 0 # 存储每次循环中最长的子串长度
        start = 0  # 记录最近重复字符所在的位置+1
        for i in range(len(s)): # 下标
            # 判断当前字符是否在字典中和当前字符的下标是否大于等于最近重复字符的所在位置
            if s[i] in d and d[s[i]] >= start: # 这里的d[s[i]]为前一个重复的下标
                start = d[s[i]] + 1
            tmp = i - start + 1
            d[s[i]] = i
            res = max(res, tmp)
        return res

class Solution(object):
    def longestPalindrome(self, s):
        str_length = len(s)
        max_length = 0   # 记录最大字符串长度,不是对称长度
        start = 0  # 记录位置
        for i in range(str_length): # 当前下标位置
            # 对称位置在对称轴间隙，偶数
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                # 记录当前开始位置
                start = i - max_length - 1
                max_length += 2
                continue
            # 对称位置在对称字符，奇数
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                start = i - max_length
                max_length += 1
        # 返回最长回文子串
        return s[start: start + max_length]


if __name__ == '__main__':
    s = "babad"
    # s = "cbbd"
    sl = Solution()
    print(sl.longestPalindrome(s))

#KMP
    def kmp_match(self, s, p):  
        m = len(s)
        n = len(p)  
        cur = 0  # 起始指针cur，累积移动数  
        table = self.partial_table(p)  
        while cur <= m-n: # 长度不够就终止  
            for i in range(n):  # 一次p从头开始匹配的长度 
                if s[i+cur] != p[i]:  
                    # 移动位数 = 已匹配的字符数 - 对应的部分匹配值
                    # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位  
                    cur += max(i - table[i-1], 1) 
                    break  
            else: # 执行了break就不会执行这句，相当于for循环里所有都满足 s[i+cur] == p[i]
                return cur # 返回匹配开始的位置
        return -1  # 匹配失败

    #部分匹配表  
    def partial_table(self, p):  
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''  
        prefix = set()  
        table = [0]  
        for i in range(1, len(p)):  # 从1开始进行前后缀比较  
            prefix.add(p[:i])  # 前缀每次累加就行
            postfix = set()
            for j in range(1, i+1):  # i+1 因为i需要包括
                postfix.add(p[j:i+1]) 
            # print(prefix, postfix)
            # print(prefix&postfix, len(prefix&postfix))
            # table.append(len((sorted((prefix&postfix),key = len)or {''}).pop()))
            if prefix&postfix:
                table.append(max(map(len,prefix&postfix)))
            else:
                table.append(0)
        return table

string = 'abc123456ab2s'r = ''.join(x for i, x in enumerate(string) if string.index(x) == i)

#!/usr/bin/python
# -*- coding: UTF-8 -*-
 
import string
s = raw_input('请输入一个字符串:\n')
letters = 0
space = 0
digit = 0
others = 0
for c in s:
    if c.isalpha():
        letters += 1
    elif c.isspace():
        space += 1
    elif c.isdigit():
        digit += 1
    else:
        others += 1
print 'char = %d,space = %d,digit = %d,others = %d' % (letters,space,digit,others)

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        left = 0
        right = len(A) - 1      
        result = [-1, -1]
        while left <= right:
            mid = (left + right) / 2           
            if A[mid] > target:
                right = mid - 1
            elif A[mid] < target:
                left = mid + 1
            else: # 找到时
                result[0] = mid
                result[1] = mid
                
                i = mid - 1 # 向前找
                while i >= 0 and A[i] == target:
                    result[0] = i
                    i -= 1
                
                i = mid + 1 # 向后找
                while i < len(A) and A[i] == target:
                    result[1] = i
                    i += 1
                break
        return result

'''
用容量为K的最大堆来存储最小的K个数。最大堆的堆顶元素就是最小K个数中的最大的一个。每次扫描一个数据X，如果X比堆顶元素Y大，则不需要改变原来的堆。如果X比堆顶元素小，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最大堆的结构，需要调整堆来维持堆的性质。用优先队列思想也一样，只不过k大小的队列每次移动的元素量较大，堆会好一些。
'''
# 使用了heapq的内置数据结构，用了一个trick 因为默认是创建小顶堆，所以在添加元素的时候加个 负号就变成大顶堆了。


import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if k > len(tinput) or k == 0: return []
        heap = []
        for num in tinput:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heapreplace(heap, -num)
        return sorted(list(map(lambda x: x*-1, heap)))

'''
利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
'''
def qselect(A,k):
    if len(A)<k:return A
    pivot = A[-1]
    right = [pivot] + [x for x in A[:-1] if x>=pivot]
    rlen = len(right)
    if rlen==k:
        return right
    if rlen>k:
        return qselect(right, k)
    else:
        left = [x for x in A[:-1] if x<pivot]
        return qselect(left, k-rlen) + right
 
for i in range(1, 10):
    print qselect([11,8,4,1,5,2,7,9], i)

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0 or x==1:
            return x
        i=0
        j=x
        mid=0
        while True:
            mid=(i+j)/2
            if mid>x/mid:
                j=mid
            else:
                if (mid+1)>x/(mid+1):
                    return mid
                i=mid

import random
def Max(firstNum,secondNum):
	if firstNum>=secondNum:
		return firstNum
	else:
		return secondNum
 
def Count(array):
	gapArray=[]
	length=len(array)
	#遍历一遍记录相邻两个之间的gap
	for i in xrange(length-1):
		gap=array[i]-array[i+1]
		gapArray.append(gap)
	#转化为子集合最大和问题
	max=-((1<<32)-1)
	sum=0
	for i in xrange(len(gapArray)):
		sum+=gapArray[i]
		max=Max(max,sum)
		if sum<0:
			sum=0
	return max
 
array=[]
for i in xrange(20):
	array.append(random.randint(0,50))
print array
print "max gap:"+str(Count(array))

#采用归并排序算法
#拆解到最后，实际变成两个数组进行排序
def MergeSort(nums):
    #请牢记传入的参数是多维数组
    #此处是递归出口
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    
    #记住此处得到的也是多维数组
    Left = MergeSort(nums[:mid])
    Right = MergeSort(nums[mid:])

    #print(Left[0], Right[0])
    #要传入的参数是数组中第一个索引处的值
    return Sort_list(Left[0], Right[0])

def Sort_list(Left, Right):
    #存储排序后的值
    res = []
    a = 0
    b = 0

    while a < len(Left) and b < len(Right):
 
        if Left[a] < Right[b]:
            res.append(Left[a])
            a += 1
        else:
            res.append(Right[b])
            b += 1
    res = res + Left[a:] + Right[b:]
    # 转为二维数组
    res = [res]
    return res

class Solution:
    def intersect(self, nums1, nums2):
        nums3 = []
        nums1.sort()
        nums2.sort()
        m = len(nums1)
        n = len(nums2)
        i = 0
        j = 0
        while i<m and j<n:
            if nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                i += 1
        return nums3

python集合支持一系列标准操作，包括并集、交集、差集和对称差集，例如：  

a = t | s          # t 和 s的并集  
  
b = t & s          # t 和 s的交集  
  
c = t – s          # 求差集（项在t中，但不在s中）

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next_ = None

def deleteNode(self,pHead,Node):
        if Node == None or pHead == None:
            return
        if Node.next != None: # else情况1：只有一个Node节点；情况2：Node节点在尾巴
            Node.val = Node.next.val
            Node.next = Node.next.next
        elif Node == pHead:# 如果链表只有一个节点，那么就把头节点删掉就好了
            pHead.val = None
        else:
            pNode = pHead  # 把Node节点删除，然后接上一个None
            while pNode.next != Node:
                pNode = pNode.next
            pNode.next = None
        return pHead

#  ============非递归版本===============
def Merge(self, pHead1, pHead2):
    if not pHead1:
        return pHead2
    if not pHead2:
        return  pHead1
    mainHead = pHead1 if pHead1.val <= pHead2.val else pHead2 # 主链
    secHead = pHead2 if mainHead == pHead1 else pHead1 # 副链
    mergeHead = mainHead
    mainNext = mainHead.next # 主链第二个指针
    while mainNext and secHead: 
        if secHead.val <= mainNext.val: # 副链节点插入到两个指针之间
            mainHead.next = secHead # 第一个指针连接到副链头指针
            secHead = secHead.next # 副链头指针后移
            mainHead.next.next = mainNext # 副链头指针连接到第二个指针
            mainHead = mainHead.next # 第一个指针后移（变成原副链的头指针），插入操作第二个指针不需要后移
        else:
            mainHead = mainNext
            mainNext = mainNext.next
    if not mainNext: # 副链元素都比第二个指针要大，不能插入，要拼接
        mainHead.next = secHead
    return mergeHead
# ==================递归版本=================
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 is None: # 处理末尾状态，pHead1为空，要拼接的就是pHead2了
            return pHead2
        if pHead2 is None:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return pHead1 # 返回整段拼接后的链表
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

'''
稍微多说一句，其实这段代码也就5行，2行是中序遍历的代码；3行是更改节点指向的代码，为if、else行。if语句段只有在中序遍历到第一个节点时调用，自此之后listHead不变，listTail跟随算法的进度。对比中序遍历可以看出来，实际上只是中序遍历中的第八行代码被上述的if-else语句替代了，仅此而已。
'''
class TreeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x

class Solution:
    def __init__(self):
        self.listHead = None
        self.listTail = None
    def Convert(self, pRootOfTree):
        if pRootOfTree==None:
            return
        self.Convert(pRootOfTree.left)
        if self.listHead==None:  # if/else替换中序遍历存储值
            self.listHead = pRootOfTree # if这一段只有中序遍历的第一个节点出现，即最左子树
            self.listTail = pRootOfTree # 此时，链表头尾指针都指向中序第一个节点
        else:
            self.listTail.right = pRootOfTree # 尾指针与中序下一个节点互连，有right属性是因为上一步self.listTail和self.listHead已经指向pRootOfTree了
            pRootOfTree.left = self.listTail
            self.listTail = pRootOfTree # 尾指针指向中序下一个节点
        self.Convert(pRootOfTree.right)
        return self.listHead

'''
翻转单链表
思路很简单：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。
'''
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        pre = None # 前指针
        cur = pHead # 当前指针
        while cur!=None:
            tmp = cur.next # 记录下一个指针，为下一步当前指针后移准备
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

# 翻转部分链表
class Solution:
    def reverseBetween(self, head, m, n):
        # 计算需要逆至的节点数
        reverse_length = n - m + 1
        pre_head = None # 初始化要记录的前驱节点
        result = head   # 最终转换后要返回的链表头结点

        # 将head向后移动m-1个位置
        while head and m > 1:
            pre_head = head
            head = head.next
            m -= 1

        # 记录翻转后的链表尾部，翻转后的尾巴即为当前head
        modify_list_tail = head
        pre = None # 前指针

        # 逆置n - m + 1个节点
        while head and reverse_length: #和翻转单链表一样，翻转后和第一、第三段是断开的
            tmp = head.next 
            head.next = pre
            pre = head
            head = tmp
            reverse_length -= 1

        # 此时，尾巴为空， modify_list_tail指向最后一个非空元素
        # 连接逆置后的链表尾与第三段的头结点结合，此时head已经指向第三段正序的头结点
        modify_list_tail.next = head

        # 如果pre_head不为空，说明不是从第一个节点开始逆至，即m>1
        if pre_head is not None:
            # pre_head指向第一段最后一个元素，连接逆序后的头结点
            pre_head.next = pre #pre指向逆序后头结点，head为第三段的头结点
        else:
            # 此时m=1，则逆置后的头结点就是链表的头结点，即翻转整个单链表
            result = pre
        return result

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""


class Solution:
    """
    @param: head: The first node of linked list.
    @return: The head of linked list.
    """
    def insertionSortList(self, head):
        # write your code here
        if head is None:
            return None
        if head.next is None:
            return head
        l=ListNode(-1)
        while head:
            node=l # 每次从头开始
            fol=head.next # 保持下一个，防止断开
            while node.next and node.next.val < head.val: # 插入到node和node.next之间
                node = node.next
            head.next = node.next  # 先连接后面head-<node.next
            node.next = head     # 再连接前面
            head = fol
        return l.next

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
class Solution:
    # 归并法
    def sortList(self, head):
        # write your code here
        if head is None or head.next is None:
            return head
        pre = head
        slow = head               # 使用快慢指针来确定中点
        fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        left = head  
        right = pre.next  # 第二段头结点
        pre.next = None           # 从中间打断链表
        left = self.sortList(left)  
        right = self.sortList(right)  
        return self.merge(left,right)
        
    def merge(self, left, right): #合并两个有序链表
        pre = ListNode(-1) # 新链表
        first = pre # 新链表头结点
        while left and right:
            if left.val < right.val:
                pre.next = left
                pre = left
                left = left.next
            else:
                pre.next = right
                pre = right
                right = right.next
        if left:
            pre.next = left
        else:
            pre.next = right             
        return first.next

class Solution(object):
    def swapPairs(self, head):
        dummy = ListNode(-1)
        dummy.next = head # 假结点连接原链表
        temp = dummy # 头结点
        while temp.next and temp.next.next:
            node1 = temp.next  # node1是B
            node2 = temp.next.next  # node2是C
            temp.next = node2  # A指向C
            node1.next = node2.next  # B指向D
            node2.next = node1  # C指向B
            temp = temp.next.next  # 跳过两个
        return dummy.next

# 思路二
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        p1, p2 = pHead1, pHead2
        while p1 != p2:
            p1 = pHead2 if not p1 else p1.next
            p2 = pHead1 if not p2 else p2.next
        return p1

class Solution(object):
    def partition(self, head, x):
        dummy = ListNode(-1)
        dummy.next = head
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)

        # small_prev和large_prev往后遍历增加，small_dummy和large_dummy则负责最后作为返回头结点
        small_prev = small_dummy
        large_prev = large_dummy
        while dummy.next:  # head第一个节点
            curr = dummy.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            dummy = dummy.next

        large_prev.next = None  # 最后指针置为none
        small_prev.next = large_dummy.next  # large_dummy对应的是大链表的第一个数
        return small_dummy.next  # 返回的是small_dummy

class Solution:
    def reorderList(self, head):
        if not head:
            return
        # split {1,2,3,4,5} to {1,2,3}{4,5}
        fast = slow = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        head1 = head
        head2 = slow.next
        slow.next = None
        # reverse the second {4,5} to {5,4}
        cur, pre = head2, None
        while cur:
            tmp = cur.next # 标记下一个
            cur.next = pre
            pre = cur
            cur = tmp
        # merge
        cur1, cur2 = head1, pre
        while cur2:
            nex1, nex2 = cur1.next, cur2.next
            cur1.next = cur2
            cur2.next = nex1
            cur1, cur2 = nex1, nex2