當前位置：首頁 > 编程语言 > python >内容正文

python

剑指Offer题解（Python版）

發布時間：2023/12/20 python 22 豆豆

生活随笔收集整理的這篇文章主要介紹了剑指Offer题解（Python版）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

??? https://blog.csdn.net/tinkle181129/article/details/79326023#

二叉樹的鏡像
??? 鏈表中環的入口結點
??? 刪除鏈表中重復的結點
??? 從尾到頭打印鏈表
??? 斐波那契數列
??? 跳臺階
??? 變態跳臺階
??? 矩形覆蓋
??? 把字符串轉換成整數
??? 平衡二叉樹
??? 和為S的連續正數序列
??? 左旋轉字符串
??? 數字在排序數組中出現的次數
??? 數組中只出現一次的數字
??? 翻轉單詞順序列
??? 二叉樹的深度
??? 和為S的兩個數字
??? 順時針打印矩陣
??? 二叉樹的下一個結點
??? 對稱的二叉樹
??? 把二叉樹打印成多行
??? 按之字形順序打印二叉樹
??? 序列化二叉樹
??? 二叉搜索樹的第k個結點
??? 數據流中的中位數
??? 重建二叉樹
??? 滑動窗口的最大值
??? 用兩個棧實現隊列
??? 旋轉數組的最小數字
??? 丑數
??? 兩個鏈表的第一個公共結點
??? 第一個只出現一次的字符位置
??? 數組中的逆序對
??? 連續子數組的最大和
??? 最小的K個數
??? 數組中出現次數超過一半的數字
??? 整數中1出現的次數（從1到n整數中1出現的次數）
??? 把數組排成最小的數
??? 數組中重復的數字
??? 構建乘積數組
??? 二維數組中的查找
??? 撲克牌順子
??? 孩子們的游戲(圓圈中最后剩下的數)
??? 正則表達式匹配
??? 表示數值的字符串
??? 字符流中第一個不重復的字符
??? 替換空格
??? 矩陣中的路徑
??? 機器人的運動范圍
??? 求1+2+3+…+n
??? 不用加減乘除做加法
??? 二叉搜索樹與雙向鏈表
??? 復雜鏈表的復制
??? 字符串的排列
??? 二進制中1的個數
??? 鏈表中倒數第k個結點
??? 合并兩個排序的鏈表
??? 反轉鏈表
??? 樹的子結構
??? 數值的整數次方
??? 調整數組順序使奇數位于偶數前面
??? 包含min函數的棧
??? 二叉樹中和為某一值的路徑
??? 從上往下打印二叉樹
??? 二叉搜索樹的后序遍歷序列
??? 棧的壓入、彈出序列

(1) 二叉樹的鏡像（Symmetric Tree）
?？途W鏈接
Leetcode鏈接

class Solution:
??? # 返回鏡像樹的根節點
??? def Mirror(self, root):
??????? if root == None:
??????????? return
??????? self.Mirror(root.left)
??????? self.Mirror(root.right)
??????? root.left,root.right = root.right,root.left

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8

（2）鏈表中環的入口結點
Leetcode 142. Linked List Cycle II
尋找環的入口結點
這題是Leetcode 141. Linked List Cycle的擴展。
判斷是否存在環用fast和slow兩個指針，從head開始，一個走一步，一個走兩步，如果最終到達同一個結點，則說明存在環。

class Solution(object):
??? def hasCycle(self, head):
??????? """
??????? :type head: ListNode
??????? :rtype: bool
??????? """
??????? if head == None or head.next == None:
??????????? return False
??????? slow = fast = head
??????? while fast and fast.next:
??????????? slow = slow.next
??????????? fast = fast.next.next
??????????? if slow == fast:
??????????????? return True
??????? return False

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

而尋找環的入口，假設入口結點距離頭結點a個單位，fast和slow相遇在距離入口結點b個單位的位置，環剩下的長度為c，則有a+b+c+b = 2*(a+b) -> a = c
因此，在重合時候，將fast置為head，再一步一步地走，當與slow重合時的結點即為入口結點

class Solution:
??? def EntryNodeOfLoop(self, pHead):
??????? # write code here
??????? if pHead== None or pHead.next == None:
??????????? return None
??????? fast = slow = pHead
??????? while(fast and fast.next):
??????????? slow = slow.next
??????????? fast = fast.next.next
??????????? if slow == fast:
??????????????? fast = pHead
??????????????? while(fast!=slow):
??????????????????? fast = fast.next
??????????????????? slow = slow.next
??????????????? return fast
??????? return None

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16

（3）刪除鏈表中重復的結點
刪除鏈表中重復的結點
Leetcode. 82. Remove Duplicates from Sorted List II
用flag來標記當前的結點是否為重復結點

class Solution:
??? def deleteDuplication(self, pHead):
??????? # write code here
??????? pos = pHead
??????? ret = ListNode(-1)
??????? tmp = ret
??????? flag = False
??????? while(pos and pos.next):
??????????? if pos.val == pos.next.val:
??????????????? flag = True
??????????????? pos.next = pos.next.next
??????????? else:
??????????????? if flag:
??????????????????? flag = False
??????????????? else:
??????????????????? tmp.next = ListNode(pos.val)
??????????????????? tmp = tmp.next
??????????????? pos = pos.next
??????? if pos and flag==False:
??????????? tmp.next = ListNode(pos.val)
??????? return ret.next

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21

（4）從頭到尾打印鏈表
從頭到尾打印鏈表

class Solution:
??? # 返回從尾部到頭部的列表值序列，例如[1,2,3]
??? def printListFromTailToHead(self, listNode):
??????? # write code here
??????? ret = []
??????? head = listNode
??????? while(head):
??????????? ret.append(head.val)
??????????? head = head.next
??????? ret.reverse()
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

（5）求斐波那契數列的第n項
斐波那契數列

# -*- coding:utf-8 -*-
class Solution:
??? def Fibonacci(self, n):
??????? if n == 0:
??????????? return 0
??????? if n==1 or n==2:
??????????? return 1
??????? memories = [1,1]
??????? for i in range(n-2):
??????????? memories.append(memories[-1]+memories[-2])
??????? return memories[-1]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

（6）跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
dp[n]=dp[n?1]+dp[n?2]

# -*- coding:utf-8 -*-
class Solution:
??? def jumpFloor(self, number):
??????? # write code here
??????? '''
??????? n = 1 : 1
??????? n = 2 : 1+1 = 2
??????? n = 3 : dp[n-2]+dp[n-1]
??????? '''
??????? if number == 1 or number == 2:
??????????? return number
??????? dp = [1,2]
??????? for i in range(number-2):
??????????? dp.append(dp[-1]+dp[-2])
??????? return dp[-1]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

（7）變態跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
思考：在dp[n] = dp[n-1] + dp[n-2] + .. + dp[1] + 1(直接跳n)步驟
即dp[n]=∑n?1i=1dp[i]+1

class Solution:
??? def jumpFloorII(self, number):
??????? # write code here
??????? if number == 1 or number == 2:
??????????? return number
??????? ret = sum_ = 3
??????? for i in range(number-2):
??????????? ret = sum_+1
??????????? sum_+=ret
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10

（8）矩形覆蓋
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
思考： 2*1 1 種； 2*2 2種 2*3 3種 2*4 5種
dp[n]=dp[n?1]+dp[n?2]

# -*- coding:utf-8 -*-
class Solution:
??? def rectCover(self, number):
??????? # write code here

??????? if number<=2:
??????????? return number
??????? dp = [1,2]
??????? for i in range(number-2):
??????????? dp.append(dp[-1]+dp[-2])
??????? return dp[-1]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

（9）把字符串轉換成整數
把字符串轉換成整數
將一個字符串轉換成一個整數，要求不能使用字符串轉換整數的庫函數。數值為0或者字符串不是一個合法的數值則返回0
思考：如果有正負號，需要在數字之前，出現其他字符或者字符串為空都非法返回0

class Solution:
??? def StrToInt(self, s):
??????? # write code here
??????? flag = True
??????? pos = 1
??????? ret = None
??????? if s=='':
??????????? return 0
??????? for i in s:
??????????? if i=='+' or i=='-':
??????????????? if flag:
??????????????????? pos = -1 if i=='-' else 1
??????????????????? flag = False
??????????????? else:
??????????????????? return 0
??????????? elif i>='0' and i<='9':
??????????????? flag = False
??????????????? if ret == None:
??????????????????? ret = int(i)
??????????????? else:
??????????????????? ret = ret*10+int(i)
??????????? else:
??????????????? return 0
??????? return pos*ret if ret else 0

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24

（10）平衡二叉樹的判斷
思考：BST的定義為|height(lefttree)?height(righttree)|<=1

，原問題拆分為計算樹高度和判斷高度差

class Solution:
??? def Treeheight(self,pRoot):
??????? if pRoot == None:
??????????? return 0
??????? if pRoot.left == None and pRoot.right == None:
??????????? return 1
??????? lh = self.Treeheight(pRoot.left)
??????? rh = self.Treeheight(pRoot.right)
??????? return max(rh,lh)+1

??? def IsBalanced_Solution(self, pRoot):
??????? # write code here
??????? if pRoot == None:
??????????? return True
??????? return abs(self.Treeheight(pRoot.left)-self.Treeheight(pRoot.right))<=1

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

（11）和為S的連續正數序列
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序
思考：S%奇數==0 或者S%偶數==偶數／2 就說明有這個連續序列，但是注意是正數序列，可能會出現越界情況

class Solution:
??? def FindContinuousSequence(self, tsum):
??????? # write code here
??????? k = 2
??????? ret = []
??????? for k in range(2,tsum):
??????????? if k%2==1 and tsum%k==0:
??????????????? tmp = []
??????????????? mid = tsum/k
??????????????? if mid-k/2>0:
??????????????????? for i in range(mid-k/2,mid+k/2+1):
??????????????????????? tmp.append(i)
??????????????????? ret.append(tmp[:])
??????????? elif k%2==0 and (tsum%k)*2==k:
??????????????? mid = tsum/k
??????????????? tmp = []
??????????????? if mid-k/2+1>0:
??????????????????? for i in range(mid-k/2+1,mid+k/2+1):
??????????????????????? tmp.append(i)
??????????????????? ret.append(tmp[:])
??????? ret.sort()
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22

（12）左旋轉字符串
對于一個給定的字符序列S，請你把其循環左移K位后的序列輸出。
思考：需要先K= K%len(S)

# -*- coding:utf-8 -*-
class Solution:
??? def LeftRotateString(self, s, n):
??????? # write code here
??????? if s == '':
??????????? return s
??????? n = n%len(s)
??????? return s[n:]+s[0:n]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8

（13）數字在排序數組中出現的次數
數字在排序數組中出現的次數
思考：原來是可以用hash做的，但是因為是排序數組，所以可以用二分查找

# -*- coding:utf-8 -*-
class Solution:
??? def GetNumberOfK(self, data, k):
??????? # write code here
??????? start = 0
??????? end = len(data)-1
??????? while(start<=end):
??????????? mid = (start+end)/2
??????????? if data[mid]==k:
??????????????? cnt = 0
??????????????? tmp = mid
??????????????? while(tmp>=0 and data[tmp]==k):
??????????????????? cnt+=1
??????????????????? tmp-=1
??????????????? tmp = mid+1
??????????????? while(tmp<len(data) and data[tmp]==k):
??????????????????? cnt+=1
??????????????????? tmp+=1
??????????????? return cnt
??????????? elif data[mid]>k:
??????????????? end = mid-1
??????????? else:
??????????????? start = mid+1
??????? return 0

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24

（14）數組中只出現一次的數字
一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字
思考：用hash；或者位運算
首先利用0 ^ a = a; a^a = 0的性質
兩個不相等的元素在位級表示上必定會有一位存在不同，
將數組的所有元素異或得到的結果為不存在重復的兩個元素異或的結果，
據異或的結果1所在的最低位，把數字分成兩半，每一半里都還有一個出現一次的數據和其他成對出現的數據,
問題就轉化為了兩個獨立的子問題“數組中只有一個數出現一次，其他數都出現了2次，找出這個數字”。

class Solution:
??? # 返回[a,b] 其中ab是出現一次的兩個數字
??? def FindNumsAppearOnce(self, array):
??????? # write code here
??????? ans,a1,a2,flag= 0,0,0,1
??????? for num in array:
??????????? ans = ans ^ num
??????? while(ans):
??????????? if ans%2 == 0:
??????????????? ans = ans >>1
??????????????? flag = flag <<1
??????????? else:
??????????????? break
??????? for num in array:
??????????? if num & flag:
??????????????? a1 = a1 ^ num
??????????? else:
??????????????? a2 = a2 ^ num
??????? return a1,a2

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19

（15）翻轉單詞順序列

# -*- coding:utf-8 -*-
class Solution:
??? def ReverseSentence(self, s):
??????? # write code here
??????? ret = s.split(" ")
??????? ret.reverse()
??????? return ' '.join(ret)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7

（16）二叉樹的深度

# -*- 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
??????? if pRoot.left == None and pRoot.right==None:
??????????? return 1
??????? return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14

（17）和為S的兩個數字
輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，是的他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的。
hash

# -*- coding:utf-8 -*-
class Solution:
??? def FindNumbersWithSum(self, array, tsum):
??????? # write code here
??????? memorys= {}
??????? ret = []
??????? for num in array:
??????????? if tsum-num in memorys:
??????????????? if ret == []:
??????????????????? ret = [tsum-num,num]
??????????????? elif ret and ret[0]*ret[1]>(tsum-num)*num:
??????????????????? ret = [tsum-num,num]
??????????? else:
??????????????? memorys[num] = 1
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

（18）順時針打印矩陣

# -*- coding:utf-8 -*-
class Solution:
??? # matrix類型為二維列表，需要返回列表
??? def printMatrix(self, matrix):
??????? # write code here
??????? m=len(matrix)
??????? ans=[]
??????? if m==0:
??????????? return ans
??????? n=len(matrix[0])
??????? #ans = [[0 for i in range(n)] for j in range(n)]
??????? #print ans
??????? upper_i =0;lower_i=m-1;left_j=0;right_j=n-1
??????? num=1
??????? i=0;j=0
??????? right_pointer=1
??????? down_pointer=0
??????? while(num<=m*n):
??????????? ans.append(matrix[i][j])
??????????? if right_pointer==1:
??????????????? if j<right_j:
??????????????????? j=j+1
??????????????? else:
??????????????????? right_pointer=0
??????????????????? down_pointer=1
??????????????????? upper_i = upper_i+1
??????????????????? i = i+1
??????????? elif down_pointer == 1:
??????????????? if i<lower_i:
??????????????????? i = i+1
??????????????? else:
??????????????????? right_pointer=-1
??????????????????? down_pointer=0
??????????????????? right_j = right_j -1
??????????????????? j = j-1
??????????? elif right_pointer ==-1:
??????????????? if j > left_j:
??????????????????? j=j-1
??????????????? else:
??????????????????? right_pointer=0
??????????????????? down_pointer=-1
??????????????????? lower_i =lower_i-1
??????????????????? i = i-1
??????????? elif down_pointer == -1:
??????????????? if i > upper_i:
??????????????????? i=i-1
??????????????? else:
??????????????????? right_pointer=1
??????????????????? down_pointer=0
??????????????????? left_j = left_j +1
??????????????????? j = j+1
??????????? num=num+1
??????? return ans

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26
??? 27
??? 28
??? 29
??? 30
??? 31
??? 32
??? 33
??? 34
??? 35
??? 36
??? 37
??? 38
??? 39
??? 40
??? 41
??? 42
??? 43
??? 44
??? 45
??? 46
??? 47
??? 48
??? 49
??? 50
??? 51
??? 52
??? 53

（19）* 二叉樹的下一個結點
二叉樹的下一個結點
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
思路：中序遍歷的順序為LVR
則有以下三種情況：
a. 如果該結點存在右子結點，那么該結點的下一個結點是右子結點樹上最左子結點
b. 如果該結點不存在右子結點，且它是它父結點的左子結點，那么該結點的下一個結點是它的父結點
c. 如果該結點既不存在右子結點，且也不是它父結點的左子結點，則需要一路向祖先結點搜索，直到找到一個結點，該結點是其父親結點的左子結點。如果這樣的結點存在，那么該結點的父親結點就是我們要找的下一個結點。

class Solution:
??? def GetNext(self, pNode):
??????? # write code here
??????? # left root right
??????? if pNode == None:
??????????? return None
??????? if pNode.right:
??????????? tmp = pNode.right
??????????? while(tmp.left):
??????????????? tmp = tmp.left
??????????? return tmp
??????? p = pNode.next
??????? while(p and p.right==pNode):
??????????? pNode = p
??????????? p = p.next
??????? return p

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16

（20）對稱的二叉樹
Leetcode 101. Symmetric Tree
判斷一棵樹是不是左右對稱的樹

class Solution:
??? def Symmetrical(self,Lnode,Rnode):
??????? if Lnode == None and Rnode == None:
??????????? return True
??????? if Lnode and Rnode:
??????????? return Lnode.val == Rnode.val and self.Symmetrical(Lnode.right,Rnode.left) and self.Symmetrical(Lnode.left,Rnode.right)
??????? else:
??????????? return False
??? def isSymmetrical(self, pRoot):
??????? # write code here
??????? if pRoot == None:
??????????? return True
??????? return self.Symmetrical(pRoot.left,pRoot.right)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13

（21）把二叉樹打印成多行
從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

class Solution:
??? # 返回二維列表[[1,2],[4,5]]
??? def Print(self, pRoot):
??????? # write code here
??????? if pRoot == None:
??????????? return []
??????? stack = [pRoot]
??????? ret = []

??????? while(stack):
??????????? tmpstack = []
??????????? tmp = []
??????????? for node in stack:
??????????????? tmp.append(node.val)
??????????????? if node.left:
??????????????????? tmpstack.append(node.left)
??????????????? if node.right:
??????????????????? tmpstack.append(node.right)
??????????? ret.append(tmp[:])
??????????? stack = tmpstack[:]
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21

（22）之字形打印二叉樹

class Solution:
??? def Print(self, pRoot):
??????? # write code here
??????? if pRoot == None:
??????????? return []
??????? stack = [pRoot]
??????? step = 1
??????? ret = []
??????? while(stack):
??????????? tmpstack = []
??????????? tmp = []
??????????? for node in stack:
??????????????? tmp+=[node.val]
??????????????? if node.left:
??????????????????? tmpstack.append(node.left)
??????????????? if node.right:
??????????????????? tmpstack.append(node.right)
??????????? if step%2==0:
??????????????? tmp.reverse()
??????????? ret.append(tmp)
??????????? step += 1
??????????? stack = tmpstack[:]
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23

（23）* 序列化和反序列化二叉樹
序列化和反序列化二叉樹
Serialize and Deserialize Binary Tree

class Solution:
??? def Serialize(self, root):
??????? # write code here
??????? def doit(node):
??????????? if node:
??????????????? vals.append(str(node.val))
??????????????? doit(node.left)
??????????????? doit(node.right)
??????????? else:
??????????????? vals.append('#')
??????? vals = []
??????? doit(root)
??????? return ' '.join(vals)

??? def Deserialize(self, s):
??????? # write code here
??????? def doit():
??????????? val = next(vals)
??????????? if val == '#':
??????????????? return None
??????????? node = TreeNode(int(val))
??????????? node.left = doit()
??????????? node.right = doit()
??????????? return node
??????? vals = iter(s.split())
??????? return doit()

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26

（24） * 數據流中的中位數
數據流中的中位數
Find Median from Data Stream

from heapq import *
class MedianFinder:

??? def __init__(self):
??????? self.heaps = [], []

??? def addNum(self, num):
??????? small, large = self.heaps
??????? heappush(small, -heappushpop(large, num))
??????? if len(large) < len(small):
??????????? heappush(large, -heappop(small))

??? def findMedian(self):
??????? small, large = self.heaps
??????? if len(large) > len(small):
??????????? return float(large[0])
??????? return (large[0] - small[0]) / 2.0

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17

（25）* 二叉平衡樹中的第k小數
二叉搜索樹中的第k大結點
Leetcode 230. Kth Smallest Element in a BST
思路：BST的中序遍歷就是一個有序數組，需要注意到Leetcode中限制了k在[1,樹結點個數]而牛客網沒有，所以需要考慮k的值有沒有超出

class Solution:
??? # 返回對應節點TreeNode
??? def KthNode(self, pRoot, k):
??????? # write code here
??????? stack = []
??????? node = pRoot
??????? while node:
??????????? stack.append(node)
??????????? node = node.left
??????? cnt = 1
??????? while(stack and cnt<=k):
??????????? node = stack.pop()
??????????? right = node.right
??????????? while right:
??????????????? stack.append(right)
??????????????? right = right.left
??????????? cnt+=1
??????? if node and k==cnt-1:
??????????? return node
??????? return None

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20

（26）重建二叉樹
Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
根據先序、中序來構建二叉樹

class Solution(object):
??? def buildTree(self, pre, tin):
??????? """
??????? :type preorder: List[int]
??????? :type inorder: List[int]
??????? :rtype: TreeNode
??????? """
??????? if pre==[]:
??????????? return None
??????? val = pre[0]
??????? idx = tin.index(val)
??????? ltin = tin[0:idx]
??????? rtin = tin[idx+1:]
??????? lpre = pre[1:1+len(ltin)]
??????? rpre = pre[1+len(ltin):]
??????? root = TreeNode(val)
??????? root.left = self.buildTree(lpre,ltin)
??????? root.right = self.buildTree(rpre,rtin)
??????? return root

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19

Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal
根據中序和后序構建二叉樹

class Solution(object):
??? def buildTree(self, inorder, postorder):
??????? """
??????? :type inorder: List[int]
??????? :type postorder: List[int]
??????? :rtype: TreeNode
??????? """
??????? if postorder == []:
??????????? return None
??????? val = postorder[-1]
??????? idx = inorder.index(val)
??????? lin = inorder[0:idx]
??????? rin = inorder[idx+1:]
??????? lpos = postorder[0:len(lin)]
??????? rpos = postorder[len(lin):-1]
??????? root = TreeNode(val)
??????? root.left = self.buildTree(lin,lpos)
??????? root.right = self.buildTree(rin,rpos)
??????? return root

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19

（27）滑動窗口的最大值
給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}；針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思考：假設當前窗口起始位置為start,結束位置為end，我們要構造一個stack, 使得stack[0]為區間[start,end]的最大值。

# -*- coding:utf-8 -*-
class Solution:
??? def maxInWindows(self, num, size):
??????? # write code here
??????? if size == 0:
??????????? return []
??????? ret = []
??????? stack = []
??????? for pos in range(len(num)):
??????????? while (stack and stack[-1][0] < num[pos]):
??????????????? stack.pop()
??????????? stack.append((num[pos], pos))
??????????? if pos>=size-1:
??????????????? while(stack and stack[0][1]<=pos-size):
??????????????????? stack.pop(0)
??????????????? ret.append(stack[0][0])
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17

(28) 用兩個棧實現隊列
思考：棧FILO，隊列FIFO

# -*- coding:utf-8 -*-
class Solution:
??? def __init__(self):
??????? self.stack1 = []
??????? self.stack2 = []
??? def push(self, node):
??????? # write code here
??????? self.stack1.append(node)

??? def pop(self):
??????? # return xx
??????? if len(self.stack2):
??????????? return self.stack2.pop()
??????? while(self.stack1):
??????????? self.stack2.append(self.stack1.pop())
??????? return self.stack2.pop()

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16

(29) 旋轉數組的最小數字
思考：二分判斷

# -*- coding:utf-8 -*-
class Solution:
??? def minNumberInRotateArray(self, rotateArray):
??????? # write code here
??????? if rotateArray == []:
??????????? return 0
??????? _len = len(rotateArray)
??????? left = 0
??????? right = _len - 1
??????? while left <= right:
??????????? mid = int((left + right) >> 1)
??????????? if rotateArray[mid]<rotateArray[mid-1]:
??????????????? return rotateArray[mid]
??????????? if rotateArray[mid] >= rotateArray[right]:
??????????????? # 說明在【mid，right】之間
??????????????? left = mid + 1
??????????? else:
??????????????? # 說明在【left，mid】之間
??????????????? right = mid - 1
??????? return rotateArray[mid]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20

（30）丑數
只包含因子2、3和5的數稱作丑數（Ugly Number），求按從小到大的順序的第N個丑數。
思路：heap

# -*- coding:utf-8 -*-
import heapq
class Solution:
??? def GetUglyNumber_Solution(self, index):
??????? # write code here
??????? if index<1:
??????????? return 0
??????? heaps = []
??????? heapq.heappush(heaps,1)
??????? lastnum = None
??????? idx = 1
??????? while(idx<=index):
??????????? curnum = heapq.heappop(heaps)
??????????? while(curnum==lastnum):
??????????????? curnum = heapq.heappop(heaps)
??????????? lastnum = curnum
??????????? idx+=1
??????????? heapq.heappush(heaps,curnum*2)
??????????? heapq.heappush(heaps,curnum*3)
??????????? heapq.heappush(heaps,curnum*5)
??????? return lastnum

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21

（31）兩個鏈表的第一個公共結點
思考：設鏈表pHead1的長度為a,到公共結點的長度為l1；鏈表pHead2的長度為b,到公共結點的長度為l2，有a+l2 = b+l1

class Solution:
??? def FindFirstCommonNode(self, pHead1, pHead2):
??????? # write code here
??????? if pHead1== None or pHead2 == None:
??????????? return None
??????? pa = pHead1
??????? pb = pHead2
??????? while(pa!=pb):
??????????? pa = pHead2 if pa is None else pa.next
??????????? pb = pHead1 if pb is None else pb.next
??????? return pa

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

(32) 第一個只出現一次的字符
思考：hash加隊列

# -*- coding:utf-8 -*-
class Solution:
??? def FirstNotRepeatingChar(self, s):
??????? # write code here
??????? queue = []
??????? memories = dict()
??????? for idx,char in enumerate(s):
??????????? if char not in memories:
??????????????? queue.append(idx)
??????????????? memories[char]=0
??????????? memories[char]+=1
??????????? while(queue and memories[s[queue[0]]]>1):
??????????????? queue.pop(0)
??????? return queue[0] if queue else -1

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14

（33）數組中的逆序對
在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。即輸出P%1000000007
思考：這邊的python會超時，但是思路是對的
時間復雜度O(nlogn),空間復雜度O(n)。
先將數組逆轉，構建一個新的數組L，將num二分插入到L中，所插入的位置i，代表有i個數字比當前這個數字小

import bisect
class Solution:
??? def InversePairs(self, data):
??????? data.reverse()
??????? L = []
??????? ret = 0
??????? for d in data:
??????????? pos = bisect.bisect_left(L,d)
??????????? L.insert(pos,d)
??????????? ret+= pos
??????????? ret = ret % 1000000007
??????? return ret % 1000000007

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12

C++解法：（來源于好朋友的博客）

/**
* 運行時間：191ms
* 占用內存：4336k
*/
class Solution {
private:
??? long long cnt;
public:
??? int InversePairs(vector<int> data)
??? {
??????? cnt = 0; ?
??????? vector<int> TmpArray(data.size());
??????? Msort(data,TmpArray,0,data.size()-1);
??????? return cnt % 1000000007;
??? }
private:
??? void Msort(vector<int>& data,vector<int>& TmpArray,int left, int right)
??? {
????? int center;
????? if(left < right)
????? {
??????? center = (left + right)/2;
??????? Msort(data,TmpArray,left,center);
??????? Msort(data,TmpArray,center+1,right);
??????? // 任意時刻只需要一個臨時數組TmpArray活動
??????? Merge(data,TmpArray,left,center+1,right);
????? }
??? }
??? void Merge(vector<int>& data,vector<int>& TmpArray,int Lpos,int Rpos,int RightEnd)
??? { // 合并算法
????? int i,LeftEnd,NumElements,TmpPos;
????? LeftEnd = Rpos - 1;
????? TmpPos = RightEnd;
????? NumElements = RightEnd - Lpos + 1;
????? /* 主循環*/
????? while(LeftEnd >= Lpos && RightEnd >= Rpos)
????? {
??????? if(data[LeftEnd] > data[RightEnd])
??????? {
????????? TmpArray[TmpPos--] = data[LeftEnd--];
????????? /*計算逆序對數*/
????????? cnt += RightEnd - Rpos + 1;
??????? }
??????? else //data[LeftEnd] <= data[RightEnd]
????????? TmpArray[TmpPos--] = data[RightEnd--];
????? }
????? while(LeftEnd >= Lpos) // 拷貝左半剩余部分
??????? TmpArray[TmpPos--] = data[LeftEnd--];
????? while(RightEnd >= Rpos) // 拷貝右半剩余部分
??????? TmpArray[TmpPos--] = data[RightEnd--];

????? /* 拷貝回原數組*/
????? for(int i = 0;i < NumElements;i++,Lpos++)
??????? data[Lpos] = TmpArray[Lpos];

??? }
};

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26
??? 27
??? 28
??? 29
??? 30
??? 31
??? 32
??? 33
??? 34
??? 35
??? 36
??? 37
??? 38
??? 39
??? 40
??? 41
??? 42
??? 43
??? 44
??? 45
??? 46
??? 47
??? 48
??? 49
??? 50
??? 51
??? 52
??? 53
??? 54
??? 55
??? 56
??? 57

(34) 連續子數組的最大和
思考：貪心

class Solution:
??? def FindGreatestSumOfSubArray(self, array):
??????? # write code here
??????? if len(array)==1:
??????????? return array[0]
??????? cur = pos = array[0]
??????? for i in range(1,len(array)):
??????????? pos = max(pos+array[i],array[i])
??????????? cur = max(cur,pos)
??????? return cur

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10

(35) 最小的K個數

import heapq
class Solution:
??? def GetLeastNumbers_Solution(self, tinput, k):
??????? # write code here
??????? heaps = []
??????? ret = []
??????? for num in tinput:
??????????? heapq.heappush(heaps,num)
??????? if k>len(heaps):
??????????? return []
??????? for i in range(k):
??????????? ret.append(heapq.heappop(heaps))
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13

（36）數組中出現次數超過一半的數字
思考：摩爾投票法

# -*- coding:utf-8 -*-
class Solution:
??? def MoreThanHalfNum_Solution(self, numbers):
??????? # write code here
??????? if numbers == []:
??????????? return 0
??????? val,cnt = None,0
??????? for num in numbers:
??????????? if cnt==0:
??????????????? val,cnt = num,1
??????????? elif val == num:
??????????????? cnt+=1
??????????? else:
??????????????? cnt-=1
??????? return val if numbers.count(val)*2>len(numbers) else 0

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

（37）* 從1到n整數中1出現的次數
思考：可以從n的每個位上入手，pos來記錄位，ans來記錄當前1的個數，last來記錄前面的數（這樣講好復雜，舉個例子好了）
xxxxYzzzz （假設9位）
在Y上1的個數由xxxx,zzzz和Y來決定
首先至少有xxxx0000個
其次看Y
如果Y大于1那么會多了10000個
如果Y等于1那么會多了（zzzz+1）個

# -*- coding:utf-8 -*-
class Solution:
??? def NumberOf1Between1AndN_Solution(self, n):
??????? # write code here
??????? if n<1:? return 0
??????? if n==1: return 1
??????? last,ans,pos = 0,0,1
??????? while(n):
??????????? num = n%10
??????????? n = n/10
??????????? ans += pos*n
??????????? if num>1:
??????????????? ans+=pos
??????????? elif num==1:
??????????????? ans+=(last+1)
??????????? last = last+num*pos
??????????? pos*=10
??????? return ans

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18

（38）把數組排成最小的數
輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為321323。
思考：總的思路是先將整型字符串化，然后重新定義排序規則，我的做法是將n擴展成長度為n+(maxlen-len(n))*n[0]的字符串，看別人的解答又覺得巧妙

# -*- coding:utf-8 -*-
import heapq
class Solution:
??? def PrintMinNumber(self, numbers):
??????? # write code here
??????? heaps = []
??????? maxlen = 0
??????? for num in numbers:
??????????? maxlen+=len(str(num))
??????? for num in numbers:
??????????? n = str(num)
??????????? heapq.heappush(heaps,(int(n+(maxlen-len(n))*n[0]),num))
??????? ret = ''
??????? while(heaps):
??????????? ret+=str(heapq.heappop(heaps)[1])
??????? return int(ret) if len(ret) else ''

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16

鏈接：https://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993
來源：牛客網
# -*- coding:utf-8 -*-
class Solution:
??? def PrintMinNumber(self, numbers):
??????? # write code here
??????? if not numbers:return ""
??????? numbers = list(map(str,numbers))
??????? numbers.sort(cmp=lambda x,y:cmp(x+y,y+x))
??????? return '0' if numbers[0]=='0' else ''.join(numbers)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

（39）數組中重復的數字
思考：哈希（然而依舊是一題Python不通過的題目）

# -*- coding:utf-8 -*-
class Solution:
??? # 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]
??? # 函數返回True/False
??? def duplicate(self, numbers, duplication):
??????? # write code here
??????? dup = dict()
??????? for num in numbers:
??????????? if num not in dup:
??????????????? dup[num] = True
??????????? else:
??????????????? duplication[0]=num
??????????????? return True

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13

（40）* 構造乘積數組
B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]
思考：分為下三角和上三角DP計算B
下三角B[i]=A[0]A[1]A[2]..A[i?1]=B[i?1]A[i?1]

上三角（從最后往前）tmp=A[?1]A[?2]A[?3]...

class Solution:
??? def multiply(self, A):
??????? # write code here
??????? size = len(A)
??????? B = [1]*size
??????? for i in range(1,size):
??????????? B[i] = B[i-1]*A[i-1]
??????? tmp = 1
??????? for i in range(size-2,-1,-1):
??????????? tmp = tmp*A[i+1]
??????????? B[i] = B[i]*tmp
??????? return B

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12

（41）二維數組中的查找
在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
思考：從0,n-1出開始，小了往下，大了往左

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

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17

（42）* 撲克牌順子
LL今天心情特別好,因為他去買了一副撲克牌,發現里面居然有2個大王,2個小王(一副牌原本是54張^_^)…他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子…..LL不高興了,他想了想,決定大\小王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。現在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何。為了方便起見,你可以認為大小王是0。

class Solution:
??? def IsContinuous(self, numbers):
??????? # write code here
??????? if not numbers:
??????????? return 0
??????? numbers.sort()
??????? zeros = numbers.count(0)
??????? for i, v in enumerate(numbers[:-1]):
??????????? if v!=0:
??????????????? if numbers[i+1]==v:
??????????????????? return False
??????????????? zeros -= (numbers[i+1]-numbers[i]-1)
??????????????? if zeros<0:
??????????????????? return False
??????? return True

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15

（43）孩子們的游戲

# -*- coding:utf-8 -*-
class Solution:
??? def LastRemaining_Solution(self, n, m):
??????? # write code here
??????? if n<1: return -1
??????? final,start = -1,0
??????? cnt = [i for i in range(n)]
??????? while cnt:
??????????? k = (start+m-1)%n
??????????? final = cnt.pop(k)
??????????? n-=1
??????????? start = k
??????? return final

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13

（44）正則表達式匹配
請實現一個函數用來匹配包括’.’和’‘的正則表達式。模式中的字符’.’表示任意一個字符，而’‘表示它前面的字符可以出現任意次（包含0次）。在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串”aaa”與模式”a.a”和”ab*ac*a”匹配，但是與”aa.a”和”ab*a”均不匹配
思考：
第一種情況，當p == ” 時 return s==”
當len(p)==1時要滿足len(s)==1 AND (p[0]==s[0] OR p[0] == ‘.’)
當len(p)>1時，要討論p[1] 是不是為’’ ，因為如果p[1]==’’ 時候可能會是p[2:] 和 s 匹配情況
但當p[1]!=’*’ 時候意味著必須要關注是否 p[0]==s[0] 或者 p[0]==’.’
那么這兩個可以合并為
IF len(p) == 0 or p[1]!=’*’
返回 len(s) AND match(p[1:],s[1:]) AND (p[0]==s[0] OR p[0] == ‘.’)
然后最復雜的一種情況p[1] == ‘*’
p = ‘b*bbacd’ s = ‘bbbbbacd’
很明顯的是如果p[0]!=s[0] 且 p[0]!=’.’ 那么看p[2:] 和 s 的匹配情況
如果p[0] == s[0] 或者 p[0] == ‘.’ ，可以判斷p[2:] 和 s[1:] … p[2:] 和 s[2:] … p[2:] 和 s[3:] … 搞個循環就可以

# -*- coding:utf-8 -*-
class Solution:
??? # s, pattern都是字符串
??? def __init__(self):
??????? self.dic = {}
??? def match(self, s, p):
??????? # write code here
??????? if (s,p) in self.dic:
??????????? return self.dic[(s,p)]
??????? if p == '':
??????????? return s==''
??????? if len(p)==1 or p[1]!='*':
??????????? self.dic[(s[1:],p[1:])] = self.match(s[1:],p[1:])
??????????? return len(s)>0 and (p[0]=='.' or p[0]==s[0]) and self.dic[(s[1:],p[1:])]
??????? while(len(s) and (p[0]=='.' or p[0]==s[0])):
??????????? self.dic[(s,p[2:])] = self.match(s,p[2:])
??????????? if self.match(s[:],p[2:]):
??????????????? return True
??????????? s = s[1:]
??????? self.dic[(s,p[2:])] = self.match(s,p[2:])
??????? return self.dic[(s,p[2:])]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21

（45）判斷一個字符串是否表示數值
就是各種邏輯

# -*- coding:utf-8 -*-
class Solution:
??? # s字符串
??? def isNumeric(self, s):
??????? # write code here
??????? INVALID=0; SPACE=1; SIGN=2; DIGIT=3; DOT=4; EXPONENT=5;
??????? #0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs
??????? transitionTable=[[-1,? 0,? 3,? 1,? 2, -1],??? #0 no input or just spaces
???????????????????????? [-1,? 8, -1,? 1,? 4,? 5],??? #1 input is digits
???????????????????????? [-1, -1, -1,? 4, -1, -1],??? #2 no digits in front just Dot
???????????????????????? [-1, -1, -1,? 1,? 2, -1],??? #3 sign
???????????????????????? [-1,? 8, -1,? 4, -1,? 5],??? #4 digits and dot in front
???????????????????????? [-1, -1,? 6,? 7, -1, -1],??? #5 input 'e' or 'E'
???????????????????????? [-1, -1, -1,? 7, -1, -1],??? #6 after 'e' input sign
???????????????????????? [-1,? 8, -1,? 7, -1, -1],??? #7 after 'e' input digits
???????????????????????? [-1,? 8, -1, -1, -1, -1]]??? #8 after valid input input space
??????? state=0; i=0
??????? while i<len(s):
??????????? inputtype = INVALID
??????????? if s[i]==' ': inputtype=SPACE
??????????? elif s[i]=='-' or s[i]=='+': inputtype=SIGN
??????????? elif s[i] in '0123456789': inputtype=DIGIT
??????????? elif s[i]=='.': inputtype=DOT
??????????? elif s[i]=='e' or s[i]=='E': inputtype=EXPONENT

??????????? state=transitionTable[state][inputtype]
??????????? if state==-1: return False
??????????? else: i+=1
??????? return state == 1 or state == 4 or state == 7 or state == 8

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26
??? 27
??? 28
??? 29

（46）字符流中第一個不重復的字符
思考：用個隊列和hash

# -*- coding:utf-8 -*-
class Solution:
??? # 返回對應char
??? def __init__(self):
??????? self.memory = dict()
??????? self.queue = []

??? def FirstAppearingOnce(self):
??????? # write code here
??????? while len(self.queue) and self.memory[self.queue[0]]>1:
??????????? self.queue.pop(0)

??????? return self.queue[0] if len(self.queue) else '#'
??? def Insert(self, char):
??????? # write code here
??????? if char not in self.memory:
??????????? self.memory[char]=0
??????? self.memory[char]+=1
??????? if self.memory[char]==1:
??????????? self.queue.append(char)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20

（47）替換空格

# -*- coding:utf-8 -*-
import re
class Solution:
??? # s 源字符串
??? def replaceSpace(self, s):
??????? # write code here
??????? return re.sub(" ","%20",s)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7

（48）矩陣中的路徑
思考：dfs加記憶化搜索

# -*- coding:utf-8 -*-
class Solution:
??? def hasPath(self, matrix, rows, cols, path):
??????? def dfs(memories,r,c,s):
??????????? if s=='':
??????????????? return True
??????????? dx = [-1,1,0,0]
??????????? dy = [0,0,-1,1]
??????????? for k in range(4):
??????????????? x = dx[k] + r
??????????????? y = dy[k] + c
??????????????? if x >= 0 and x < rows and y >= 0 and y < cols and memories[x][y] and matrix[x*cols+y]==s[0]:
??????????????????? memories[x][y]=False
??????????????????? if dfs(memories[:], x, y,s[1:]):
??????????????????????? return True
??????????????????? memories[x][y]=True
??????????? return False

??????? if path == '':
??????????? return True
??????? memories = [[True for c in range(cols)] for r in range(rows)]
??????? for r in range(rows):
??????????? for c in range(cols):
??????????????? if matrix[r*cols+c] == path[0]:
??????????????????? memories[r][c] = False
??????????????????? if dfs(memories[:],r,c,path[1:]):
??????????????????????? return True
??????????????????? memories[r][c] = True
??????? return False

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26
??? 27
??? 28
??? 29

（49）機器人的運動范圍
地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
思考：dfs+記憶化搜索

# -*- coding:utf-8 -*-
class Solution:
??? def movingCount(self, threshold, rows, cols):
??????? # write code here
??????? memories = set()
??????? def dfs(i,j):
??????????? def judge(i,j):
??????????????? return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold
??????????? if not judge(i,j) or (i,j) in memories:
??????????????? return
??????????? memories.add((i,j))
??????????? if i != rows - 1:
??????????????? dfs(i + 1, j)
??????????? if j != cols - 1:
??????????????? dfs(i, j + 1)
??????? dfs(0,0)
??????? return len(memories)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17

（50）求1+2+3+..+n
思考：遞歸

# -*- coding:utf-8 -*-
class Solution:
??? def Sum_Solution(self, n):
??????? # write code here
??????? if n == 1: return 1
??????? return n+self.Sum_Solution(n-1)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6

（51）* 不用加減乘除做加法
思考：不計進位的和為 a^b，進位就是 a&b
a+b = a^b + (a&b)<<1;
這題python依舊有坑 = =

public class Solution {
??? public int Add(int a,int b) {
??????? int unit = a ^ b; ?
??????? int carry_bit = a & b; ?
??????? while(carry_bit != 0) { ?
??????????? int temp_a = unit; ?
??????????? int temp_b = carry_bit << 1; ?
??????????? unit = temp_a ^ temp_b; ?
??????????? carry_bit = temp_a & temp_b; ?
??????? } ?
??????? return unit; ?
??? }
}

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13

（52）二叉搜索樹與雙向鏈表
思考：左子樹上最右結點 -> root -> 右子樹上的最左結點

class Solution:
??? def Convert(self, pRootOfTree):
??????? # write code here
??????? if pRootOfTree == None:
??????????? return pRootOfTree
??????? if pRootOfTree.left == None and pRootOfTree.right == None:
??????????? return pRootOfTree
??????? left = self.Convert(pRootOfTree.left)
??????? p = left
??????? if left:
??????????? while(p.right):
??????????????? p = p.right
??????????? p.right = pRootOfTree
??????????? pRootOfTree.left = p
??????? right = self.Convert(pRootOfTree.right)
??????? if right:
??????????? pRootOfTree.right = right
??????????? right.left = pRootOfTree
??????? return left if left else pRootOfTree

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19

（53）復雜鏈表的復制
輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的head。（注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）
思考：hash

class Solution:
??? # 返回 RandomListNode
??? def Clone(self, head):
??????? """
??????? :type head: RandomListNode
??????? :rtype: RandomListNode
??????? """

??????? if head == None:
??????????? return head
??????? node_dict = {}
??????? node_dict[head] = RandomListNode(head.label)
??????? tmp = head
??????? while(head):
??????????? random = head.random
??????????? nexthd = head.next
??????????? if random !=None:
??????????????? if random not in node_dict:
??????????????????? node_dict[random] = RandomListNode(random.label)
??????????????? node_dict[head].random = node_dict[random]
??????????? if nexthd !=None:
??????????????? if nexthd not in node_dict:
??????????????????? node_dict[nexthd] = RandomListNode(nexthd.label)
??????????????? node_dict[head].next = node_dict[nexthd]
??????????? head = head.next
??????? return node_dict[tmp]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26

（54）字符串的排列
思考：dfs

# -*- coding:utf-8 -*-
class Solution:
??? def Permutation(self, ss):
??????? def dfs(s):
??????????? if len(s) == '':
??????????????? return []
??????????? if len(s)==1:
??????????????? return [s]
??????????? if len(s)==2:
??????????????? return list(set([s[0]+s[1],s[1]+s[0]]))
??????????? ans = set([])
??????????? left = s[0]
??????????? right = dfs(s[1:])
??????????? for word in right:
??????????????? for i in range(len(word)+1):
??????????????????? ans.add(word[:i]+left+word[i:])
??????????? return list(ans)
??????? if ss == '':
??????????? return []
??????? return sorted(dfs(ss))

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20

（55）二進制中1的個數
思考：python沒有無符號移動，需要處理下

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

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

（56）鏈表中倒數第k個結點
思考：兩個指針p,q p先走k步

class Solution:
??? def FindKthToTail(self, head, k):
??????? # write code here
??????? p1 = p2 = head
??????? for i in range(k):
??????????? if p1==None:
??????????????? return None
??????????? p1 = p1.next
??????? while(p1):
??????????? p2 = p2.next
??????????? p1 = p1.next
??????? return p2

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12

（57）合并兩個排序的鏈表

class Solution:
??? # 返回合并后列表
??? def Merge(self, pHead1, pHead2):
??????? # write code here
??????? ret = ListNode(0)
??????? tmp = ret
??????? p1 = pHead1
??????? p2 = pHead2
??????? while(p1 and p2):
??????????? if p1.val<p2.val:
??????????????? tmp.next = ListNode(p1.val)
??????????????? p1 = p1.next
??????????? else:
??????????????? tmp.next = ListNode(p2.val)
??????????????? p2 = p2.next
??????????? tmp = tmp.next
??????? if p1:
??????????? tmp.next = p1
??????? if p2:
??????????? tmp.next = p2
??????? return ret.next

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21

（58）翻轉鏈表

class Solution:
??? # 返回ListNode
??? def ReverseList(self, pHead):
??????? # write code here
??????? head = None
??????? while(pHead):
??????????? tmp = ListNode(pHead.val)
??????????? tmp.next = head
??????????? head = tmp
??????????? pHead = pHead.next
??????? return head

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11

class Solution:
??? # 返回ListNode
??? def ReverseList(self, pHead):
??????? # write code here
??????? if pHead==None or pHead.next == None:
??????????? return pHead
??????? p = self.ReverseList(pHead.next)
??????? pHead.next.next = pHead
??????? pHead.next = None
??????? return p

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10

（59）判斷樹B是否是樹A的子結構

class Solution:
??? def HasSubtree(self, pRoot1, pRoot2):
??????? def subtree(pRoot1,pRoot2):
??????????? if pRoot2 == None and pRoot1 == None:
??????????????? return True
??????????? if pRoot2 == None:
??????????????? return False
??????????? if pRoot1 == None:
??????????????? return False

??????????? if pRoot2.val == pRoot1.val:
??????????????? if pRoot2.left == None and pRoot2.right == None:
??????????????????? return True
??????????????? if subtree(pRoot1.left,pRoot2.left) and subtree(pRoot1.right,pRoot2.right):
??????????????????? return True
??????????? return subtree(pRoot1.left,pRoot2) or subtree(pRoot1.right,pRoot2)
??????? if pRoot1 == None and pRoot2 == None:
??????????? return False
??????? return subtree(pRoot1,pRoot2)

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19

（60）* 數值的n次方
思考：109
可以分解為10(1001,2)

，用二分

class Solution:
??? def Power(self, base, exponent):
??????? # write code here
??????? if exponent==0:
??????????? return 1
??????? ans = exp = pos = 1
??????? if exponent<0:
??????????? pos,exponent = -1,-exponent
??????? while(exponent):
??????????? if exponent % 2:
??????????????? ans = ans*(base**(exp))
??????????? exponent = exponent>>1
??????????? exp = exp*2
??????? return ans if pos==1 else 1.0/ans

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14

（61）調整數組順序使奇數位于偶數前面

# -*- coding:utf-8 -*-
class Solution:
??? def reOrderArray(self, array):
??????? size = len(array)
??????? pos = size-1
??????? cnt = 0
??????? while(cnt<size):
??????????? if array[pos]%2==1:
??????????????? tmp = array[pos]
??????????????? for i in range(pos-1,-1,-1):
??????????????????? array[i+1] = array[i]
??????????????? array[0] = tmp
??????????? else:
??????????????? pos -=1
??????????? cnt +=1
??????? return array

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16

（62）包含min函數的棧
定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。

# -*- coding:utf-8 -*-
class Solution:

??? def __init__(self):
??????? """
??????? initialize your data structure here.
??????? """
??????? self.stack = []
??????? self.minstack =[]

??? def push(self, x):
??????? """
??????? :type x: int
??????? :rtype: void
??????? """
??????? self.stack.append(x)
??????? if len(self.minstack)==0 or self.minstack[-1][0]>x:
??????????? self.minstack.append((x,1))
??????? elif self.minstack[-1][0] == x:
??????????? self.minstack[-1] = (x,self.minstack[-1][1]+1)

??? def pop(self):
??????? """
??????? :rtype: void
??????? """
??????? ans = self.stack[-1]
??????? self.stack = self.stack[0:len(self.stack)-1]
??????? if ans == self.minstack[-1][0]:
??????????? if self.minstack[-1][1] == 1:
??????????????? self.minstack.remove(self.minstack[-1])
??????????? else:
??????????????? self.minstack[-1] = (ans,self.minstack[-1][1]-1)

??? def top(self):
??????? """
??????? :rtype: int
??????? """
??????? return self.stack[-1]

??? def min(self):
??????? """
??????? :rtype: int
??????? """
??????? return self.minstack[-1][0]

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25
??? 26
??? 27
??? 28
??? 29
??? 30
??? 31
??? 32
??? 33
??? 34
??? 35
??? 36
??? 37
??? 38
??? 39
??? 40
??? 41
??? 42
??? 43
??? 44
??? 45
??? 46

（63）二叉樹中和為某一值的路徑
輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。
思考：dfs

class Solution:
??? # 返回二維列表，內部每個列表表示找到的路徑
??? def FindPath(self, root, expectNumber):
??????? # write code here
??????? ret = []
??????? def dfs(root,sum_,tmp):
??????????? if root:
??????????????? if root.left==None and root.right == None:
??????????????????? if root.val == sum_:
??????????????????????? tmp.append(root.val)
??????????????????????? ret.append(tmp[:])
??????????????? else:
??????????????????? tmp.append(root.val)
??????????????????? dfs(root.left,sum_-root.val,tmp[:])
??????????????????? dfs(root.right,sum_-root.val,tmp[:])
??????? dfs(root,expectNumber,[])
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17

（64）從上往下打印二叉樹
思考：bfs

class Solution:
??? # 返回從上到下每個節點值列表，例：[1,2,3]
??? def PrintFromTopToBottom(self, root):
??????? # write code here
??????? ret = []
??????? if root == None:
??????????? return ret
??????? bfs = [root]
??????? while(bfs):
??????????? tbfs = []
??????????? for node in bfs:
??????????????? ret.append(node.val)
??????????????? if node.left:
??????????????????? tbfs.append(node.left)
??????????????? if node.right:
??????????????????? tbfs.append(node.right)
??????????? bfs = tbfs[:]
??????? return ret

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18

（65）* 二叉搜索樹的后序遍歷序列
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
思考：后序遍歷意味著num[-1]為root，那么根據這個值和二叉搜索樹的性質，可以把數組劃分成兩個部分，left 和 right ，再遞歸判斷

# -*- coding:utf-8 -*-
class Solution:
??? def VerifySquenceOfBST(self, sequence):
??????? # write code here
??????? if len(sequence)==0:
??????????? return False
??????? root = sequence[-1]

??????? i = 0
??????? for node in sequence[:-1]:
??????????? if node > root:
??????????????? break
??????????? i += 1

??????? for node in sequence[i:-1]:
??????????? if node < root:
??????????????? return False
??????? left = True
??????? if i > 1:
??????????? left = self.VerifySquenceOfBST(sequence[:i])

??????? right = True
??????? if i < len(sequence) - 2 and left:
??????????? right = self.VerifySquenceOfBST(sequence[i+1:-1])
??????? return left and right

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12
??? 13
??? 14
??? 15
??? 16
??? 17
??? 18
??? 19
??? 20
??? 21
??? 22
??? 23
??? 24
??? 25

（66）棧的壓入、彈出序列

# -*- coding:utf-8 -*-
class Solution:
??? def IsPopOrder(self, pushV, popV):
??????? # write code here
??????? stack = []
??????? while(popV):
??????????? if pushV and pushV[0]==popV[0]:
??????????????? pushV.pop(0)
??????????????? popV.pop(0)
??????????? elif stack and stack[-1]==popV[0]:
??????????????? stack.pop()
??????????????? popV.pop(0)
??????????? elif pushV:
??????????????? stack.append(pushV.pop(0))
??????????? else:
??????????????? return False
??????? return True
--------------------- ?
作者：ep_mashiro ?
來源：CSDN ?
原文：https://blog.csdn.net/tinkle181129/article/details/79326023 ?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

轉載于:https://www.cnblogs.com/fengff/p/10452817.html

總結

以上是生活随笔為你收集整理的剑指Offer题解（Python版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：计算机考研408高分复习规划-如何复习4
下一篇： Python学习之路——装饰器