1. 二維數(shù)組中的查找
題目描述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序术羔，每一列都按照從上到下遞增的順序排序苹支。請(qǐng)完成一個(gè)函數(shù)赊时，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)抖所。
class Solution:
# array 二維列表
def Find(self, target, array):
rowNum = len(array)
columnNum = len(array[0])
for p in range(rowNum):
for q in range(columnNum):
if target == array[p][q]:
return True
return False
2. 替換空格
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)梨州，將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如田轧，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy暴匠。
class Solution:
# s 源字符串
def replaceSpace(self, s):
return s.replace(" ", "%20")
3. 從頭到尾打印鏈表
題目描述
輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè)ArrayList傻粘。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回從尾部到頭部的列表值序列每窖，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
answer = []
head = listNode
while head:
answer.append(head.val)
head = head.next
return answer[::-1]
4. 重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹弦悉。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字窒典。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回稽莉。
思路：前序遍歷的第一個(gè)節(jié)點(diǎn)即為樹的root瀑志，然后在中序遍歷中找到這個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)左邊的即為left subtree污秆，右邊的即為right subtree后室。
例：{1,2,4,7,3,5,6,8}中1為root，{4,7,2,1,5,3,8,6}中{4,7,2}即為left subtree混狠，{5,3,8,6}即為right subtree岸霹。
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回構(gòu)造的TreeNode根節(jié)點(diǎn)
def reConstructBinaryTree(self, pre, tin):
if len(pre)==0 or len(tin)==0 :
return None
elif len(pre)==1 and len(tin)==1 :
return TreeNode(pre[0])
else:
root = TreeNode(pre[0])
root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[0:tin.index(pre[0])])
root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
return root
5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作将饺。 隊(duì)列中的元素為int類型贡避。
思路：push到stack1，從stack2來pop予弧，stack2空了再加刮吧。
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if self.stack2:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
6. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)掖蛤。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)杀捻，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)蚓庭，該數(shù)組的最小值為1致讥。 NOTE：給出的所有元素都大于0仅仆，若數(shù)組大小為0，請(qǐng)返回0垢袱。
思路：如果后一個(gè)數(shù)比前一個(gè)數(shù)小墓拜，則其為最小的數(shù)。
class Solution:
def minNumberInRotateArray(self, rotateArray):
if len(rotateArray) == 0:
return 0
for i in range(len(rotateArray)):
if rotateArray[i] > rotateArray[i+1]:
return rotateArray[i+1]
7. 斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列请契，現(xiàn)在要求輸入一個(gè)整數(shù)n咳榜，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）爽锥。
class Solution:
def Fibonacci(self, n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a
8. 跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階涌韩，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）氯夷。
思路：Fibonacci的應(yīng)用
class Solution:
def jumpFloor(self, number):
a, b = 0, 1
for i in range(number+1):
a, b = b, a+b
return a
9. 變態(tài)跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階贸辈，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法肠槽。
思路：算出通項(xiàng)公式擎淤。f(n) = 2f(n - 1)
class Solution:
def jumpFloorII(self, number):
return 2**(number - 1)
10. 矩形覆蓋
題目描述
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)2*1的小矩形無重疊地覆蓋一個(gè)2*n的大矩形秸仙，總共有多少種方法嘴拢？
class Solution:
def rectCover(self, number):
if number == 0:
return 0
a, b = 0, 1
for i in range(number+1):
a, b = b, a+b
return a
11. 二進(jìn)制中1的個(gè)數(shù)
題目描述
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)寂纪。其中負(fù)數(shù)用補(bǔ)碼表示席吴。
思路：python的負(fù)數(shù)的補(bǔ)碼表示方法。
參考：Python小技巧：負(fù)數(shù)的補(bǔ)碼表示
class Solution:
def NumberOf1(self, n):
count = 0
if n >= 0:
string = str(bin(n).replace('0b',''))
for i in range(len(string)):
if '1' == string[i]:
count += 1
return count
else:
string = str(bin(((1 << 32) - 1) & n)[2:].zfill(32).replace('0b',''))
for i in range(len(string)):
if '1' == string[i]:
count += 1
return count
12. 數(shù)值的整數(shù)次方
題目描述
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent捞蛋。求base的exponent次方孝冒。
class Solution:
def Power(self, base, exponent):
return base ** exponent
13. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目描述
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序拟杉，使得所有的奇數(shù)位于數(shù)組的前半部分庄涡，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)搬设，偶數(shù)和偶數(shù)之間的相對(duì)位置不變穴店。
class Solution:
def reOrderArray(self, array):
even, odd = [], []
for i in range(len(array)):
if array[i] % 2 == 0:
even.append(array[i])
else:
odd.append(array[i])
return odd + even
14. 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
題目描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)拿穴。
思路：兩個(gè)指針泣洞，一個(gè)先走k步，當(dāng)?shù)谝粋€(gè)指針到最后了默色，第二個(gè)指針即為倒數(shù)第k個(gè)節(jié)點(diǎn)球凰。
class Solution:
def FindKthToTail(self, head, k):
pre = post = head
for i in range(k):
if pre == None:
return None
pre = pre.next
while pre != None:
pre = pre.next
post = post.next
return post
15. 反轉(zhuǎn)鏈表
題目描述
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭呕诉。
class Solution:
def ReverseList(self, pHead):
if pHead == None:
return None
last = None
while pHead:
temp = pHead.next
pHead.next = last
last = pHead
pHead = temp
return last
16. 合并兩個(gè)排序的鏈表
題目描述
輸入兩個(gè)單調(diào)遞增的鏈表缘厢，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則义钉。
class Solution:
def Merge(self, pHead1, pHead2):
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
pHead = None
if pHead1.val > pHead2.val:
pHead = pHead2
pHead.next = self.Merge(pHead1, pHead2.next)
else:
pHead = pHead1
pHead.next = self.Merge(pHead1.next, pHead2)
return pHead
17. 樹的子結(jié)構(gòu)
題目描述
輸入兩棵二叉樹A，B规肴，判斷B是不是A的子結(jié)構(gòu)捶闸。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
class Solution:
def Tree1HasTree2(self, tree1, tree2):
if tree2 == None:
return True
if tree1 == None:
return False
if tree1.val != tree2.val:
return False
return self.Tree1HasTree2(tree1.left, tree2.left) and self.Tree1HasTree2(tree1.right, tree2.right)
def HasSubtree(self, pRoot1, pRoot2):
result = False
if pRoot1 != None and pRoot2 != None:
if pRoot1.val == pRoot2.val:
result = self.Tree1HasTree2(pRoot1, pRoot2)
if not result:
result = self.HasSubtree(pRoot1.left, pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right, pRoot2)
return result
18. 二叉樹的鏡像
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像拖刃。
輸入描述:
二叉樹的鏡像定義：
源二叉樹
鏡像二叉樹
class Solution:
# 返回鏡像樹的根節(jié)點(diǎn)
def Mirror(self, root):
if root == None:
return None
root.left, root.right = root.right, root.left
if root.left != None:
self.Mirror(root.left)
if root.right != None:
self.Mirror(root.right)
19. 順時(shí)針打印矩陣
題目描述
輸入一個(gè)矩陣删壮，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，例如兑牡，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
參考 https://www.runoob.com/python3/python3-func-zip.html
https://blog.csdn.net/weixin_41679411/article/details/86484570
class Solution:
# matrix類型為二維列表央碟，需要返回列表
def printMatrix(self, matrix):
return matrix and list(matrix.pop(0)) + self.printMatrix(list(zip(*matrix))[::-1])
20. 包含min函數(shù)的棧
題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O(1)）均函。
參考https://blog.csdn.net/qq_34364995/article/details/81451186
class Solution:
def __init__(self):
self.stack=[]
self.min_stack=[]
self.min_number = float('inf')
def push(self, node):
if node < self.min_number:
self.min_number = node
self.min_stack.append(self.min_number)
self.stack.append(node)
def pop(self):
if self.stack != []:
if self.stack[-1] == self.min_number:
self.min_stack.pop()
self.stack.pop(-1)
def top(self):
if self.stack != []:
return self.stack[-1]
else:
return None
def min(self):
return self.min_stack[-1]
21. 棧的壓入亿虽、彈出序列
題目描述
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序苞也，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序洛勉。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序如迟，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列收毫，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長度是相等的）
構(gòu)造一個(gè)輔助棧來判斷彈出序列是不是和壓棧序列對(duì)應(yīng)殷勘。首先遍歷壓棧序列的元素push到輔助棧此再，判斷是不是彈出序列的首元素，如果是玲销，則彈出序列pop首元素（指針后移）输拇，如果不是，則繼續(xù)push贤斜，再接著判斷淳附；直到遍歷完了壓棧序列，如果輔助棿拦牛或者彈出序列為空奴曙，則返回True，否則返回False草讶。
class Solution:
def IsPopOrder(self, pushV, popV):
stack = []
for each in pushV:
stack.append(each)
while stack and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if stack == []:
return True
else:
return False
22. 從上往下打印二叉樹
題目描述
從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)洽糟，同層節(jié)點(diǎn)從左至右打印。
class Solution:
# 返回從上到下每個(gè)節(jié)點(diǎn)值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
node_list = [root]
result = []
if not root:
return result
while node_list:
current_root = node_list.pop(0)
result.append(current_root.val)
if current_root.left:
node_list.append(current_root.left)
if current_root.right:
node_list.append(current_root.right)
return result
23. 二叉搜索樹的后序遍歷序列
題目描述
輸入一個(gè)整數(shù)數(shù)組坤溃，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果拍霜。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同薪介。
二叉搜索樹是對(duì)一個(gè)有序數(shù)組進(jìn)行二分查找形成的搜索樹祠饺，它指一棵空樹或者具有下列性質(zhì)的二叉樹：
- 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值汁政；
- 若任意節(jié)點(diǎn)的右子樹不空道偷，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
- 任意節(jié)點(diǎn)的左记劈、右子樹也分別為二叉查找樹勺鸦；'
特點(diǎn)：左子樹結(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，右子樹結(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
后序遍歷：先后序遍歷左子樹目木，再后序遍歷右子樹换途，最后訪問根節(jié)點(diǎn)
后序遍歷得到的序列，最后一個(gè)數(shù)是樹的根節(jié)點(diǎn)的值 刽射，序列中最后一個(gè)數(shù)前面的數(shù)可以分為兩部分：一部分是左子樹節(jié)點(diǎn)的值军拟，它們都比根節(jié)點(diǎn)的值小誓禁；第二部分是右子樹節(jié)點(diǎn)的值吻谋，它們都比根節(jié)點(diǎn)的值要大。
class Solution:
def VerifySquenceOfBST(self, sequence):
if len(sequence) == 0:
return False
root = sequence[-1]
for split_index in range(len(sequence)):
if sequence[split_index] > root:
break
for temp in range(split_index, len(sequence)):
if sequence[temp] < root:
return False
left, right = True, True
left = self.VerifySquenceOfBST(sequence[0:split_index])
if left and split_index < len(sequence) - 1:
right = self.VerifySquenceOfBST(sequence[split_index:-1])
return right
24. 二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹的根節(jié)點(diǎn)和一個(gè)整數(shù)现横，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑漓拾。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中戒祠，數(shù)組長度大的數(shù)組靠前)
思路：
- 如果只有根節(jié)點(diǎn)或者找到葉子節(jié)點(diǎn)骇两，我們就把其對(duì)應(yīng)的val值返回
- 如果不是葉子節(jié)點(diǎn)，我們分別對(duì)根節(jié)點(diǎn)的左子樹姜盈、右子樹進(jìn)行遞歸低千，直到找到葉子結(jié)點(diǎn)。然后遍歷把葉子結(jié)點(diǎn)和父節(jié)點(diǎn)對(duì)應(yīng)的val組成的序列返回上一層馏颂；如果沒找到路徑示血，其實(shí)也返回了序列，只不過是[]
class Solution:
# 返回二維列表救拉，內(nèi)部每個(gè)列表表示找到的路徑
def FindPath(self, root, expectNumber):
result = []
if not root:
return result
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:
result.append([root.val] + item)
return result
25. 復(fù)雜鏈表的復(fù)制
題目描述
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值难审，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)亿絮，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）告喊，返回結(jié)果為復(fù)制后復(fù)雜鏈表的head麸拄。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用黔姜，否則判題程序會(huì)直接返回空）
思路：第一步在原鏈表的基礎(chǔ)上復(fù)制節(jié)點(diǎn)拢切，將節(jié)點(diǎn)復(fù)制在原節(jié)點(diǎn)的后面。第二步復(fù)制隨機(jī)節(jié)點(diǎn)秆吵。 第三步將新舊鏈表分離淮椰。
三步
class Solution:
def Clone(self, pHead):
if pHead == None:
return None
# Step 1
pCur = pHead
while pCur:
node = RandomListNode(pCur.label)
node.next = pCur.next
pCur.next = node
pCur = node.next
# Step 2
pCur = pHead
while pCur:
if pCur.random != None:
pCur.next.random = pCur.random.next
pCur = pCur.next.next
# Step 3
head = pHead.next
cur = head
pCur = pHead
while pCur:
pCur.next = pCur.next.next
if cur.next != None:
cur.next = cur.next.next
cur = cur.next
pCur = pCur.next
return head
26. 二叉搜索樹與雙向鏈表
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表纳寂。要求不能創(chuàng)建任何新的結(jié)點(diǎn)主穗，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。
思路：核心算法依舊是中序遍歷烈疚；不是從根節(jié)點(diǎn)開始黔牵，而是從中序遍歷得到的第一個(gè)節(jié)點(diǎn)開始聪轿；定義兩個(gè)輔助節(jié)點(diǎn)listHead(鏈表頭節(jié)點(diǎn))爷肝、listTail(鏈表尾節(jié)點(diǎn))。事實(shí)上陆错，二叉樹只是換了種形式的鏈表灯抛；listHead用于記錄鏈表的頭節(jié)點(diǎn)，用于最后算法的返回音瓷；listTail用于定位當(dāng)前需要更改指向的節(jié)點(diǎn)对嚼。
參考：https://blog.csdn.net/u010005281/article/details/79657259
class Solution:
def __init__(self):
self.listHead = None
self.listTail = None
def Convert(self, pRootOfTree):
if pRootOfTree == None:
return
self.Convert(pRootOfTree.left)
if self.listHead == None:
self.listHead = pRootOfTree
self.listTail = pRootOfTree
else:
self.listTail.right = pRootOfTree
pRootOfTree.left = self.listTail
self.listTail = pRootOfTree
self.Convert(pRootOfTree.right)
return self.listHead
27. 字符串的排列
題目描述
輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba绳慎。
輸入描述:
輸入一個(gè)字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母纵竖。
思路：化繁為簡，像青蛙跳臺(tái)階的思想那樣杏愤，無論輸入的字符串有多長靡砌，其排列出來的組合式樣式均可分為“第一個(gè)字符串+剩下的字符串”的樣式，可以通過遍歷賦予第一位上不同的字符珊楼。那剩下的字符串又可以如上分解通殃。
注意：ss的索引字符串會(huì)超出范圍，不過python在對(duì)字符串做切片操作時(shí)厕宗，當(dāng)索引位置超出長度画舌，python不會(huì)報(bào)錯(cuò)只會(huì)跳出本次循環(huán)。當(dāng)然我們還要考慮字符串中是否包含重復(fù)元素已慢，因?yàn)樵谳斎胫杏兄貜?fù)值時(shí)就會(huì)生產(chǎn)相同的字符串曲聂，因此在代碼中加一個(gè)判斷即可。
class Solution:
def Permutation(self, ss):
result = []
if len(ss) <= 1:
return ss
for i in range(len(ss)):
for j in map(lambda x: ss[i] + x, self.Permutation(ss[:i]+ss[i+1:])):
if j not in result:
result.append(j)
return result
28. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
題目描述
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半佑惠，請(qǐng)找出這個(gè)數(shù)字句葵。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}厕鹃。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半乍丈，因此輸出2剂碴。如果不存在則輸出0。
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
numbers = sorted(numbers)
count = 0
for each in range(len(numbers)):
if numbers[each] == numbers[len(numbers) // 2]:
count = count + 1
if count > len(numbers)/2:
return numbers[len(numbers) // 2]
else:
return 0
29. 最小的k個(gè)數(shù)
題目描述
輸入n個(gè)整數(shù)轻专，找出其中最小的K個(gè)數(shù)忆矛。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,请垛。
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
return sorted(tinput)[:k] if len(tinput) >= k else []
30. 連續(xù)子數(shù)組的最大和
題目描述
HZ偶爾會(huì)拿些專業(yè)問題來忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)催训。今天測試組開完會(huì)后，他又發(fā)話了：在古老的一維模式識(shí)別中宗收，常常需要計(jì)算連續(xù)子向量的最大和漫拭，當(dāng)向量全為正數(shù)的時(shí)候，問題很好解決混稽。但是采驻，如果向量中包含負(fù)數(shù)，是否應(yīng)該包含某個(gè)負(fù)數(shù)匈勋，并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢礼旅？例如：{6,-3,-2,7,-15,1,2,2}，連續(xù)子向量的最大和為8(從第0個(gè)開始洽洁，到第3個(gè)為止)痘系。給一個(gè)數(shù)組，返回它的最大連續(xù)子序列的和饿自，你會(huì)不會(huì)被他忽悠滋洹？(子向量的長度至少是1)
有個(gè)最優(yōu)子結(jié)構(gòu)性質(zhì)：DP[i] = max{DP[i-1] + A[i], A[i]}
class Solution:
def FindGreatestSumOfSubArray(self, array):
res = max(array)
temp = 0
for each in array:
temp = max(each, temp + each)
res = max(temp, res)
return res
31. 整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）
題目描述
求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)昭雌？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1笨篷、10姻成、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問題他就沒轍了奏候。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）厢破。
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
number_string = ''
for each in range(1, n+1):
number_string = number_string + str(each)
return len(number_string) - len(number_string.replace('1', ''))
32. 把數(shù)組排成最小的數(shù)
題目描述
輸入一個(gè)正整數(shù)數(shù)組愧旦，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)跌造，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3间聊，32攒盈，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323哎榴。
class Solution:
def PrintMinNumber(self, numbers):
if numbers is None or len(numbers) == 0:
return ''
numbers = map(str, numbers)
numbers.sort(cmp = lambda x, y : cmp(x + y, y + x))
return ''.join(numbers).lstrip()
33. 丑數(shù)
題目描述
把只包含質(zhì)因子2型豁、3和5的數(shù)稱作丑數(shù)（Ugly Number）僵蛛。例如6、8都是丑數(shù)迎变，但14不是充尉，因?yàn)樗|(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)衣形。求按從小到大的順序的第N個(gè)丑數(shù)驼侠。
參考：https://blog.csdn.net/weixin_36372879/article/details/84871967
class Solution:
def GetUglyNumber_Solution(self, index):
if index < 1:
return 0
if index == 1:
return 1
uglyNumberList = [1]
t2, t3, t5 = 0, 0, 0
for i in range(1, index):
if uglyNumberList[t2] * 2 <= uglyNumberList[i-1]:
t2 += 1
if uglyNumberList[t3] * 3 <= uglyNumberList[i-1]:
t3 += 1
if uglyNumberList[t5] * 5 <= uglyNumberList[i-1]:
t5 += 1
uglyNumber = min(uglyNumberList[t2]*2,uglyNumberList[t3]*3,uglyNumberList[t5]*5)
uglyNumberList.append(uglyNumber)
return uglyNumberList[index - 1]
34. 第一個(gè)只出現(xiàn)一次的字符
題目描述
在一個(gè)字符串(0<=字符串長度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）.
class Solution:
def FirstNotRepeatingChar(self, s):
if not s or len(s)>10000:
return -1
for each in s:
if s.count(each) == 1:
return s.index(each)
35. 數(shù)組中的逆序?qū)?/h1>
題目描述
在數(shù)組中的兩個(gè)數(shù)字谆吴，如果前面一個(gè)數(shù)字大于后面的數(shù)字倒源，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P句狼。并將P對(duì)1000000007取模的結(jié)果輸出笋熬。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：
對(duì)于%50的數(shù)據(jù),size<=10^4
對(duì)于%75的數(shù)據(jù),size<=10^5
對(duì)于%100的數(shù)據(jù),size<=2*10^5
示例1
輸入：1,2,3,4,5,6,7,0
輸出：7
超過運(yùn)行時(shí)間限制。
class Solution:
def InversePairs(self, data):
count = 0
while len(data)>1:
min_data_index = data.index(min(data))
count += min_data_index
data.pop(min_data_index)
return count%1000000007
36. 兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)
題目描述
輸入兩個(gè)鏈表腻菇，找出它們的第一個(gè)公共結(jié)點(diǎn)胳螟。
思路：
- 如果兩個(gè)鏈表長度一樣，則正常遍歷芜繁，找到相同的或者不存在旺隙。
- 如果兩個(gè)鏈表長度不同绒极，則首先短的遍歷結(jié)束后會(huì)從另一個(gè)鏈表開頭開始遍歷骏令，而當(dāng)另一個(gè)節(jié)點(diǎn)遍歷結(jié)束后從另一個(gè)鏈表頭開始遍歷時(shí)，這兩個(gè)鏈表的差則會(huì)消除垄提。
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
p1 = pHead1
p2 = pHead2
while p1 != p2:
p1 = pHead2 if p1 is None else p1.next
p2 = pHead1 if p2 is None else p2.next
return p1
37. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
題目描述
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)榔袋。
class Solution:
def GetNumberOfK(self, data, k):
return data.count(k)
38. 二叉樹的深度
題目描述
輸入一棵二叉樹，求該樹的深度铡俐。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根凰兑、葉結(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度审丘。
class Solution:
def TreeDepth(self, pRoot):
if pRoot == None:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left, right) + 1
39. 平衡二叉樹
題目描述
輸入一棵二叉樹吏够，判斷該二叉樹是否是平衡二叉樹。
class Solution:
def IsBalanced_Solution(self, pRoot):
if pRoot == None:
return True
left_depth = self.TreeDepth(pRoot.left)
right_depth = self.TreeDepth(pRoot.right)
if abs(left_depth - right_depth) > 1:
return False
return True
def TreeDepth(self, pRoot):
if pRoot == None:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left, right) + 1
40. 數(shù)組中只出現(xiàn)一次的數(shù)字
題目描述
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外滩报，其他的數(shù)字都出現(xiàn)了兩次锅知。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
class Solution:
# 返回[a,b] 其中ab是出現(xiàn)一次的兩個(gè)數(shù)字
def FindNumsAppearOnce(self, array):
result = []
for each in array:
if array.count(each) == 1:
result.append(each)
return result
41. 和為s的連續(xù)正數(shù)序列
題目描述
小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫出了正確答案是100脓钾。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))售睹。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列：18,19,20,21,22。現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述
輸出所有和為S的連續(xù)正數(shù)序列可训。序列內(nèi)按照從小至大的順序昌妹，序列間按照開始數(shù)字從小到大的順序
class Solution:
def FindContinuousSequence(self, tsum):
result = []
for i in range(1, tsum // 2 + 1):
t_sum = 0
for j in range(i, tsum // 2 + 2):
t_sum += j
if t_sum == tsum:
result.append(list(range(i,j+1)))
return result
42. 和為S的兩個(gè)數(shù)字
題目描述
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S捶枢，在數(shù)組中查找兩個(gè)數(shù)，使得他們的和正好是S飞崖，如果有多對(duì)數(shù)字的和等于S烂叔，輸出兩個(gè)數(shù)的乘積最小的。
輸出描述
對(duì)應(yīng)每個(gè)測試案例固歪，輸出兩個(gè)數(shù)长已，小的先輸出。
class Solution:
def FindNumbersWithSum(self, array, tsum):
result = []
for i in range(len(array)):
for j in range(len(array)-1, i-1, -1):
if array[i] + array[j] == tsum:
result.append(array[i])
result.append(array[j])
return result
return result
43. 左旋轉(zhuǎn)字符串
題目描述
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）昼牛，現(xiàn)在有個(gè)簡單的任務(wù)术瓮，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果。對(duì)于一個(gè)給定的字符序列S贰健，請(qǐng)你把其循環(huán)左移K位后的序列輸出胞四。例如，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果伶椿，即“XYZdefabc”辜伟。是不是很簡單？OK脊另，搞定它导狡！
class Solution:
def LeftRotateString(self, s, n):
if s == '':
return ''
s_list = list(s)
for i in range(n):
temp = s_list.pop(0)
s_list.append(temp)
return ''.join(str(i) for i in s_list)
44. 翻轉(zhuǎn)單詞順序列
題目描述
牛客最近來了一個(gè)新員工Fish偎痛，每天早晨總是會(huì)拿著一本英文雜志旱捧，寫些句子在本子上。同事Cat對(duì)Fish寫的內(nèi)容頗感興趣踩麦，有一天他向Fish借來翻看枚赡，但卻讀不懂它的意思。例如谓谦，“student. a am I”贫橙。后來才意識(shí)到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了反粥，正確的句子應(yīng)該是“I am a student.”卢肃。Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么才顿？
class Solution:
def ReverseSentence(self, s):
s_list = s.split(' ')
return ' '.join(str(i) for i in s_list[::-1])
45. 撲克牌順子
題目描述
LL今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張_)...他隨機(jī)從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿Ｄ妗！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13娜膘。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”逊脯。LL決定去買體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運(yùn)氣如何竣贪， 如果牌能組成順子就輸出true军洼，否則就輸出false巩螃。為了方便起見,你可以認(rèn)為大小王是0。
得到hash表后只需計(jì)算最大的鍵值和最小的鍵值的差匕争，若小于5避乏，不需考慮有多少大小王，都可以組成順子甘桑。
class Solution:
def IsContinuous(self, numbers):
if len(numbers) != 5:
return False
cards = {}
for each in numbers:
if each == 0:
continue
if each in cards.keys():
return False
else:
cards[each] = 1
if max(cards.keys()) - min(cards.keys()) < 5:
return True
else:
return False
46. 孩子們的游戲（圓圈中最后剩下的數(shù)）
題目描述
每年六一兒童節(jié),排钠ぃ客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為排芎迹客的資深元老,自然也準(zhǔn)備了一些小游戲铆帽。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開始報(bào)數(shù)德谅。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到诺鳎客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢窄做？(注：小朋友的編號(hào)是從0到n-1)
約瑟夫環(huán)問題
參考：https://blog.csdn.net/fuxuemingzhu/article/details/79702974
class Solution:
def LastRemaining_Solution(self, n, m):
if n < 1 or m < 1:
return -1
result = 0
for i in range(2, n+1):
result = (result + m) % i
return result
47. 求1+2+3+...+n
題目描述
求1+2+3+...+n愧驱，要求不能使用乘除法、for椭盏、while组砚、if、else掏颊、switch糟红、case等關(guān)鍵字及條件判斷語句（A?B:C）。
class Solution:
def Sum_Solution(self, n):
result = n
temp = (n > 1 and self.Sum_Solution(n - 1))
result = result + temp
return result
48. 不用加減乘除做加法
題目描述
寫一個(gè)函數(shù)蚯舱，求兩個(gè)整數(shù)之和改化，要求在函數(shù)體內(nèi)不得使用+掩蛤、-枉昏、*、/四則運(yùn)算符號(hào)揍鸟。
參考：https://www.acwing.com/activity/content/code/content/21074/
class Solution:
def Add(self, num1, num2):
while True:
# 不進(jìn)位加法
s = num1 ^ num2
# 計(jì)算進(jìn)位
carry = num1 & num2
# 手動(dòng)把高于 32 位的部分變成 0
num1 = s & 0xFFFFFFFF
num2 = carry << 1
if carry == 0:
break
# 如果是正數(shù)和 0 兄裂，就直接返回這個(gè)正數(shù)
if num1 >> 31 == 0:
return num1
# 如果是負(fù)數(shù)
return num1 - (1 << 32)
49. 把字符串轉(zhuǎn)換成整數(shù)
題目描述
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)(實(shí)現(xiàn)Integer.valueOf(string)的功能，但是string不符合數(shù)字要求時(shí)返回0)阳藻，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)晰奖。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0。
輸入描述:
輸入一個(gè)字符串,包括數(shù)字字母符號(hào),可以為空
輸出描述:
如果是合法的數(shù)值表達(dá)則返回該數(shù)字腥泥，否則返回0
示例1
輸入
+2147483647
1a33
輸出
2147483647
0
50. 數(shù)組中重復(fù)的數(shù)字
題目描述
在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)匾南。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的蛔外。也不知道每個(gè)數(shù)字重復(fù)幾次蛆楞。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字溯乒。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}豹爹，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2裆悄。
class Solution:
# 這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
# 函數(shù)返回True/False
def duplicate(self, numbers, duplication):
n = {}
for each in numbers:
if each in n.keys():
duplication[0] = each
return True
else:
n[each] = 1
return False
51. 構(gòu)建乘機(jī)數(shù)組
題目描述
給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法臂聋。
class Solution:
def multiply(self, A):
if not A:
return []
B = [1 for _ in range(len(A))]
for i in range(1, len(A)):
B[i] = B[i-1] * A[i-1]
temp = 1
for i in range(len(A)-2, -1, -1):
temp *= A[i+1]
B[i] *= temp
return B
52. 正則表達(dá)式匹配
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包括'.'和'*'的正則表達(dá)式光稼。模式中的字符'.'表示任意一個(gè)字符，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）孩等。 在本題中艾君，匹配是指字符串的所有字符匹配整個(gè)模式。例如肄方，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配腻贰，但是與"aa.a"和"ab*a"均不匹配
參考：https://blog.csdn.net/u010005281/article/details/80200492
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
if s == pattern:
return True
if len(pattern) > 1 and pattern[1] == '*':
if s and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s, pattern[2:]) or self.match(s[1:], pattern)
else:
return self.match(s, pattern[2:])
elif s and pattern and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s[1:], pattern[1:])
return False
53. 表示數(shù)值的字符串
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如扒秸，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值播演。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
54. 字符流中第一個(gè)不重復(fù)的字符
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來找出字符流中第一個(gè)只出現(xiàn)一次的字符伴奥。例如写烤，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"拾徙。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)洲炊，第一個(gè)只出現(xiàn)一次的字符是"l"。
輸出描述:
如果當(dāng)前字符流沒有存在出現(xiàn)一次的字符尼啡，返回#字符暂衡。
class Solution:
def __init__(self):
self.char_dic = {}
self.char_s = ''
def FirstAppearingOnce(self):
for each in self.char_s:
if self.char_dic[each] == 1:
return each
return '#'
def Insert(self, char):
if char not in self.char_dic.keys():
self.char_dic[char] = 1
else:
self.char_dic[char] += 1
self.char_s += char
55. 鏈表中環(huán)的入口結(jié)點(diǎn)
題目描述
給一個(gè)鏈表，若其中包含環(huán)崖瞭，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)狂巢，否則，輸出null书聚。
56. 刪除鏈表中重復(fù)的結(jié)點(diǎn)
題目描述
在一個(gè)排序的鏈表中唧领，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)雌续，重復(fù)的結(jié)點(diǎn)不保留斩个，返回鏈表頭指針。 例如驯杜，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
57. 二叉樹的下一個(gè)結(jié)點(diǎn)
題目描述
給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)受啥，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)滚局，同時(shí)包含指向父結(jié)點(diǎn)的指針叁温。
分三種情況：
- 給定的節(jié)點(diǎn)為空——返回空；
- 給定的節(jié)點(diǎn)有右子樹——沿著該右子樹核畴，返回右子樹的第一個(gè)左葉子節(jié)點(diǎn)膝但；
- 給定的節(jié)點(diǎn)沒有右子樹——如果位于某個(gè)節(jié)點(diǎn)的左子樹中，則上溯直至找到該節(jié)點(diǎn)谤草；否則就返回空跟束。
class Solution:
def GetNext(self, pNode):
if not pNode:
return None
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
else:
while pNode.next:
if pNode == pNode.next.left:
return pNode.next
pNode = pNode.next
return None
58. 對(duì)稱的二叉樹
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一顆二叉樹是不是對(duì)稱的丑孩。注意冀宴，如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的，定義其為對(duì)稱的温学。
class Solution:
def isSymmetrical(self, pRoot):
if not pRoot:
return True
return self.checkSymmetrical(pRoot.left, pRoot.right)
def checkSymmetrical(self, left, right):
if not left and not right:
return True
if not left or not right:
return False
if left.val != right.val:
return False
return self.checkSymmetrical(left.left, right.right) and self.checkSymmetrical(left.right, right.left)
59. 按之字形順序打印二叉樹
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹略贮，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印仗岖，第三行按照從左到右的順序打印逃延，其他行以此類推。
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
i = -1
result_list = []
current_layer = [pRoot]
while current_layer:
i *= -1
current_list = []
next_layer = []
for node in current_layer:
current_list.append(node.val)
if node.left:
next_layer.append(node.left)
if node.right:
next_layer.append(node.right)
result_list.append(current_list[::i])
current_layer = next_layer
return result_list
60. 把二叉樹打印成多行
題目描述
從上到下按層打印二叉樹轧拄，同一層結(jié)點(diǎn)從左至右輸出揽祥。每一層輸出一行。
class Solution:
# 返回二維列表[[1,2],[4,5]]
def Print(self, pRoot):
if not pRoot:
return []
result_list = []
current_layer = [pRoot]
while current_layer:
current_list = []
next_layer = []
for node in current_layer:
current_list.append(node.val)
if node.left:
next_layer.append(node.left)
if node.right:
next_layer.append(node.right)
result_list.append(current_list)
current_layer = next_layer
return result_list
61. 序列化二叉樹
題目描述
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)檩电，分別用來序列化和反序列化二叉樹
序列化是將數(shù)據(jù)結(jié)構(gòu)或?qū)ο筠D(zhuǎn)換為一系列位的過程拄丰，以便它可以存儲(chǔ)在文件或內(nèi)存緩沖區(qū)中，或通過網(wǎng)絡(luò)連接鏈路傳輸俐末，以便稍后在同一個(gè)或另一個(gè)計(jì)算機(jī)環(huán)境中重建料按。
class Solution:
def Serialize(self, root):
if not root:
return '#'
return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)
def Deserialize(self, s):
s_list = s.split(',')
return self.DeserializeTree(s_list)
def DeserializeTree(self, s_list):
if len(s_list) == 0:
return None
value = s_list.pop(0)
root = None
if value != '#':
root = TreeNode(int(value))
root.left = self.DeserializeTree(s_list)
root.right = self.DeserializeTree(s_list)
return root
62. 二叉搜索樹的第k個(gè)結(jié)點(diǎn)
題目描述
給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)卓箫。例如载矿， （5，3丽柿，7恢准，2，4甫题，6，8）中涂召，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4坠非。
class Solution:
count = 0
def KthNode(self, pRoot, k):
if not pRoot:
return None
node = self.KthNode(pRoot.left, k)
if node:
return node
self.count += 1
if self.count == k:
return pRoot
node = self.KthNode(pRoot.right, k)
if node:
return node
63. 數(shù)據(jù)流中的中位數(shù)
題目描述
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值果正，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值炎码。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值盟迟，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流潦闲，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)攒菠。
class Solution:
def __init__(self):
self.arr = []
def Insert(self, num):
self.arr.append(num)
self.arr.sort()
def GetMedian(self, n=None):
length = len(self.arr)
if length % 2 == 1:
return self.arr[length//2]
else:
return (self.arr[length//2 - 1] + self.arr[length//2]) / 2.0
64. 滑動(dòng)窗口的最大值
題目描述
給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值歉闰。例如辖众，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口和敬，他們的最大值分別為{4,4,6,6,6,5}凹炸； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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]}变骡。
class Solution:
def maxInWindows(self, num, size):
result = []
if not num or len(num) < size or size < 1:
return result
for i in range(len(num)-size + 1):
result.append(max(num[i:i+size]))
return result
65. 矩陣中的路徑
題目描述
請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑芭逝。路徑可以從矩陣中的任意一個(gè)格子開始锣光，每一步可以在矩陣中向左，向右铝耻，向上誊爹，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子瓢捉，則之后不能再次進(jìn)入這個(gè)格子频丘。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑泡态，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后搂漠，路徑不能再次進(jìn)入該格子。
回溯法
參考：https://blog.csdn.net/qq_20141867/article/details/81065793
class Solution:
def hasPath(self, matrix, rows, cols, path):
if len(matrix) == 0 or len(matrix) != rows * cols or len(path) == 0:
return False
visited = [False] * len(matrix)
pathLengthFound = 0
for x in range(cols):
for y in range(rows):
if self.hasPathAlgorithm(matrix, rows, cols, path, x, y, visited, pathLengthFound):
return True
return False
def hasPathAlgorithm(self, matrix, rows, cols, path, x, y, visited, pathLengthFound):
if pathLengthFound == len(path):
return True
current_haspath = False
if 0 <= x <cols and 0 <= y < rows and matrix[y * cols + x] == path[pathLengthFound] and not visited[y * cols + x]:
visited[y * cols + x] = True
pathLengthFound += 1
current_haspath = self.hasPathAlgorithm(matrix, rows, cols, path, x-1, y, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x, y-1, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x+1, y, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x, y+1, visited, pathLengthFound)
if not current_haspath:
pathLengthFound -= 1
visited[y * cols + x] = False
return current_haspath
66. 機(jī)器人的運(yùn)動(dòng)范圍
題目描述
地上有一個(gè)m行和n列的方格某弦。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)桐汤，每一次只能向左，右靶壮，上怔毛，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子腾降。 例如拣度，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18抗果。但是筋帖，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19冤馏。請(qǐng)問該機(jī)器人能夠達(dá)到多少個(gè)格子日麸？
回溯法
class Solution:
def movingCount(self, threshold, rows, cols):
matrix = [[0 for _ in range(cols)] for _ in range(rows)]
count = self.find_grid(threshold, rows, cols, matrix, 0, 0)
return count
def find_grid(self, threshold, rows, cols, matrix, x, y):
count = 0
if 0 <= x < rows and 0 <= y < cols and matrix[x][y] == 0 and self.judge(threshold, x, y):
matrix[x][y] = 1
count = 1 + self.find_grid(threshold, rows, cols, matrix, x-1, y) + self.find_grid(threshold, rows, cols, matrix, x, y-1) + self.find_grid(threshold, rows, cols, matrix, x+1, y) + self.find_grid(threshold, rows, cols, matrix, x, y+1)
return count
def judge(self, threshold, x, y):
if sum(map(int, str(x) + str(y))) <= threshold:
return True
else:
return False
