python剑指offer题解

笔记笔记笔记-待更新

二维数组中查找

题目

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

思路

从最右一列往下查找,效率比直接遍历高

代码

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        i = 0
        j = len(array[0])-1
        while i <len(array) and j>=0:
            if target==array[i][j]:
                return True
            elif target<array[i][j]:
                j-=1
            else:
                i+=1
        return False

替换空格

题目

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

思路

一种是建立新的字符串,然后遍历原来的字符串时,加到新的里第二种是原地操作,先统计空格的数量,然后在原字符串后面补足空间,再从后往前遍历替换

代码

#1.新空间
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        new_s = ''
        b = '%20'
        for i in s:
            if i ==' ':
                new_s+=b
            else:
                new_s+=i
        return new_s

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        #字符串不能直接修改和添加,所以要先转为list 
        s = list(s)
        blank = s.count(' ')
        lenght = len(s)
        s += [0]*2*blank
        new_len = len(s)
        while lenght:
            if s[lenght-1]==' ':
                s[new_len-1]='0'
                s[new_len-2]='2'
                s[new_len-3]='%'
                new_len-=3
            else:
                s[new_len-1]=s[lenght-1]
                new_len-=1
            lenght-=1
        #把list重新转为字符串
        s = ''.join(s)
        return s

从尾到头打印链表

题目

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

代码

#?好像很简单
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, ListNode):
        # write code here
        if not ListNode:
            return []
        res = []
        while ListNode:
            res.append(ListNode.val)
            ListNode = ListNode.next
        return res[::-1]

重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 not pre or not tin:
            return None

        root = TreeNode(pre.pop(0))
        index = tin.index(root.val)
        root.left = self.reConstructBinaryTree(pre,tin[:index])
        root.right = self.reConstructBinaryTree(pre, tin[index + 1:])

        return root

用两个栈实现队列

代码

class Solution:
    #使用self，把stack1,2当作class的两个属性，pop和push成为两个方法
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self,node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

旋转数组的最小数字

题目

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

代码

#就是变形的查找，可以简单查找，也可以二分查找
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if len(rotateArray)==2:
            return rotateArray[1]
        res = len(rotateArray)/2
        if rotateArray[res]<rotateArray[0]:
            return self.minNumberInRotateArray(rotateArray[:res+1])
        elif rotateArray[res]>rotateArray[0]:
            return self.minNumberInRotateArray(rotateArray[res:])
        else:
            for i in range(1,len(rotateArray)):
                if rotateArray[i] < rotateArray[0]:
                    return rotateArray[i]
        return rotateArray[0]

斐波那契数列

题目

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

代码

#递归很简单，也可以用迭代
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        res = [0,1,1,2]
        while len(res)<=n:
            res.append(res[-1]+res[-2])
        return res[n]
        # write code here

跳台阶

题目

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

分析

跳上第n个台阶有两种情况，从n-1跳一阶上去和从n-2跳两阶上去，因此可能的情况为f(n-1)+f(n-2)，也就是斐波那契数列

代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        a = 1
        b = 1
        for i in range(number):
            a,b = b,a+b
        return a

变态跳台阶

题目

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

思路

易知 f(n)=f(n-1)+f(n-2)+……f(1) f(n-1)=f(n-2)+……f(1) 两式相减得f(n)=2f(n-1)

代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 0:
            return 0
        else:
            return pow(2,number-1)

矩形覆盖

题目

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

二进制中1的个数

题目

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

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

题目

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

思路

题目本身不难,简单的方法有
一:遍历数组,将奇数放在第一个,偶数放在最后一个,同时移动其他数的位置,时间复杂度较高.
二:另开两个数组,分别存储奇偶数,再合起来,空间复杂度较高
三:对复杂度有要求时,可以使用两个指针,分别从头尾出发,到遇到奇偶数时调换两个的位置

3代码

#牛客上通不过的实例本地没问题
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        length = len(array)
        p1 = 0
        p2 = length-1
        while p1<p2:
            while array[p1]%2!=0:
                p1+=1
            while array[p2]%2==0:
                p2-=1
            if p1<p2:
                array[p1],array[p2]=array[p2],array[p1]
                p1+=1
                p2-=1
        return array

链表中倒数第k个节点

题目

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

代码

# -*- 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==None or k<=0:
            return None
        res = 0
        p = q = head
        while res<k-1 and q:
            q = q.next
            res+=1
        if q is None:
            return None
        while q.next:
            q = q.next
            p = p.next
        return p

反转链表

题目

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

思路

想清楚思路就简单,不然很乱
思路:
①从None创建一个新链表,标记链表第一个,
②标记原链表的第一个,从原链表上一个一个摘下来,添到新链表的头上
③另外还需要标记原链表的第二个,防止丢失

代码

class Solution:
    def ReverseList(self, pHead):
        # write code here
        if pHead == None:
            return None

        p2 = None
        p1 = pHead

        while p1!=None:
            tmp = p1.next
            p1.next = p2
            p2 = p1
            p1 = tmp
        return p2

合并两个排序链表

题目

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

代码

#创建一个空节点做头,并且要标记
# -*- 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
        pHead = ListNode(0)
        p = pHead
        while pHead1 and pHead2:
            if pHead1.val<pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        if pHead1:
            p.next = pHead1
        if pHead2:
            p.next = pHead2
        return pHead.next

树的子结构

题目

输入两棵二叉树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 not pRoot1 or not pRoot2:
            return False
        return self.is_subtree(pRoot1,pRoot2) or self.is_subtree(pRoot1.left,pRoot2) or self.is_subtree(pRoot1.right,pRoot2)
    def is_subtree(self,pRoot1,pRoot2):
        if not pRoot2:
            return True
        if not pRoot1 or pRoot1.val!=pRoot2.val:
            return False
        return self.is_subtree(pRoot1.left,pRoot2.left) and self.is_subtree(pRoot1.right,pRoot2.right)

二叉树的镜像

题目

操作给定的二叉树，将其变换为源二叉树的镜像。

代码

# -*- 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 not root:
            return None
        root.left,root.right = root.right,root.left
        root.left = self.Mirror(root.left)
        root.right = self.Mirror(root.right)

        return root

顺时针打印矩阵

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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):
        out = []
        while matrix:
            # 上边界即为数组的第一个子数组
            # 加载第一行
            out += matrix.pop(0)
            # 如果这里仅判断if matrix，那么对于测试数组例[[1],[2],[3]]，循环后变成了[[],[]]，matrix不为空
            if matrix and matrix[0]:
                # 右边界即为数组每一项的最后一个元素
                for row in matrix:
                    # 加载每一行的最后一个
                    out.append(row.pop())
            # 下边界即为数组最后一个子数组的逆序排列
            if matrix:
                #倒序加载最后一行
                out += matrix.pop()[::-1]
            if matrix and matrix[0]:
                # 左边界即为数组从尾到头的每一项子数组的第一个元素
                for row in matrix[::-1]:
                    #倒序加载第一列
                    out.append(row.pop(0))
        return out

#代码2
# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        res=[]
        n=len(matrix)
        m=len(matrix[0])
        if n==1 and m==1:
            res=[matrix[0][0]]
            return res
        for o in xrange((min(m,n)+1)//2):
            [res.append(matrix[o][i]) for i in xrange(o,m-o)]
            [res.append(matrix[j][m-1-o]) for j in xrange(o,n-o) if matrix[j][m-1-o] not in res]
            [res.append(matrix[n-1-o][k]) for k in xrange(m-1-o,o-1,-1) if matrix[n-1-o][k] not in res]
            [res.append(matrix[l][o]) for l in xrange(n-1-o,o-1,-1) if matrix[l][o] not in res]
        return res

包含min函数的栈

题目

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

代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, node):
        self.stack.append(node)
        if not self.min_stack or node<=self.min_stack[-1]:
            self.min_stack.append(node)
    def pop(self):
        if self.stack[-1]==self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
    def top(self):
        return self.stack[-1]
    def min(self):
        return self.min_stack[-1]

栈的压入,弹出序列

题目

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

代码

#思路没问题,但是数组的操作要注意,res全部pop完以后再切片就会报错,所以要加一个判断res是否有元素
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        res = []
        while pushV:
            res.append(pushV.pop(0))
            # 加一个while res
            while res and res[-1]==popV[0] and res:
                res.pop()
                popV.pop(0)
        if not res:
            return True

从上往下打印二叉树

题目

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

代码

# -*- 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 not root:
            return []
        res = [root]
        l = []
        while res:
            a = res.pop(0)
            l.append(a.val)
            if a.left:
                res.append(a.left)
            if a.right:
                res.append(a.right)
        return l

二叉搜索树的后序遍历序列

题目

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

代码

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence)==0:
            return False
        index = 0
        for i in range(len(sequence)):
            if sequence[i]>sequence[-1]:
                index = i
                break
        for j in range(i,len(sequence)):
            if sequence[j]<sequence[-1]:
                return False
        left = True
        right = True
        if len(sequence[:index])>0:
            left = self.VerifySquenceOfBST(sequence[:index])
        if len(sequence[index:-1])>0:
            right = self.VerifySquenceOfBST(sequence[index:-1])
        return left and right

二叉树中和为某一值的路径

题目

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

复杂链表的复制

题目

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

题解

把复制的结点链接在原始链表的每一对应结点后面
把复制的结点的random指针指向被复制结点的random指针的下一个结点
拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，next指针要重新赋值None(判定程序会认定你没有完成复制）

代码

# -*- 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):
        # 返回 RandomListNode
        if not pHead:
            return None

        p = pHead
        # first step, N' to N next
        while p:
            pnext = p.next
            copynode = RandomListNode(p.label)
            copynode.next = pnext
            p.next = copynode
            p = pnext

        p = pHead

        # second step, random' to random'
        while p:
            copyp = p.next
            if p.random:
                copyp.random = p.random.next
            p = copyp.next

        p = pHead
        # third step, split linked list
        copyHead = pHead.next
        while p:
            copynode = p.next
            pnext = copynode.next
            p.next = pnext
            if pnext:
                copynode.next = pnext.next
            else:
                copynode.next = None
            p = pnext
        return copyHead

二叉搜索树与双向链表

题目

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

代码

## 二维数组中查找#### 题目在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数#### 思路从最右一列往下查找,效率比直接遍历高#### 代码
```# -*- coding:utf-8 -*-class Solution: # array 二维列表 def Find(self, target, array): # write code here i = 0 j = len(array[0])-1 while i <len(array) and j>=0: if target==array[i][j]: return True elif target<array[i][j]: j-=1 else: i+=1 return False```----## 替换空格#### 题目请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。#### 思路一种是建立新的字符串,然后遍历原来的字符串时,加到新的里第二种是原地操作,先统计空格的数量,然后在原字符串后面补足空间,再从后往前遍历替换#### 代码```#1.新空间class Solution: # s 源字符串 def replaceSpace(self, s): # write code here new_s = '' b = '%20' for i in s: if i ==' ': new_s+=b else: new_s+=i return new_s``````class Solution: # s 源字符串 def replaceSpace(self, s): # write code here #字符串不能直接修改和添加,所以要先转为list   s = list(s) blank = s.count(' ') lenght = len(s) s += [0]*2*blank new_len = len(s) while lenght: if s[lenght-1]==' ': s[new_len-1]='0' s[new_len-2]='2' s[new_len-3]='%' new_len-=3 else: s[new_len-1]=s[lenght-1] new_len-=1 lenght-=1 #把list重新转为字符串 s = ''.join(s) return s```----## 从尾到头打印链表#### 题目输入一个链表，按链表从尾到头的顺序返回一个ArrayList。#### 代码```#?好像很简单class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, ListNode): # write code here if not ListNode: return [] res = [] while ListNode: res.append(ListNode.val) ListNode = ListNode.next return res[::-1]```----## 重建二叉树#### 题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 = Noneclass Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here if not pre or not tin: return None     root = TreeNode(pre.pop(0)) index = tin.index(root.val) root.left = self.reConstructBinaryTree(pre,tin[:index]) root.right = self.reConstructBinaryTree(pre, tin[index + 1:])     return root``` ## 用两个栈实现队列#### 代码````class Solution: #使用self，把stack1,2当作class的两个属性，pop和push成为两个方法 def __init__(self): self.stack1 = [] self.stack2 = [] def push(self,node): self.stack1.append(node) def pop(self): if self.stack2: return self.stack2.pop() else: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop()````
----## 旋转数组的最小数字#### 题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。\输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。\例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。\NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。#### 代码```#就是变形的查找，可以简单查找，也可以二分查找class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if not rotateArray: return 0 if len(rotateArray)==2: return rotateArray[1] res = len(rotateArray)/2 if rotateArray[res]<rotateArray[0]: return self.minNumberInRotateArray(rotateArray[:res+1]) elif rotateArray[res]>rotateArray[0]: return self.minNumberInRotateArray(rotateArray[res:]) else: for i in range(1,len(rotateArray)): if rotateArray[i] < rotateArray[0]: return rotateArray[i] return rotateArray[0]   ```
----
## 斐波那契数列#### 题目大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39#### 代码```#递归很简单，也可以用迭代# -*- coding:utf-8 -*-class Solution: def Fibonacci(self, n): res = [0,1,1,2] while len(res)<=n: res.append(res[-1]+res[-2]) return res[n] # write code here   ```----## 跳台阶#### 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。#### 分析跳上第n个台阶有两种情况，从n-1跳一阶上去和从n-2跳两阶上去，因此可能的情况为f(n-1)+f(n-2)，也就是斐波那契数列#### 代码```# -*- coding:utf-8 -*-class Solution: def jumpFloor(self, number): # write code here a = 1 b = 1 for i in range(number): a,b = b,a+b return a```----## 变态跳台阶#### 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。#### 思路易知 f(n)=f(n-1)+f(n-2)+……f(1)f(n-1)=f(n-2)+……f(1)两式相减得f(n)=2f(n-1)#### 代码```# -*- coding:utf-8 -*-class Solution: def jumpFloorII(self, number): # write code here if number <= 0: return 0 else: return pow(2,number-1)```----## 矩形覆盖#### 题目我们可以用2* 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2* 1的小矩形无重叠地覆盖一个2* n的大矩形，总共有多少种方法？
----## 二进制中1的个数#### 题目输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
----## 调整数组顺序使奇数位于偶数前面#### 题目输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。#### 思路题目本身不难,简单的方法有\一:遍历数组,将奇数放在第一个,偶数放在最后一个,同时移动其他数的位置,时间复杂度较高.\二:另开两个数组,分别存储奇偶数,再合起来,空间复杂度较高\三:对复杂度有要求时,可以使用两个指针,分别从头尾出发,到遇到奇偶数时调换两个的位置#### 3代码```#牛客上通不过的实例本地没问题# -*- coding:utf-8 -*-class Solution: def reOrderArray(self, array): # write code here length = len(array) p1 = 0 p2 = length-1 while p1<p2: while array[p1]%2!=0: p1+=1 while array[p2]%2==0: p2-=1 if p1<p2: array[p1],array[p2]=array[p2],array[p1] p1+=1 p2-=1 return array```----## 链表中倒数第k个节点#### 题目输入一个链表，输出该链表中倒数第k个结点。#### 代码```# -*- 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==None or k<=0: return None res = 0 p = q = head while res<k-1 and q: q = q.next res+=1 if q is None: return None while q.next: q = q.next p = p.next return p```----## 反转链表#### 题目输入一个链表，反转链表后，输出新链表的表头。#### 思路想清楚思路就简单,不然很乱\思路:\①从None创建一个新链表,标记链表第一个,\②标记原链表的第一个,从原链表上一个一个摘下来,添到新链表的头上\③另外还需要标记原链表的第二个,防止丢失#### 代码```class Solution: def ReverseList(self, pHead): # write code here if pHead == None: return None    p2 = None p1 = pHead    while p1!=None: tmp = p1.next p1.next = p2 p2 = p1 p1 = tmp return p2```----## 合并两个排序链表#### 题目输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。#### 代码```#创建一个空节点做头,并且要标记# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here pHead = ListNode(0) p = pHead while pHead1 and pHead2: if pHead1.val<pHead2.val: p.next = pHead1 pHead1 = pHead1.next else: p.next = pHead2 pHead2 = pHead2.next p = p.next if pHead1: p.next = pHead1 if pHead2: p.next = pHead2 return pHead.next```----## 树的子结构#### 题目输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）#### 代码```# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if not pRoot1 or not pRoot2: return False return self.is_subtree(pRoot1,pRoot2) or self.is_subtree(pRoot1.left,pRoot2) or self.is_subtree(pRoot1.right,pRoot2) def is_subtree(self,pRoot1,pRoot2): if not pRoot2: return True if not pRoot1 or pRoot1.val!=pRoot2.val: return False return self.is_subtree(pRoot1.left,pRoot2.left) and self.is_subtree(pRoot1.right,pRoot2.right)```----## 二叉树的镜像#### 题目操作给定的二叉树，将其变换为源二叉树的镜像。#### 代码```# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: # 返回镜像树的根节点 def Mirror(self, root): # write code here if not root: return None root.left,root.right = root.right,root.left root.left = self.Mirror(root.left) root.right = self.Mirror(root.right)     return root```----## 顺时针打印矩阵#### 题目输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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): out = [] while matrix: # 上边界即为数组的第一个子数组 # 加载第一行 out += matrix.pop(0) # 如果这里仅判断if matrix，那么对于测试数组例[[1],[2],[3]]，循环后变成了[[],[]]，matrix不为空 if matrix and matrix[0]: # 右边界即为数组每一项的最后一个元素 for row in matrix: # 加载每一行的最后一个 out.append(row.pop()) # 下边界即为数组最后一个子数组的逆序排列 if matrix: #倒序加载最后一行 out += matrix.pop()[::-1] if matrix and matrix[0]: # 左边界即为数组从尾到头的每一项子数组的第一个元素 for row in matrix[::-1]: #倒序加载第一列 out.append(row.pop(0)) return out``````#代码2# -*- coding:utf-8 -*-class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): # write code here res=[] n=len(matrix) m=len(matrix[0]) if n==1 and m==1: res=[matrix[0][0]] return res for o in xrange((min(m,n)+1)//2): [res.append(matrix[o][i]) for i in xrange(o,m-o)] [res.append(matrix[j][m-1-o]) for j in xrange(o,n-o) if matrix[j][m-1-o] not in res] [res.append(matrix[n-1-o][k]) for k in xrange(m-1-o,o-1,-1) if matrix[n-1-o][k] not in res] [res.append(matrix[l][o]) for l in xrange(n-1-o,o-1,-1) if matrix[l][o] not in res] return res```----## 包含min函数的栈#### 题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。#### 代码```# -*- coding:utf-8 -*-class Solution: def __init__(self): self.stack = [] self.min_stack = [] def push(self, node): self.stack.append(node) if not self.min_stack or node<=self.min_stack[-1]: self.min_stack.append(node) def pop(self): if self.stack[-1]==self.min_stack[-1]: self.min_stack.pop() self.stack.pop() def top(self): return self.stack[-1] def min(self): return self.min_stack[-1]```----
## 栈的压入,弹出序列#### 题目输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）#### 代码```#思路没问题,但是数组的操作要注意,res全部pop完以后再切片就会报错,所以要加一个判断res是否有元素# -*- coding:utf-8 -*-class Solution: def IsPopOrder(self, pushV, popV): # write code here res = [] while pushV: res.append(pushV.pop(0)) # 加一个while res while res and res[-1]==popV[0] and res: res.pop() popV.pop(0) if not res: return True```----## 从上往下打印二叉树#### 题目从上往下打印出二叉树的每个节点，同层节点从左至右打印。#### 代码```# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): # write code here if not root: return [] res = [root] l = [] while res: a = res.pop(0) l.append(a.val) if a.left: res.append(a.left) if a.right: res.append(a.right) return l```----## 二叉搜索树的后序遍历序列#### 题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。#### 代码```# -*- coding:utf-8 -*-class Solution: def VerifySquenceOfBST(self, sequence): # write code here if len(sequence)==0: return False index = 0 for i in range(len(sequence)): if sequence[i]>sequence[-1]: index = i break for j in range(i,len(sequence)): if sequence[j]<sequence[-1]: return False left = True right = True if len(sequence[:index])>0: left = self.VerifySquenceOfBST(sequence[:index]) if len(sequence[index:-1])>0: right = self.VerifySquenceOfBST(sequence[index:-1]) return left and right```----## 二叉树中和为某一值的路径#### 题目输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)----## 复杂链表的复制#### 题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）#### 题解 1. 把复制的结点链接在原始链表的每一对应结点后面![image](https://uploadfiles.nowcoder.com/images/20160726/737942_1469488971641_84B136C6E4052690517046794A4F80B0) 2. 把复制的结点的random指针指向被复制结点的random指针的下一个结点![image](https://uploadfiles.nowcoder.com/images/20160726/737942_1469488996797_F052D5F977FA4E843FE926BA3200084A)3. 拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，next指针要重新赋值None(判定程序会认定你没有完成复制）![image](https://uploadfiles.nowcoder.com/images/20160726/737942_1469489231960_95E2453212A43966E21F1ABC09A80999)#### 代码```# -*- coding:utf-8 -*-# class RandomListNode:# def __init__(self, x):# self.label = x# self.next = None# self.random = Noneclass Solution: # 返回 RandomListNode def Clone(self, pHead): # 返回 RandomListNode if not pHead: return None    p = pHead # first step, N' to N next while p: pnext = p.next copynode = RandomListNode(p.label) copynode.next = pnext p.next = copynode p = pnext     p = pHead     # second step, random' to random' while p: copyp = p.next if p.random:   copyp.random = p.random.next p = copyp.next     p = pHead     # third step, split linked list copyHead = pHead.next while p: copynode = p.next pnext = copynode.next p.next = pnext if pnext: copynode.next = pnext.next else: copynode.next = None p = pnext return copyHead```----## 二叉搜索树与双向链表#### 题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。#### 代码