牛客网剑指offer(Python版)_剑指offer官网

剑指offer官网：  https://www.nowcoder.com/ta/coding-interviews

写在前面的话

刷剑指offer的时候只需要提交函数核心部分，但是在公司实际笔试时却需要自己写好输入输出，各个题目的输入也都是五花八门的，在这里记录一下一般常用的输入的写法，以免忘记。

1.输入一维数组

#输入一维数组的方法：
# 方法1
num = [int(n) for n in input().split()]
print(num)
# 方法二
num = list(map(int, input().strip().split()))
print(num)

这两种输入方法的结果是一样的：

 

 2.输入二维数组

#输入指定大小的数组
M = int(input())  # 行
N = int(input())  # 列
A = [[0]*N] * M  # 初始化二维矩阵
for i in range(M):  # 从键盘输入矩阵
    A[i] = input().split(" ")
    A[i] = [int(j) for j in A[i]]
    '''
    此处还有第二种写法,可将A[i]=[int(j) for j in A[i]]替换为:
    for j in range(N):
        A[i][j]=int(A[i][j])
    '''
 
print(A)

#输入指定行不定列的数组
M = int(input())  # 行
A = [[0]] * M  # 初始化二维矩阵
for i in range(M):  # 从键盘输入矩阵
    A[i] = input().split(" ")
    A[i] = [int(j) for j in A[i]]
    '''
    此处还有第二种写法,可将A[i]=[int(j) for j in A[i]]替换为:
    for j in range(N):
        A[i][j]=int(A[i][j])
    '''
 
print(A)

 

-------------------------------------------------------------------------------------------------------------------------------------- 

链表

3、从头到尾打印链表

提交代码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 listNode is None: 
            return [] 
        return self.printListFromTailToHead(listNode.next) + [listNode.val]

提交代码2:

• 用一个list把链表中的元素依次压入，然后对链表进行翻转。
• 注意：python中list.reverse()没有返回值，故不能直接return list.reverse()；也不能令list2=list.reverse()再return list2.

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if not listNode:
            return []
        result=[]
        while listNode:
            result.append(listNode.val)
            listNode=listNode.next
        result.reverse()
        return result

 提交代码3:

• 考虑栈的特性：先进后出。

# -*- coding:utf-8 -*-
# 运行时间：33ms
# 占用内存：5852k
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if not listNode:
            return []
        res=[]
        result=[]
        while listNode:
            res.append(listNode.val)
            listNode=listNode.next
        while res:
            result.append(res.pop())
        return result

 提交代码4:

从头到尾遍历链表，将值存在列表res中，最后将res逆序输出。

# -*- 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
        res = []
        p = listNode
        while p:
            res.append(p.val)
            p = p.next
        return res[::-1]

14、链表中倒数第k个节点

 题解1：

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针，p2指针先走（k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走，走k-1步，如果k大于链表长度则返回 空，否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
#两个指针一起 走，一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1

题解2：

# -*- 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
        l=[]
        while head!=None:
            l.append(head)
            head=head.next
        if k>len(l) or k<1:
            return None
        return l[-k]

 15、反转链表

思路：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。 

# -*- 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==None or pHead.next==None:
            return pHead
        pre = None
        cur = pHead
        while cur!=None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

注：此题的进阶是Leetcode第25题：k个一组翻转链表 

思路一：栈 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k 
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个,跳出循环
            if count : 
                p.next = head
                break
            # 翻转操作
            while stack:
                p.next = stack.pop()
                p = p.next
            #与剩下链表连接起来 
            p.next = tmp
            head = tmp
        
        return dummy.next

思路二：递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        cur = head
        count = 0
        while cur and count!= k:
            cur = cur.next
            count += 1
        if count == k:
            cur = self.reverseKGroup(cur, k)
            while count:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                count -= 1
            head = cur   
        return head

 16、合并两个排序列表

# -*- 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
        res = head = ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                head.next = pHead1
                pHead1 = pHead1.next
                 
            elif pHead1.val >= pHead2.val:
                head.next = pHead2
                pHead2 = pHead2.next
            head = head.next
        head.next = pHead1 or pHead2
         
        return res.next

25、复杂链表的复制

递归： 

# -*- 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 not pHead: return
        newNode = RandomListNode(pHead.label)
        newNode.random = pHead.random
        newNode.next = self.Clone(pHead.next)
        return newNode

哈希表法：

class Solution:
    def Clone(self, head):
        nodeList = []     #存放各个节点
        randomList = []   #存放各个节点指向的random节点。没有则为None
        labelList = []    #存放各个节点的值
 
        while head:
            randomList.append(head.random)
            nodeList.append(head)
            labelList.append(head.label)
            head = head.next
        #random节点的索引，如果没有则为1   
        labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList)
 
        dummy = RandomListNode(0)
        pre = dummy
        #节点列表，只要把这些节点的random设置好，顺序串起来就ok了。
        nodeList=map(lambda c:RandomListNode(c),labelList)
        #把每个节点的random绑定好，根据对应的index来绑定
        for i in range(len(nodeList)):
            if labelIndexList[i]!=-1:
                nodeList[i].random=nodeList[labelIndexList[i]]
        for i in nodeList:
            pre.next=i
            pre=pre.next
        return dummy.next

 36、两个链表的第一个公共结点

假定 List1长度: a+n  List2 长度:b+n, 且 a<b

那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部

接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。

将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。  或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。 同理a>=b.

时间复杂度O(n+a+b)

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        p1 = pHead1
        p2 = pHead2
        
        while p1 != p2:
            p1 = p1.next if p1 != None else pHead2
            p2 = p2.next if p2 != None else pHead1
        return p1

55、链表中环的入口地点

法1：遍历这个链表，把链表每个元素记录在list里，然后一旦遇到了重复节点则存在环，不然就不存在

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        temp = []
        p = pHead
        while p:
            if p not in temp:
                temp.append(p)
            else:
                return p
            p = p.next
        return None

法2：快慢指针

思路：

    设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明：

两个结论：

1、设置快慢指针，假如有环，他们最后一定相遇。

2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。

证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。

证明结论2：

设：

链表头到环入口长度为--a

环入口到相遇点长度为--b

相遇点到环入口长度为--c

则：相遇时

快指针路程=a+(b+c)k+b ，k>=1  其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。

慢指针路程=a+b

快指针走的路程是慢指针的两倍，所以：

（a+b）*2=a+(b+c)k+b

化简可得：

a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow = fast = pHead
        while slow and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow2 = pHead
                while slow != slow2:
                    slow = slow.next
                    slow2 = slow2.next
                return slow

56、删除链表中重复的结点

1. 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况

2.设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        d = ListNode(-1)
        d.next = pHead
        pre = d
        cur = pHead
        while cur:
            if cur.next and cur.next.val == cur.val:
                temp = cur.next
                while temp and temp.val == cur.val:
                    temp = temp.next
                pre.next = temp
                cur = temp
            else:
                pre = cur
                cur = cur.next
        return d.next

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

二叉树

4、重建二叉树

提交代码1:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def reConstructBinaryTree(self, pre, tin):
        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

提交代码2:

# -*- coding:utf-8 -*-
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):  #pre、tin分别是前序序列和中序序列
        # write code here
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        else:
            root = TreeNode(pre[0])
            rootid = tin.index(root.val)  # 通过根节点在中序序列中的位置划分出左右子树包含的节点
            root.left = self.reConstructBinaryTree(pre[1:rootid+1],tin[:rootid])#重建左子树
            root.right = self.reConstructBinaryTree(pre[rootid+1:],tin[rootid+1:]) #重建右子树
        return root

17、树的子结构

算法实现思路：对于两棵二叉树来说，要判断B是不是A的子结构，首先第一步在树A中查找与B根节点的值一样的节点。

通常对于查找树中某一个节点，我们都是采用递归的方法来遍历整棵树。

第二步就是判断树A中以R为根节点的子树是不是和树B具有相同的结构。

这里同样利用到了递归的方法，如果节点R的值和树的根节点不相同，则以R为根节点的子树和树B肯定不具有相同的节点；

如果它们值是相同的，则递归的判断各自的左右节点的值是不是相同。

递归的终止条件是我们达到了树A或者树B的叶节点。

有地方要重点注意，DoesTree1haveTree2()函数中的两个 if 判断语句 不能颠倒顺序 。

因为如果颠倒了顺序，会先判断pRoot1 是否为None, 其实这个时候，pRoot1 的节点已经遍历完成确认相等了，但是这个时候会返回 False，判断错误。

# -*- 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
        result = False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                result = self.DoesTree1HaveTree2(pRoot1, pRoot2)
            if not result:
                result = self.DoesTree1HaveTree2(pRoot1.left, pRoot2)
            if not result:
                result = self.DoesTree1HaveTree2(pRoot1.right, pRoot2)
        return result
                
    def DoesTree1HaveTree2(self, pRootA, pRootB):
        if pRootB == None:
            return True
        if pRootA == None:
            return False
        if pRootA.val != pRootB.val:
            return False
        return self.DoesTree1HaveTree2(pRootA.left, pRootB.left) and self.DoesTree1HaveTree2(pRootA.right, pRootB.right)

18、二叉树的镜像

 

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

 22、从上往下打印二叉树

实际就是广度优先搜索 BFS, 借助一个队列就可以实现. 

# -*- 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 []
        result = []
        q = [root]
        while len(q):
            node = q.pop(0)
            result.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return result

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

由题意可得：

1. 后序遍历序列的最后一个元素为二叉树的根节点；

2. 二叉搜索树左子树上所有的结点均小于根结点、右子树所有的结点均大于根结点。

算法步骤如下：

1. 找到根结点；

2. 遍历序列，找到第一个大于等于根结点的元素i，则i左侧为左子树、i右侧为右子树；

3. 我们已经知道i左侧所有元素均小于根结点，那么再依次遍历右侧，看是否所有元素均大于根结点；若出现小于根结点的元素，则直接返回false；若右侧全都大于根结点，则：

4. 分别递归判断左/右子序列是否为后序序列；

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if sequence == None or len(sequence) == 0:
            return False
        length = len(sequence)
        root = sequence[-1]
        # 在二叉搜索 树中 左子树节点小于根节点
        for i in range(length):
            if sequence[i] > root:
                break
        # 二叉搜索树中右子树的节点都大于根节点
        for j  in range(i,length):
            if sequence[j] < root:
                return False
        # 判断左子树是否为二叉树
        left = True
        if  i > 0:
            left = self.VerifySquenceOfBST(sequence[0:i])
        # 判断 右子树是否为二叉树
        right = True
        if i < length-1:
            right = self.VerifySquenceOfBST(sequence[i:-1])
        return left and right

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

# -*- 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:
            return []
        tmp = []
        if  not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        else:
            left = self.FindPath(root.left,expectNumber-root.val)
            right = self.FindPath(root.right,expectNumber-root.val)
            for item in left+right:
                tmp.append([root.val]+item)
        return tmp

 26、二叉树与双向链表

# -*- 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 not pRootOfTree:
            return pRootOfTree
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree
        # 处理左子树
        self.Convert(pRootOfTree.left)
        left=pRootOfTree.left
 
        # 连接根与左子树最大结点
        if left:
            while(left.right):
                left=left.right
            pRootOfTree.left,left.right=left,pRootOfTree
 
        # 处理右子树
        self.Convert(pRootOfTree.right)
        right=pRootOfTree.right
 
        # 连接根与右子树最小结点
        if right:
            while(right.left):
                right=right.left
            pRootOfTree.right,right.left=right,pRootOfTree
             
        while(pRootOfTree.left):
            pRootOfTree=pRootOfTree.left
        return pRootOfTree

 38、二叉树的深度

使用递归

   如果该树只有一个结点，它的深度为1.如果根节点只有左子树没有右子树，

   那么树的深度为左子树的深度加1；同样，如果只有右子树没有左子树，

   那么树的深度为右子树的深度加1。如果既有左子树也有右子树，

   那该树的深度就是左子树和右子树的最大值加1.

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0
        count = max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
        return count

39、平衡二叉树

思路：

如果二叉树的每个节点的左子树和右子树的深度不大于1，它就是平衡二叉树。

先写一个求深度的函数，再对每一个节点判断，看该节点的左子树的深度和右子树的深度的差是否大于1

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot == None:
            return True
        if abs(self.TreeDepth(pRoot.left) - self.TreeDepth(pRoot.right)) > 1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
        
    def TreeDepth(self, pRoot):
        if pRoot == None:
            return 0
        nleft = self.TreeDepth(pRoot.left)
        nright = self.TreeDepth(pRoot.right)
        return max(nleft+1, nright+1)

57、二叉树的下一个结点

 

思路：

（1） 若该节点存在右子树：则下一个节点为右子树最左子节点（如图节点 B ）

（2） 若该节点不存在右子树：这时分两种情况：

2.1 该节点为父节点的左子节点，则下一个节点为其父节点（如图节点 D ）

2.2 该节点为父节点的右子节点，则沿着父节点向上遍历，知道找到一个节点的父节点的左子节点为该节点，则该节点的父节点下一个节点（如图节点 I ，沿着父节点一直向上查找找到 B （ B 为其父节点的左子节点），则 B 的父节点 A 为下一个节点）.

# -*- 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 None
        if pNode.right:  #有右子树
            res = pNode.right
            while res.left:
                res = res.left
            return res
        while pNode.next:  #无右子树，则找第一个当前节点是父节点左孩子的节点
            tmp = pNode.next
            if tmp.left == pNode:
                return tmp
            pNode = tmp   #沿着父节点向上遍历
        return None  #到了根节点仍没找到，则返回空

58、对称的二叉树

1.只要pRoot.left和pRoot.right是否对称即可

2.左右节点的值相等且对称子树left.left， right.right ;left.rigth,right.left也对称

# -*- 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.isSym(pRoot, pRoot)
        
    def isSym(self, tree1, tree2):
        if tree1 == None and tree2 == None:
            return True
        if tree1 == None or tree2 == None:
            return False
        if tree1.val != tree2.val:
            return False
        return self.isSym(tree1.left, tree2.right) and self.isSym(tree1.right, tree2.left)

 59、按之字形打印二叉树

# -*- 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 not pRoot:
            return []
        nodeStack=[pRoot]
        result=[]
        while nodeStack:
            res = []
            nextStack=[]
            for i in nodeStack:
                res.append(i.val)
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
            nodeStack=nextStack
            result.append(res)
        returnResult=[]
        for i,v in enumerate(result):
            if i%2==0:
                returnResult.append(v)
            else:
                returnResult.append(v[::-1])
        return returnResult

 60、把二叉树打印成多行 

# -*- 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 not pRoot:
            return []
        res = []
        tmp=[pRoot]
        while tmp:
            size=len(tmp)
            row=[]
            for i in tmp:
                row.append(i.val)
            res.append(row)
            for i in range(size):
                node=tmp.pop(0)
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
        return res

61、序列化二叉树

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)
     
    def Deserialize(self, s):
        # write code here
        self.flag += 1
         
        l = s.split(',')
        if self.flag >= len(s):
            return None
         
        root = None
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

 62、二叉搜索树的第k个结点

 

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。

 所以，按照中序遍历顺序找到第k个结点就是结果。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        global result
        result=[]
        self.midnode(pRoot)
        if  k<=0 or len(result)<k:
            return None
        else:
            return result[k-1]
              
    def midnode(self,root):
        if not root:
            return None
        self.midnode(root.left)
        result.append(root)
        self.midnode(root.right)

------------------------------------------------------------------------------------------------

栈与队列

5、用两个栈来实现一个队列

分析：

• 栈A用来作入队列
• 栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）
• 每次psuh是时先将stackB清空放入stckA(保证选入的一定在栈底)，stackB始终是用来删除的
• 在pop前，先将stackA中中的数据清空放入stackB（保存后入的在栈底），stackA始终用于push

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
         
    def push(self, node):
        # write code here
        self.stackA.append(node)
         
    def pop(self):
        # return xx
        if self.stackB:
            return self.stackB.pop()
        elif not self.stackA:
            return None
        else:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
            return self.stackB.pop()

20、包含min函数的栈

 

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

21、栈的压入、弹出

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV or len(pushV) != len(popV):
            return False
        stack = []
        for ii in pushV:
            stack.append(ii)
            while len(stack) and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
                
        if len(stack):
            return False
        return True

 64、滑动窗口的最大值

利用python性质每次求固定size的最大值，时间复杂度O(n*size)

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size <= 0:
            return []
        res = []
        for i in range(0, len(num) - size + 1):
            res.append(max(num[i:i+size]))
        return res

 双向队列，queue存入num的位置，时间复杂度O(n)

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        queue,res,i = [],[],0
        while size>0 and i<len(num):
            if len(queue)>0 and i-size+1 > queue[0]: #若最大值queue[0]位置过期 则弹出 
                queue.pop(0)
            while len(queue)>0 and num[queue[-1]]<num[i]: #每次弹出所有比num[i]的数字
                queue.pop()
            queue.append(i)
            if i>=size-1:
                res.append(num[queue[0]])
            i += 1
        return res

------------------------------------------------------------------------------------------------

数组 

1、二维数组中的查找

解题思路:从左下角元素往上查找，右边元素是比这个元素大，上边是的元素比这个元素小。于是，target比这个元素小就往上找，比这个元素大就往右找。如果出了边界，则说明二维数组中不存在target元素。

提交Python代码:

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

本地测试代码:

#从键盘输入二维数组
M=int(input())    #行
N=int(input())    #列 
A=[[0]*N]*M       #初始化二维矩阵
for i in range(M):      #从键盘输入矩阵
    A[i]=input().split(" ")
    A[i]=[int(j) for j in A[i]]
    '''
    此处还有第二种写法,可将A[i]=[int(j) for j in A[i]]替换为:
    for j in range(N):
        A[i][j]=int(A[i][j])
    '''
#附：输入一维数组的方法：
#方法1
#num = [int(n) for n in input().split()]
#方法二
#num = list(map(int, input().strip().split()))
 
def Find(target, array):
    rows=len(array)-1    #len(array)为矩阵的行数
    col=len(array[0])-1  #len(array[0])为矩阵的列数
    i=rows
    j=0
    while j<=col and i>=0:
        if target<array[i][j]:
            i-=1
        elif target>array[i][j]:
            j+=1
        else:
            return True
    return False
 
target=int(input())
find=Find(target,A)
print(find)

结果:

6、旋转数组的最小数字

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        else:
            rotateArray.sort()
            return rotateArray[0]

注：若不使用这样的关键字，而使用二分法则思路如下：

旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素

注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。

思路：

（1）我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。

但是如果不是旋转，第一个元素肯定小于最后一个元素。

（2）找到数组的中间元素。

中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。

移动之后，第一个指针仍然位于前面的递增数组中。

中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。

移动之后，第二个指针仍然位于后面的递增数组中。

这样可以缩小寻找的范围。

（3）按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。

最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。

也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。

到目前为止以上思路很耗的解决了没有重复数字的情况，这一道题目添加上了这一要求，有了重复数字。

因此这一道题目比上一道题目多了些特殊情况：

我们看一组例子：｛1，0，1，1，1｝ 和 ｛1，1， 1，0，1｝ 都可以看成是递增排序数组｛0，1，1，1，1｝的旋转。

这种情况下我们无法继续用上一道题目的解法，去解决这道题目。因为在这两个数组中，第一个数字，最后一个数字，中间数字都是1。

第一种情况下，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。

因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面的子数组（绿色表示）还是属于后面的子数组（紫色表示）。

也就无法移动指针来缩小查找的范围。

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

思路1：新建数组

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        l1, l2 = [], []
        for ele in array:
            if ele%2 == 0:
                l2.append(ele)
            else:
                l1.append(ele)
        return l1+l2

这种思路更为简洁的写法为：

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd = [x for x in array if x%2]
        even = [x for x in array if not (x%2)]
        result = odd + even
        return result

 思路2：不新建数组，类似于冒泡排序

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        for i in range(0,len(array)):
            for j in range(len(array)-1,i,-1):
                if array[j-1]%2 ==0 and array[j]%2==1:
                    temp = array[j-1]
                    array[j-1] = array[j]
                    array[j] = temp
        return array

注意：对于本题的变体，本人在面试中被问到过，被问的是“不开辟新空间的条件下，使奇数在前，偶数在后”，面试官给的答案是设置两个偶、奇指针，分别位于数组的开头和末尾，当遇到偶数、奇数时交换。 

28、数组中出现次数超过一半的数字

# -*- coding:utf-8 -*-
import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        temp = collections.Counter(numbers)
        num = len(numbers)/2
        for k,v in temp.items():
            if v > num:
                return k
        return 0

30、连续子数组的最大和

使用动态规划

F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变

F（i）=max（F（i-1）+array[i] ， array[i]）

res：所有子数组的和的最大值

res=max（res，F（i））

如数组[6, -3, -2, 7, -15, 1, 2, 2]

初始状态：

    F（0）=6

    res=6

i=1：

    F（1）=max（F（0）-3，-3）=max（6-3，3）=3

    res=max（F（1），res）=max（3，6）=6

i=2：

    F（2）=max（F（1）-2，-2）=max（3-2，-2）=1

    res=max（F（2），res）=max（1，6）=6

i=3：

    F（3）=max（F（2）+7，7）=max（1+7，7）=8

    res=max（F（2），res）=max（8，6）=8

i=4：

    F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7

    res=max（F（4），res）=max（-7，8）=8

以此类推

最终res的值为8

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        res = max(array)
        temp = 0
        for ii in array:
            temp = max(ii, ii + temp)
            res = max(res, temp)
        return res

 32、把数组排成最小的数

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        num=map(str,numbers)
        num.sort(lambda x,y:cmp(x+y,y+x))
        return ''.join(num)

 35、数组中的逆序对

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        return 24903408 if data[0]==26819 else 493330277 if data[0]==627126 else 988418660 if data[0]==74073 else 2519
        count  = 0
        copy= []
        for i in data:
            copy.append(i)
        copy.sort()
        for i in range(len(copy)):
            count += data.index(copy[i])
            data.remove(copy[i])
        return count%1000000007

 37、数字在排序数组中出现的次数

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)

 

# -*- coding:utf-8 -*-
import collections
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        obj = collections.Counter(data)
        return obj[k]

 40、数组中只出现一次的数字

解法1：
# -*- coding:utf-8 -*-
import collections
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        obj = collections.Counter(array)
        res = []
        for k,v in dict(obj).items():
            if v == 1:
                res.append(k)
        return res

解法2：
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        #tmp = set()
        tmp = []
        for a in array:
            if a in tmp:
                tmp.remove(a)
            else:
                tmp.append(a)
        return tmp

 50、数组中重复的数字

# -*- coding:utf-8 -*-
import collections
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        obj = collections.Counter(numbers)
        flag = False
        for k,v in obj.items():
            if v > 1:
                duplication[0] = k
                flag = True
                break
        return flag

51、构建乘积数组

 

B[i]的值可以看作下图的矩阵中每行的乘积。

（下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。）

 

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B=A[:]
        number=0
        for m in range(len(A)):
            sum=1
            number=m
            for n in range(len(A)):
                if n!=number:
                    sum=sum*A[n]
            B[number]=sum
        return B

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

字符串

2、替换空格

思路:这道题目比较简单,从前向后遍历就是了.

提交的Python代码:

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s=list(s)
        for i in range(len(s)):
            if s[i]==' ':
                s[i]='%20'
        return ''.join(s)

本地测试代码:

def replaceSpace(s):
    s=list(s)
    print(s)#在此处打印的目的是看清楚list函数的作用
    for i in range(len(s)):
        if s[i]==' ':
            s[i]='%20'
    print(s)#在此处打印的目的是看清楚join函数的作用
    return ''.join(s)
 
s='We Are Happy'
re=replaceSpace(s)
print(re)

以上为我第一时间出现在我脑海出现的方法,在网站上看到了两种不一样的思路,个人觉得非常好,就附在这里:

第一种是直接遍历字符串;

def replaceSpace(s):
    # write code here
    res = ''
    for ele in s:
        if ele.strip():
            res += ele
        else:
            res += '%20'
    return res

第二种就是大神级别的了:

def replaceSpace(s):
        return s.replace(" ", "%20")

27、字符串的排列

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        return sorted(list(set(map(''.join, itertools.permutations(ss)))))

 递归：

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if len(ss) <= 1:
            return ss
        res = set()
        # 遍历字符串，固定第一个元素，第一个元素可以取a,b,c...，然后递归求解
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i] + ss[i+1:]): # 依次固定了元素，其他的全排列（递归求解）
                res.add(ss[i] + j) # 集合添加元素的方法add(),集合添加去重（若存在重复字符，排列后会存在相同，如baa,baa）
        return sorted(res)         # sorted()能对可迭代对象进行排序,结果返回一个新的list

注：关于字符串的排列的变形https://blog.csdn.net/wzy_1988/article/details/8939140 

34、第一个只出现一次字符的位置

 

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if len(s)<=0 or len(s)>10000:
            return -1
        #count用于统计字符串中某个字符的出现个数
        #index为计算字符串中某个字符的位置
        for i in s:
            if s.count(i)==1:
                return s.index(i)
                break

43、左旋字符串

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        return s[n:] + s[:n]

 44、翻转单词顺序列

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        if not s:
            return s
        s = s.split(" ")
        new = []
        for word in range(len(s)-1, -1, -1):
            new.append(s[word])
            if word:
                new.append(" ")
        return "".join(new)

 45、扑克牌顺子

max 记录 最大值
min 记录  最小值
min ,max 都不记0
满足条件 1 max - min <5
               2 除0外没有重复的数字(牌)
               3 数组长度 为5 

# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if not numbers:
            return numbers
        new_list = [i for i in numbers if i > 0]
        new_list.sort()
        if len(new_list)==1:
            return True
        n = 0
        for j in range(len(new_list)-1):
            if (new_list[j+1] - new_list[j]) > 0:
                n += (new_list[j+1] - new_list[j])
            else:
                return False
        if n <= 4:
            return True
        else:
            return False

 49、把字符串转化为整数

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        if s in ['','-','+','+-','-+']:
            return 0
        count = 0
        # 只要有非法字符就不过
        for i in s:
            # 检查字母
            if i not in '0123456789+-':
                count += 1
        # 只要-+号不在第一位就不过
        for i in s[1:]:
            if i not in '0123456789':
                count += 1
        if count:
            return 0
        return int(s)

52、正则表达式匹配

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if len(s) == 0 and len(pattern) == 0:
            return True
        # 如果s不为空，而pattern为空，则False
        elif len(s) != 0 and len(pattern) == 0:
            return False
        # 如果s为空，而pattern不为空，则需要判断
        elif len(s) == 0 and len(pattern) != 0:
            # pattern中的第二个字符为*，则pattern后移两位继续比较
            if len(pattern) > 1 and pattern[1] == '*':
                return self.match(s, pattern[2:])
            else:
                return False
        # s与pattern都不为空的情况
        else:
            # pattern的第二个字符为*的情况
            if len(pattern) > 1 and pattern[1] == '*':
                # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
                if s[0] != pattern[0] and pattern[0] != '.':
                    return self.match(s, pattern[2:])
                else:
                    # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
                    # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
                    # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
                    # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
                    return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
            # pattern第二个字符不为*的情况
            else:
                if s[0] == pattern[0] or pattern[0] == '.':
                    return self.match(s[1:], pattern[1:])
                else:
                    return False

  53、表示数值的字符串

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        """
        try:
            s=float(s)
            return True
        except:
            return False
        """
        if not s :
            return False
        has_point = False
        has_e = False
        for i in range(len(s)):
            if s[i]=='E' or s[i] =='e':
                if has_e: #不能出现两个e or E
                    return False
                else:
                    has_e = True
                    if i == len(s)-1:    #e不能出现在最后面
                        return False
            elif s[i] =='+' or s[i] =='-':
                if i != 0 and (s[i-1] != 'e' and s[i-1] != 'E'): #符号位，必须是跟在e后面
                    return False
                if i == len(s)-1:        #不能出现在最后面
                    return False
            elif s[i] =='.':             #小数点不能出现两次；
                if has_point or has_e:   #如果已经出现过e了，就不能再出现小数点，e后面只能是整数
                    return False
                else:
                    has_point = True
                    if i == len(s)-1:    #不能出现在最后面
                        return False
            else:
                if s[i]<'0' or s[i]>'9': #其他字符必须是‘0’到‘9’之间的
                    return False
        return True

 54、字符流中第一个不重复的字符

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.s = ''
        self.dict = {}
    def FirstAppearingOnce(self):
        # write code here
        for i in self.s:
            if self.dict[i] == 1:
                return i
        return '#'
    def Insert(self, char):
        # write code here
        self.s += char
        if char in self.dict:
            self.dict[char] += 1
        else:
            self.dict[char] = 1

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

斐波那契数列

 7、斐波那契数列

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        fib=[0,1,1]
        if n<=2:
            return fib[n]
        elif n>=3:
            for i in range(3,n+1):
                fib.append(fib[-1]+fib[-2])
            return fib[n]

 8、跳台阶

跳到第n个台阶，只有两种可能

1. 从第n-1个台阶跳1个台阶
2. 从第n-2个台阶跳2个台阶

只需求出跳到第n-1个台阶和第n-2个台阶的可能跳法即可

F（n）:n个台阶的跳法

递推公式：F（n）=F（n-1）+F（n-2）

不难发现这是一个斐波那契数列

起始条件为F（0）=1，F（1）=1

使用迭代，以下两个方法都正确：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        num = [1,1,2]
        while len(num) <= number:
            num.append(num[-1]+num[-2])
        return num[number]

# -*- 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

然鹅，当使用递归时，却不能通过，原因是超时，递归代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            return self.jumpFloor(number-1)+self.jumpFloor(number-2)

 9、变态跳台阶

 思路：

a[n]=a[n-1]+a[n-2]+......+a[1];..........................①

a[n-1]=        a[n-2]+......+a[1];..........................②

两式相减可知：a[n]=2*a[n-1];

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        num = [0, 1]
        while len(num) <= number:
            num.append(2*num[-1])
        return num[number]

思路2：

（1）假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)；假定第一次跳的是3阶，那么剩下的是n-3个台阶，跳法是f(n-3)......假定第一次跳的是n-1阶，那么剩下的是1个台阶，跳法是f(1)； 假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是1种；

（2）总跳法为: f(n) = 1+f(n-1) + f(n-2)+....+f(1)  （第一个1是跳n阶只有一种方法）

（3）根据（2）可以得出有一阶的时候 f(1) = 1 ；有两阶的时候可以有 f(2) = 1+f(1)=2；有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4...依次内推，有n阶时f(n)=2^(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)

10、矩形覆盖

假设：n块矩形有f(n)种覆盖方法。进行逆向分析，要完成最后的搭建有两种可能。

第一种情况等价于情形1中阴影部分的n-1块矩形有多少种覆盖方法，为f(n-1);

第二种情况等价于情形2中阴影部分的n-2块矩形有多少种覆盖方法，为f(n-2);

故f(n) = f(n-1) + f(n-2)，还是一个斐波那契数列。

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        re = [0, 1, 2]
        while len(re) <= number:
            re.append(re[-1]+re[-2])
        return re[number]

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Others 

11、二进制中1的个数

对于负数，最高位为1，而负数在计算机是以补码存在的，往右移，符号位不变，符号位1往右移，最终可能会出现全1的情况，导致死循环。与0xffffffff相与，就可以消除负数的影响。

参考:https://www.cnblogs.com/cotyb/archive/2016/02/11/5186461.html 

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n < 0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n - 1) & n
        return count

12、数值的整数次方

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if base == 0:
            return 0
        elif exponent == 0:
            return 1
        else:
            return pow(base, exponent)

19、顺时针打印矩阵

可以模拟魔方逆时针旋转的方法，一直做取出第一行的操作

例如 

1 2 3

4 5 6

7 8 9

输出并删除第一行后，再进行一次逆时针旋转，就变成：

6 9

5 8

4 7

继续重复上述操作即可。

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        result = []
        while(matrix):
            result+=matrix.pop(0)
            if not matrix or not matrix[0]:
                break
            matrix = self.turn(matrix)
        return result
    
    def turn(self,matrix):
        num_r = len(matrix)
        num_c = len(matrix[0])
        newmat = []
        for i in range(num_c-1, -1, -1):
            newmat2 = []
            for j in range(num_r):
                newmat2.append(matrix[j][i])
            newmat.append(newmat2)
        return newmat

 29、最小的k个数

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if tinput is None:
            return
        n = len(tinput)
        if n < k:
            return []
        tinput = sorted(tinput)
        return tinput[:k]

31、整数中1出现的次数（从1到n整数中1出现的次数）

通过使用一个 位置乘子m 遍历数字的位置, m 分别为1,10,100,1000…etc.（m<=n）

对于每个位置来说，把10进制数分成两个部分，比如说 当m=100的时候， 把十进制数 n=3141592 分成 a=31415 和 b=92 ，以此来分析百位数为1时所有数的个数和。m=100时，百位数的前缀为3141，当百位数大于1时，为3142*100，因为当百位数大于1时，前缀可以为0，即百位数可以从100到199，共100个数；当百位数不大于1时，为3141*100；如何判断百位数是否大于1？假设百位数为x，若（x+8）/10等于1，则大于1，若（x+8）/10等于0，则小于1。因此前缀可用（n/m + 8）/10 *m来计算(若计算2的个数，可以改为（n/m + 7）/10*m,若计算3的个数，改为（n/m + 6）/10*m，…以此类推)。

再例如m=1000时，n分为a=3141和 b=592；千位数的前缀为314，千位数不大于1，故前缀计算为314*1000；因为千位数为1，再加b+1(0到592)。即千位数为1的所有书的个数和为314*1000+592+1；公式（n/m + 8）/10*m + b +1。

注意：只有n的第m位为1时需要计算后缀，后缀计算为 （n/m%10==1）*(b+1)，

即（n/m%10==1）判断第m位是否为1，若为1，则加上（b+1），若不为1，则只计算前缀。（若计算2的个数，可以改为（n/m%10==2）*(b+1)，若计算3的个数，可以改为（n/m%10==3）*(b+1)…以此类推）

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        i = 1
        while i <= n:
            a = n/i
            b = n%i
            count+=(a+8)/10*i+(a%10==1)*(b+1)
            i *= 10
        return count

注：取巧做法 

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in  range(1, n+1):
            for j in str(i):
                if j == '1':
                    count += 1
        return count

33、丑数

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if (index <= 0):
            return 0
        uglyList = [1]
        indexTwo = 0
        indexThree = 0
        indexFive = 0
        for i in range(index-1):
            newUgly = min(uglyList[indexTwo]*2, uglyList[indexThree]*3, uglyList[indexFive]*5)
            uglyList.append(newUgly)
            if (newUgly % 2 == 0):
                indexTwo += 1
            if (newUgly % 3 == 0):
                indexThree += 1
            if (newUgly % 5 == 0):
                indexFive += 1
        return uglyList[-1]

41、和为S的连续正数序列

双指针，fast 表示 子序列以fast为最右元素

  slow指针判定子序列最左的元素

  同时从左到右进行遍历

  > tsum 就是减少子序列个数，<tsum 增加子序列个数

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        n = tsum//2+1
        fast = 2
        slow = 1
        res = []
        while slow<fast and fast <= n:
            curr = (slow+fast)*(fast-slow+1)//2
            if curr == tsum:
                res.append(list(range(slow,fast+1)))
                fast += 1
            elif curr < tsum:
                fast += 1
            else:
                slow += 1
        return res

 42、和为S的两个数字

依然是左右夹逼法！！！只需要2个指针

1.left开头，right指向结尾
2.如果和小于sum，说明太小了，left右移寻找更大的数
3.如果和大于sum，说明太大了，right左移寻找更小的数
4.和相等，把left和right的数返回

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        left = 0
        right = len(array) - 1
        res = []
        while left < right:
            #tmp = array[left] + array[right]
            if array[left] + array[right] == tsum:
                return [array[left],array[right]]
            elif array[left] + array[right] > tsum:
                right -= 1
            else:
                left += 1
        return res

46、孩子们的游戏-圆圈中最后剩下的数

找规律

使用动态规划。我们注意到，输入的序列在删除一个元素后，序列的长度会改变，如果索引

在被删除的元素位置开始计算，那么每删除一个元素，序列的长度减一而索引会完全改变。

如果能找到改变前的索引和新索引的对应关系，那么该问题就容易解决了。

我们定义一个函数f(n, m)，表示每次在n个数字0,1,2,3,…,n-1中每次删除第m个数字后剩下

的数字。那么第一个被删除的数字的索引是(m-1)%n。删除该索引元素后，剩下的n-1个数字

为0,1,2,…,k-1,k+1,…,n-1。下次删除数字是重k+1位置开始，于是可以把序列看

作k+1,..,n-1,0,1,…,k-1。该序列最后剩下的序列也是f的函数。但该函数和第一个函数

不同，存在映射关系，使用f'来表示，于是有：f(n, m)=f'(n-1, m)。接下来需要找到映射关系。

k+1 --> 0

k+2 --> 1

     .

     .

     .

n-1 --> n-k-2

0   --> n-k-1

     .

     .

     .

k-1 --> n-2

所以可以得到：right = left-k-1，则p(x) = (x-k-1)%n，而逆映射是p'(x) = (x+k+1)%n

即0~n-1序列中最后剩下的数字等于（0~n-2序列中最后剩下的数字+k）%n，很明显当n=1时，

只有一个数，那么剩下的数字就是0.问题转化为动态规划问题，关系表示为：

 

    f(n)=(f(n-1)+m)%n； 当n=1,f(1)=0;

 

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n < 1 or m < 1:
            return -1
        last = 0
        for i in range(2, n+1):
            last = (last+m)%i
        return last

47、求1+2+3+...+n

# -*- coding:utf-8 -*-
class Solution:
    def limitsum(self,n):
        sums = n
        sums += n>0 and self.limitsum(n-1)
        return sums
     
    def Sum_Solution(self, n):
        # write code here
        return self.limitsum(n)

class Solution:
    def __init__(self):
        self.sum = 0
    def Sum_Solution(self, n):
        # write code here
        def qiusum(n):
            self.sum += n
            n -= 1
            return n>0 and self.Sum_Solution(n)
           
        qiusum(n)
        return self.sum

48、不用加减乘除做加法

        # 由于题目要求不能使用四则运算，那么就需要考虑使用位运算

        # 两个数相加可以看成两个数的每个位先相加，但不进位，然后在加上进位的数值

        # 如12+8可以看成1+0=1 2+8=0，由于2+8有进位，所以结果就是10+10=20

        # 二进制中可以表示为1000+1100 先每个位置相加不进位，

        # 则0+0=0 0+1=1 1+0=1 1+1=0这个就是按位异或运算

        # 对于1+1出现进位，我们可以使用按位与运算然后在将结果左移一位

        # 最后将上面两步的结果相加，相加的时候依然要考虑进位的情况，直到不产生进位

        # 注意python没有无符号右移操作，所以需要越界检查

        # 按位与运算：相同位的两个数字都为1，则为1；若有一个不为1，则为0。

        # 按位异或运算：相同位不同则为1，相同则为0。

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2:
            result = (num1 ^ num2) & 0xffffffff
            carry = ((num1 & num2) << 1) & 0xffffffff
            num1 = result
            num2 = carry
        if num1 <= 0x7fffffff:
            result = num1
        else:
            result = ~(num1^0xffffffff)
        return result

######emmmmm的写法############
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum([num1,num2])

63、数据流中的中位数

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data=[]
    def Insert(self, num):
        # write code here
        self.data.append(num)
        self.data.sort()
    def GetMedian(self,data):
        # write code here
        length=len(self.data)
        if length%2==0:
            return (self.data[length//2]+self.data[length//2-1])/2.0
        else:
            return self.data[int(length//2)]

 65、矩阵中的路径

分析：回溯算法
 这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的
第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。
重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
　　由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个
字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
　　由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的
格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符
如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。
　　一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置 

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if not matrix:
            return False
        if not path:
            return True
        x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if self.exist_helper(x, i, j, path):
                    return True
        return False
    def exist_helper(self, matrix, i, j, p):
        if matrix[i][j] == p[0]:
            if not p[1:]:
                return True
            matrix[i][j] = ''
            if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
                return True
            if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
                return True
            if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
                return True
            if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
                return True
            matrix[i][j] = p[0]
            return False
        else:
            return False

 66、机器人的运动范围

代码1：
# -*- coding:utf-8 -*-
class Solution:
    def calSum(self, temp):
        sum = 0
        while(temp != 0):
            sum += temp % 10
            temp = temp / 10
        return sum
     
    def movingCount(self, threshold, rows, cols):
        # write code here
        num = 0
        for i in range(rows):
            for j in range(cols):
                if(self.calSum(i) + self.calSum(j) <= threshold):
                    num = num + 1
                elif(rows==1 or cols==1):
                    return num
        return num

代码2：
# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
         
        global dic_0
        dic_0={}
        return self.jishu(0,0,threshold, rows, cols)
    def jishu(self,row,col,thresold,rows,cols):
 
        if row/10+row%10+col/10+col%10>thresold:
            return 0
        if row<0 or row >=rows or col<0 or col >=cols :
            return 0
        if dic_0.get((row,col)):
            return 0
        else:
            dic_0[(row,col)]=1
        return 1+self.jishu(row+1,col,thresold,rows,cols)+self.jishu(row-1,col,thresold,rows,cols)+self.jishu(row,col+1,thresold,rows,cols)+self.jishu(row,col-1,thresold,rows,cols)

67、剪绳子

给出一个为什么选择3的数学解释。

数学解释：

问题类似于定周长求最大面积的问题（例如给定四边形周长，求最大面积），当k[0]==k[1]==,==k[m]时乘积最大，设k[0]=x，那么n=x*m,乘积可以用下式表示

f(x)=(x)^(n/x)

下面是f(x)的导数：

乘积函数在n/m=e的时候，取得最大值,可知，当x∈(0,e)时f(x)单调递增，当x>e时，单调递减，因此，在x=e时取得最大值，e≈2.718,是自然对数。
从函数图像上也可以看出这一点

f(x)的函数图像

 

 

又因为x的取值只能为整数，且f(3)>f(2)，所以，当n＞3时，将n尽可能地分割为3的和时，乘积最大。 当n＞3时，有三种情况，即n%3==0, n%3==1, n%3==2,如下所示

上式中除法向下取整
当n≤3时，只有
当n==2时f(x)=1；
当n==3时f(x)=2；

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2:
            return 0
        elif number == 2:
            return 1
        elif number == 3:
            return 2
        n = number//3
        l = number%3
        if l == 1:
            return int(4*pow(3, (n-1)))
        elif l == 2:
            return int(pow(3, n)*2)
        else:
            return int(pow(3, n))