剑指offer

剑指offer Python实现

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array:
            return False
        row = len(array)
        col = len(array[0])
        i = 0
        j = col-1
        while i < row and j >= 0:
            if array[i][j] > target:
                j -= 1
            elif array[i][j] < target:
                i += 1
            else:
                return True
        return False

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        """
        s = s.replace(" ", "%20")
        return s
        """
        # 先统计空格的数量
        num_space = 0
        for i in s:
            if i == " ":
                num_space += 1
        l = len(s)
        replace_s = [None for _ in range(l + 2 * num_space)]
        i = l-1
        j = len(replace_s)-1
        while i >= 0:
            if s[i] != " ":
                replace_s[j] = s[i]
                j -= 1
            else:
                replace_s[j] = ‘0‘
                j -= 1
                replace_s[j] = ‘2‘
                j -= 1
                replace_s[j] = ‘%‘
                j -= 1
            i -= 1
        return "".join(replace_s)

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        """
        # write code here
        # 采用栈存储数据
        res = []
        while listNode:
            res.insert(0, listNode.val)
            listNode = listNode.next
        return res
        """
        ‘‘‘
        # 直接采用递归的方法
        res = []
        def add_list(listNode):
            if not listNode:
                return
            add_list(listNode.next)
            res.append(listNode.val)
        add_list(listNode)
        return res
        ‘‘‘
        # 直接采用递归的方法
        def add_list(listNode, res):
            if not listNode:
                return res
            res = add_list(listNode.next, res)
            res.append(listNode.val)
            return res
        return add_list(listNode, [])

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)>0:
            # 根节点必定在pre的第一个数
            root = TreeNode(pre[0])
            # 在中序遍历数列中找到树根节点位置
            root_id = tin.index(pre[0])
            # 由于先序遍历的第一个是中序遍历的最后一个（子树中）， 所以pre从1开始，tin从root_id-1结束
            root.left = self.reConstructBinaryTree(pre[1:1+root_id], tin[:root_id])
            root.right = self.reConstructBinaryTree(pre[1+root_id:], tin[root_id+1:])
            return root

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    def push(self, node):
        # write code here
        self.s1.append(node)
    def pop(self):
        # return xx
        if self.s2:
            return self.s2.pop()
        else:
            # 将s1中的数据依次取出放入s2中
            while self.s1:
                self.s2.append(self.s1.pop())
            return self.s2.pop()

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        def getMin(low,high,arr):
            if low > high:
                return 0
            if low == high:
                return arr[low]
            mid = (low+high)//2
            if arr[mid-1] > arr[mid]:
                return arr[mid]
            elif arr[mid] > arr[mid+1]:
                return arr[mid+1]
            elif arr[mid] < arr[high]:
                return getMin(low, mid-1, arr)
            elif arr[mid] > arr[low]:
                return getMin(mid+1, high, arr)
            else:
                return min(getMin(mid+1, high, arr), getMin(low, mid-1, arr))
        return getMin(0, len(rotateArray)-1, rotateArray)

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
class Solution:
    def Fibonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        # write code here
        fibNMinusOne = 0
        fibNMinusTwo = 1
        res = 0
        for i in range(2, n+1):
            res = fibNMinusOne + fibNMinusTwo
            fibNMinusOne = fibNMinusTwo
            fibNMinusTwo = res
        return res

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 0:
            return 0
        res = [1, 2]
        if number == 1:
            return res[0]
        if number == 2:
            return res[1]
        minus1 = 1
        minus2 = 2
        for i in range(3, number+1):
            res = minus1 + minus2
            minus1 = minus2
            minus2 = res
        return res

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        minus = 2
        for i in range(3, number+1):
            res = 2*minus
            minus = res
        return res

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        minus1 = 1
        minus2 = 2
        res = 0
        for i in range(3, number+1):
            res = minus1 + minus2
            minus1 = minus2
            minus2 = res
        return res

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class Solution:
    def NumberOf1(self, n):
        # write code here
        ‘‘‘
        count = 0
        # 由于这里有32,所以不会陷入死循环的状态
        for i in range(32):
            count += (1 & n>>i)
        return count
        #return sum([(n>>i & 1) for i in range(0,32)])
        ‘‘‘
        count = 0
        # 由于python是动态语言，所以数的大小会根据需要自动改变，这里需要控制为32位
        while (n & 0xffffffff):
            count += 1
            n = (n-1) & n
        return count

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class Solution:
    def Power(self, base, exponent):
        # write code here
        # return base**exponent
        if base == 0 and exponent < 0:
            # 无意义
            return 0
        res = 1
        i = 1
        abs_exponent = abs(exponent)
        while i <= abs_exponent:
            res *= base
            i += 1
        if exponent <= 0:
            return 1/res
        else:
            return res

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
class Solution:
    def reOrderArray(self, array):
        # write code here
        ‘‘‘
        # 采用冒泡算法排序
        for i in range(len(array)-1):
            for j in range(0, len(array)-i-1):
                if array[j] % 2 == 0 and array[j+1] % 2 == 1:
                    array[j], array[j+1] = array[j+1], array[j]
        return array
        ‘‘‘
        # 采用额外数组法
        res = []
        l = len(array)
        for i in range(len(array)):
            if array[l-i-1] % 2 != 0:
                res.insert(0, array[l-i-1])
            if array[i] % 2 == 0:
                res.append(array[i])
        return res

输入一个链表，输出该链表中倒数第k个结点。
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head:
            return
        # python中的数据是没有头结点的
        l1 = head
        l2 = l1
        i = 0
        while i < k:
            l2 = l2.next
            i += 1
            if not l2 and i < k:
                return 
        while l2:
            l1 = l1.next
            l2 = l2.next
        return l1

输入一个链表，反转链表后，输出新链表的表头。
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 就地转换法
        if not pHead:
            return 
        pre = pHead
        cur = pHead.next
        pHead.next = None
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        head = pHead1
        pre = pHead1
        next_p = pHead2.next
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                pre = pHead1
                pHead1 = pHead1.next
            else:
                pre.next = pHead2
                pHead2.next = pHead1
                pre = pHead1
                pHead1 = pHead1.next
                pHead2 = next_p
                if pHead2:
                    next_p = pHead2.next
          # 判断是哪个指针为None
        if not pHead1:
            pre.next = pHead2
            return head
        if not pHead2:
            return head

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot2 or not pRoot1:
            return False
        return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
    def is_subtree(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.is_subtree(A.left, B.left) and self.is_subtree(A.right, B.right)

操作给定的二叉树，将其变换为源二叉树的镜像。
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root:
            tmp = root.left
            root.left = root.right
            root.right = tmp
            self.Mirror(root.left)
            self.Mirror(root.right)

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        if not matrix:
            return matrix
        res = []
        startX = 0
        while len(matrix) > 2*startX and len(matrix[0]) > 2*startX:
            res.extend(self.print_matrix_incircle(matrix, startX))
            startX += 1
        return res
    def print_matrix_incircle(self, matrix, start):
        res = []
        endX = len(matrix[0]) - 1 -start
        endY = len(matrix) - 1 - start
        # 从左往右打印,没有约束条件
        for i in range(start, endX+1):
            print(matrix[start][i])
            res.append(matrix[start][i])
        # 从上往下打印，至少有两行
        if endY > start:
            for i in range(start+1, endY+1):
                print(matrix[i][endX])
                res.append(matrix[i][endX])
        # 从右往左打印，至少有两行两列
        if start < endX and endY > start:
            for i in range(endX-1, start-1, -1):
                print(matrix[endY][i])
                res.append(matrix[endY][i])
        # 从下往上打印，至少有三行两列
        if start < endY-1 and start<endX:
            for i in range(endY-1, start, -1):
                print(matrix[i][start])
                res.append(matrix[i][start])
        return res

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.stack2:
            self.stack2.append(node)
        elif node <= self.stack2[-1]:
            self.stack2.append(node)
    def pop(self):
        # write code here
        if self.stack[-1] == self.stack2[-1]:
            self.stack2.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.stack2[-1]

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if len(pushV) != len(popV):
            return False
        i = 0
        j = 0
        stack = []
        while i < len(pushV):
            stack.append(pushV[i])
            i += 1
            while stack and stack[-1] == popV[j]:
                stack.pop()
                j += 1
        #return not stack and j == len(popV)
        return not stack

从上往下打印出二叉树的每个节点，同层节点从左至右打印。
from collections import deque
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        res = []
        queue = deque()
        queue.append(root)
        while queue:
            root = queue.popleft()
            res.append(root.val)
            if root.left:
                queue.append(root.left)
            if root.right:
                queue.append(root.right)
        return res

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence) == 1:
            return True
        root = sequence[-1]
        i = 0
        while i < len(sequence)-1:
            if sequence[i] > root:
                break
            i += 1
        j = i
        # 判断后面的数是否都大于root值
        while j < len(sequence)-1:
            if sequence[j] < root:
                return False
            j += 1
        if i == 0:
            return self.VerifySquenceOfBST(sequence[i:len(sequence)-1])
        elif i == len(sequence) - 1:
            return self.VerifySquenceOfBST(sequence[:i])
        else:
            return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:len(sequence)-1])

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        res = []
        def equal_path(root, expectNumber, path, res):
            if not root:
                return
            path.append(root.val)
            if not root.left or not root.right:
                if sum(path) == expectNumber:
                    res.append([i for i in path])
            equal_path(root.left, expectNumber, path, res)
            equal_path(root.right, expectNumber, path, res)
            path.pop()
        equal_path(root, expectNumber, [], res)
        return res

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        ‘‘‘
        # 空间换时间的方法
        if not pHead:
            return pHead
        source_copy = {}
        copy_head = RandomListNode(pHead.label)
        source_copy[id(pHead)] = copy_head
        copy_normal_p = copy_head
        normal_p = pHead.next
        # 对节点进行复制
        while normal_p:
            node = RandomListNode(normal_p.label)
            source_copy[id(normal_p)] = node
            copy_normal_p.next = node
            copy_normal_p = node
            normal_p = normal_p.next
        # 对特殊指针进行复制
        special_p = pHead
        copy_special_p = copy_head
        while special_p:
            if special_p.random:
                copy_special_p.random = source_copy[id(special_p.random)]
            special_p = special_p.next
            copy_special_p = copy_special_p.next
        return copy_head
        ‘‘‘
        if not pHead:
            return pHead
        self.insert(pHead)
        self.dup_random(pHead)
        return self.split(pHead)
    # 嵌入-复制-分离法
    # 将复制主干内容嵌入原链表
    def insert(self, pHead):
        pre = pHead
        while pre:
            back = pre.next
            node = RandomListNode(pre.label)
            pre.next = node
            node.next = back
            pre = back
    # 复制随机指针
    def dup_random(self, pHead):
        pre = pHead
        dup = pHead.next
        while dup.next:
            if pre.random:
                dup.random = pre.random.next
            if dup.next:
                dup = dup.next.next
                pre = pre.next.next
     # 分离链表
    def split(self, pHead):
        ‘‘‘
        pNode=pHead
        #pClonedHead=None
        #pCloned=None
        if pHead:
            pClonedHead=pCloned=pNode.next
            pNode.next=pCloned.next
            pNode=pCloned.next
        while pNode:
            pCloned.next=pNode.next
            pCloned=pCloned.next
            pNode.next=pCloned.next
            pNode=pNode.next
        return pClonedHead
    ‘‘‘
        # 在分开链表的时候，必须把最后一个连接也要去掉，不去掉所以出了很大的问题
        pNode = pHead
        pCloneHead= pClone = pNode.next
        while pClone.next:
            pNode.next = pClone.next
            pNode = pClone.next
            pClone.next = pNode.next
            pClone = pNode.next
        # 切断最后一个连接
        pNode.next = None
        return pCloneHead

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
class Solution:
    def __init__(self):
        self.pHead = None
        self.pEnd = None
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return 
        self.Convert(pRootOfTree.left)
        pRootOfTree.left = self.pEnd
        if not self.pHead:
            self.pHead = pRootOfTree
        else:
            self.pEnd.right = pRootOfTree
        self.pEnd = pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.pHead

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        ss = list(ss)
        res = []
        self.perm(ss, res, 0)
        uniq = list(set(res))
        return sorted(uniq)
    def perm(self, ss, res, start):
        if start == len(ss)-1:
            res.append("".join(ss))
        else:
            i = start
            while i < len(ss):
                ss[i], ss[start] = ss[start], ss[i]
                self.perm(ss, res, start+1)
                ss[i], ss[start] = ss[start], ss[i]
                i += 1

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        ‘‘‘
        # 方法一：采用空间换时间
        count_dic = {}
        for i in range(len(numbers)):
            count_dic[numbers[i]] = count_dic.get(numbers[i], 0) + 1
            if count_dic[numbers[i]] > len(numbers) >> 1:
                return numbers[i]
        return 0
        ‘‘‘
        # 方法二：采用partition方法，类快排的方法，找到中位数
        begin = 0
        end = len(numbers) - 1
        return self.get_more_than_half(numbers, begin, end)
    def get_more_than_half(self, numbers, begin, end):
        index = self.partition(numbers, begin, end)
        while index != len(numbers) >> 1:
            if index < len(numbers) >> 1:
                index = self.partition(numbers,index+1, end)
            elif index > len(numbers) >> 1:
                index = self.partition(numbers, begin, index-1)
        count = 0
        for i in range(len(numbers)):
            if numbers[i] == numbers[index]:
                count += 1
        return numbers[index] if count > len(numbers) >> 1 else 0
    def partition(self, numbers, begin, end):
        index = begin
        key = numbers[index]
        while begin < end:
            while begin < end and numbers[end] >= key:
                end -= 1
            numbers[begin] = numbers[end]
            while begin < end and numbers[begin] <= key:
                begin += 1
            numbers[end] = numbers[begin]
        numbers[begin] = key
        return begin

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        # 采用partition的方法
        if k == 0 or len(tinput) < k:
        #if not tinput or k == 0 or len(tinput) < k:
            return []
        start = 0
        end = len(tinput) -1
        index = self.partition(tinput, start, end)
        while index != k-1:
            if index > k-1:
                index = self.partition(tinput, start, index-1)
            elif index < k-1:
                index = self.partition(tinput, index+1, end)
        res = sorted(tinput[:k])
        return res
    def partition(self, tinput, start, end):
        key = tinput[start]
        while start < end:
            if start < end and tinput[end] >= key:
                end -= 1
            tinput[start] = tinput[end]
            if start < end and tinput[start] <= key:
                start += 1
            tinput[end] = tinput[start]
        tinput[start] = key
        return start

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return 0
        nEnd = array[0]
        nAll = array[0]
        for i in range(1, len(array)):
            if nEnd + array[i] < array[i]:
                nEnd = array[i]
            else:
                nEnd += array[i]
            nAll = max(nEnd, nAll)
        return nAll

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        res = 0
        while True:
            # 首先判断n的位数
            n_copy = n
            count = 0
            while n_copy:
                n_copy //= 10
                count += 1
            middle_num = 0
            for i in range(count - 1):
                middle_num += n // (10 ** i) % 10 * 10**i
            res += self.get_count_1(n, count, middle_num)
            n = middle_num
            if n < 2:
                break
        return res
    def get_count_1(self, n, count, middle_num):
        if n > 0 and n < 10:
            return 1
        if n < 1:
            return 0
        num = 0
        copy_n = n
        count_copy = count
        while count_copy > 1:
            copy_n //= 10
            count_copy -= 1
        if copy_n > 1:
            num += 10 ** (count - 1)
        else:
            num += middle_num+1
        num += copy_n * (count - 1) * 10 ** (count - 2)
        return num

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        return "".join(sorted([str(i) for i in numbers], cmp = lambda x, y: int(x+y) - int(y+x)))

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return 0
        ugly_number = [1]
        if index == 1:
            return 1
        m2 = 0
        m3 = 0
        m5 = 0
        i = 1
        while i < index:
            num = min(ugly_number[m2]*2, ugly_number[m3]*3, ugly_number[m5]*5)
            ugly_number.append(num)
            # 这里的if不能用elif，有可能该数为2或者3或者5的最小公倍数
            if ugly_number[m2]*2 <= num:
                m2 += 1
            if ugly_number[m3]*3 <= num:
                m3 += 1
            if ugly_number[m5]*5 <= num:
                m5 += 1
            i += 1
        return ugly_number[-1]

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        # 建立hash表，第一次遍历s添加次数到hash表，第二次遍历s找到第一个只出现一次的字符
        res = {}
        for i in s:
            res[i] = res.get(i, 0) + 1
        for i in s:
            if res[i] == 1:
                return s.index(i)
        return -1

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
class Solution:
    def InversePairs(self, data):
        # write code here
        if not data:
            return 0
        data_copy = [i for i in data]
        count = self.InversePairsCore(data, data_copy, 0, len(data)-1)
        return count% 1000000007
    def InversePairsCore(self, data, data_copy, start, end):
        if start == end:
            data_copy[start] = data[start]
            return 0
        length = (end-start)//2
        left = self.InversePairsCore(data_copy, data, start, start+length)
        right = self.InversePairsCore(data_copy, data, start+length+1, end)
        i = start+length
        j = end
        indexCopy = end
        count = 0
        while i>=start and j >=start+length+1:
            if data[i]>data[j]:
                data_copy[indexCopy] = data[i]
                indexCopy -= 1
                i -= 1
                count += j-start-length
            else:
                data_copy[indexCopy] = data[j]
                indexCopy -= 1
                j -= 1
        while i >= start:
            data_copy[indexCopy] = data[i]
            i -= 1
            indexCopy -= 1
        while j >= start+length+1:
            data_copy[indexCopy] = data[j]
            j -= 1
            indexCopy -= 1
        return left + right + count

输入两个链表，找出它们的第一个公共结点。
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        l1 = 0
        l2 = 0
        p1 = pHead1
        p2 = pHead2
        while p1:
            p1 = p1.next
            l1 += 1
        while p2:
            p2 = p2.next
            l2 += 1
        if l1 > l2:
            i = 0
            while i < abs(l1-l2):
                pHead1= pHead1.next
                i += 1
            while pHead1 and pHead2:
                if pHead1 == pHead2:
                    return pHead1
                else:
                    pHead1 = pHead1.next
                    pHead2 = pHead2.next
        else:
            i = 0
            while i < abs(l1-l2):
                pHead2 = pHead2.next
                i += 1
            while pHead1 and pHead2:
                if pHead1 == pHead2:
                    return pHead2
                else:
                    pHead1 = pHead1.next
                    pHead2 = pHead2.next
        return None

统计一个数字在排序数组中出现的次数。
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:
            return 0
        start = 0
        # end指针为数组下标
        end = len(data)-1
        flag = 0
        while start <= end:
            mid = (start+end) >> 1
            if data[mid] > k:
                end = mid-1
            elif data[mid] < k:
                start = mid+1
            else:
                flag = 1
                break
        if flag == 0:
            return 0
        count = 0
        i = mid
        while i >= 0 and data[i] == k:
            count += 1
            i -= 1
        j = mid+1
        while j < len(data) and data[j] == k:
            count += 1
            j += 1
        return count

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        return max(1 + self.TreeDepth(pRoot.left), 1 + self.TreeDepth(pRoot.right))

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        ‘‘‘
        if not pRoot:
            return True
        return self.IsBanlanced(pRoot) and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def IsBanlanced(self, pRoot):
        if abs(self.height(pRoot.left) - self.height(pRoot.right)) <= 1:
            return True
        else:
            return False
    def height(self, pRoot):
        if not pRoot:
            return 0
        return max(1+self.height(pRoot.left), 1+self.height(pRoot.right))
        ‘‘‘
        # 通过后续遍历自下往上进行遍历
        return self.dfs(pRoot) != -1
    def dfs(self, pRoot):
        if not pRoot:
            return 0
        left = self.dfs(pRoot.left)
        if left == -1:
            return -1
        right = self.dfs(pRoot.right)
        if right == -1:
            return -1
        if abs(left-right) > 1:
            return -1
        return max(left, right) + 1

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        c = 0
        #for i in array:
         # c ^= i
        c = reduce(lambda x, y: x^y, array)
        k = 0
        d = c
        while d & 1 != 1:
            k += 1
            d = d >> 1
        s = []
        for i in array:
            if i >> k & 1 == 1:
                s.append(i)
        e = 0
        e = reduce(lambda x, y: x^y, s)
        return [c^e, e]