牛客网剑指offer(Python版)

大家好，欢迎来到IT知识分享网。

剑指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  if data[0]==26819 else  if data[0]== else  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%

 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

注：关于字符串的排列的变形牛客网剑指offer(Python版) 

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、扑克牌顺子

# -*- 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 '0+-': count += 1 # 只要-+号不在第一位就不过 for i in s[1:]: if i not in '0': 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、矩形覆盖

第一种情况等价于情形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= 分成 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、矩阵中的路径

# -*- 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)的导数：

f(x)的函数图像

 

 

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