《剑指offer》 刷题记录(Python)

系统 262 0

本博客同时发布于个人主页:www.doctorsrn.cn

《剑指offer》 刷题记录

最近使用Python把《剑指offer》刷了一遍,自己能第一时间有想法的题目就直接写,没有思路的题目就看懂书上的思路和参考其他开源的实现后再自己写一遍。主要以牛客网《剑指offer》作为在线评测网站,有些题目牛客网没有的再找其他网站进行在线评测,主要使用的其他网站有:

  • AcWing
  • LintCode

刷题过程主要参考的开源实现有:

  • https://github.com/Lazy-Pig/CodingInterviewChinese2
  • https://github.com/apachecn/Interview/tree/master/docs/Algorithm/剑指offer/Python

本博客对应的代码仓库在此。

今年企业缩招,找工作的行情不容乐观,秋招路漫漫啊。

3.数组中重复数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

            
              
                ## 方法一:排序,然后查找
              
              
                ## 时间复杂度:O(nlog n)  空间复杂度:*
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
              
              
                # 函数返回True/False
              
              
                def
              
              
                duplicate
              
              
                (
              
              self
              
                ,
              
               numbers
              
                ,
              
               duplication
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               numbers 
              
                or
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i
              
                <
              
              
                0
              
              
                or
              
               i 
              
                >
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                -
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        numbers_sorted 
              
                =
              
               self
              
                .
              
              quickSort
              
                (
              
              numbers
              
                )
              
              
                for
              
               i
              
                ,
              
              j 
              
                in
              
              
                zip
              
              
                (
              
              numbers_sorted
              
                [
              
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                ,
              
              numbers_sorted
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                :
              
              
                if
              
               i 
              
                ==
              
               j
              
                :
              
              
                duplication
              
                [
              
              
                0
              
              
                ]
              
              
                =
              
               i
                
              
                return
              
              
                True
              
              
                return
              
              
                False
              
              
                def
              
              
                quickSort
              
              
                (
              
              self
              
                ,
              
               arr
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              arr
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
               arr
         
        length 
              
                =
              
              
                len
              
              
                (
              
              arr
              
                )
              
              
        pivot 
              
                =
              
               arr
              
                [
              
              length 
              
                //
              
              
                2
              
              
                ]
              
              
         
        left 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                >
              
               pivot
              
                ]
              
              
        right 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                <
              
               pivot
              
                ]
              
              
        mid 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                ==
              
               pivot
              
                ]
              
              
                # 升序排列可以通过,降序排列无法通过全部测试样例
              
              
                return
              
               self
              
                .
              
              quickSort
              
                (
              
              right
              
                )
              
              
                +
              
               mid 
              
                +
              
               self
              
                .
              
              quickSort
              
                (
              
              left
              
                )
              
              
                #return self.quickSort(left) + mid + self.quickSort(right)
              
            
          
            
              
                ## 方法二:引入hash表(字典)
              
              
                ## 时间复杂度:O(n)  空间复杂度:O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
              
              
                # 函数返回True/False
              
              
                def
              
              
                duplicate
              
              
                (
              
              self
              
                ,
              
               numbers
              
                ,
              
               duplication
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               numbers 
              
                or
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i 
              
                <
              
              
                0
              
              
                or
              
               i 
              
                >
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                -
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
             
        dic 
              
                =
              
              
                {
              
              
                }
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               dic
              
                .
              
              has_key
              
                (
              
              i
              
                )
              
              
                :
              
              
                duplication
              
                [
              
              
                0
              
              
                ]
              
              
                =
              
               i
                
              
                return
              
              
                True
              
              
                else
              
              
                :
              
              
                dic
              
                [
              
              i
              
                ]
              
              
                =
              
              
                1
              
              
                return
              
              
                False
              
            
          
            
              
                ## 方法三:利用数字自身下标和值的key-value特性
              
              
                ## 时间复杂度:O(n)  空间复杂度:O(1)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
              
              
                # 函数返回True/False
              
              
                def
              
              
                duplicate
              
              
                (
              
              self
              
                ,
              
               numbers
              
                ,
              
               duplication
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               numbers 
              
                or
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i 
              
                <
              
              
                0
              
              
                or
              
               i 
              
                >
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                -
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        i 
              
                =
              
              
                0
              
              
                while
              
               i 
              
                <
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                :
              
              
                if
              
               i 
              
                ==
              
               numbers
              
                [
              
              i
              
                ]
              
              
                :
              
              
                i 
              
                +=
              
              
                1
              
              
                elif
              
               numbers
              
                [
              
              i
              
                ]
              
              
                ==
              
               numbers
              
                [
              
              numbers
              
                [
              
              i
              
                ]
              
              
                ]
              
              
                :
              
              
                duplication
              
                [
              
              
                0
              
              
                ]
              
              
                =
              
               numbers
              
                [
              
              i
              
                ]
              
              
                return
              
              
                True
              
              
                else
              
              
                :
              
              
                tmp 
              
                =
              
               numbers
              
                [
              
              i
              
                ]
              
              
                numbers
              
                [
              
              i
              
                ]
              
              
                =
              
               numbers
              
                [
              
              tmp
              
                ]
              
              
                numbers
              
                [
              
              tmp
              
                ]
              
              
                =
              
               tmp
        
              
                return
              
              
                False
              
            
          

4.二维数组的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

            
              
                # 方法一:暴力遍历法
              
              
                # 时间复杂度:O(n^2)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # array 二维列表
              
              
                def
              
              
                Find
              
              
                (
              
              self
              
                ,
              
               target
              
                ,
              
               array
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                for
              
               i 
              
                in
              
               array
              
                :
              
              
                for
              
               j 
              
                in
              
               i
              
                :
              
              
                if
              
               target 
              
                ==
              
               j
              
                :
              
              
                return
              
              
                True
              
              
                return
              
              
                False
              
            
          
            
              
                # 方法二:反向剔除不满足元素法:从右上角进行查找
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # array 二维列表
              
              
                def
              
              
                Find
              
              
                (
              
              self
              
                ,
              
               target
              
                ,
              
               array
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                <
              
              
                1
              
              
                or
              
              
                len
              
              
                (
              
              array
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        
        r_l 
              
                =
              
              
                len
              
              
                (
              
              array
              
                )
              
              
        c_l 
              
                =
              
              
                len
              
              
                (
              
              array
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                # 从右上角开始搜索
              
              
        i
              
                ,
              
               j 
              
                =
              
              
                0
              
              
                ,
              
               c_l
              
                -
              
              
                1
              
              
                while
              
               target 
              
                !=
              
               array
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                :
              
              
                if
              
               target 
              
                >
              
               array
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                :
              
              
                if
              
               i 
              
                <
              
               r_l 
              
                -
              
              
                1
              
              
                :
              
              
                    i 
              
                +=
              
              
                1
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
              
                else
              
              
                :
              
              
                if
              
               j 
              
                >
              
              
                0
              
              
                :
              
              
                    j 
              
                -=
              
              
                1
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
              
                return
              
              
                True
              
            
          

5.替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

            
              
                # 方法一:遍历判断然后替换法,时间复杂度O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # s 源字符串
              
              
                def
              
              
                replaceSpace
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
              
                isinstance
              
              
                (
              
              s
              
                ,
              
              
                str
              
              
                )
              
              
                or
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                or
              
               s 
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
               s
        tmp 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               s
              
                :
              
              
                if
              
               i 
              
                !=
              
              
                ' '
              
              
                :
              
              
                tmp
              
                .
              
              append
              
                (
              
              i
              
                )
              
              
                else
              
              
                :
              
              
                tmp
              
                .
              
              append
              
                (
              
              
                "%20"
              
              
                )
              
              
        
        res 
              
                =
              
              
                ''
              
              
                .
              
              join
              
                (
              
              tmp
              
                )
              
              
                return
              
               res

            
          
            
              
                # 方法二:从后向前遍历替换法,时间复杂度O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # s 源字符串
              
              
                def
              
              
                replaceSpace
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
              
                isinstance
              
              
                (
              
              s
              
                ,
              
              
                str
              
              
                )
              
              
                or
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                or
              
               s 
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
              
                ''
              
              
        
        spaceN 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
               s
              
                :
              
              
                if
              
               i 
              
                ==
              
              
                ' '
              
              
                :
              
              
                spaceN 
              
                +=
              
              
                1
              
              
        total 
              
                =
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                +
              
              
                2
              
              
                *
              
               spaceN
        newStr 
              
                =
              
              
                [
              
              
                None
              
              
                ]
              
              
                *
              
               total
        
        indexO
              
                ,
              
               indexN 
              
                =
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                -
              
              
                1
              
              
                ,
              
               total
              
                -
              
              
                1
              
              
                while
              
               indexO 
              
                >=
              
              
                0
              
              
                :
              
              
                if
              
               s
              
                [
              
              indexO
              
                ]
              
              
                ==
              
              
                ' '
              
              
                :
              
              
                newStr
              
                [
              
              indexN
              
                ]
              
              
                =
              
              
                '0'
              
              
                newStr
              
                [
              
              indexN
              
                -
              
              
                1
              
              
                ]
              
              
                =
              
              
                '2'
              
              
                newStr
              
                [
              
              indexN
              
                -
              
              
                2
              
              
                ]
              
              
                =
              
              
                '%'
              
              
                indexN 
              
                -=
              
              
                3
              
              
                indexO 
              
                -=
              
              
                1
              
              
                else
              
              
                :
              
              
                newStr
              
                [
              
              indexN
              
                ]
              
              
                =
              
               s
              
                [
              
              indexO
              
                ]
              
              
                indexN 
              
                -=
              
              
                1
              
              
                indexO 
              
                -=
              
              
                1
              
              
                return
              
              
                ''
              
              
                .
              
              join
              
                (
              
              newStr
              
                )
              
            
          

6.从尾到头打印链表

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

            
              
                # 方法一: 使用栈
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回从尾部到头部的列表值序列,例如[1,2,3]
              
              
                def
              
              
                printListFromTailToHead
              
              
                (
              
              self
              
                ,
              
               listNode
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               listNode 
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
                if
              
               listNode
              
                .
              
              
                next
              
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
               listNode
              
                .
              
              val
        
        stack 
              
                =
              
              
                [
              
              
                ]
              
              
        nextNode 
              
                =
              
               listNode
        
              
                while
              
               nextNode
              
                .
              
              
                next
              
              
                !=
              
              
                None
              
              
                :
              
              
            stack
              
                .
              
              append
              
                (
              
              nextNode
              
                .
              
              val
              
                )
              
              
            nextNode 
              
                =
              
               nextNode
              
                .
              
              
                next
              
              
        
        stack
              
                .
              
              append
              
                (
              
              nextNode
              
                .
              
              val
              
                )
              
              
                return
              
               stack
              
                [
              
              
                :
              
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
            
          
            
              
                # 方法二:递归的方法
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回从尾部到头部的列表值序列,例如[1,2,3]
              
              
                def
              
              
                printListFromTailToHead
              
              
                (
              
              self
              
                ,
              
               listNode
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               listNode
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
                if
              
               listNode
              
                .
              
              
                next
              
              
                ==
              
              
                None
              
              
                :
              
              
            res 
              
                =
              
              
                [
              
              
                ]
              
              
            res
              
                .
              
              append
              
                (
              
              listNode
              
                .
              
              val
              
                )
              
              
                return
              
               res
        re 
              
                =
              
               self
              
                .
              
              printListFromTailToHead
              
                (
              
              listNode
              
                .
              
              
                next
              
              
                )
              
              
        re
              
                .
              
              append
              
                (
              
              listNode
              
                .
              
              val
              
                )
              
              
                return
              
               re

L
              
                =
              
              
                [
              
              
                ]
              
              
l
              
                =
              
              ListNode
              
                (
              
              
                1
              
              
                )
              
              
t 
              
                =
              
               l

              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                4
              
              
                )
              
              
                :
              
              
    t
              
                .
              
              
                next
              
              
                =
              
               ListNode
              
                (
              
              i
              
                )
              
              
    t 
              
                =
              
               t
              
                .
              
              
                next
              
              
                # while l.next != None:
              
              
                #     print(l.val)
              
              
                #     l = l.next
              
              
                # print(l.val)
              
              
s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
s
              
                .
              
              printListFromTailToHead
              
                (
              
              l
              
                )
              
            
          

7.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

            
              
                # 递归法
              
              
                # 按照前序遍历和中序遍历的特点进行递归重建
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回构造的TreeNode根节点
              
              
                def
              
              
                reConstructBinaryTree
              
              
                (
              
              self
              
                ,
              
               pre
              
                ,
              
               tin
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 有效性判断
              
              
                if
              
              
                set
              
              
                (
              
              pre
              
                )
              
              
                !=
              
              
                set
              
              
                (
              
              tin
              
                )
              
              
                :
              
              
                return
              
              
                None
              
              
                # 递归终止条件
              
              
                if
              
              
                len
              
              
                (
              
              pre
              
                )
              
              
                <
              
              
                1
              
              
                or
              
              
                len
              
              
                (
              
              tin
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              
                if
              
              
                len
              
              
                (
              
              pre
              
                )
              
              
                ==
              
              
                1
              
              
                or
              
              
                len
              
              
                (
              
              tin
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               TreeNode
              
                (
              
              pre
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
        
        root 
              
                =
              
               pre
              
                [
              
              
                0
              
              
                ]
              
              
        root_index 
              
                =
              
               tin
              
                .
              
              index
              
                (
              
              root
              
                )
              
              
        L_tin
              
                ,
              
               R_tin 
              
                =
              
               tin
              
                [
              
              
                :
              
              root_index
              
                ]
              
              
                ,
              
               tin
              
                [
              
              root_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
        L_pre
              
                ,
              
               R_pre 
              
                =
              
               pre
              
                [
              
              
                1
              
              
                :
              
              
                1
              
              
                +
              
              
                len
              
              
                (
              
              L_tin
              
                )
              
              
                ]
              
              
                ,
              
               pre
              
                [
              
              
                1
              
              
                +
              
              
                len
              
              
                (
              
              L_tin
              
                )
              
              
                :
              
              
                ]
              
              
                # 构建左树
              
              
        L_child 
              
                =
              
               self
              
                .
              
              reConstructBinaryTree
              
                (
              
              L_pre
              
                ,
              
               L_tin
              
                )
              
              
                # 构建右树
              
              
        R_child 
              
                =
              
               self
              
                .
              
              reConstructBinaryTree
              
                (
              
              R_pre
              
                ,
              
               R_tin
              
                )
              
              
        
        node 
              
                =
              
               TreeNode
              
                (
              
              root
              
                )
              
              
        node
              
                .
              
              left
              
                ,
              
               node
              
                .
              
              right 
              
                =
              
               L_child
              
                ,
              
               R_child
        
        
              
                return
              
               node

            
          

8.二叉树的下一个节点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                TreeLinkNode
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                ,
              
               x
              
                )
              
              
                :
              
              
        self
              
                .
              
              val 
              
                =
              
               x
        self
              
                .
              
              left 
              
                =
              
              
                None
              
              
        self
              
                .
              
              right 
              
                =
              
              
                None
              
              
        self
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeLinkNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                GetNext
              
              
                (
              
              self
              
                ,
              
               pNode
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               pNode
              
                :
              
              
                return
              
               pNode
        
        
              
                # 如果存在右子节点,则下一个节点是右子节点中的最左节点
              
              
                if
              
               pNode
              
                .
              
              right
              
                :
              
              
            pNode 
              
                =
              
               pNode
              
                .
              
              right
            
              
                while
              
               pNode
              
                .
              
              left
              
                :
              
              
                pNode 
              
                =
              
               pNode
              
                .
              
              left
            
              
                return
              
               pNode
        
              
                # 如果不存在右子节点,则反向根据父节点和子节点的关系确定
              
              
                else
              
              
                :
              
              
            pC 
              
                =
              
               pNode  
              
                # 记录当前节点
              
              
                # 当父节点不为根节点时,如果当前节点是父左子节点,返回当前节点
              
              
                while
              
               pNode
              
                .
              
              
                next
              
              
                :
              
               
                pN 
              
                =
              
               pNode
              
                .
              
              
                next
              
              
                if
              
               pN
              
                .
              
              left 
              
                and
              
               pN
              
                .
              
              left 
              
                ==
              
               pNode
              
                :
              
              
                return
              
               pN
                
              
                else
              
              
                :
              
              
                    pC 
              
                =
              
               pNode
                    pNode 
              
                =
              
               pN
            
            
              
                # 当父节点是根节点时,如果当前节点是根节点的左子节点,则返回根节点
              
              
                if
              
               pNode
              
                .
              
              left 
              
                and
              
               pNode
              
                .
              
              left 
              
                ==
              
               pC
              
                :
              
              
                return
              
               pNode
            
              
                else
              
              
                :
              
              
                return
              
              
                None
              
              

a 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'a'
              
              
                )
              
              
b 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'b'
              
              
                )
              
              
c 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'c'
              
              
                )
              
              
d 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'd'
              
              
                )
              
              
e 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'e'
              
              
                )
              
              
f 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'f'
              
              
                )
              
              
g 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'g'
              
              
                )
              
              
h 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'h'
              
              
                )
              
              
i 
              
                =
              
               TreeLinkNode
              
                (
              
              
                'i'
              
              
                )
              
              
a
              
                .
              
              left
              
                ,
              
               a
              
                .
              
              right 
              
                =
              
               b
              
                ,
              
               c
b
              
                .
              
              left
              
                ,
              
               b
              
                .
              
              right
              
                ,
              
               b
              
                .
              
              
                next
              
              
                =
              
               d
              
                ,
              
               e
              
                ,
              
               a
c
              
                .
              
              left
              
                ,
              
               c
              
                .
              
              right
              
                ,
              
               c
              
                .
              
              
                next
              
              
                =
              
               f
              
                ,
              
               g
              
                ,
              
               a
d
              
                .
              
              
                next
              
              
                =
              
               b
e
              
                .
              
              left
              
                ,
              
               e
              
                .
              
              right
              
                ,
              
               e
              
                .
              
              
                next
              
              
                =
              
               h
              
                ,
              
               i
              
                ,
              
               b
h
              
                .
              
              
                next
              
              
                =
              
               e
i
              
                .
              
              
                next
              
              
                =
              
               e
f
              
                .
              
              
                next
              
              
                ,
              
               g
              
                .
              
              
                next
              
              
                =
              
               c
              
                ,
              
               c

s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
                print
              
              
                (
              
              s
              
                .
              
              GetNext
              
                (
              
              i
              
                )
              
              
                .
              
              val
              
                )
              
            
          

9.用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                )
              
              
                :
              
              
        self
              
                .
              
              stack1 
              
                =
              
              
                [
              
              
                ]
              
              
                # 用于push
              
              
        self
              
                .
              
              stack2 
              
                =
              
              
                [
              
              
                ]
              
              
                # 用于pop
              
              
                def
              
              
                push
              
              
                (
              
              self
              
                ,
              
               node
              
                )
              
              
                :
              
              
                # write code here
              
              
        self
              
                .
              
              stack1
              
                .
              
              append
              
                (
              
              node
              
                )
              
              
                def
              
              
                pop
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              self
              
                .
              
              stack1
              
                )
              
              
                ==
              
              
                0
              
              
                and
              
              
                len
              
              
                (
              
              self
              
                .
              
              stack2
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                None
              
              
                # stack2不为空时,弹出栈顶元素即为队列头部元素
              
              
                elif
              
              
                len
              
              
                (
              
              self
              
                .
              
              stack2
              
                )
              
              
                >
              
              
                0
              
              
                :
              
                
            res 
              
                =
              
               self
              
                .
              
              stack2
              
                .
              
              pop
              
                (
              
              
                )
              
              
                return
              
               res
        
              
                else
              
              
                :
              
              
                # stack2为空时,将stack1元素弹出后压入stack2,则stack2栈顶元素即为队列头部元素
              
              
                while
              
              
                len
              
              
                (
              
              self
              
                .
              
              stack1
              
                )
              
              
                >
              
              
                0
              
              
                :
              
               
                i 
              
                =
              
               self
              
                .
              
              stack1
              
                .
              
              pop
              
                (
              
              
                )
              
              
                self
              
                .
              
              stack2
              
                .
              
              append
              
                (
              
              i
              
                )
              
              
            res 
              
                =
              
               self
              
                .
              
              stack2
              
                .
              
              pop
              
                (
              
              
                )
              
              
                return
              
               res

            
          

10. 斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39

f ( n ) = { 0 n = 0 1 n = 1 f ( n − 1 ) + f ( n − 2 ) n > 1 f(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f(n-1)+f(n-2) & n > 1 \end{cases} f ( n ) = 0 1 f ( n 1 ) + f ( n 2 ) n = 0 n = 1 n > 1

            
              
                # 方法一:循环法实现
              
              
                # 时间复杂度为:O(n)
              
              
                # 自下而上的求解
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Fibonacci
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
              
                isinstance
              
              
                (
              
              n
              
                ,
              
              
                int
              
              
                )
              
              
                or
              
               n 
              
                <
              
              
                0
              
              
                or
              
               n 
              
                >
              
              
                39
              
              
                :
              
              
                return
              
              
                None
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                1
              
              
        
        fn1
              
                ,
              
               fn2 
              
                =
              
              
                1
              
              
                ,
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                2
              
              
                ,
              
              n
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            fn 
              
                =
              
               fn1 
              
                +
              
               fn2
            fn2 
              
                =
              
               fn1
            fn1 
              
                =
              
               fn
        
        
              
                return
              
               fn

            
          
            
              
                # 方法二:递归法实现----运行超时
              
              
                # 时间复杂度为n的指数级
              
              
                # 自上而下的求解
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Fibonacci
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
              
                isinstance
              
              
                (
              
              n
              
                ,
              
              
                int
              
              
                )
              
              
                or
              
               n 
              
                <
              
              
                0
              
              
                or
              
               n 
              
                >
              
              
                39
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                1
              
              
                return
              
               self
              
                .
              
              Fibonacci
              
                (
              
              n
              
                -
              
              
                1
              
              
                )
              
              
                +
              
               self
              
                .
              
              Fibonacci
              
                (
              
              n
              
                -
              
              
                2
              
              
                )
              
            
          

方法三:时间复杂度为 O ( l o g &ThinSpace; n ) O(log \, n) O ( l o g n ) 的不实用解法

可证明存在如下公式:
[ f ( n ) f ( n − 1 ) f ( n − 1 ) f ( n − 2 ) ] = [ 1 1 1 0 ] n − 1 \begin{bmatrix} f(n)& f(n-1)\\ f(n-1)& f(n-2) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} [ f ( n ) f ( n 1 ) f ( n 1 ) f ( n 2 ) ] = [ 1 1 1 0 ] n 1
利用上述公式可以根据 [ 1 1 1 0 ] n − 1 \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} [ 1 1 1 0 ] n 1 求得 f ( n ) f(n) f ( n )

            
              
                # 方法一:更简洁的循环实现
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Fibonacci
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
        tempArray 
              
                =
              
              
                [
              
              
                0
              
              
                ,
              
              
                1
              
              
                ]
              
              
                if
              
               n 
              
                >=
              
              
                2
              
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                2
              
              
                ,
              
               n
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                tempArray
              
                [
              
              i
              
                %
              
              
                2
              
              
                ]
              
              
                =
              
               tempArray
              
                [
              
              
                0
              
              
                ]
              
              
                +
              
               tempArray
              
                [
              
              
                1
              
              
                ]
              
              
                return
              
               tempArray
              
                [
              
              n
              
                %
              
              
                2
              
              
                ]
              
            
          

10.2 跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

**分析:**设跳法是台阶数n的函数f(n), n>2时第一次跳有两种跳法,跳一个台阶则共f(n-1)种,跳两个台阶则共f(n-2)种,所以总共f(n)=f(n-1)+f(n-2)

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                jumpFloor
              
              
                (
              
              self
              
                ,
              
               number
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               number 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               number 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                1
              
              
                if
              
               number 
              
                ==
              
              
                2
              
              
                :
              
              
                return
              
              
                2
              
              
        
        fn1 
              
                =
              
              
                2
              
              
        fn2 
              
                =
              
              
                1
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                3
              
              
                ,
              
               number
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            fn 
              
                =
              
               fn1 
              
                +
              
               fn2
            
            fn2 
              
                =
              
               fn1
            fn1 
              
                =
              
               fn
        
              
                return
              
               fn

            
          

10.3 变态跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

**解析:**类比普通跳台阶问题,设跳法是台阶数n的函数f(n), 则有:
f ( n ) = f ( n − 1 ) + f ( n − 2 ) + . . . + f ( 1 ) + 1 f(n)=f(n-1)+f(n-2)+...+f(1)+1 f ( n ) = f ( n 1 ) + f ( n 2 ) + . . . + f ( 1 ) + 1
递推可得: f ( n − 1 ) = f ( n − 2 ) + f ( n − 3 ) + . . . + f ( 1 ) + 1 f(n-1)=f(n-2)+f(n-3)+...+f(1)+1 f ( n 1 ) = f ( n 2 ) + f ( n 3 ) + . . . + f ( 1 ) + 1
两式相减可得: f ( n ) − f ( n − 1 ) = f ( n − 1 ) f(n)-f(n-1)=f(n-1) f ( n ) f ( n 1 ) = f ( n 1 )
f ( n ) = 2 f ( n − 1 ) f(n)=2f(n-1) f ( n ) = 2 f ( n 1 ) ,即 f ( n ) f(n) f ( n ) 是公比为2的等比级数: f ( n ) = 2 n − 1 f(n)=2^{n-1} f ( n ) = 2 n 1

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                jumpFloorII
              
              
                (
              
              self
              
                ,
              
               number
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               number 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
        fn 
              
                =
              
              
                1
              
              
                if
              
               number 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               fn
        
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              
                2
              
              
                ,
              
              number
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            fn 
              
                *=
              
              
                2
              
              
                return
              
               fn

            
          

10.4 矩形覆盖问题

我们可以用2 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                rectCover
              
              
                (
              
              self
              
                ,
              
               number
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               number 
              
                <
              
              
                1
              
              
                or
              
              
                not
              
              
                isinstance
              
              
                (
              
              number
              
                ,
              
              
                int
              
              
                )
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               number 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                1
              
              
                if
              
               number 
              
                ==
              
              
                2
              
              
                :
              
              
                return
              
              
                2
              
              
        
        fn1 
              
                =
              
              
                2
              
              
        fn2 
              
                =
              
              
                1
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                3
              
              
                ,
              
               number
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            fn 
              
                =
              
               fn1 
              
                +
              
               fn2
            
            fn2 
              
                =
              
               fn1
            fn1 
              
                =
              
               fn
        
        
              
                return
              
               fn

            
          

11.旋转数组中的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

            
              
                # 方法一:暴力遍历法--不推荐
              
              
                # 时间复杂度为:O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                minNumberInRotateArray
              
              
                (
              
              self
              
                ,
              
               rotateArray
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
        small 
              
                =
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               rotateArray
              
                :
              
              
                if
              
               small 
              
                >
              
               i
              
                :
              
              
                small 
              
                =
              
               i
                
              
                return
              
               small
        
              
                return
              
               small

            
          
            
              
                # 方法二:二分法
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                minNumberInRotateArray
              
              
                (
              
              self
              
                ,
              
               rotateArray
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
        
        index 
              
                =
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                //
              
              
                2
              
              
                # index >= 1
              
              
        base 
              
                =
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                //
              
              
                2
              
              
                while
              
              
                0
              
              
                <=
              
               base 
              
                <
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                :
              
              
                if
              
               rotateArray
              
                [
              
              base
              
                -
              
              
                1
              
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                :
              
              
                # 如果前一个大于当前数,则当前数为最小
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                elif
              
               base 
              
                +
              
              
                1
              
              
                <
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                and
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              base
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
                # 如果后一个数存在且小于当前数,则后一个数为最小
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                +
              
              
                1
              
              
                ]
              
              
                else
              
              
                :
              
              
                # 否则重新搜索,以数组第一个数为基准移动索引
              
              
                if
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                    base 
              
                +=
              
               index 
              
                //
              
              
                2
              
              
                else
              
              
                :
              
              
                    base 
              
                -=
              
               index 
              
                //
              
              
                2
              
              
                index 
              
                //=
              
              
                2
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                ## 这个方法存在问题,当针对[1,1,1,1,1,0,1]时无法正常判断,所以应该修改为当base与左右值相等时采用顺序查找的方法搜索最小值
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                minNumberInRotateArray
              
              
                (
              
              self
              
                ,
              
               rotateArray
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
        
        index 
              
                =
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                //
              
              
                2
              
              
                # index >= 1
              
              
        base 
              
                =
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                //
              
              
                2
              
              
                while
              
              
                0
              
              
                <=
              
               base 
              
                <
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                :
              
              
                if
              
               rotateArray
              
                [
              
              base
              
                -
              
              
                1
              
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                :
              
              
                # 如果前一个大于当前数,则当前数为最小
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                elif
              
               base 
              
                +
              
              
                1
              
              
                <
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                and
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              base
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
                # 如果后一个数存在且小于当前数,则后一个数为最小
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                +
              
              
                1
              
              
                ]
              
              
                else
              
              
                :
              
              
                # 否则重新搜索,以数组第一个数为基准移动索引
              
              
                if
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                >
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                    base 
              
                +=
              
               index 
              
                //
              
              
                2
              
              
                elif
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                <
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                    base 
              
                -=
              
               index 
              
                //
              
              
                2
              
              
                else
              
              
                :
              
              
                # 顺序查找
              
              
                    minNum 
              
                =
              
               self
              
                .
              
              minSearch
              
                (
              
              rotateArray
              
                )
              
              
                return
              
               minNum
                index 
              
                //=
              
              
                2
              
              
                return
              
               rotateArray
              
                [
              
              base
              
                ]
              
              
                def
              
              
                minSearch
              
              
                (
              
              self
              
                ,
              
               rotateArray
              
                )
              
              
                :
              
              
        small 
              
                =
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               rotateArray
              
                :
              
              
                if
              
               small 
              
                >
              
               i
              
                :
              
              
                small 
              
                =
              
               i
                
              
                return
              
               small
        
              
                return
              
               small

            
          
            
              
                # 方法三:二分法示例代码
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                minNumberInRotateArray
              
              
                (
              
              self
              
                ,
              
               rotateArray
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                # 双指针
              
              
        first 
              
                =
              
              
                0
              
              
        end 
              
                =
              
              
                len
              
              
                (
              
              rotateArray
              
                )
              
              
                -
              
              
                1
              
              
                while
              
               end 
              
                -
              
               first 
              
                !=
              
              
                1
              
              
                :
              
              
            mid 
              
                =
              
              
                (
              
              first 
              
                +
              
               end
              
                )
              
              
                //
              
              
                2
              
              
                if
              
               rotateArray
              
                [
              
              first
              
                ]
              
              
                ==
              
               rotateArray
              
                [
              
              mid
              
                ]
              
              
                ==
              
               rotateArray
              
                [
              
              end
              
                ]
              
              
                :
              
              
                # 特殊情况,使用顺序查找
              
              
                minN 
              
                =
              
               rotateArray
              
                [
              
              
                0
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               rotateArray
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                :
              
              
                if
              
               i 
              
                <
              
               minN
              
                :
              
              
                        minN 
              
                =
              
               i
                
              
                return
              
               minN
            
              
                elif
              
               rotateArray
              
                [
              
              first
              
                ]
              
              
                <
              
               rotateArray
              
                [
              
              end
              
                ]
              
              
                :
              
              
                # 特殊情况,整个数组是升序,没有进行旋转
              
              
                return
              
               rotateArray
              
                [
              
              first
              
                ]
              
              
                elif
              
               rotateArray
              
                [
              
              mid
              
                ]
              
              
                >=
              
               rotateArray
              
                [
              
              first
              
                ]
              
              
                :
              
              
                first 
              
                =
              
               mid
            
              
                else
              
              
                :
              
              
                end 
              
                =
              
               mid
        
              
                return
              
               rotateArray
              
                [
              
              end
              
                ]
              
            
          

12.矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 [ a b c e s f c s a d e e ] \begin{bmatrix} a & b & c & e \\ s & f & c & s \\ a & d & e & e \end{bmatrix} a s a b f d c c e e s e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

            
              
                # 回溯法--使用递归实现
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                hasPath
              
              
                (
              
              self
              
                ,
              
               matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              matrix
              
                )
              
              
                <
              
              
                1
              
              
                or
              
               rows 
              
                <
              
              
                1
              
              
                or
              
               cols 
              
                <
              
              
                1
              
              
                or
              
              
                len
              
              
                (
              
              path
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        
        visited 
              
                =
              
              
                [
              
              
                0
              
              
                ]
              
              
                *
              
              
                (
              
              rows 
              
                *
              
               cols
              
                )
              
              
        pathL 
              
                =
              
              
                0
              
              
                for
              
               row 
              
                in
              
              
                range
              
              
                (
              
              rows
              
                )
              
              
                :
              
              
                for
              
               col 
              
                in
              
              
                range
              
              
                (
              
              cols
              
                )
              
              
                :
              
              
                if
              
               self
              
                .
              
              if_has_path
              
                (
              
              matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                :
              
              
                return
              
              
                True
              
              
                return
              
              
                False
              
              
                def
              
              
                if_has_path
              
              
                (
              
              self
              
                ,
              
               matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
               pathL 
              
                ==
              
              
                len
              
              
                (
              
              path
              
                )
              
              
                :
              
              
                return
              
              
                True
              
              
        hasPath 
              
                =
              
              
                False
              
              
                if
              
              
                0
              
              
                <=
              
               row 
              
                <
              
               rows 
              
                and
              
              
                0
              
              
                <=
              
               col 
              
                <
              
               cols 
              
                and
              
               \
            matrix
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                ==
              
               path
              
                [
              
              pathL
              
                ]
              
              
                and
              
               \
            
              
                not
              
               visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                :
              
              
                pathL 
              
                +=
              
              
                1
              
              
                visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                =
              
              
                1
              
              
                
                hasPath 
              
                =
              
               self
              
                .
              
              if_has_path
              
                (
              
              matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                -
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                or
              
               \
                          self
              
                .
              
              if_has_path
              
                (
              
              matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                +
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                or
              
               \
                          self
              
                .
              
              if_has_path
              
                (
              
              matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                ,
              
               col
              
                -
              
              
                1
              
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                or
              
               \
                          self
              
                .
              
              if_has_path
              
                (
              
              matrix
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               path
              
                ,
              
               row
              
                ,
              
               col
              
                +
              
              
                1
              
              
                ,
              
               visited
              
                ,
              
               pathL
              
                )
              
              
                if
              
              
                not
              
               hasPath
              
                :
              
              
                    pathL 
              
                -=
              
              
                1
              
              
                    visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                =
              
              
                0
              
              
                return
              
               hasPath

            
          

13.机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

            
              
                # 回溯法
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                movingCount
              
              
                (
              
              self
              
                ,
              
               threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               threshold 
              
                <
              
              
                1
              
              
                or
              
               rows 
              
                <
              
              
                1
              
              
                or
              
               cols 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
        visited 
              
                =
              
              
                [
              
              
                0
              
              
                ]
              
              
                *
              
              
                (
              
              rows 
              
                *
              
               cols
              
                )
              
              
                # 记录当前位置是否访问过
              
              
        available 
              
                =
              
              
                [
              
              
                0
              
              
                ]
              
              
                *
              
              
                (
              
              rows 
              
                *
              
               cols
              
                )
              
              
                # 记录当前位置是否可达
              
              

        self
              
                .
              
              ifAvailable
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
                return
              
              
                sum
              
              
                (
              
              available
              
                )
              
              
                def
              
              
                ifTrue
              
              
                (
              
              self
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               threshold
              
                )
              
              
                :
              
              
        res 
              
                =
              
              
                0
              
              
                while
              
               row 
              
                !=
              
              
                0
              
              
                :
              
              
            res 
              
                +=
              
               row 
              
                %
              
              
                10
              
              
            row 
              
                //=
              
              
                10
              
              
                while
              
               col 
              
                !=
              
              
                0
              
              
                :
              
              
            res 
              
                +=
              
               col 
              
                %
              
              
                10
              
              
            col 
              
                //=
              
              
                10
              
              
                if
              
               res 
              
                <=
              
               threshold
              
                :
              
              
                return
              
              
                True
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
              
                def
              
              
                ifAvailable
              
              
                (
              
              self
              
                ,
              
               threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
                :
              
              
                if
              
              
                0
              
              
                <=
              
               row 
              
                <
              
               rows 
              
                and
              
              
                0
              
              
                <=
              
               col 
              
                <
              
               cols 
              
                and
              
               self
              
                .
              
              ifTrue
              
                (
              
              row
              
                ,
              
               col
              
                ,
              
               threshold
              
                )
              
              
                and
              
               \
            
              
                not
              
               visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                :
              
              
            available
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                =
              
              
                1
              
              
            visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                =
              
              
                1
              
              
            self
              
                .
              
              ifAvailable
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                -
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
            self
              
                .
              
              ifAvailable
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                +
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
            self
              
                .
              
              ifAvailable
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                -
              
              
                1
              
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
            self
              
                .
              
              ifAvailable
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                +
              
              
                1
              
              
                ,
              
               visited
              
                ,
              
               available
              
                )
              
              
                else
              
              
                :
              
              
                # visited[row * cols + col] = 0
              
              
                return
              
            
          
            
              
                # 回溯法--示例代码
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                movingCount
              
              
                (
              
              self
              
                ,
              
               threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                )
              
              
                :
              
              
        visited 
              
                =
              
              
                [
              
              
                False
              
              
                ]
              
              
                *
              
              
                (
              
              rows 
              
                *
              
               cols
              
                )
              
              
        count 
              
                =
              
               self
              
                .
              
              movingCountCore
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
               visited
              
                )
              
              
                return
              
               count

    
              
                def
              
              
                movingCountCore
              
              
                (
              
              self
              
                ,
              
               threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                )
              
              
                :
              
              
        count 
              
                =
              
              
                0
              
              
                if
              
               self
              
                .
              
              check
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                )
              
              
                :
              
              
            visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                =
              
              
                True
              
              
            count 
              
                =
              
              
                1
              
              
                +
              
               self
              
                .
              
              movingCountCore
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                -
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                )
              
              
                +
              
               \
                        self
              
                .
              
              movingCountCore
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                +
              
              
                1
              
              
                ,
              
               col
              
                ,
              
               visited
              
                )
              
              
                +
              
               \
                        self
              
                .
              
              movingCountCore
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                -
              
              
                1
              
              
                ,
              
               visited
              
                )
              
              
                +
              
               \
                        self
              
                .
              
              movingCountCore
              
                (
              
              threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                +
              
              
                1
              
              
                ,
              
               visited
              
                )
              
              
                return
              
               count

    
              
                def
              
              
                check
              
              
                (
              
              self
              
                ,
              
               threshold
              
                ,
              
               rows
              
                ,
              
               cols
              
                ,
              
               row
              
                ,
              
               col
              
                ,
              
               visited
              
                )
              
              
                :
              
              
                if
              
               row 
              
                >=
              
              
                0
              
              
                and
              
               row 
              
                <
              
               rows 
              
                and
              
               col 
              
                >=
              
              
                0
              
              
                and
              
               col 
              
                <
              
               cols 
              
                and
              
               self
              
                .
              
              getDigitSum
              
                (
              
              row
              
                )
              
              
                +
              
               self
              
                .
              
              getDigitSum
              
                (
              
              col
              
                )
              
              
                <=
              
               threshold 
              
                and
              
              
                not
              
               visited
              
                [
              
              row 
              
                *
              
               cols 
              
                +
              
               col
              
                ]
              
              
                :
              
              
                return
              
              
                True
              
              
                return
              
              
                False
              
              
                def
              
              
                getDigitSum
              
              
                (
              
              self
              
                ,
              
               number
              
                )
              
              
                :
              
              
                sum
              
              
                =
              
              
                0
              
              
                while
              
               number 
              
                >
              
              
                0
              
              
                :
              
              
                sum
              
              
                +=
              
              
                (
              
              number 
              
                %
              
              
                10
              
              
                )
              
              
            number 
              
                =
              
               number 
              
                //
              
              
                10
              
              
                return
              
              
                sum
              
            
          

14.剪绳子

与leetcode 343题一样,中文版:
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

注意 :存储最优解的数组的前三个值是剪开后或者不剪情况下绳子的最大值,而不仅仅是剪开后乘积的最大值
参考题解:https://blog.csdn.net/weixin_41796401/article/details/84899457

            
              
                # 方法一:动态规划法
              
              
                # 时间复杂度为O(n^2),空间复杂度为O(n)
              
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                integerBreak
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                """
        :type n: int
        :rtype: int
        """
              
              
                if
              
               n 
              
                <
              
              
                2
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                ==
              
              
                2
              
              
                :
              
              
                return
              
              
                1
              
              
                if
              
               n 
              
                ==
              
              
                3
              
              
                :
              
              
                return
              
              
                2
              
              
                # mem[0] not used
              
              
                # !!! mem中存储的是剪开后或者不剪情况下绳子的最大值,而不仅仅是剪开后乘积的最大值
              
              
        mem 
              
                =
              
              
                [
              
              
                0
              
              
                ]
              
              
                *
              
              
                (
              
              n
              
                +
              
              
                1
              
              
                )
              
                
        mem
              
                [
              
              
                1
              
              
                ]
              
              
                ,
              
               mem
              
                [
              
              
                2
              
              
                ]
              
              
                ,
              
               mem
              
                [
              
              
                3
              
              
                ]
              
              
                =
              
              
                1
              
              
                ,
              
              
                2
              
              
                ,
              
              
                3
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                4
              
              
                ,
              
               n
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            max_product 
              
                =
              
              
                0
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
               i
              
                //
              
              
                2
              
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                max_product 
              
                =
              
              
                max
              
              
                (
              
              max_product
              
                ,
              
               mem
              
                [
              
              j
              
                ]
              
              
                *
              
               mem
              
                [
              
              i
              
                -
              
              j
              
                ]
              
              
                )
              
              
            mem
              
                [
              
              i
              
                ]
              
              
                =
              
               max_product
        
        
              
                return
              
               mem
              
                [
              
              n
              
                ]
              
            
          
            
              
                # 方法二:贪婪法
              
              
                # 证明:n > 4时,3(n-3) >= 2(n-2) > n
              
              
                # 尽可能多的将数分解成3,当余下是4时,分解成2*2
              
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                integerBreak
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                """
        :type n: int
        :rtype: int
        """
              
              
                if
              
               n 
              
                <
              
              
                2
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                ==
              
              
                2
              
              
                :
              
              
                return
              
              
                1
              
              
                if
              
               n 
              
                ==
              
              
                3
              
              
                :
              
              
                return
              
              
                2
              
              
        
        p 
              
                =
              
              
                (
              
              n 
              
                //
              
              
                3
              
              
                )
              
              
        r 
              
                =
              
              
                (
              
              n 
              
                %
              
              
                3
              
              
                )
              
              
                if
              
               r 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                pow
              
              
                (
              
              
                3
              
              
                ,
              
               p
              
                )
              
              
                elif
              
               r 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                pow
              
              
                (
              
              
                3
              
              
                ,
              
               p
              
                -
              
              
                1
              
              
                )
              
              
                *
              
              
                4
              
              
                elif
              
               r 
              
                ==
              
              
                2
              
              
                :
              
              
                return
              
              
                pow
              
              
                (
              
              
                3
              
              
                ,
              
               p
              
                )
              
              
                *
              
              
                2
              
            
          

15.二进制中1的个数

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

解析:

  • 使用位运算的效率高于除法
  • 负数的右移运算会在高位进行补1,如果没考虑这一点,可能导致程序陷入死循环
  • 可以使用与运算实现1的个数统计
            
              
                # 方法一:常规不会陷入死循环的方法
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                NumberOf1
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
                # 设置循环终止条件
              
              
        MAX_INT 
              
                =
              
              
                (
              
              
                1
              
              
                <<
              
              
                (
              
              
                32
              
              
                -
              
              
                1
              
              
                )
              
              
                )
              
               
        flag 
              
                =
              
              
                1
              
              
        count 
              
                =
              
              
                0
              
              
                while
              
               n 
              
                and
              
               flag 
              
                <=
              
               MAX_INT 
              
                :
              
              
                if
              
               n 
              
                &
              
               flag
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                n 
              
                -=
              
               flag
            flag 
              
                =
              
               flag 
              
                <<
              
              
                1
              
              
                return
              
               count

            
          
            
              
                # 方法二:技巧性方法:正数减去1,再和原来的数做与运算,会把正数最右边的1变成0
              
              
                # 参考:https://www.cnblogs.com/klchang/p/8017627.html
              
              
                # 或者根据负数补码的特点,使用模将负数转化:n = n & 0xffffffff,然后再进行减1做与运算
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                NumberOf1
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
        count 
              
                =
              
              
                0
              
              
                # 假设系统的整数是四字节,由于python自身整数是8字节,所以手动设置整数的界限
              
              
                # 例如-1在8字节情况下的补码是:1111.......1111(64个),在4字节下1111.......1111(32个)
              
              
        MAX_INT 
              
                =
              
              
                1
              
              
                <<
              
              
                (
              
              
                32
              
              
                -
              
              
                1
              
              
                )
              
              
                while
              
               n 
              
                !=
              
              
                0
              
              
                :
              
              
                if
              
              
                -
              
              MAX_INT 
              
                >
              
               n 
              
                or
              
               n 
              
                >
              
               MAX_INT
              
                :
              
              
                # 主要是针对负数,当n为负数时,随着n = n & (n-1),n将越界
              
              
                break
              
              
                # 如果不添加该终止循环的条件,程序将陷入死循环
              
              
            count 
              
                +=
              
              
                1
              
              
            n 
              
                =
              
               n 
              
                &
              
              
                (
              
              n
              
                -
              
              
                1
              
              
                )
              
              
                return
              
               count

            
          

16.数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

            
              
                # 方法一:普通方法
              
              
                # 注意边界条件的控制、功能的测试、
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Power
              
              
                (
              
              self
              
                ,
              
               base
              
                ,
              
               exponent
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               base 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
        res 
              
                =
              
              
                1
              
              
                if
              
               exponent 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
               res
        
              
                elif
              
               exponent 
              
                >
              
              
                0
              
              
                :
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              exponent
              
                )
              
              
                :
              
              
                res 
              
                *=
              
               base
            
              
                return
              
               res
        
              
                else
              
              
                :
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              
                abs
              
              
                (
              
              exponent
              
                )
              
              
                )
              
              
                :
              
              
                res 
              
                *=
              
               base
            
              
                if
              
               res 
              
                !=
              
              
                0
              
              
                :
              
              
                return
              
              
                1
              
              
                /
              
              res
            
              
                else
              
              
                :
              
              
                return
              
            
          

方法二:高效法

利用如下的递推公式:
a n = { a n / 2 ⋅ a n / 2 n 为 偶 数 a ( n − 1 ) / 2 ⋅ a ( n − 1 ) / 2 ⋅ a n 为 奇 数 a^n = \begin{cases} a^{n/2}\cdot a^{n/2} & n 为偶数 \\ a^{(n-1)/2}\cdot a^{(n-1)/2}\cdot a & n 为奇数 \end{cases} a n = { a n / 2 a n / 2 a ( n 1 ) / 2 a ( n 1 ) / 2 a n n

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Power
              
              
                (
              
              self
              
                ,
              
               base
              
                ,
              
               exponent
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 要考虑base=0而exponent为负数这种异常情况的处理
              
              
                if
              
               base 
              
                ==
              
              
                0
              
              
                and
              
               exponent 
              
                <
              
              
                0
              
              
                :
              
              
                raise
              
               Exception
              
                (
              
              
                'Error: base is zero '
              
              
                )
              
              
                if
              
               base 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               exponent 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                1
              
              
                if
              
               exponent 
              
                >
              
              
                0
              
              
                :
              
              
                return
              
               self
              
                .
              
              power_re
              
                (
              
              base
              
                ,
              
               exponent
              
                )
              
              
                else
              
              
                :
              
              
                return
              
              
                1
              
              
                /
              
              self
              
                .
              
              power_re
              
                (
              
              base
              
                ,
              
              
                abs
              
              
                (
              
              exponent
              
                )
              
              
                )
              
              
                # 递归求解
              
              
                def
              
              
                power_re
              
              
                (
              
              self
              
                ,
              
               base
              
                ,
              
               exponent
              
                )
              
              
                :
              
              
                if
              
               exponent 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               base
        
              
                if
              
              
                (
              
              exponent 
              
                &
              
              
                0x1
              
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
               self
              
                .
              
              power_re
              
                (
              
              base
              
                ,
              
              
                (
              
              exponent 
              
                >>
              
              
                1
              
              
                )
              
              
                )
              
              
                *
              
              self
              
                .
              
              Power
              
                (
              
              base
              
                ,
              
              
                (
              
              exponent 
              
                >>
              
              
                1
              
              
                )
              
              
                )
              
              
                else
              
              
                :
              
              
                return
              
               self
              
                .
              
              power_re
              
                (
              
              base
              
                ,
              
              
                (
              
              
                (
              
              exponent
              
                -
              
              
                1
              
              
                )
              
              
                >>
              
              
                1
              
              
                )
              
              
                )
              
              
                *
              
               self
              
                .
              
              Power
              
                (
              
              base
              
                ,
              
              
                (
              
              
                (
              
              exponent
              
                -
              
              
                1
              
              
                )
              
              
                >>
              
              
                1
              
              
                )
              
              
                )
              
              
                *
              
              base

            
          

17. 打印1到最大的n位数

解析:主要需要解决大数问题

            
              
                # 方法一:使用字符串数组解决大数问题,实现进位功能
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Print1ToMaxofNDigits
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                if
              
               n 
              
                <
              
              
                1
              
              
                :
              
              
                raise
              
               Exception
              
                (
              
              
                'invalid input n'
              
              
                )
              
              
        
        str_num 
              
                =
              
              
                [
              
              
                '0'
              
              
                ]
              
              
                *
              
               n
        
        
              
                while
              
              
                True
              
              
                :
              
              
                # 确定进位的位置
              
              
            i 
              
                =
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                -
              
              
                1
              
              
                while
              
               str_num
              
                [
              
              i
              
                ]
              
              
                ==
              
              
                '9'
              
              
                and
              
               i 
              
                >
              
              
                0
              
              
                :
              
              
                i 
              
                -=
              
              
                1
              
              
                # 打印结束终止条件
              
              
                if
              
               str_num
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
              
                '9'
              
              
                and
              
               i 
              
                ==
              
              
                0
              
              
                :
              
              
                break
              
              
                # 不需要进位
              
              
                if
              
               i 
              
                ==
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                -
              
              
                1
              
              
                :
              
              
                str_num
              
                [
              
              i
              
                ]
              
              
                =
              
              
                str
              
              
                (
              
              
                int
              
              
                (
              
              str_num
              
                [
              
              i
              
                ]
              
              
                )
              
              
                +
              
              
                1
              
              
                )
              
              
                self
              
                .
              
              Print
              
                (
              
              str_num
              
                )
              
              
                # 需要进位
              
              
                else
              
              
                :
              
              
                str_num
              
                [
              
              i
              
                ]
              
              
                =
              
              
                str
              
              
                (
              
              
                int
              
              
                (
              
              str_num
              
                [
              
              i
              
                ]
              
              
                )
              
              
                +
              
              
                1
              
              
                )
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              i
              
                +
              
              
                1
              
              
                ,
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                )
              
              
                :
              
              
                    str_num
              
                [
              
              j
              
                ]
              
              
                =
              
              
                '0'
              
              
                self
              
                .
              
              Print
              
                (
              
              str_num
              
                )
              
              
                def
              
              
                Print
              
              
                (
              
              self
              
                ,
              
               str_num
              
                )
              
              
                :
              
              
        index 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               str_num
              
                [
              
              i
              
                ]
              
              
                !=
              
              
                '0'
              
              
                :
              
               
                index 
              
                =
              
               i
                
              
                break
              
              
                print
              
              
                (
              
              
                ''
              
              
                .
              
              join
              
                (
              
              str_num
              
                [
              
              index
              
                :
              
              
                ]
              
              
                )
              
              
                )
              
              
                  
s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
s
              
                .
              
              Print1ToMaxofNDigits
              
                (
              
              
                3
              
              
                )
              
            
          
            
              
                # 方法二:使用数字排列的方法实现
              
              
                # 使用递归实现数字排列:从上到下分析,从下到上实现。。
              
              
                # 从上到下分析:从最高位开始排列,高位排列完后排列低一位,直到排列完最低位
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Print1ToMaxofNDigits
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                if
              
               n 
              
                <
              
              
                1
              
              
                :
              
              
                raise
              
               Exception
              
                (
              
              
                'invalid input n'
              
              
                )
              
              
        
        str_num 
              
                =
              
              
                [
              
              
                '0'
              
              
                ]
              
              
                *
              
               n
        
        
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                10
              
              
                )
              
              
                :
              
              
            str_num
              
                [
              
              
                0
              
              
                ]
              
              
                =
              
              
                str
              
              
                (
              
              i
              
                )
              
              
            self
              
                .
              
              recursivePrint1ToMaxofNDigits
              
                (
              
              str_num
              
                ,
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                ,
              
               index
              
                =
              
              
                0
              
              
                )
              
              
                def
              
              
                recursivePrint1ToMaxofNDigits
              
              
                (
              
              self
              
                ,
              
               str_num
              
                ,
              
               length
              
                ,
              
               index
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
               index 
              
                ==
              
               length 
              
                -
              
              
                1
              
              
                :
              
              
            self
              
                .
              
              Print
              
                (
              
              str_num
              
                )
              
              
                return
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                10
              
              
                )
              
              
                :
              
              
            str_num
              
                [
              
              index 
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
              
                str
              
              
                (
              
              i
              
                )
              
              
            self
              
                .
              
              recursivePrint1ToMaxofNDigits
              
                (
              
              str_num
              
                ,
              
               length
              
                ,
              
               index 
              
                +
              
              
                1
              
              
                )
              
              
                def
              
              
                Print
              
              
                (
              
              self
              
                ,
              
               str_num
              
                )
              
              
                :
              
              
        index 
              
                =
              
              
                -
              
              
                1
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              str_num
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               str_num
              
                [
              
              i
              
                ]
              
              
                !=
              
              
                '0'
              
              
                :
              
               
                index 
              
                =
              
               i
                
              
                break
              
              
                if
              
               index 
              
                !=
              
              
                -
              
              
                1
              
              
                :
              
              
                print
              
              
                (
              
              
                ''
              
              
                .
              
              join
              
                (
              
              str_num
              
                [
              
              index
              
                :
              
              
                ]
              
              
                )
              
              
                )
              
                      
        
s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
s
              
                .
              
              Print1ToMaxofNDigits
              
                (
              
              
                2
              
              
                )
              
            
          

18.删除链表节点

题目一:在 O ( 1 ) O(1) O ( 1 ) 时间内删除链表节点

给定单向链表的头指针和一个节点指针,定义一个函数在 O ( 1 ) O(1) O ( 1 ) 时间内删除该节点。

lintcode: https://www.lintcode.com/problem/delete-node-in-a-linked-list/description

            
              
                # 解题思路:将要删除节点的下一个节点复制到当前节点即可
              
              
                """
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
              
              
                class
              
              
                Solution
              
              
                :
              
              
                """
    @param: node: the node in the list should be deleted
    @return: nothing
    """
              
              
                def
              
              
                deleteNode
              
              
                (
              
              self
              
                ,
              
               node
              
                )
              
              
                :
              
              
                # write your code here
              
              
                if
              
              
                not
              
               node 
              
                or
              
              
                not
              
               node
              
                .
              
              
                next
              
              
                :
              
              
            node 
              
                =
              
              
                None
              
              
                return
              
              

        node
              
                .
              
              val 
              
                =
              
               node
              
                .
              
              
                next
              
              
                .
              
              val
        node
              
                .
              
              
                next
              
              
                =
              
               node
              
                .
              
              
                next
              
              
                .
              
              
                next
              
            
          

题目二:删除链表中的重复节点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

            
              
                # 标准解答:https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/56-%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E7%BB%93%E7%82%B9.py
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                deleteDuplication
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                or
              
               pHead
              
                .
              
              
                next
              
              
                is
              
              
                None
              
              
                :
              
              
                return
              
               pHead
        
        first 
              
                =
              
               ListNode
              
                (
              
              
                -
              
              
                1
              
              
                )
              
              
        first
              
                .
              
              
                next
              
              
                =
              
               pHead
        last 
              
                =
              
               first  
              
                # 记录上一个有效节点
              
              
                # 遍历不重复节点,更新last自身和last指向的节点
              
              
                while
              
               pHead 
              
                and
              
               pHead
              
                .
              
              
                next
              
              
                :
              
              
                if
              
               pHead
              
                .
              
              val 
              
                ==
              
               pHead
              
                .
              
              
                next
              
              
                .
              
              val
              
                :
              
              
                # 遍历得到与当前值不相等的节点,并将last指向该节点
              
              
                val 
              
                =
              
               pHead
              
                .
              
              val
                
              
                while
              
               pHead 
              
                and
              
               val 
              
                ==
              
               pHead
              
                .
              
              val
              
                :
              
              
                    pHead 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                last
              
                .
              
              
                next
              
              
                =
              
               pHead
            
              
                else
              
              
                :
              
              
                # 如果当前节点有效,则更新last节点
              
              
                last 
              
                =
              
               pHead
                pHead 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                return
              
               first
              
                .
              
              
                next
              
            
          

19. 正则表达式的匹配

请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符,而’*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

题解参考:递归求解,根据s和pattern长度不同进行分情况讨论:

  • 递归终止条件的确定:s和pattern长度均为0,或s不为0而pattern为0
  • s长度为0,pattern长度不为0
  • s和pattern长度都不为0,此时根据pattern第二位是否为"*"进行分情况讨论
    • pattern第二位不为"*",s和pattern比较后各后移一位
    • pattern第二位为"*",根据首位是否相等讨论:
      • 首位不相等,则s不变,pattern向后移动2位,相当于pattern前两位当成空
      • 首位相等,则有三种情况:
        1. pattern后移2位,s不变;相当于把pattern前两位当成空,匹配后面的
        2. pattern后移2位,s后移1位;相当于pattern前两位与s[0]匹配
        3. pattern不变,s后移1位;相当于pattern前两位与s中的多位进行匹配

另外可以使用动态规划来优化递归,参考题解。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # s, pattern都是字符串
              
              
                def
              
              
                match
              
              
                (
              
              self
              
                ,
              
               s
              
                ,
              
               pattern
              
                )
              
              
                :
              
              
                # write code here
              
              
                #if not s and not pattern:
              
              
                #    return False
              
              
                return
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                ,
              
               pattern
              
                )
              
              
                def
              
              
                match_recursion
              
              
                (
              
              self
              
                ,
              
               s
              
                ,
              
               pattern
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                ==
              
              
                0
              
              
                and
              
              
                len
              
              
                (
              
              pattern
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                True
              
              
                elif
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                !=
              
              
                0
              
              
                and
              
              
                len
              
              
                (
              
              pattern
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                False
              
              
                elif
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                ==
              
              
                0
              
              
                and
              
              
                len
              
              
                (
              
              pattern
              
                )
              
              
                !=
              
              
                0
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              pattern
              
                )
              
              
                >
              
              
                1
              
              
                and
              
               pattern
              
                [
              
              
                1
              
              
                ]
              
              
                is
              
              
                "*"
              
              
                :
              
              
                return
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                ,
              
               pattern
              
                [
              
              
                2
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
              
                else
              
              
                :
              
              
                # s和pattern都不为空
              
              
                if
              
              
                len
              
              
                (
              
              pattern
              
                )
              
              
                >
              
              
                1
              
              
                and
              
               pattern
              
                [
              
              
                1
              
              
                ]
              
              
                is
              
              
                "*"
              
              
                :
              
              
                # s和pattern第一个元素不相同,则s不变,pattern向后移动2位,相当于pattern前两位当成空
              
              
                if
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                !=
              
               pattern
              
                [
              
              
                0
              
              
                ]
              
              
                and
              
               pattern
              
                [
              
              
                0
              
              
                ]
              
              
                !=
              
              
                "."
              
              
                :
              
              
                return
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                ,
              
               pattern
              
                [
              
              
                2
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                # 如果s[0]和pattern[0]相同,此时有三种情况
              
              
                # 1.pattern后移2位,s不变;相当于把pattern前两位当成空,匹配后面的
              
              
                # 2.pattern后移2位,s后移1位;相当于pattern前两位与s[0]匹配
              
              
                # 3.pattern不变,s后移1位;相当于pattern前两位与s中的多位进行匹配
              
              
                return
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                ,
              
              pattern
              
                [
              
              
                2
              
              
                :
              
              
                ]
              
              
                )
              
              
                or
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
               pattern
              
                [
              
              
                2
              
              
                :
              
              
                ]
              
              
                )
              
              
                or
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
               pattern
              
                )
              
              
                else
              
              
                :
              
              
                if
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
               pattern
              
                [
              
              
                0
              
              
                ]
              
              
                or
              
               pattern
              
                [
              
              
                0
              
              
                ]
              
              
                is
              
              
                "."
              
              
                :
              
              
                return
              
               self
              
                .
              
              match_recursion
              
                (
              
              s
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
               pattern
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
            
          

20.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # s字符串
              
              
                def
              
              
                isNumeric
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        dot_index 
              
                =
              
              
                -
              
              
                1
              
              
        e_index 
              
                =
              
              
                -
              
              
                1
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               s
              
                [
              
              i
              
                ]
              
              
                is
              
              
                '.'
              
              
                :
              
              
                dot_index 
              
                =
              
               i
            
              
                if
              
               s
              
                [
              
              i
              
                ]
              
              
                is
              
              
                'e'
              
              
                or
              
               s
              
                [
              
              i
              
                ]
              
              
                is
              
              
                'E'
              
              
                :
              
              
                e_index 
              
                =
              
               i
                
              
                break
              
              
        res 
              
                =
              
              
                True
              
              
                if
              
               dot_index 
              
                >
              
              
                0
              
              
                :
              
              
                # 小数点不在首位
              
              
            res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isInt
              
                (
              
              s
              
                [
              
              
                :
              
              dot_index
              
                ]
              
              
                ,
              
              
                1
              
              
                )
              
              
                if
              
               e_index 
              
                >
              
              
                0
              
              
                :
              
              
                # 存在e或者E
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              e_index
              
                ]
              
              
                )
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isInt
              
                (
              
              s
              
                [
              
              e_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
              
                0
              
              
                )
              
              
                else
              
              
                :
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                elif
              
               dot_index 
              
                ==
              
              
                0
              
              
                :
              
              
                # 小数点在首位
              
              
                if
              
               e_index 
              
                >
              
              
                0
              
              
                :
              
              
                # 存在e或者E
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              e_index
              
                ]
              
              
                )
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isInt
              
                (
              
              s
              
                [
              
              e_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
              
                0
              
              
                )
              
              
                else
              
              
                :
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                # 不存在小数点
              
              
                if
              
               e_index 
              
                >
              
              
                0
              
              
                :
              
              
                # 存在e或者E  -+E
              
              
                if
              
               s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                ]
              
              
                ==
              
              
                '-'
              
              
                or
              
               s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                ]
              
              
                ==
              
              
                '+'
              
              
                :
              
              
                    res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                2
              
              
                :
              
              e_index
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                    res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              e_index
              
                ]
              
              
                )
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isInt
              
                (
              
              s
              
                [
              
              e_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
              
                0
              
              
                )
              
              
                else
              
              
                :
              
              
                # 不存在小数点和E
              
              
                res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isInt
              
                (
              
              s
              
                [
              
              dot_index
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                ,
              
              
                0
              
              
                )
              
              
                return
              
               res
            
            
    
              
                def
              
              
                isInt
              
              
                (
              
              self
              
                ,
              
               s
              
                ,
              
               case
              
                )
              
              
                :
              
              
                # 是否是整形数字,即“-+”在首位的0--9数字
              
              
                # case = 1:表示要判断的部分在数字的开头,此时可以仅有“-+”,而没有数字
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                if
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
              
                '+'
              
              
                or
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
              
                '-'
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                ==
              
              
                1
              
              
                and
              
               case
              
                :
              
              
                return
              
              
                True
              
              
                else
              
              
                :
              
              
                return
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                return
              
               self
              
                .
              
              scanInt
              
                (
              
              s
              
                [
              
              
                0
              
              
                :
              
              
                ]
              
              
                )
              
              
                def
              
              
                scanInt
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # 必须在0--9之间
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
        a 
              
                =
              
              
                [
              
              
                str
              
              
                (
              
              x
              
                )
              
              
                for
              
               x 
              
                in
              
              
                range
              
              
                (
              
              
                10
              
              
                )
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               s
              
                :
              
              
                if
              
              
                not
              
               i 
              
                in
              
               a
              
                :
              
              
                return
              
              
                False
              
              
                return
              
              
                True
              
            
          

21.调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                reOrderArray
              
              
                (
              
              self
              
                ,
              
               array
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
               array
        
              
                # write code here
              
              
        odd_number 
              
                =
              
              
                [
              
              
                ]
              
              
        even_number 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               array
              
                :
              
              
                if
              
               i
              
                %
              
              
                2
              
              
                ==
              
              
                1
              
              
                :
              
              
                odd_number
              
                .
              
              append
              
                (
              
              i
              
                )
              
              
                else
              
              
                :
              
              
                even_number
              
                .
              
              append
              
                (
              
              i
              
                )
              
              
                return
              
               odd_number
              
                +
              
              even_number

            
          

22.链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个结点

            
              
                # 方法1:先计数,在输出
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                FindKthToTail
              
              
                (
              
              self
              
                ,
              
               head
              
                ,
              
               k
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               head 
              
                is
              
              
                None
              
              
                or
              
               k 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                None
              
              
        
        count 
              
                =
              
              
                1
              
              
        temp 
              
                =
              
               head
        
              
                while
              
               temp
              
                .
              
              
                next
              
              
                !=
              
              
                None
              
              
                :
              
              
            count 
              
                +=
              
              
                1
              
              
            temp 
              
                =
              
               temp
              
                .
              
              
                next
              
              
                if
              
               count 
              
                <
              
               k
              
                :
              
              
                return
              
              
                None
              
              
                else
              
              
                :
              
              
            k 
              
                =
              
               count 
              
                -
              
               k
            count 
              
                =
              
              
                0
              
              
                while
              
               count 
              
                !=
              
               k
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                head 
              
                =
              
               head
              
                .
              
              
                next
              
              
                return
              
               head

            
          
            
              
                # 方法二:双指针法,使用两个间隔为k-1的指针
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                FindKthToTail
              
              
                (
              
              self
              
                ,
              
               head
              
                ,
              
               k
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               head 
              
                is
              
              
                None
              
              
                or
              
               k 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                None
              
              
        
        fP 
              
                =
              
               head
        sP 
              
                =
              
               head
        count 
              
                =
              
              
                0
              
              
                while
              
               count 
              
                <
              
               k
              
                :
              
              
                # 注意对fP是否为空的判断
              
              
                if
              
               fP 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
            fP 
              
                =
              
               fP
              
                .
              
              
                next
              
              
            count 
              
                +=
              
              
                1
              
              
                while
              
               fP 
              
                !=
              
              
                None
              
              
                :
              
              
            fP 
              
                =
              
               fP
              
                .
              
              
                next
              
              
            sP 
              
                =
              
               sP
              
                .
              
              
                next
              
              
                return
              
               sP

            
          

23.链表中环的入口节点

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

            
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                EntryNodeOfLoop
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
        
        node_num 
              
                =
              
               self
              
                .
              
              hasCircle
              
                (
              
              pHead
              
                )
              
              
                if
              
               node_num 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                None
              
              
                else
              
              
                :
              
              
                # 存在环,环中节点数为node_num,查找环的入口节点
              
              
            fP 
              
                =
              
               pHead 
              
                # first point
              
              
            sP 
              
                =
              
               pHead 
              
                # second point
              
              
            count 
              
                =
              
              
                0
              
              
                while
              
               count 
              
                <
              
               node_num
              
                :
              
              
                fP 
              
                =
              
               fP
              
                .
              
              
                next
              
              
                count 
              
                +=
              
              
                1
              
              
                while
              
               fP 
              
                !=
              
               sP
              
                :
              
              
                fP 
              
                =
              
               fP
              
                .
              
              
                next
              
              
                sP 
              
                =
              
               sP
              
                .
              
              
                next
              
              
                return
              
               sP
        
        
    
              
                def
              
              
                hasCircle
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # 判断是否存在circle,返回0表示不存在,返回正整数表示环中节点个数
              
              
        fast 
              
                =
              
               pHead
        slow 
              
                =
              
               pHead
        
        
              
                while
              
               fast 
              
                !=
              
              
                None
              
              
                :
              
              
                # fast 移动两步,slow移动一步
              
              
            fast 
              
                =
              
               fast
              
                .
              
              
                next
              
              
                if
              
               fast 
              
                ==
              
              
                None
              
              
                :
              
              
                break
              
              
            fast 
              
                =
              
               fast
              
                .
              
              
                next
              
              
            slow 
              
                =
              
               slow
              
                .
              
              
                next
              
              
                if
              
               fast 
              
                ==
              
               slow
              
                :
              
              
                # 存在环,统计环中节点的个数
              
              
                num 
              
                =
              
              
                1
              
              
                fast 
              
                =
              
               fast
              
                .
              
              
                next
              
              
                while
              
               fast 
              
                !=
              
               slow
              
                :
              
              
                    num 
              
                +=
              
              
                1
              
              
                    fast 
              
                =
              
               fast
              
                .
              
              
                next
              
              
                return
              
               num
        
              
                return
              
              
                0
              
            
          

24.反转链表

输入一个链表,反转链表后,输出新链表的表头。

            
              
                # 借助三个指针,一边遍历链表一边修改当前节点的指向,直到遍历完整个链表
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回ListNode
              
              
                def
              
              
                ReverseList
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
        
        previous_p 
              
                =
              
               pHead
        current_p 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                if
              
               current_p 
              
                is
              
              
                None
              
              
                :
              
              
                # 只有一个节点
              
              
                return
              
               pHead
        next_p 
              
                =
              
               current_p
              
                .
              
              
                next
              
              
                if
              
               next_p 
              
                is
              
              
                None
              
              
                :
              
              
                # 只有两个节点
              
              
            previous_p
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
            current_p
              
                .
              
              
                next
              
              
                =
              
               previous_p
            
              
                return
              
               current_p
        
        
              
                #节点数大于等于3,借助三个指针一边遍历一边修改指向
              
              
        previous_p
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
                while
              
               next_p 
              
                !=
              
              
                None
              
              
                :
              
              
            current_p
              
                .
              
              
                next
              
              
                =
              
               previous_p
            
              
                # 更新各个指针指向。向前移动
              
              
            previous_p 
              
                =
              
               current_p
            current_p 
              
                =
              
               next_p
            next_p 
              
                =
              
               next_p
              
                .
              
              
                next
              
              
        
        current_p
              
                .
              
              
                next
              
              
                =
              
               previous_p
        
        
              
                return
              
               current_p
            
            
        
        
        

            
          
            
              
                # 方法二:递归法实现,从尾部开始修改指向
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                ListNode
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                ,
              
               x
              
                )
              
              
                :
              
              
        self
              
                .
              
              val 
              
                =
              
               x
        self
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回ListNode
              
              
                def
              
              
                ReverseList
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
        
        previous_p 
              
                =
              
               pHead
        current_p 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                if
              
               current_p 
              
                is
              
              
                None
              
              
                :
              
              
                # 只有一个节点
              
              
                return
              
               pHead
        
        
              
                #节点数大于等于2,递归实现反转
              
              
        previous_p
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
                return
              
               self
              
                .
              
              Rev_recursion
              
                (
              
              previous_p
              
                ,
              
               current_p
              
                )
              
              
                def
              
              
                Rev_recursion
              
              
                (
              
              self
              
                ,
              
               pre
              
                ,
              
               cur
              
                )
              
              
                :
              
              
                # 递归终止条件:遍历至尾节点
              
              
                if
              
               cur
              
                .
              
              
                next
              
              
                is
              
              
                None
              
              
                :
              
              
            cur
              
                .
              
              
                next
              
              
                =
              
               pre
            
              
                return
              
               cur
        
        next_node 
              
                =
              
               cur
              
                .
              
              
                next
              
              
                # 保存当前节点下一节点的指向
              
              
        cur
              
                .
              
              
                next
              
              
                =
              
               pre  
              
                # 修改当前节点指向上一节点
              
              
                return
              
               self
              
                .
              
              Rev_recursion
              
                (
              
              cur
              
                ,
              
               next_node
              
                )
              
              
                def
              
              
                PrintList
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                while
              
               pHead
              
                .
              
              
                next
              
              
                !=
              
              
                None
              
              
                :
              
              
                print
              
              
                (
              
              pHead
              
                .
              
              val
              
                )
              
              
            pHead 
              
                =
              
              pHead
              
                .
              
              
                next
              
              
                print
              
              
                (
              
              pHead
              
                .
              
              val
              
                )
              
              
                # test
              
              
a 
              
                =
              
               ListNode
              
                (
              
              
                1
              
              
                )
              
              
b 
              
                =
              
               ListNode
              
                (
              
              
                2
              
              
                )
              
              
c 
              
                =
              
               ListNode
              
                (
              
              
                3
              
              
                )
              
              
d 
              
                =
              
               ListNode
              
                (
              
              
                4
              
              
                )
              
              
a
              
                .
              
              
                next
              
              
                =
              
               b
b
              
                .
              
              
                next
              
              
                =
              
               c
c
              
                .
              
              
                next
              
              
                =
              
               d

s
              
                =
              
              Solution
              
                (
              
              
                )
              
              
h 
              
                =
              
               s
              
                .
              
              ReverseList
              
                (
              
              a
              
                )
              
              
s
              
                .
              
              PrintList
              
                (
              
              h
              
                )
              
            
          
            
              4
3
2
1

            
          

25.合并两个排序链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

Tips:python对象如果是结构体或类,则把对象的引用值修改,那么原始对象的值也会被改变。

            
              
                # 方法1:确定头节点后,将另一个链表插入头节点所在的链表
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                ListNode
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                ,
              
               x
              
                )
              
              
                :
              
              
        self
              
                .
              
              val 
              
                =
              
               x
        self
              
                .
              
              
                next
              
              
                =
              
              
                None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回合并后列表
              
              
                def
              
              
                Merge
              
              
                (
              
              self
              
                ,
              
               pHead1
              
                ,
              
               pHead2
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead1 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
               pHead2
        
              
                elif
              
               pHead2 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
               pHead1
        
        
              
                # 确定头结点
              
              
                if
              
               pHead1
              
                .
              
              val 
              
                >
              
               pHead2
              
                .
              
              val
              
                :
              
              
            head 
              
                =
              
               self
              
                .
              
              insertMerge
              
                (
              
              pHead2
              
                ,
              
               pHead1
              
                )
              
              
                else
              
              
                :
              
              
            head 
              
                =
              
               self
              
                .
              
              insertMerge
              
                (
              
              pHead1
              
                ,
              
               pHead2
              
                )
              
              
                return
              
               head
    
              
                def
              
              
                insertMerge
              
              
                (
              
              self
              
                ,
              
               head
              
                ,
              
               insertL
              
                )
              
              
                :
              
              
                # head指头节点所在的链表,insertL链表中的元素将被插入head指向的链表
              
              
        pHead 
              
                =
              
               head
        insert_h 
              
                =
              
               insertL
        
              
                while
              
               pHead
              
                .
              
              
                next
              
              
                !=
              
              
                None
              
              
                :
              
              
            pre1 
              
                =
              
               pHead
            cur1 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
            insert_p 
              
                =
              
               insert_h
            
              
                if
              
               insert_p
              
                .
              
              val 
              
                <=
              
               cur1
              
                .
              
              val
              
                :
              
              
                # 介于两个节点之间,满足插入条件,插入后移动head所在链表和insertL链表
              
              
                # !!!!必须先更新,在重新连接节点,否则变量的值已经被改变
              
              
                # 如果按照注释中的顺序执行,则变量pHead和insert_h的值就会收到前面赋值的影响
              
              
                # 此处insert_h值的更新必须要在insert_p.next的赋值之前,因为结构体内部值的改变会间接改变原始变量的值
              
              
                #                 pre1.next = insert_p
              
              
                #                 insert_p.next = cur1
              
              
                #                 pHead = pHead.next
              
              
                #                 insert_h = insert_h.next
              
              
                
                pHead 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                insert_h 
              
                =
              
               insert_h
              
                .
              
              
                next
              
              
                
                pre1
              
                .
              
              
                next
              
              
                =
              
               insert_p
                insert_p
              
                .
              
              
                next
              
              
                =
              
               cur1
                
            
              
                else
              
              
                :
              
              
                # 不满足插入条件,移动head所在链表,insertL链表不动
              
              
                pHead 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                if
              
               insert_h 
              
                !=
              
              
                None
              
              
                :
              
              
            pHead
              
                .
              
              
                next
              
              
                =
              
               insert_h
            
        
              
                return
              
               head
    
    
              
                def
              
              
                PrintList
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                while
              
               pHead
              
                .
              
              
                next
              
              
                !=
              
              
                None
              
              
                :
              
              
                print
              
              
                (
              
              pHead
              
                .
              
              val
              
                )
              
              
            pHead 
              
                =
              
              pHead
              
                .
              
              
                next
              
              
                print
              
              
                (
              
              pHead
              
                .
              
              val
              
                )
              
              

a 
              
                =
              
               ListNode
              
                (
              
              
                1
              
              
                )
              
              
b 
              
                =
              
               ListNode
              
                (
              
              
                3
              
              
                )
              
              
c 
              
                =
              
               ListNode
              
                (
              
              
                5
              
              
                )
              
              
d 
              
                =
              
               ListNode
              
                (
              
              
                7
              
              
                )
              
              
a
              
                .
              
              
                next
              
              
                =
              
               b
b
              
                .
              
              
                next
              
              
                =
              
               c
c
              
                .
              
              
                next
              
              
                =
              
               d

e 
              
                =
              
               ListNode
              
                (
              
              
                2
              
              
                )
              
              
f 
              
                =
              
               ListNode
              
                (
              
              
                4
              
              
                )
              
              
g 
              
                =
              
               ListNode
              
                (
              
              
                6
              
              
                )
              
              
h 
              
                =
              
               ListNode
              
                (
              
              
                8
              
              
                )
              
               
e
              
                .
              
              
                next
              
              
                =
              
               f
f
              
                .
              
              
                next
              
              
                =
              
               g
g
              
                .
              
              
                next
              
              
                =
              
               h

s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
h 
              
                =
              
               s
              
                .
              
              Merge
              
                (
              
              a
              
                ,
              
               e
              
                )
              
              
                # s.PrintList(h)
              
            
          
            
              
                # 方法二:递归法
              
              
                # 只对两个链表的头节点进行重排,直到其中一个链表排至尾部时终止
              
              
                # -*- coding:utf-8 -*-
              
              
                # class ListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.next = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回合并后列表
              
              
                def
              
              
                Merge
              
              
                (
              
              self
              
                ,
              
               pHead1
              
                ,
              
               pHead2
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 递归终止条件
              
              
                if
              
               pHead1 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
               pHead2
        
              
                elif
              
               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


            
          

26.树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

            
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                HasSubtree
              
              
                (
              
              self
              
                ,
              
               pRoot1
              
                ,
              
               pRoot2
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 特殊边界情况判断
              
              
                if
              
               pRoot1 
              
                is
              
              
                None
              
              
                or
              
               pRoot2 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                False
              
              
        
        res 
              
                =
              
              
                False
              
              
                if
              
               pRoot1
              
                .
              
              val 
              
                ==
              
               pRoot2
              
                .
              
              val
              
                :
              
              
            res 
              
                =
              
               self
              
                .
              
              isEqual
              
                (
              
              pRoot1
              
                ,
              
               pRoot2
              
                )
              
              
                if
              
              
                not
              
               res
              
                :
              
              
                # 当前节点不相等则继续递归遍历树
              
              
                if
              
               pRoot1
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                res 
              
                =
              
               self
              
                .
              
              HasSubtree
              
                (
              
              pRoot1
              
                .
              
              left
              
                ,
              
               pRoot2
              
                )
              
              
                if
              
              
                not
              
               res 
              
                and
              
               pRoot1
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                res 
              
                =
              
               self
              
                .
              
              HasSubtree
              
                (
              
              pRoot1
              
                .
              
              right
              
                ,
              
               pRoot2
              
                )
              
              
                return
              
               res
    
    
              
                def
              
              
                isEqual
              
              
                (
              
              self
              
                ,
              
               pRoot1
              
                ,
              
               pRoot2
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
               pRoot2 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                True
              
              
                if
              
               pRoot1 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                False
              
              
                if
              
               pRoot2
              
                .
              
              val 
              
                ==
              
               pRoot1
              
                .
              
              val
              
                :
              
              
            res 
              
                =
              
               self
              
                .
              
              isEqual
              
                (
              
              pRoot1
              
                .
              
              left
              
                ,
              
               pRoot2
              
                .
              
              left
              
                )
              
              
                else
              
              
                :
              
              
                return
              
              
                False
              
              
                # 递归
              
              
        res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              isEqual
              
                (
              
              pRoot1
              
                .
              
              left
              
                ,
              
               pRoot2
              
                .
              
              left
              
                )
              
              
                and
              
               self
              
                .
              
              isEqual
              
                (
              
              pRoot1
              
                .
              
              right
              
                ,
              
               pRoot2
              
                .
              
              right
              
                )
              
              
                return
              
               res

            
          

27.二叉树的镜像

操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:
源二叉树

            
                  	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11

            
          

镜像二叉树

            
                  	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

            
          

非递归实现:

  • 借助于栈,先交换两棵子树,再求完一棵子树的镜像后在求还有一棵子树的镜像(纵向,深度优先)
  • 借助于队列以用广度优先的顺序遍历一遍实现逐层镜像(横向,广度优先)
            
              
                # 递归法
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回镜像树的根节点
              
              
                def
              
              
                Mirror
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 异常情况判断
              
              
                if
              
               root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                # 递归终止条件:遍历至非叶子节点
              
              
                if
              
               root
              
                .
              
              left 
              
                is
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                if
              
               root
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
            root
              
                .
              
              left
              
                ,
              
               root
              
                .
              
              right 
              
                =
              
               root
              
                .
              
              right
              
                ,
              
               root
              
                .
              
              left
            self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              left
              
                )
              
              
            self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              right
              
                )
              
              
                elif
              
               root
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                is
              
              
                None
              
              
                :
              
              
            root
              
                .
              
              left
              
                ,
              
               root
              
                .
              
              right 
              
                =
              
              
                None
              
              
                ,
              
               root
              
                .
              
              left
            self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              right
              
                )
              
              
                elif
              
               root
              
                .
              
              left 
              
                is
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
            root
              
                .
              
              left
              
                ,
              
               root
              
                .
              
              right 
              
                =
              
               root
              
                .
              
              right
              
                ,
              
              
                None
              
              
            self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              left
              
                )
              
              
                return
              
            
          
            
              
                # 更简洁的递归实现
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回镜像树的根节点
              
              
                def
              
              
                Mirror
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 异常情况判断
              
              
                if
              
               root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                # 递归终止条件:遍历至非叶子节点
              
              
                if
              
               root
              
                .
              
              left 
              
                is
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
        root
              
                .
              
              left
              
                ,
              
               root
              
                .
              
              right 
              
                =
              
               root
              
                .
              
              right
              
                ,
              
               root
              
                .
              
              left
        self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              left
              
                )
              
              
        self
              
                .
              
              Mirror
              
                (
              
              root
              
                .
              
              right
              
                )
              
              
                return
              
            
          

28.对称的二叉树

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

            
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                isSymmetrical
              
              
                (
              
              self
              
                ,
              
               pRoot
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 空树对称
              
              
                if
              
               pRoot 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                True
              
              
                return
              
               self
              
                .
              
              issymm_recursion
              
                (
              
              pRoot
              
                .
              
              left
              
                ,
              
               pRoot
              
                .
              
              right
              
                )
              
              
                def
              
              
                issymm_recursion
              
              
                (
              
              self
              
                ,
              
               left
              
                ,
              
               right
              
                )
              
              
                :
              
              
                # 如果左右节点均为None,则遍历结束,且满足对称
              
              
                if
              
               left 
              
                is
              
              
                None
              
              
                and
              
               right 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                True
              
              
                # 反之仅有一个节点为空则不满足对称
              
              
                if
              
               left 
              
                is
              
              
                None
              
              
                or
              
               right 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                False
              
              
                # 当两个节点均不为空时,对其值进行判断
              
              
        res 
              
                =
              
              
                False
              
              
                if
              
               left
              
                .
              
              val 
              
                ==
              
               right
              
                .
              
              val
              
                :
              
              
                # 两个节点的值相等时,对其子节点进行递归判断
              
              
                # 对称前序遍历递归实现
              
              
            res 
              
                =
              
               self
              
                .
              
              issymm_recursion
              
                (
              
              left
              
                .
              
              left
              
                ,
              
               right
              
                .
              
              right
              
                )
              
              
            res 
              
                =
              
               res 
              
                and
              
               self
              
                .
              
              issymm_recursion
              
                (
              
              left
              
                .
              
              right
              
                ,
              
               right
              
                .
              
              left
              
                )
              
              
                return
              
               res
        

            
          
            
              
                # 更简洁的参考实现:
              
              
                # https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/58-%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91.py
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                isSymmetrical
              
              
                (
              
              self
              
                ,
              
               pRoot
              
                )
              
              
                :
              
              
                # write code here
              
              
                return
              
               self
              
                .
              
              selfIsSym
              
                (
              
              pRoot
              
                ,
              
              pRoot
              
                )
              
              
                def
              
              
                selfIsSym
              
              
                (
              
              self
              
                ,
              
              root1
              
                ,
              
              root2
              
                )
              
              
                :
              
              
                if
              
               root1 
              
                ==
              
               root2 
              
                and
              
               root2 
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
              
                True
              
              
                if
              
               root1 
              
                ==
              
              
                None
              
              
                or
              
               root2 
              
                ==
              
              
                None
              
              
                :
              
              
                return
              
              
                False
              
              
                if
              
               root1
              
                .
              
              val 
              
                !=
              
               root2
              
                .
              
              val
              
                :
              
              
                return
              
              
                False
              
              
                return
              
               self
              
                .
              
              selfIsSym
              
                (
              
              root1
              
                .
              
              left
              
                ,
              
               root2
              
                .
              
              right
              
                )
              
              
                and
              
               self
              
                .
              
              selfIsSym
              
                (
              
              root1
              
                .
              
              right
              
                ,
              
              root2
              
                .
              
              left
              
                )
              
            
          

29.顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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.

            
              
                # 方法一:借助四个数指定打印范围
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # matrix类型为二维列表,需要返回列表
              
              
                def
              
              
                printMatrix
              
              
                (
              
              self
              
                ,
              
               matrix
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              matrix
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              
                if
              
              
                len
              
              
                (
              
              matrix
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
            m 
              
                =
              
              
                [
              
              x
              
                [
              
              
                0
              
              
                ]
              
              
                for
              
               x 
              
                in
              
               matrix
              
                ]
              
              
                return
              
               m
        row_len 
              
                =
              
              
                len
              
              
                (
              
              matrix
              
                )
              
              
                # 行
              
              
        col_len 
              
                =
              
              
                len
              
              
                (
              
              matrix
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                # 列
              
              
                # 四个数确定打印的边界
              
              
        a
              
                ,
              
               b
              
                ,
              
               c
              
                ,
              
               d 
              
                =
              
              
                0
              
              
                ,
              
               row_len
              
                -
              
              
                1
              
              
                ,
              
              
                0
              
              
                ,
              
               col_len
              
                -
              
              
                1
              
              
        
        m 
              
                =
              
              
                [
              
              
                ]
              
              
                while
              
               a 
              
                <=
              
               b 
              
                and
              
               c 
              
                <=
              
               d
              
                :
              
              
                # 在当前边界条件下打印一次
              
              
            m 
              
                =
              
               m 
              
                +
              
               self
              
                .
              
              Print
              
                (
              
              matrix
              
                ,
              
               a
              
                ,
              
               b
              
                ,
              
               c
              
                ,
              
               d
              
                )
              
              
                # 更新边界
              
              
            a 
              
                +=
              
              
                1
              
              
            b 
              
                -=
              
              
                1
              
              
            c 
              
                +=
              
              
                1
              
              
            d 
              
                -=
              
              
                1
              
              
                return
              
               m
    
    
              
                def
              
              
                Print
              
              
                (
              
              self
              
                ,
              
               matrix
              
                ,
              
               a
              
                ,
              
               b
              
                ,
              
               c
              
                ,
              
               d
              
                )
              
              
                :
              
              
        m 
              
                =
              
              
                [
              
              
                ]
              
              
                # 打印过程为:先横向右移,再纵向下移,再横向左移,最后纵向上移
              
              
        m 
              
                =
              
               matrix
              
                [
              
              a
              
                ]
              
              
                [
              
              c
              
                :
              
              d
              
                +
              
              
                1
              
              
                ]
              
              
                # 横向右移打印
              
              
                # 如果a=b,则只需要横向打印一次即完成打印
              
              
                if
              
               a 
              
                ==
              
               b
              
                :
              
              
                return
              
               m
        m 
              
                =
              
               m 
              
                +
              
              
                [
              
              x
              
                [
              
              d
              
                ]
              
              
                for
              
               x 
              
                in
              
               matrix
              
                [
              
              a
              
                +
              
              
                1
              
              
                :
              
              b
              
                +
              
              
                1
              
              
                ]
              
              
                ]
              
              
                # 纵向下移打印
              
              
                if
              
               c 
              
                ==
              
              
                0
              
              
                :
              
              
                #横向左移打印
              
              
            m 
              
                =
              
               m 
              
                +
              
              
                (
              
              matrix
              
                [
              
              b
              
                ]
              
              
                [
              
              d
              
                -
              
              
                1
              
              
                :
              
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
            m 
              
                =
              
               m 
              
                +
              
              
                (
              
              matrix
              
                [
              
              b
              
                ]
              
              
                [
              
              d
              
                -
              
              
                1
              
              
                :
              
              c
              
                -
              
              
                1
              
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
        
        m 
              
                =
              
               m 
              
                +
              
              
                (
              
              
                [
              
              x
              
                [
              
              c
              
                ]
              
              
                for
              
               x 
              
                in
              
               matrix
              
                [
              
              b
              
                -
              
              
                1
              
              
                :
              
              a
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                ]
              
              
                )
              
              
                # 纵向上移打印
              
              
                return
              
               m

s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
a 
              
                =
              
              
                [
              
              
                [
              
              
                1
              
              
                ,
              
              
                2
              
              
                ]
              
              
                ,
              
              
                [
              
              
                3
              
              
                ,
              
              
                4
              
              
                ]
              
              
                ]
              
              
s
              
                .
              
              printMatrix
              
                (
              
              a
              
                )
              
            
          
            
              [1, 2, 4, 3]

            
          
            
              
                # 方法二:根据规律左上角的坐标中行标和列标总是相等的
              
              
                # 参考代码
              
              
                # https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/19-%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5.py
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # matrix类型为二维列表,需要返回列表
              
              
                def
              
              
                printMatrix
              
              
                (
              
              self
              
                ,
              
               matrix
              
                )
              
              
                :
              
              
                if
              
              
                not
              
               matrix
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        
        rows 
              
                =
              
              
                len
              
              
                (
              
              matrix
              
                )
              
              
        columns 
              
                =
              
              
                len
              
              
                (
              
              matrix
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
        start 
              
                =
              
              
                0
              
              
        result 
              
                =
              
              
                [
              
              
                ]
              
              
                while
              
               rows 
              
                >
              
               start 
              
                *
              
              
                2
              
              
                and
              
               columns 
              
                >
              
               start 
              
                *
              
              
                2
              
              
                :
              
              
            self
              
                .
              
              PrintMatrixInCircle
              
                (
              
              matrix
              
                ,
              
               columns
              
                ,
              
               rows
              
                ,
              
               start
              
                ,
              
              result
              
                )
              
              
            start 
              
                +=
              
              
                1
              
              
                return
              
               result    
            
    
              
                def
              
              
                PrintMatrixInCircle
              
              
                (
              
              self
              
                ,
              
               matrix
              
                ,
              
               columns
              
                ,
              
               rows
              
                ,
              
              start
              
                ,
              
              result
              
                )
              
              
                :
              
              
        endX 
              
                =
              
               columns 
              
                -
              
              
                1
              
              
                -
              
               start
        endY 
              
                =
              
               rows 
              
                -
              
              
                1
              
              
                -
              
               start

        
              
                # 从左到右打印一行
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              start
              
                ,
              
               endX
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                #number = matrix[start][i]
              
              
            result
              
                .
              
              append
              
                (
              
              matrix
              
                [
              
              start
              
                ]
              
              
                [
              
              i
              
                ]
              
              
                )
              
              
                # 从上到下打印一行
              
              
                if
              
               start 
              
                <
              
               endY
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              start
              
                +
              
              
                1
              
              
                ,
              
               endY
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                #number = matrix[i][endX]
              
              
                result
              
                .
              
              append
              
                (
              
              matrix
              
                [
              
              i
              
                ]
              
              
                [
              
              endX
              
                ]
              
              
                )
              
              
                # 从右到左打印一行
              
              
                if
              
               start 
              
                <
              
               endX 
              
                and
              
               start 
              
                <
              
               endY
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              endX
              
                -
              
              
                1
              
              
                ,
              
               start
              
                -
              
              
                1
              
              
                ,
              
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                #number = matrix[endY][i]
              
              
                result
              
                .
              
              append
              
                (
              
              matrix
              
                [
              
              endY
              
                ]
              
              
                [
              
              i
              
                ]
              
              
                )
              
              
                # 从下到上打印一行
              
              
                if
              
               start 
              
                <
              
               endX 
              
                and
              
               start 
              
                <
              
               endY
              
                -
              
              
                1
              
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              endY
              
                -
              
              
                1
              
              
                ,
              
               start
              
                ,
              
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                #number = matrix[i][start]
              
              
                result
              
                .
              
              append
              
                (
              
              matrix
              
                [
              
              i
              
                ]
              
              
                [
              
              start
              
                ]
              
              
                )
              
            
          

30.包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

            
              
                # 借助辅助栈实现
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                )
              
              
                :
              
              
        self
              
                .
              
              stack 
              
                =
              
              
                [
              
              
                ]
              
              
        self
              
                .
              
              assist_stack 
              
                =
              
              
                [
              
              
                ]
              
              
                def
              
              
                push
              
              
                (
              
              self
              
                ,
              
               node
              
                )
              
              
                :
              
              
                # write code here
              
              
        self
              
                .
              
              stack
              
                .
              
              append
              
                (
              
              node
              
                )
              
              
                if
              
              
                len
              
              
                (
              
              self
              
                .
              
              assist_stack
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
            self
              
                .
              
              assist_stack
              
                .
              
              append
              
                (
              
              node
              
                )
              
              
                elif
              
               node 
              
                <
              
               self
              
                .
              
              assist_stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
            self
              
                .
              
              assist_stack
              
                .
              
              append
              
                (
              
              node
              
                )
              
              
                else
              
              
                :
              
              
            self
              
                .
              
              assist_stack
              
                .
              
              append
              
                (
              
              self
              
                .
              
              assist_stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
                def
              
              
                pop
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              self
              
                .
              
              stack
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              
                else
              
              
                :
              
              
            self
              
                .
              
              assist_stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                return
              
               self
              
                .
              
              stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                def
              
              
                top
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                # write code here
              
              
                return
              
               self
              
                .
              
              stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                def
              
              
                min
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                # write code here
              
              
                return
              
               self
              
                .
              
              assist_stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
            
          

31.栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

            
              
                # 方法:借助辅助栈实现
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                IsPopOrder
              
              
                (
              
              self
              
                ,
              
               pushV
              
                ,
              
               popV
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              pushV
              
                )
              
              
                !=
              
              
                len
              
              
                (
              
              popV
              
                )
              
              
                :
              
              
                return
              
              
                False
              
              
                elif
              
              
                len
              
              
                (
              
              pushV
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                True
              
              
        
        stack 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               popV
              
                :
              
              
                # 辅助栈为空时,根据情况向辅助栈压入一个元素
              
              
                if
              
              
                len
              
              
                (
              
              stack
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              pushV
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                False
              
              
                else
              
              
                :
              
              
                    stack
              
                .
              
              append
              
                (
              
              pushV
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                )
              
              
                while
              
               i 
              
                !=
              
               stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                # 判断辅助栈栈顶元素是否和当前弹出元素相等,不相等则将压入序列中元素不断压入辅助栈,直到发现相等元素
              
              
                if
              
              
                len
              
              
                (
              
              pushV
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                # 如果压入序列为空,则没有元素可以匹配,所以不满足弹出顺序
              
              
                return
              
              
                False
              
              
                else
              
              
                :
              
              
                    stack
              
                .
              
              append
              
                (
              
              pushV
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                )
              
              
                # 如果弹出序列和辅助栈栈顶元素相等则,将辅助栈栈顶元素弹出
              
              
            stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                return
              
              
                True
              
            
          
            
              
                # 参考实现
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                IsPopOrder
              
              
                (
              
              self
              
                ,
              
               pushV
              
                ,
              
               popV
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pushV 
              
                ==
              
              
                [
              
              
                ]
              
              
                or
              
               popV 
              
                ==
              
              
                [
              
              
                ]
              
              
                :
              
              
                return
              
              
                False
              
              
        
        stack 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               pushV
              
                :
              
              
            stack
              
                .
              
              append
              
                (
              
              i
              
                )
              
              
                while
              
              
                len
              
              
                (
              
              stack
              
                )
              
              
                and
              
               stack
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                ==
              
               popV
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                popV
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                if
              
              
                len
              
              
                (
              
              stack
              
                )
              
              
                :
              
              
                return
              
              
                False
              
              
                else
              
              
                :
              
              
                return
              
              
                True
              
            
          

32.从上到下打印二叉树

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

            
              
                # 方法:借助辅助队列实现
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回从上到下每个节点值列表,例:[1,2,3]
              
              
                def
              
              
                PrintFromTopToBottom
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        
        que 
              
                =
              
              
                [
              
              
                ]
              
              
        res 
              
                =
              
              
                [
              
              
                ]
              
              
        que
              
                .
              
              append
              
                (
              
              root
              
                )
              
              
                while
              
              
                len
              
              
                (
              
              que
              
                )
              
              
                >=
              
              
                1
              
              
                :
              
              
            node 
              
                =
              
               que
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
            res
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                if
              
               node
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
                return
              
               res

        

            
          

32.2 把二叉树打印成多行

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

            
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回二维列表[[1,2],[4,5]]
              
              
                def
              
              
                Print
              
              
                (
              
              self
              
                ,
              
               pRoot
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pRoot 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        
        que1 
              
                =
              
              
                [
              
              
                ]
              
              
                # 存储每行元素构成的队列,que1是二维数组
              
              
        que2 
              
                =
              
              
                [
              
              
                ]
              
              
                # 将一行元素作为队列存储
              
              
        
        que2
              
                .
              
              append
              
                (
              
              pRoot
              
                )
              
              
        que1
              
                .
              
              append
              
                (
              
              que2
              
                )
              
              
        
        res 
              
                =
              
              
                [
              
              
                ]
              
              
                # 存储最终结果,是二维数组
              
              
        res1 
              
                =
              
              
                [
              
              
                ]
              
              
                # 存储每一行打印的结果
              
              
                while
              
              
                len
              
              
                (
              
              que1
              
                )
              
              
                >=
              
              
                1
              
              
                :
              
              
                # 打印所有行
              
              
            nodes 
              
                =
              
               que1
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
            que2 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               node 
              
                in
              
               nodes
              
                :
              
              
                # 打印一行
              
              
                res1
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                if
              
               node
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                    que2
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                    que2
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
                if
              
              
                len
              
              
                (
              
              que2
              
                )
              
              
                >=
              
              
                1
              
              
                :
              
              
                que1
              
                .
              
              append
              
                (
              
              que2
              
                )
              
              
                # 存储当前行打印的结果
              
              
            res
              
                .
              
              append
              
                (
              
              res1
              
                )
              
              
            res1 
              
                =
              
              
                [
              
              
                ]
              
              
                return
              
               res

            
          

32.3 之字形打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

            
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Print
              
              
                (
              
              self
              
                ,
              
               pRoot
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pRoot 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        
        count 
              
                =
              
              
                1
              
              
                # 打印层数记录
              
              
        res
              
                ,
              
               res1 
              
                =
              
              
                [
              
              
                ]
              
              
                ,
              
              
                [
              
              
                ]
              
              
        nodes 
              
                =
              
              
                [
              
              pRoot
              
                ]
              
              
                while
              
               nodes
              
                :
              
              
            que 
              
                =
              
              
                [
              
              
                ]
              
              
                if
              
               count 
              
                %
              
              
                2
              
              
                ==
              
              
                1
              
              
                :
              
              
                for
              
               node 
              
                in
              
               nodes
              
                :
              
              
                    res1
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                # 节点存储顺序由左至右,然后翻转
              
              
                if
              
               node
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                        que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                        que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
                else
              
              
                :
              
              
                for
              
               node 
              
                in
              
               nodes
              
                :
              
              
                    res1
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                # 节点存储顺序由右至左,然后翻转
              
              
                if
              
               node
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                        que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
                if
              
               node
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                        que
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              

            nodes 
              
                =
              
               que
              
                [
              
              
                :
              
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
            res
              
                .
              
              append
              
                (
              
              res1
              
                )
              
              
            res1 
              
                =
              
              
                [
              
              
                ]
              
              
            count 
              
                +=
              
              
                1
              
              
                return
              
               res

            
          

33.二叉搜索树的后续遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

            
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                VerifySquenceOfBST
              
              
                (
              
              self
              
                ,
              
               sequence
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              sequence
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                False
              
              
                return
              
               self
              
                .
              
              recursion_verify
              
                (
              
              sequence
              
                )
              
              
                def
              
              
                recursion_verify
              
              
                (
              
              self
              
                ,
              
               sequence
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              sequence
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
              
                True
              
              
        
        root 
              
                =
              
               sequence
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              sequence
              
                )
              
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                if
              
               sequence
              
                [
              
              i
              
                ]
              
              
                >
              
               root
              
                :
              
              
                break
              
              
                # 如果只有左子树,仅对左子树递归判断
              
              
                if
              
               i 
              
                ==
              
              
                len
              
              
                (
              
              sequence
              
                )
              
              
                -
              
              
                2
              
              
                :
              
              
                return
              
               self
              
                .
              
              recursion_verify
              
                (
              
              sequence
              
                [
              
              
                0
              
              
                :
              
              i
              
                ]
              
              
                )
              
              
                for
              
               j 
              
                in
              
               sequence
              
                [
              
              i
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                if
              
               j 
              
                <
              
               root
              
                :
              
              
                return
              
              
                False
              
              
                # 左右子树都有节点,则对左右子树递归判断
              
              
                return
              
               self
              
                .
              
              recursion_verify
              
                (
              
              sequence
              
                [
              
              
                0
              
              
                :
              
              i
              
                ]
              
              
                )
              
              
                and
              
               self
              
                .
              
              recursion_verify
              
                (
              
              sequence
              
                [
              
              i
              
                :
              
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
    
s
              
                =
              
              Solution
              
                (
              
              
                )
              
              
                # a = [4,8,6,12,16,14,10]
              
              
a 
              
                =
              
              
                [
              
              
                5
              
              
                ,
              
              
                4
              
              
                ,
              
              
                3
              
              
                ,
              
              
                2
              
              
                ,
              
              
                1
              
              
                ]
              
              
                print
              
              
                (
              
              s
              
                .
              
              VerifySquenceOfBST
              
                (
              
              a
              
                )
              
              
                )
              
            
          
            
              True

            
          

34.二叉树中和为某一值的函数

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

            
              
                # 方法:递归法
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回二维列表,内部每个列表表示找到的路径
              
              
                def
              
              
                FindPath
              
              
                (
              
              self
              
                ,
              
               root
              
                ,
              
               expectNumber
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        stack 
              
                =
              
              
                [
              
              
                ]
              
              
                # 辅助栈,存储路径节点
              
              
        path 
              
                =
              
              
                [
              
              
                ]
              
              
                # 存储路径
              
              
        sums 
              
                =
              
               root
              
                .
              
              val 
              
                # 和值
              
              
        stack
              
                .
              
              append
              
                (
              
              root
              
                )
              
              
        
        res 
              
                =
              
               self
              
                .
              
              recursion_find
              
                (
              
              root
              
                ,
              
               expectNumber
              
                ,
              
               stack
              
                ,
              
               sums
              
                ,
              
               path
              
                )
              
              
                return
              
               res
    
    
              
                def
              
              
                recursion_find
              
              
                (
              
              self
              
                ,
              
               root
              
                ,
              
               expectNumber
              
                ,
              
               stack
              
                ,
              
               sums
              
                ,
              
               path
              
                )
              
              
                :
              
              
                # 递归终止条件:递归至叶节点
              
              
                # 或只有根节点的情况
              
              
                if
              
               root
              
                .
              
              left 
              
                is
              
              
                None
              
              
                and
              
               root
              
                .
              
              right 
              
                is
              
              
                None
              
              
                :
              
              
                if
              
               sums 
              
                ==
              
               expectNumber
              
                :
              
              
                res 
              
                =
              
              
                [
              
              x
              
                .
              
              val 
              
                for
              
               x 
              
                in
              
               stack
              
                ]
              
              
                # 将路径节点转换为值列表
              
              
                path
              
                .
              
              append
              
                (
              
              res
              
                )
              
              
                return
              
               path
            
              
                else
              
              
                :
              
              
                return
              
               path
        
              
                else
              
              
                :
              
              
                #VLR前序递归
              
              
                if
              
               root
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                # 递归左节点
              
              
                stack
              
                .
              
              append
              
                (
              
              root
              
                .
              
              left
              
                )
              
              
                sums 
              
                +=
              
               root
              
                .
              
              left
              
                .
              
              val 
                self
              
                .
              
              recursion_find
              
                (
              
              root
              
                .
              
              left
              
                ,
              
               expectNumber
              
                ,
              
               stack
              
                ,
              
               sums
              
                ,
              
               path
              
                )
              
              
                stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                # 一次递归结束后弹出当前节点,并恢复原来的和值
              
              
                sums 
              
                -=
              
               root
              
                .
              
              left
              
                .
              
              val

            
              
                if
              
               root
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                # 递归右节点
              
              
                stack
              
                .
              
              append
              
                (
              
              root
              
                .
              
              right
              
                )
              
              
                sums 
              
                +=
              
               root
              
                .
              
              right
              
                .
              
              val
                self
              
                .
              
              recursion_find
              
                (
              
              root
              
                .
              
              right
              
                ,
              
               expectNumber
              
                ,
              
               stack
              
                ,
              
               sums
              
                ,
              
               path
              
                )
              
              
                stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
                # 一次递归结束后弹出当前节点,并恢复原来的和值
              
              
                sums 
              
                -=
              
               root
              
                .
              
              right
              
                .
              
              val
        
        
              
                return
              
              
                sorted
              
              
                (
              
              path
              
                ,
              
               key
              
                =
              
              
                lambda
              
               x
              
                :
              
              
                -
              
              
                len
              
              
                (
              
              x
              
                )
              
              
                )
              
              
                # 降序排列
              
            
          
            
              
                # 参考解法
              
              
                # https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/24-%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84.py
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回二维列表,内部每个列表表示找到的路径
              
              
                def
              
              
                FindPath
              
              
                (
              
              self
              
                ,
              
               root
              
                ,
              
               expectNumber
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                not
              
               root 
              
                or
              
               root
              
                .
              
              val 
              
                >
              
               expectNumber
              
                :
              
              
                # 没有找到路径,递归终止
              
              
                return
              
              
                [
              
              
                ]
              
              
                if
              
              
                not
              
               root
              
                .
              
              left 
              
                and
              
              
                not
              
               root
              
                .
              
              right 
              
                and
              
               root
              
                .
              
              val 
              
                ==
              
               expectNumber
              
                :
              
              
                # 找到路径
              
              
                return
              
              
                [
              
              
                [
              
              root
              
                .
              
              val
              
                ]
              
              
                ]
              
              
                else
              
              
                :
              
              
            expectNumber 
              
                -=
              
               root
              
                .
              
              val
            left 
              
                =
              
               self
              
                .
              
              FindPath
              
                (
              
              root
              
                .
              
              left
              
                ,
              
              expectNumber
              
                )
              
              
            right 
              
                =
              
               self
              
                .
              
              FindPath
              
                (
              
              root
              
                .
              
              right
              
                ,
              
              expectNumber
              
                )
              
              
            
            result 
              
                =
              
              
                [
              
              
                [
              
              root
              
                .
              
              val
              
                ]
              
              
                +
              
              i 
              
                for
              
               i 
              
                in
              
               left
              
                ]
              
              
                for
              
               i 
              
                in
              
               right
              
                :
              
              
                result
              
                .
              
              append
              
                (
              
              
                [
              
              root
              
                .
              
              val
              
                ]
              
              
                +
              
              i
              
                )
              
              
                return
              
              
                sorted
              
              
                (
              
              result
              
                ,
              
               key
              
                =
              
              
                lambda
              
               x
              
                :
              
              
                -
              
              
                len
              
              
                (
              
              x
              
                )
              
              
                )
              
            
          

35.复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

            
              
                # 解法一: 分两步:第一步:顺序复制链表,第二步:复制特殊指针,每次从原始链表头部开始遍历查找特殊指针的位置
              
              
                # 时间复杂度:O(n^2)
              
              
                # -*- coding:utf-8 -*-
              
              
                # class RandomListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.label = x
              
              
                #         self.next = None
              
              
                #         self.random = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回 RandomListNode
              
              
                def
              
              
                Clone
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
        
        pH_new_c 
              
                =
              
               RandomListNode
              
                (
              
              pHead
              
                .
              
              label
              
                )
              
              
                # 复制链表的头结点
              
              
        pH_new 
              
                =
              
               pH_new_c 
              
                # 定义临时变量,用于遍历
              
              
        next_node 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                # 定义临时变量,用于遍历
              
              
                # 先顺序复制
              
              
                while
              
               next_node 
              
                !=
              
              
                None
              
              
                :
              
              
            copy_next_node 
              
                =
              
               RandomListNode
              
                (
              
              next_node
              
                .
              
              label
              
                )
              
              
            pH_new
              
                .
              
              
                next
              
              
                =
              
               copy_next_node
            
            next_node 
              
                =
              
               next_node
              
                .
              
              
                next
              
              
            pH_new 
              
                =
              
               copy_next_node
        
        
              
                # 复制特殊指针
              
              
        pH_new 
              
                =
              
               pH_new_c 
              
                # 临时变量,用于遍历
              
              
        next_node 
              
                =
              
               pHead
        rand_node 
              
                =
              
               pHead
              
                .
              
              random
        
              
                while
              
               next_node 
              
                !=
              
              
                None
              
              
                :
              
              
            rand_node 
              
                =
              
               next_node
              
                .
              
              random
            
              
                if
              
               rand_node 
              
                ==
              
              
                None
              
              
                :
              
              
                pH_new
              
                .
              
              random 
              
                =
              
              
                None
              
              
                else
              
              
                :
              
              
                temp 
              
                =
              
               pHead  
              
                # 原始头结点
              
              
                copy_random 
              
                =
              
               pH_new_c 
              
                # 复制链表的头结点
              
              
                # 同时遍历原始链表和复制链表,寻找复制链表中特殊指针指向的节点
              
              
                while
              
               temp 
              
                !=
              
              
                None
              
              
                :
              
              
                if
              
               temp
              
                .
              
              label 
              
                ==
              
               rand_node
              
                .
              
              label
              
                :
              
              
                # 找到特殊指针指向的节点
              
              
                break
              
              
                else
              
              
                :
              
              
                        temp 
              
                =
              
               temp
              
                .
              
              
                next
              
              
                        copy_random 
              
                =
              
               copy_random
              
                .
              
              
                next
              
              
                pH_new
              
                .
              
              random 
              
                =
              
               copy_random 
              
                # 给复制链表当前节点的特殊指针赋值
              
              
                # 进行下个节点特殊指针的赋值
              
              
            next_node 
              
                =
              
               next_node
              
                .
              
              
                next
              
              
            pH_new 
              
                =
              
               pH_new
              
                .
              
              
                next
              
              
                return
              
               pH_new_c

            
          
            
              
                # 解法二:时间换空间法,借助哈希表存储当前节点和特殊指针之间的对应关系
              
              
                # 时间和空间复杂度均为:O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                # class RandomListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.label = x
              
              
                #         self.next = None
              
              
                #         self.random = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回 RandomListNode
              
              
                def
              
              
                Clone
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
        
        pH_new_c 
              
                =
              
               RandomListNode
              
                (
              
              pHead
              
                .
              
              label
              
                )
              
              
                # 复制链表的头结点
              
              
        pH_new 
              
                =
              
               pH_new_c 
              
                # 定义临时变量,用于遍历
              
              
        next_node 
              
                =
              
               pHead
              
                .
              
              
                next
              
              
                # 定义临时变量,用于遍历
              
              
        
        N_Nc 
              
                =
              
              
                {
              
              
                }
              
              
                # 定义字典,存储赋值前--赋值后节点对
              
              
        N_Nc
              
                [
              
              pHead
              
                .
              
              label
              
                ]
              
              
                =
              
               pH_new
        
        
              
                # 先顺序复制
              
              
                while
              
               next_node 
              
                !=
              
              
                None
              
              
                :
              
              
            copy_next_node 
              
                =
              
               RandomListNode
              
                (
              
              next_node
              
                .
              
              label
              
                )
              
              
            pH_new
              
                .
              
              
                next
              
              
                =
              
               copy_next_node
            N_Nc
              
                [
              
              next_node
              
                .
              
              label
              
                ]
              
              
                =
              
               copy_next_node 
              
                # 存储赋值前--赋值后节点对
              
              
            
            next_node 
              
                =
              
               next_node
              
                .
              
              
                next
              
              
            pH_new 
              
                =
              
               copy_next_node
        
        
              
                # 复制特殊指针
              
              
        pH_new 
              
                =
              
               pH_new_c 
              
                # 临时变量,用于遍历
              
              
        next_node 
              
                =
              
               pHead
        rand_node 
              
                =
              
               pHead
              
                .
              
              random
        
              
                while
              
               next_node 
              
                !=
              
              
                None
              
              
                :
              
              
            rand_node 
              
                =
              
               next_node
              
                .
              
              random
            
              
                if
              
               rand_node 
              
                ==
              
              
                None
              
              
                :
              
              
                pH_new
              
                .
              
              random 
              
                =
              
              
                None
              
              
                else
              
              
                :
              
              
                # 借助哈希表存储的赋值前--赋值后节点对,给复制链表当前节点的特殊指针赋值
              
              
                pH_new
              
                .
              
              random 
              
                =
              
               N_Nc
              
                [
              
              rand_node
              
                .
              
              label
              
                ]
              
              
                # 进行下个节点特殊指针的赋值
              
              
            next_node 
              
                =
              
               next_node
              
                .
              
              
                next
              
              
            pH_new 
              
                =
              
               pH_new
              
                .
              
              
                next
              
              
                return
              
               pH_new_c

            
          
            
              
                # 解法三:不使用辅助空间,在原始链表上添加复制链表成为一个长链表,然后拆分出复制链表
              
              
                # -*- coding:utf-8 -*-
              
              
                # class RandomListNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.label = x
              
              
                #         self.next = None
              
              
                #         self.random = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                # 返回 RandomListNode
              
              
                def
              
              
                Clone
              
              
                (
              
              self
              
                ,
              
               pHead
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pHead 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              

        node 
              
                =
              
               pHead 
              
                # 定义临时变量,用于遍历
              
              
                # 先顺序复制,将复制的节点接在原始节点后面,得到一个长链表
              
              
                while
              
               node 
              
                !=
              
              
                None
              
              
                :
              
              
            next_node 
              
                =
              
               node
              
                .
              
              
                next
              
              
            copy_next_node 
              
                =
              
               RandomListNode
              
                (
              
              node
              
                .
              
              label
              
                )
              
              
            copy_next_node
              
                .
              
              
                next
              
              
                =
              
               next_node
            
            node
              
                .
              
              
                next
              
              
                =
              
               copy_next_node
            node 
              
                =
              
               next_node
        
        node 
              
                =
              
               pHead
        
              
                while
              
               node 
              
                !=
              
              
                None
              
              
                :
              
              
            next_node 
              
                =
              
               node
              
                .
              
              
                next
              
              
                if
              
               node
              
                .
              
              random 
              
                !=
              
              
                None
              
              
                :
              
              
                next_node
              
                .
              
              random 
              
                =
              
               node
              
                .
              
              random
              
                .
              
              
                next
              
              

            node 
              
                =
              
               next_node
              
                .
              
              
                next
              
              
        
        node 
              
                =
              
               pHead
        pH_new 
              
                =
              
               pH_new_c 
              
                =
              
               node
              
                .
              
              
                next
              
              
                # 复制链表的头节点
              
              
        node
              
                .
              
              
                next
              
              
                =
              
               pH_new
              
                .
              
              
                next
              
              
                # 需要借助node.next进行节点的赋值
              
              
        node 
              
                =
              
               node
              
                .
              
              
                next
              
              
                while
              
               node 
              
                !=
              
              
                None
              
              
                :
              
              
            pH_new_c
              
                .
              
              
                next
              
              
                =
              
               node
              
                .
              
              
                next
              
              
                # 复制节点
              
              
            pH_new_c 
              
                =
              
               pH_new_c
              
                .
              
              
                next
              
              
                # 复制节点
              
              
            node
              
                .
              
              
                next
              
              
                =
              
               pH_new_c
              
                .
              
              
                next
              
              
                # 原始节点,需要借助node.next进行节点的赋值
              
              
            node 
              
                =
              
               node
              
                .
              
              
                next
              
              
                #原始节点
              
              
                return
              
               pH_new

            
          

36.二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

            
              
                # 方法:将二叉搜索树的左右节点分别重置为双向链表的向前、向后指针
              
              
                # 使用LVR递归遍历实现
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Convert
              
              
                (
              
              self
              
                ,
              
               pRootOfTree
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               pRootOfTree 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
                return
              
               self
              
                .
              
              recursion_modify
              
                (
              
              pRootOfTree
              
                )
              
              
                def
              
              
                recursion_modify
              
              
                (
              
              self
              
                ,
              
               pRoot
              
                )
              
              
                :
              
              
                if
              
               pRoot 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                None
              
              
                if
              
               pRoot
              
                .
              
              left 
              
                is
              
              
                None
              
              
                and
              
               pRoot
              
                .
              
              right 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
               pRoot

        self
              
                .
              
              recursion_modify
              
                (
              
              pRoot
              
                .
              
              left
              
                )
              
              
        left 
              
                =
              
               pRoot
              
                .
              
              left
        
              
                if
              
               left 
              
                !=
              
              
                None
              
              
                :
              
              
                while
              
               left
              
                .
              
              right 
              
                !=
              
              
                None
              
              
                :
              
              
                left 
              
                =
              
               left
              
                .
              
              right
            pRoot
              
                .
              
              left 
              
                =
              
               left
            left
              
                .
              
              right 
              
                =
              
               pRoot
        
        self
              
                .
              
              recursion_modify
              
                (
              
              pRoot
              
                .
              
              right
              
                )
              
              
        right 
              
                =
              
               pRoot
              
                .
              
              right
        
              
                if
              
               right 
              
                !=
              
              
                None
              
              
                :
              
              
                while
              
               right
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
                right 
              
                =
              
               right
              
                .
              
              left
            pRoot
              
                .
              
              right 
              
                =
              
               right
            right
              
                .
              
              left 
              
                =
              
               pRoot
            
        
              
                while
              
               pRoot
              
                .
              
              left 
              
                !=
              
              
                None
              
              
                :
              
              
            pRoot 
              
                =
              
               pRoot
              
                .
              
              left
        
        
              
                return
              
               pRoot

            
          

37.序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树

            
              
                # 使用前序遍历实现序列化和反序列化
              
              
                # -*- coding:utf-8 -*-
              
              
                # class TreeNode:
              
              
                #     def __init__(self, x):
              
              
                #         self.val = x
              
              
                #         self.left = None
              
              
                #         self.right = None
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Serialize
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                '$,'
              
              
                return
              
              
                str
              
              
                (
              
              root
              
                .
              
              val
              
                )
              
              
                +
              
              
                ','
              
              
                +
              
               self
              
                .
              
              Serialize
              
                (
              
              root
              
                .
              
              left
              
                )
              
              
                +
              
               self
              
                .
              
              Serialize
              
                (
              
              root
              
                .
              
              right
              
                )
              
              
                def
              
              
                Deserialize
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 特殊情况处理
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              
                # 原始二叉树为空时,序列化得到的是"$,",此时直接返回None
              
              
                elif
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                ==
              
              
                2
              
              
                and
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
              
                '$'
              
              
                :
              
              
                return
              
              
                None
              
              
        
        s_list 
              
                =
              
               s
              
                .
              
              split
              
                (
              
              
                ','
              
              
                )
              
              
        root 
              
                =
              
               TreeNode
              
                (
              
              
                int
              
              
                (
              
              s_list
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                )
              
              
                # 设置头节点
              
              
        s_list
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                # 将用过的节点弹出
              
              
                # 递归重构二叉树
              
              
        root
              
                .
              
              left 
              
                =
              
               self
              
                .
              
              recursion_deserialize
              
                (
              
              s_list
              
                )
              
              
        root
              
                .
              
              right 
              
                =
              
               self
              
                .
              
              recursion_deserialize
              
                (
              
              s_list
              
                )
              
              
                return
              
               root
    
              
                def
              
              
                recursion_deserialize
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              
                if
              
               s
              
                [
              
              
                0
              
              
                ]
              
              
                ==
              
              
                '$'
              
              
                :
              
              
            s
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                return
              
              
                None
              
              
                # 递归重构二叉树
              
              
        val 
              
                =
              
               s
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
        node 
              
                =
              
               TreeNode
              
                (
              
              
                int
              
              
                (
              
              val
              
                )
              
              
                )
              
              
        node
              
                .
              
              left 
              
                =
              
               self
              
                .
              
              recursion_deserialize
              
                (
              
              s
              
                )
              
              
        node
              
                .
              
              right 
              
                =
              
               self
              
                .
              
              recursion_deserialize
              
                (
              
              s
              
                )
              
              
                return
              
               node

            
          

38.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

            
              
                # 递归法:将字符串分为头部+头部之外两部分
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                Permutation
              
              
                (
              
              self
              
                ,
              
               ss
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               ss 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
                if
              
              
                len
              
              
                (
              
              ss
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                list
              
              
                (
              
              ss
              
                )
              
              

        s 
              
                =
              
              
                list
              
              
                (
              
              ss
              
                )
              
              
        s
              
                .
              
              sort
              
                (
              
              
                )
              
              
                # 得到升序排列的字符数组
              
              
        res 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                )
              
              
                :
              
              
                if
              
               i 
              
                >
              
              
                0
              
              
                and
              
               s
              
                [
              
              i
              
                ]
              
              
                ==
              
               s
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                # 重复字符排列过就不用再重排
              
              
                continue
              
              
            temp 
              
                =
              
               self
              
                .
              
              Permutation
              
                (
              
              
                ''
              
              
                .
              
              join
              
                (
              
              s
              
                [
              
              
                :
              
              i
              
                ]
              
              
                )
              
              
                +
              
              
                ''
              
              
                .
              
              join
              
                (
              
              s
              
                [
              
              i
              
                +
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                )
              
              
                for
              
               j 
              
                in
              
               temp
              
                :
              
              
                res
              
                .
              
              append
              
                (
              
              s
              
                [
              
              i
              
                ]
              
              
                +
              
               j
              
                )
              
              
                return
              
               res

            
          

39.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

            
              
                # 方法一:借助字典实现,统计每个数字出现的频次
              
              
                # 时间和空间复杂度均为:O(n)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                MoreThanHalfNum_Solution
              
              
                (
              
              self
              
                ,
              
               numbers
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               numbers 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                0
              
              
        count 
              
                =
              
              
                {
              
              
                }
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                //
              
              
                2
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i 
              
                in
              
               count
              
                :
              
              
                count
              
                [
              
              i
              
                ]
              
              
                +=
              
              
                1
              
              
                else
              
              
                :
              
              
                count
              
                [
              
              i
              
                ]
              
              
                =
              
              
                1
              
              
                for
              
               key 
              
                in
              
               count
              
                :
              
              
                if
              
               count
              
                [
              
              key
              
                ]
              
              
                >
              
               length
              
                :
              
              
                return
              
               key
        
        
              
                return
              
              
                0
              
            
          
            
              
                # 方法二:根据数组特点寻找,次数超过一半
              
              
                # 使用两个变量记录当前数字和数字出现的次数,出现与当前数字相同的数时次数加1,否则减1,若减为0,则将之前的数改为当前的数字
              
              
                # 最后存储的数字在进行是否频次大于长度一半的验证即可
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                MoreThanHalfNum_Solution
              
              
                (
              
              self
              
                ,
              
               numbers
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               numbers 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                0
              
              
        count 
              
                =
              
              
                1
              
              
        num 
              
                =
              
               numbers
              
                [
              
              
                0
              
              
                ]
              
              
                for
              
               i 
              
                in
              
               numbers
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                :
              
              
                if
              
               i 
              
                ==
              
               num
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                else
              
              
                :
              
              
                if
              
               count 
              
                >
              
              
                0
              
              
                :
              
              
                    count 
              
                -=
              
              
                1
              
              
                else
              
              
                :
              
              
                    count 
              
                +=
              
              
                1
              
              
                    num 
              
                =
              
               i
        
              
                # 验证num是否次数大于长度一半
              
              
        count 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i 
              
                ==
              
               num
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                if
              
               count 
              
                >
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                //
              
              
                2
              
              
                :
              
              
                return
              
               num
        
              
                else
              
              
                :
              
              
                return
              
              
                0
              
            
          
            
              
                # 方法三:利用快速排序得到排序后的数组,判断排序后的数组中位数是否出现频次大于数组长度一半
              
              
                # 时间复杂度:O(nlogn)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                MoreThanHalfNum_Solution
              
              
                (
              
              self
              
                ,
              
               numbers
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               numbers 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                0
              
              

        nums 
              
                =
              
               self
              
                .
              
              quickSort
              
                (
              
              numbers
              
                )
              
              
                # 排序
              
              
        num 
              
                =
              
               nums
              
                [
              
              
                len
              
              
                (
              
              nums
              
                )
              
              
                //
              
              
                2
              
              
                ]
              
              
                # 取中位数
              
              
                # 验证num是否次数大于长度一半
              
              
        count 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
               numbers
              
                :
              
              
                if
              
               i 
              
                ==
              
               num
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                if
              
               count 
              
                >
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                //
              
              
                2
              
              
                :
              
              
                return
              
               num
        
              
                else
              
              
                :
              
              
                return
              
              
                0
              
              
                # 快排
              
              
                def
              
              
                quickSort
              
              
                (
              
              self
              
                ,
              
               numbers
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
               numbers
        pivot 
              
                =
              
               numbers
              
                [
              
              
                0
              
              
                ]
              
              
        left 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               numbers 
              
                if
              
               x 
              
                <
              
               pivot
              
                ]
              
              
        mid 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               numbers 
              
                if
              
               x 
              
                ==
              
               pivot
              
                ]
              
              
        right 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               numbers 
              
                if
              
               x 
              
                >
              
               pivot
              
                ]
              
              
                return
              
               self
              
                .
              
              quickSort
              
                (
              
              left
              
                )
              
              
                +
              
               mid 
              
                +
              
               self
              
                .
              
              quickSort
              
                (
              
              right
              
                )
              
            
          

40.最小的K个数

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

            
              
                # 方法一:排序后取前K个
              
              
                # 时间复杂度由排序算法决定:快排则为O(nlogn)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                GetLeastNumbers_Solution
              
              
                (
              
              self
              
                ,
              
               tinput
              
                ,
              
               k
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               tinput 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              tinput
              
                )
              
              
                <
              
               k
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        tinput 
              
                =
              
               self
              
                .
              
              quickSort
              
                (
              
              tinput
              
                )
              
              
                return
              
               tinput
              
                [
              
              
                0
              
              
                :
              
              k
              
                ]
              
              
                def
              
              
                quickSort
              
              
                (
              
              self
              
                ,
              
               arr
              
                )
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              arr
              
                )
              
              
                <=
              
              
                1
              
              
                :
              
              
                return
              
               arr
        
        pivot 
              
                =
              
               arr
              
                [
              
              
                0
              
              
                ]
              
              
        
        left 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                <
              
               pivot
              
                ]
              
              
        mid 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                ==
              
               pivot
              
                ]
              
              
        right 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               arr 
              
                if
              
               x 
              
                >
              
               pivot
              
                ]
              
              
                return
              
               self
              
                .
              
              quickSort
              
                (
              
              left
              
                )
              
              
                +
              
               mid 
              
                +
              
               self
              
                .
              
              quickSort
              
                (
              
              right
              
                )
              
            
          
            
              
                # 方法二:类似计数排序法,计数后取出前K个
              
              
                # 时间复杂度O(n+k)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                GetLeastNumbers_Solution
              
              
                (
              
              self
              
                ,
              
               tinput
              
                ,
              
               k
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               tinput 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              tinput
              
                )
              
              
                <
              
               k 
              
                or
              
               k 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        tinput 
              
                =
              
               self
              
                .
              
              countingSort
              
                (
              
              tinput
              
                ,
              
               k
              
                )
              
              
                return
              
               tinput

    
              
                def
              
              
                countingSort
              
              
                (
              
              self
              
                ,
              
               arr
              
                ,
              
               k
              
                )
              
              
                :
              
              
        min_num 
              
                =
              
              
                min
              
              
                (
              
              arr
              
                )
              
              
        max_num 
              
                =
              
              
                max
              
              
                (
              
              arr
              
                )
              
              
        
        counts 
              
                =
              
              
                [
              
              
                0
              
              
                ]
              
              
                *
              
              
                (
              
              max_num
              
                -
              
              min_num
              
                +
              
              
                1
              
              
                )
              
              
                for
              
               i 
              
                in
              
               arr
              
                :
              
              
            counts
              
                [
              
              i
              
                -
              
              min_num
              
                ]
              
              
                +=
              
              
                1
              
              
        res 
              
                =
              
              
                [
              
              
                ]
              
              
        count 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              counts
              
                )
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              counts
              
                [
              
              i
              
                ]
              
              
                )
              
              
                :
              
              
                res
              
                .
              
              append
              
                (
              
              i
              
                +
              
              min_num
              
                )
              
              
                if
              
              
                len
              
              
                (
              
              res
              
                )
              
              
                ==
              
               k
              
                :
              
              
                return
              
               res

            
          

41.数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

            
              
                # 方法一:使用有序数组
              
              
                # 插入数据和查找中位数的时间复杂度分别为:O(n),O(1)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                )
              
              
                :
              
              
        self
              
                .
              
              num 
              
                =
              
              
                [
              
              
                ]
              
              
                def
              
              
                Insert
              
              
                (
              
              self
              
                ,
              
               num
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               num 
              
                !=
              
              
                None
              
              
                :
              
              
            length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              num
              
                )
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              length
              
                )
              
              
                :
              
              
                if
              
               num 
              
                <=
              
               self
              
                .
              
              num
              
                [
              
              i
              
                ]
              
              
                :
              
              
                    self
              
                .
              
              num
              
                .
              
              insert
              
                (
              
              i
              
                ,
              
               num
              
                )
              
              
                break
              
              
                # 如果没有插入,则说明该数最大,所以放置于数组末尾
              
              
                if
              
               length 
              
                ==
              
              
                len
              
              
                (
              
              self
              
                .
              
              num
              
                )
              
              
                :
              
              
                self
              
                .
              
              num
              
                .
              
              append
              
                (
              
              num
              
                )
              
              
                def
              
              
                GetMedian
              
              
                (
              
              self
              
                ,
              
               x
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
              
                len
              
              
                (
              
              self
              
                .
              
              num
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                None
              
              

        length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              num
              
                )
              
              
                if
              
               length 
              
                %
              
              
                2
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               self
              
                .
              
              num
              
                [
              
              length
              
                //
              
              
                2
              
              
                ]
              
              
                else
              
              
                :
              
              
                return
              
              
                (
              
              self
              
                .
              
              num
              
                [
              
              length
              
                //
              
              
                2
              
              
                ]
              
              
                +
              
              self
              
                .
              
              num
              
                [
              
              length
              
                //
              
              
                2
              
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
                /
              
              
                2.0
              
            
          
            
              
                # 方法二:使用大顶堆和小顶堆存储数据,实现中位数的查找
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                __init__
              
              
                (
              
              self
              
                )
              
              
                :
              
              
        self
              
                .
              
              min_heap 
              
                =
              
              
                [
              
              
                ]
              
              
                # 小顶堆
              
              
        self
              
                .
              
              max_heap 
              
                =
              
              
                [
              
              
                ]
              
              
                # 大顶堆
              
              
                def
              
              
                Insert
              
              
                (
              
              self
              
                ,
              
               num
              
                )
              
              
                :
              
              
                # write code here
              
              
                # 根据数据总个数插入,当数据总数为奇数时插入大顶堆,否则插入小顶堆
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              min_heap
              
                )
              
              
                +
              
              
                len
              
              
                (
              
              self
              
                .
              
              max_heap
              
                )
              
              
                if
              
               length 
              
                %
              
              
                2
              
              
                ==
              
              
                1
              
              
                :
              
              
                # 总数为奇数,将元素插入大顶堆
              
              
            self
              
                .
              
              min_heap
              
                .
              
              append
              
                (
              
              num
              
                )
              
              
            min_num 
              
                =
              
               self
              
                .
              
              adjustMin
              
                (
              
              
                )
              
              
            self
              
                .
              
              min_heap
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                # 将小顶堆最小元素弹出后放入大顶堆
              
              
            self
              
                .
              
              adjustMin
              
                (
              
              
                )
              
              
                # 弹出后再次调整堆结构
              
              
            self
              
                .
              
              max_heap
              
                .
              
              append
              
                (
              
              min_num
              
                )
              
              
            self
              
                .
              
              adjustMax
              
                (
              
              
                )
              
              
                else
              
              
                :
              
              
                # 总数为偶数,将元素插入小顶堆
              
              
            self
              
                .
              
              max_heap
              
                .
              
              append
              
                (
              
              num
              
                )
              
              
            max_num 
              
                =
              
               self
              
                .
              
              adjustMax
              
                (
              
              
                )
              
              
            self
              
                .
              
              max_heap
              
                .
              
              pop
              
                (
              
              
                0
              
              
                )
              
              
                # 将小顶堆最小元素弹出后放入大顶堆
              
              
            self
              
                .
              
              adjustMax
              
                (
              
              
                )
              
              
                # 弹出后再次调整堆结构
              
              
            self
              
                .
              
              min_heap
              
                .
              
              append
              
                (
              
              max_num
              
                )
              
              
            self
              
                .
              
              adjustMin
              
                (
              
              
                )
              
              
                def
              
              
                GetMedian
              
              
                (
              
              self
              
                ,
              
               x
              
                )
              
              
                :
              
              
                # x 为无效参数
              
              
                # write code here
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              min_heap
              
                )
              
              
                +
              
              
                len
              
              
                (
              
              self
              
                .
              
              max_heap
              
                )
              
              
                if
              
               length 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
                if
              
               length 
              
                %
              
              
                2
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               self
              
                .
              
              min_heap
              
                [
              
              
                0
              
              
                ]
              
              
                else
              
              
                :
              
              
                return
              
              
                (
              
              self
              
                .
              
              max_heap
              
                [
              
              
                0
              
              
                ]
              
              
                +
              
              self
              
                .
              
              min_heap
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                /
              
              
                2.0
              
              
                def
              
              
                adjustMax
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                # 大顶堆调整,返回堆顶元素
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              max_heap
              
                )
              
              
                if
              
               length 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                if
              
               length 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               self
              
                .
              
              max_heap
              
                [
              
              
                0
              
              
                ]
              
              
        i 
              
                =
              
               length 
              
                //
              
              
                2
              
              
                -
              
              
                1
              
              
                while
              
               i 
              
                >=
              
              
                0
              
              
                :
              
              
            left 
              
                =
              
              
                2
              
              
                *
              
              i 
              
                +
              
              
                1
              
              
            right 
              
                =
              
              
                2
              
              
                *
              
              i 
              
                +
              
              
                2
              
              
                if
              
               right 
              
                <
              
               length 
              
                and
              
               self
              
                .
              
              max_heap
              
                [
              
              left
              
                ]
              
              
                <
              
               self
              
                .
              
              max_heap
              
                [
              
              right
              
                ]
              
              
                :
              
              
                left 
              
                =
              
               right
            
              
                if
              
               self
              
                .
              
              max_heap
              
                [
              
              left
              
                ]
              
              
                >
              
               self
              
                .
              
              max_heap
              
                [
              
              i
              
                ]
              
              
                :
              
              
                self
              
                .
              
              max_heap
              
                [
              
              i
              
                ]
              
              
                ,
              
               self
              
                .
              
              max_heap
              
                [
              
              left
              
                ]
              
              
                =
              
               self
              
                .
              
              max_heap
              
                [
              
              left
              
                ]
              
              
                ,
              
               self
              
                .
              
              max_heap
              
                [
              
              i
              
                ]
              
              
                if
              
               left 
              
                <=
              
               length 
              
                //
              
              
                2
              
              
                -
              
              
                1
              
              
                :
              
              
                    i 
              
                =
              
               left
                    
              
                continue
              
              
            i 
              
                -=
              
              
                1
              
              
                return
              
               self
              
                .
              
              max_heap
              
                [
              
              
                0
              
              
                ]
              
              
                def
              
              
                adjustMin
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                # 小顶堆调整,返回堆顶元素
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              self
              
                .
              
              min_heap
              
                )
              
              
                if
              
               length 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                if
              
               length 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               self
              
                .
              
              min_heap
              
                [
              
              
                0
              
              
                ]
              
              
        i 
              
                =
              
               length 
              
                //
              
              
                2
              
              
                -
              
              
                1
              
              
                while
              
               i 
              
                >=
              
              
                0
              
              
                :
              
              
            left 
              
                =
              
              
                2
              
              
                *
              
              i 
              
                +
              
              
                1
              
              
            right 
              
                =
              
              
                2
              
              
                *
              
              i 
              
                +
              
              
                2
              
              
                if
              
               right 
              
                <
              
               length 
              
                and
              
               self
              
                .
              
              min_heap
              
                [
              
              left
              
                ]
              
              
                >
              
               self
              
                .
              
              min_heap
              
                [
              
              right
              
                ]
              
              
                :
              
              
                left 
              
                =
              
               right
            
              
                if
              
               self
              
                .
              
              min_heap
              
                [
              
              left
              
                ]
              
              
                <
              
               self
              
                .
              
              min_heap
              
                [
              
              i
              
                ]
              
              
                :
              
              
                self
              
                .
              
              min_heap
              
                [
              
              i
              
                ]
              
              
                ,
              
               self
              
                .
              
              min_heap
              
                [
              
              left
              
                ]
              
              
                =
              
               self
              
                .
              
              min_heap
              
                [
              
              left
              
                ]
              
              
                ,
              
               self
              
                .
              
              min_heap
              
                [
              
              i
              
                ]
              
              
                if
              
               left 
              
                <=
              
               length 
              
                //
              
              
                2
              
              
                -
              
              
                1
              
              
                :
              
              
                    i 
              
                =
              
               left
                    
              
                continue
              
              
            i 
              
                -=
              
              
                1
              
              
                return
              
               self
              
                .
              
              min_heap
              
                [
              
              
                0
              
              
                ]
              
            
          

42.连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)要求时间复杂度为 O ( n ) O(n) O ( n )

            
              
                # 方法一:根据数组和的规律进行查找
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                FindGreatestSumOfSubArray
              
              
                (
              
              self
              
                ,
              
               array
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               array 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                if
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               array
              
                [
              
              
                0
              
              
                ]
              
              
        
        max_sum 
              
                =
              
              
                0
              
              
        final_max 
              
                =
              
               array
              
                [
              
              
                0
              
              
                ]
              
              
                # 存储最大和
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                )
              
              
                :
              
              
            max_sum 
              
                +=
              
               array
              
                [
              
              i
              
                ]
              
              
                print
              
              
                (
              
              max_sum
              
                )
              
              
                print
              
              
                (
              
              array
              
                [
              
              i
              
                ]
              
              
                )
              
              
                if
              
               max_sum 
              
                <
              
               array
              
                [
              
              i
              
                ]
              
              
                :
              
              
                max_sum 
              
                =
              
               array
              
                [
              
              i
              
                ]
              
              
                if
              
               final_max 
              
                <
              
               max_sum
              
                :
              
              
                final_max 
              
                =
              
               max_sum

        
              
                return
              
               final_max

            
          
            
              
                # 方法二:动态规划法
              
              
                # 设f(i)表示第i个数结尾的的子数组的最大和,则要求的最大和为max(f(i))
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                FindGreatestSumOfSubArray
              
              
                (
              
              self
              
                ,
              
               array
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               array 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                if
              
              
                len
              
              
                (
              
              array
              
                )
              
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               array
              
                [
              
              
                0
              
              
                ]
              
              
        
        max_sum 
              
                =
              
              
                0
              
              
                # f(i)
              
              
        final_max 
              
                =
              
               array
              
                [
              
              
                0
              
              
                ]
              
              
                # 存储最大和 max(f(i))
              
              
                for
              
               i 
              
                in
              
               array
              
                :
              
              
                # 循环实现动态规划
              
              
                if
              
               max_sum 
              
                <=
              
              
                0
              
              
                :
              
              
                max_sum 
              
                =
              
               i
            
              
                else
              
              
                :
              
              
                max_sum 
              
                +=
              
               i
            
            
              
                if
              
               final_max 
              
                <
              
               max_sum
              
                :
              
              
                final_max 
              
                =
              
               max_sum
            
        
              
                return
              
               final_max

            
          

43. 1~n整数中1出现的次数

求出1 13的整数中1出现的次数,并算出100 1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

            
              
                # 方法一:暴力遍历法,时间复杂度为O(nlogn)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                NumberOf1Between1AndN_Solution
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               n 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
        count 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              n
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
            count 
              
                +=
              
               self
              
                .
              
              countNum
              
                (
              
              i
              
                )
              
              
                return
              
               count
    
    
              
                def
              
              
                countNum
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
        count 
              
                =
              
              
                0
              
              
                while
              
               n 
              
                >
              
              
                0
              
              
                :
              
              
                if
              
               n 
              
                %
              
              
                10
              
              
                ==
              
              
                1
              
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
            n 
              
                =
              
               n 
              
                //
              
              
                10
              
              
                return
              
               count

s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
s
              
                .
              
              NumberOf1Between1AndN_Solution
              
                (
              
              
                10000
              
              
                )
              
            
          
            
              4001

            
          
            
              
                # 方法二:递归法,根据数字的规律进行递归求解
              
              
                # 时间复杂度:O(logn)
              
              
                # -*- coding:utf-8 -*-
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                NumberOf1Between1AndN_Solution
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               n 
              
                is
              
              
                None
              
              
                or
              
               n 
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
                return
              
               self
              
                .
              
              recursion_count
              
                (
              
              n
              
                )
              
              
                def
              
              
                recursion_count
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
                if
              
               n 
              
                <
              
              
                10
              
              
                :
              
              
                return
              
              
                1
              
              
        
        count 
              
                =
              
              
                0
              
              
        high_num
              
                ,
              
               time 
              
                =
              
               self
              
                .
              
              getHigh
              
                (
              
              n
              
                )
              
              
                # 1在最高位时
              
              
                if
              
               high_num 
              
                >
              
              
                1
              
              
                :
              
              
            count 
              
                =
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               time
              
                -
              
              
                1
              
              
                )
              
              
                else
              
              
                :
              
              
            count 
              
                =
              
               n 
              
                -
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               time
              
                -
              
              
                1
              
              
                )
              
              
                +
              
              
                1
              
              
                # 1在除最高位之外的位置时
              
              
        count 
              
                +=
              
               high_num 
              
                *
              
              
                (
              
              time 
              
                -
              
              
                1
              
              
                )
              
              
                *
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               time 
              
                -
              
              
                2
              
              
                )
              
              
                # 排列组合
              
              
                # 递归
              
              
        count 
              
                +=
              
               self
              
                .
              
              recursion_count
              
                (
              
              n 
              
                -
              
               high_num
              
                *
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               time
              
                -
              
              
                1
              
              
                )
              
              
                )
              
              
                return
              
               count
        
    
              
                def
              
              
                getHigh
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # 获取高位数字和总的位数
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                0
              
              
        time 
              
                =
              
              
                0
              
              
                while
              
               n 
              
                >
              
              
                0
              
              
                :
              
              
            time 
              
                +=
              
              
                1
              
              
                if
              
               n 
              
                <
              
              
                10
              
              
                :
              
              
                return
              
               n
              
                ,
              
               time
            
            n 
              
                =
              
               n 
              
                //
              
              
                10
              
            
          

44.数字序列中每一位的数字

数字以01234567891011121314…的格式排列。在这个序列中,第5位(从0开始计)是5,第13位是1,第19位是4。求任意第n为对应的数字。

**PS:**此题牛客网没有对应的在线评测,可以在acwing第57题进行在线评测。

            
              
                # 方法:根据数字不同位数所占个数的规律进行求解
              
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                digitAtIndex
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                """
        :type n: int
        :rtype: int
        """
              
              
        i 
              
                =
              
              
                1
              
              
                # 数字位数
              
              
                while
              
               n 
              
                -
              
               self
              
                .
              
              count_of_integers
              
                (
              
              i
              
                )
              
              
                >=
              
              
                0
              
              
                :
              
              
            n 
              
                =
              
               n 
              
                -
              
               self
              
                .
              
              count_of_integers
              
                (
              
              i
              
                )
              
              
            i 
              
                +=
              
              
                1
              
              
        rest 
              
                =
              
               n 
              
                //
              
               i 
              
                # 相对当前位数数字所处的位置
              
              
        inte 
              
                =
              
               n 
              
                %
              
               i 
              
                # 相对当前数字的位置
              
              
                return
              
               self
              
                .
              
              get_number
              
                (
              
              i
              
                ,
              
               rest
              
                ,
              
               inte
              
                )
              
              
                def
              
              
                count_of_integers
              
              
                (
              
              self
              
                ,
              
               n
              
                )
              
              
                :
              
              
                # 计算不同位数数字的个数
              
              
                if
              
               n 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
              
                10
              
              
                else
              
              
                :
              
              
                return
              
              
                (
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               n
              
                )
              
              
                -
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               n
              
                -
              
              
                1
              
              
                )
              
              
                )
              
              
                *
              
               n
    
    
              
                def
              
              
                get_number
              
              
                (
              
              self
              
                ,
              
               i
              
                ,
              
               rest
              
                ,
              
               inte
              
                )
              
              
                :
              
              
                # 根据数字位数i,相对i位数起始第rest个数字,得到第rest个数字的第inte位的数字
              
              
                if
              
               i 
              
                ==
              
              
                1
              
              
                :
              
              
            num 
              
                =
              
              
                0
              
              
                +
              
               rest
        
              
                else
              
              
                :
              
              
            num 
              
                =
              
              
                pow
              
              
                (
              
              
                10
              
              
                ,
              
               i
              
                -
              
              
                1
              
              
                )
              
              
                +
              
               rest
        
        inte 
              
                =
              
               i 
              
                -
              
               inte 
              
                -
              
              
                1
              
              
                while
              
               inte 
              
                !=
              
              
                0
              
              
                :
              
              
            num 
              
                =
              
               num 
              
                //
              
              
                10
              
              
            inte 
              
                -=
              
              
                1
              
              
                return
              
               num 
              
                %
              
              
                10
              
            
          

45.把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

            
              
                # 方法:重新定义比较大小函数,根据字符串m+n与n+m的比较结果进行排序
              
              
                # python3中利用functools模块,实现自定义排序
              
              
                # -*- coding:utf-8 -*-
              
              
                import
              
               functools

              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                PrintMinNumber
              
              
                (
              
              self
              
                ,
              
               numbers
              
                )
              
              
                :
              
              
                # write code here
              
              
                if
              
               numbers 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              numbers
              
                )
              
              
                ==
              
              
                0
              
              
                :
              
              
                return
              
              
                ''
              
              
        
        numbers 
              
                =
              
              
                [
              
              
                str
              
              
                (
              
              x
              
                )
              
              
                for
              
               x 
              
                in
              
               numbers
              
                ]
              
              
        numbers
              
                .
              
              sort
              
                (
              
              key
              
                =
              
              functools
              
                .
              
              cmp_to_key
              
                (
              
              self
              
                .
              
              comp
              
                )
              
              
                )
              
              
                return
              
              
                ""
              
              
                .
              
              join
              
                (
              
              numbers
              
                )
              
              
                def
              
              
                comp
              
              
                (
              
              self
              
                ,
              
               x
              
                ,
              
               y
              
                )
              
              
                :
              
              
                if
              
              
                (
              
              
                str
              
              
                (
              
              x
              
                )
              
              
                +
              
              
                str
              
              
                (
              
              y
              
                )
              
              
                )
              
              
                <
              
              
                (
              
              
                str
              
              
                (
              
              y
              
                )
              
              
                +
              
              
                str
              
              
                (
              
              x
              
                )
              
              
                )
              
              
                :
              
              
                return
              
              
                -
              
              
                1
              
              
                else
              
              
                :
              
              
                return
              
              
                1
              
              
s 
              
                =
              
               Solution
              
                (
              
              
                )
              
              
num 
              
                =
              
              
                [
              
              
                3
              
              
                ,
              
              
                5
              
              
                ,
              
              
                1
              
              
                ,
              
              
                4
              
              
                ,
              
              
                2
              
              
                ]
              
              
                #num = [3, 32, 321]
              
              
s
              
                .
              
              PrintMinNumber
              
                (
              
              num
              
                )
              
            
          
            
              '12345'

            
          

46.把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:

0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译,它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

PS : 此题牛客网没有对应的在线评测,可以在acwing第55题进行评测。

方法一:递归法,自上而下的实现

自上而下的实现(即从字符串左至右递归),存在很多重复计算的问题。
递归公式: f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) ∗ f ( i + 2 ) f(i)=f(i+1)+g(i,i+1)*f(i+2) f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) f ( i + 2 )

其中 f ( i ) f(i) f ( i ) 表示从第i位数字开始的翻译数目, g ( i , i + 1 ) g(i,i+1) g ( i , i + 1 ) 表示第i位和第i+1为组合的数字如果在10–25范围则为1,否则为0

            
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                getTranslationCount
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                """
        :type s: str
        :rtype: int
        """
              
              
                if
              
              
                int
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                0
              
              
                or
              
               s 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                0
              
              
                # 将数字拆分
              
              
        s 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               s
              
                ]
              
              
                return
              
               self
              
                .
              
              recursion_count
              
                (
              
              s
              
                )
              
              
                def
              
              
                recursion_count
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                2
              
              
                :
              
              
                return
              
              
                1
              
              
        
        count 
              
                =
              
              
                0
              
              
                # 将s拆分为1个元素和其余元素
              
              
        count 
              
                +=
              
               self
              
                .
              
              recursion_count
              
                (
              
              s
              
                [
              
              
                1
              
              
                :
              
              
                ]
              
              
                )
              
              
                # 将s拆分为前两个元素和其余元素
              
              
                if
              
              
                10
              
              
                <=
              
              
                int
              
              
                (
              
              s
              
                [
              
              
                0
              
              
                ]
              
              
                +
              
              s
              
                [
              
              
                1
              
              
                ]
              
              
                )
              
              
                <=
              
              
                25
              
              
                :
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                >=
              
              
                3
              
              
                :
              
              
                count 
              
                +=
              
               self
              
                .
              
              recursion_count
              
                (
              
              s
              
                [
              
              
                2
              
              
                :
              
              
                ]
              
              
                )
              
              
                else
              
              
                :
              
              
                count 
              
                +=
              
              
                1
              
              
                return
              
               count

            
          

方法二:递归法,自下而上使用循环实现

自下而上实现(即从字符串右至左循环)效率更高。递归公式相同: f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) ∗ f ( i + 2 ) f(i)=f(i+1)+g(i,i+1)*f(i+2) f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) f ( i + 2 )

从i=len(s)开始循环计算。

            
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                getTranslationCount
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                """
        :type s: str
        :rtype: int
        """
              
              
                if
              
              
                int
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                0
              
              
                or
              
               s 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                0
              
              
                # 将数字拆分
              
              
        s 
              
                =
              
              
                [
              
              x 
              
                for
              
               x 
              
                in
              
               s
              
                ]
              
              
                return
              
               self
              
                .
              
              curlce_count
              
                (
              
              s
              
                )
              
              
                def
              
              
                curlce_count
              
              
                (
              
              self
              
                ,
              
               s
              
                )
              
              
                :
              
              
                # 递归终止条件
              
              
                if
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                <
              
              
                2
              
              
                :
              
              
                return
              
              
                1
              
              
        
        count 
              
                =
              
              
                0
              
              
        length 
              
                =
              
              
                len
              
              
                (
              
              s
              
                )
              
              
                # 递推公式fi = fi_1 + g(i,i+1)*fi_2
              
              
                # 初始赋值,i从len(s)-1开始,此时赋值如下
              
              
        fi_2
              
                ,
              
              fi_1
              
                ,
              
              fi 
              
                =
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                1
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              length
              
                -
              
              
                2
              
              
                ,
              
              
                -
              
              
                1
              
              
                ,
              
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                if
              
               i
              
                +
              
              
                2
              
              
                >
              
               length
              
                :
              
              
                fi_2 
              
                =
              
              
                0
              
              
                # 更新
              
              
            fi_2
              
                ,
              
               fi_1 
              
                =
              
               fi_1
              
                ,
              
               fi

            
              
                if
              
              
                10
              
              
                <=
              
              
                int
              
              
                (
              
              s
              
                [
              
              i
              
                ]
              
              
                +
              
              s
              
                [
              
              i
              
                +
              
              
                1
              
              
                ]
              
              
                )
              
              
                <=
              
              
                25
              
              
                :
              
              
                fi 
              
                =
              
               fi_1 
              
                +
              
               fi_2
            
              
                else
              
              
                :
              
              
                fi 
              
                +
              
               fi_1
            
        
              
                return
              
               fi

            
          

47.礼物的最大价值

在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。
你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?

**PS:**此题牛客网没有对应的在线评测,可以在acwing第60题进行评测。

            
              
                # 方法一:动态规划
              
              
                # 递推公式:f(i,j) = max(f(i, j-1), f(i-1, j)) + gift[i, j]
              
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                getMaxValue
              
              
                (
              
              self
              
                ,
              
               grid
              
                )
              
              
                :
              
              
                """
        :type grid: List[List[int]]
        :rtype: int
        """
              
              
                if
              
               grid 
              
                is
              
              
                None
              
              
                or
              
              
                len
              
              
                (
              
              grid
              
                )
              
              
                <
              
              
                1
              
              
                or
              
              
                len
              
              
                (
              
              grid
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                <
              
              
                1
              
              
                :
              
              
                return
              
              
                0
              
              
        m
              
                ,
              
               n 
              
                =
              
              
                len
              
              
                (
              
              grid
              
                )
              
              
                ,
              
              
                len
              
              
                (
              
              grid
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
        
        assist_list 
              
                =
              
              
                [
              
              
                [
              
              
                0
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              n
              
                )
              
              
                ]
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              m
              
                )
              
              
                ]
              
              
                # 辅助二维数组
              
              
                # 递推公式为:f(i,j) = max(f(i, j-1), f(i-1, j)) + gift[i, j]
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              m