二維數(shù)據(jù)中的查找
題目描述
在一個(gè)二維數(shù)組中枯怖，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序能曾。請(qǐng)完成一個(gè)函數(shù)嫁怀，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)借浊。
分析
本題關(guān)鍵在于找到左下角和右上角這兩個(gè)元素塘淑，因?yàn)檫@兩個(gè)元素在兩個(gè)方向是分別遞增和遞減，就可以有規(guī)律的移動(dòng)需要比較的目標(biāo)元素蚂斤。如果選用左上角或者右下角存捺，對(duì)于兩個(gè)方向都是遞增或遞減
class Solution:
# array 二維列表
def Find(self, target, array):
col = 0
# 行數(shù)
row_n = len(array)
# 列數(shù)
col_n = len(array[0])
# 判斷是否大于最大值小于最小值
if target > array[row_n - 1][col_n - 1] or target < array[0][0]:
return False
# 向上向右移動(dòng)的時(shí)候不能越界
while col <= col_n - 1 and row_n >= 0:
# 需要和目標(biāo)值比較的值(初始為左下角的元素或者是右上角)
list_target = array[row_n - 1][col]
# 如果目標(biāo)值大于
if target > list_target:
# 向右移動(dòng)
col += 1
# 如果等于返回true
elif target == list_target:
return True
# 如果小于
else:
# 向上移動(dòng)
row_n -= 1
return False
替換空格
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如捌治，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy岗钩。
分析
看到題目的直接反應(yīng)就是用字符串的替換方法，可能題目的意思時(shí)不能調(diào)用str的方法肖油，但是偶嫦牛客這里可以通過。
看有的解析還用了正則替換森枪，當(dāng)然都可以
class Solution:
# s 源字符串
def replaceSpace(self, s):
return str(s).replace(" ", "%20")
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)视搏，將一個(gè)字符串中的空格替換成“%20”。例如县袱，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy浑娜。
分析
看到題目的直接反應(yīng)就是用字符串的替換方法，可能題目的意思時(shí)不能調(diào)用str的方法式散，但是沤钤猓客這里可以通過。
看有的解析還用了正則替換暴拄，當(dāng)然都可以
# s 源字符串
def replaceSpace(self, s):
return str(s).replace(" ", "%20")
從尾到頭打印鏈表
題目描述
輸入一個(gè)鏈表漓滔，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。
分析
有很多種辦法乖篷，可以正向遍歷存入列表次和，然后翻轉(zhuǎn)列表；可以使用棧存儲(chǔ)那伐，還可以使用遞歸向列表中添加節(jié)點(diǎn)的值
class Solution:
def __init__(self):
self.list1 = []
# 返回從尾部到頭部的列表值序列踏施，例如[1,2,3]
def printListFromTailToHead(self, listNode):
if listNode is not None:
self.printListFromTailToHead(listNode.next)
self.list1.append(listNode.val)
return self.list1
斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n罕邀，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)畅形。
n<=39
分析
首先想到的是遞歸，最簡(jiǎn)潔诉探，但是會(huì)有超時(shí)之類的問題日熬，所以改為迭代相加
class Solution:
def Fibonacci(self, n):
"""
斐波那契數(shù)列
:param n:
:return:
"""
num0 = 0
num1 = 1
num_n = 0
if n == 0:
return 0
if n == 1:
return 1
for i in range(2, n + 1):
num_n = num0 + num1
num0 = num1
num1 = num_n
return num_n
跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)肾胯。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法竖席。
分析
通過分析前幾次結(jié)果，我們也能發(fā)現(xiàn)這也是一個(gè)斐波那契數(shù)列敬肚，所以按照同樣的方法即可
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5毕荐， 可以總結(jié)出f(n) = f(n-1) + f(n-2)的規(guī)律
class Solution:
def jumpFloor(self, number):
"""
f(n) = f(n-1) + f(n-2)
:param number:
:return:
"""
a, b = 1, 1
for i in range(number):
a, b = b, a + b
return a
變態(tài)跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)艳馒。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法憎亚。
分析
第一種方法:
因?yàn)閚級(jí)臺(tái)階员寇，第一步有n種跳法：跳1級(jí)、跳2級(jí)第美、到跳n級(jí)
跳1級(jí)蝶锋，剩下n-1級(jí)，則剩下跳法是f(n-1)
跳2級(jí)什往，剩下n-2級(jí)扳缕，則剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因?yàn)閒(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)第二種方法
每個(gè)臺(tái)階都有跳與不跳兩種情況（除了最后一個(gè)臺(tái)階），最后一個(gè)臺(tái)階必須跳别威。所以共用2^(n-1)中情況
class Solution:
def jumpFloorII(self, number):
"""
每個(gè)臺(tái)階都有跳與不跳兩種情況（除了最后一個(gè)臺(tái)階）躯舔，最后一個(gè)臺(tái)階必須跳庸毫。所以共用2^(n-1)中情況
:param number: int
:return: int
"""
if number <= 0:
return 0
else:
return pow(2, number - 1)
矩形覆蓋
題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形仔拟。請(qǐng)問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法利花？
分析
通過分析前幾次結(jié)果，我們也能發(fā)現(xiàn)這也是一個(gè)斐波那契數(shù)列权薯，所以按照同樣的方法即可,
對(duì)于0這個(gè)特殊值需要特殊處理
class Solution:
def rectCover(self, number):
"""
分析可知，還是斐波那契數(shù)列
:param number:
:return:
"""
if number == 0:
return 0
a, b = 1, 1
for i in range(number):
a, b = b, a + b
return a
二進(jìn)制中1的個(gè)數(shù)
題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2*n的大矩形甩鳄，總共有多少種方法？
分析
重點(diǎn)在怎么求補(bǔ)碼，我的解法是轉(zhuǎn)換為二進(jìn)制字符串然后統(tǒng)計(jì)1的個(gè)數(shù)
還有吧一種使用&進(jìn)行操作的這里不做說明
class Solution:
def NumberOf1(self, n):
"""
求補(bǔ)碼然后使用字符串count函數(shù)統(tǒng)計(jì)
:param n:
:return:
"""
if n < 0:
return bin(2 ** 32 + n).count('1')
return bin(n).count('1')
數(shù)值的整數(shù)次方
題目描述
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent淡喜。求base的exponent次方瘟芝。
分析
沒怎么研究，直接使用的內(nèi)置函數(shù)，通過查閱資料叫榕，看到一種快速冪求解方式浑侥，有興趣自己研究下
class Solution:
def Power(self, base, exponent):
"""
還可以使用快速冪求法
:param base:
:param exponent:
:return:
"""
return pow(base, exponent)
調(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ì)位置不變伶选。
分析
用了最簡(jiǎn)單的解法史飞，創(chuàng)建兩個(gè)列表分別接收奇數(shù)和偶數(shù)，最后拼起來
class Solution:
def reOrderArray(self, array):
odd_list = []
even_list = []
for i in array:
if i % 2 != 0:
odd_list.append(i)
else:
even_list.append(i)
return odd_list + even_list
反轉(zhuǎn)鏈表
題目描述
輸入一個(gè)鏈表仰税，反轉(zhuǎn)鏈表后构资，輸出鏈表的所有元素。
分析
首先判斷頭節(jié)點(diǎn)或者第一個(gè)節(jié)點(diǎn)是否為空陨簇，在不為空的時(shí)候迭代鏈表
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
"""
倒置鏈表
:param pHead:
:return:
"""
# 判斷當(dāng)前節(jié)點(diǎn)是否為空或者下一個(gè)節(jié)點(diǎn)為空
if not pHead or not pHead.next:
return pHead
# 初始化未節(jié)點(diǎn)為空
last = None
# 循環(huán)迭代頭節(jié)點(diǎn)
while pHead:
# 創(chuàng)建一個(gè)中間節(jié)點(diǎn)接受頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
tmp = pHead.next
# 將尾節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
pHead.next = last
# 將頭節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
last = pHead
# 將中間節(jié)點(diǎn)賦值給頭節(jié)點(diǎn)
pHead = tmp
return last
合并兩個(gè)排序的鏈表
題目描述
輸入兩個(gè)單調(diào)遞增的鏈表吐绵，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則
分析
我們使用其中的一個(gè)結(jié)點(diǎn)將兩個(gè)鏈表拼接起來河绽，換句話說己单，就是將一個(gè)鏈表合并到另一個(gè)鏈表上，所以并不能創(chuàng)建一個(gè)新鏈表去進(jìn)行操作耙饰。
當(dāng)其中某一個(gè)鏈表為空時(shí)纹笼，只需要返回另一個(gè)鏈表即可，這種情況需要單獨(dú)討論
當(dāng)兩個(gè)鏈表均不為空時(shí)苟跪，我們需要去比較結(jié)點(diǎn)兩個(gè)鏈表中結(jié)點(diǎn)的大小廷痘，當(dāng)l1的結(jié)點(diǎn)值小于l2的結(jié)點(diǎn)時(shí)，我們就需要將l2合并到l1上削咆，把l2的結(jié)點(diǎn)一個(gè)一個(gè)拼到l1上牍疏，知道l2為為空時(shí)蠢笋，循環(huán)就可以結(jié)束了拨齐。這個(gè)過程是重復(fù)的，所以我們這里可以使用遞歸操作昨寞，反之，當(dāng)l2的結(jié)點(diǎn)小于l1時(shí)，就把l1拼接到l2上
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
"""
倒置鏈表
:param pHead:
:return:
"""
# 判斷當(dāng)前節(jié)點(diǎn)是否為空或者下一個(gè)節(jié)點(diǎn)為空
if not pHead or not pHead.next:
return pHead
# 初始化未節(jié)點(diǎn)為空
last = None
# 循環(huán)迭代頭節(jié)點(diǎn)
while pHead:
# 創(chuàng)建一個(gè)中間節(jié)點(diǎn)接受頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
tmp = pHead.next
# 將尾節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
pHead.next = last
# 將頭節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
last = pHead
# 將中間節(jié)點(diǎn)賦值給頭節(jié)點(diǎn)
pHead = tmp
return last
樹的子結(jié)構(gòu)
題目描述
輸入兩棵二叉樹A箱舞，B锹锰，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
分析
判斷是否是子樹享怀，也就是其中部分樹與另一個(gè)樹相等羽峰，我們可以單獨(dú)寫一個(gè)函數(shù)判斷兩個(gè)樹是否相同，然后將一個(gè)樹的左右子樹遞歸帶入即可
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# 如果root1或者root2有一個(gè)為null
if not pRoot1 or not pRoot2:
return False
return self.is_subtree(pRoot1, pRoot2) \
or self.HasSubtree(pRoot1.left, pRoot2) \
or self.HasSubtree(pRoot1.right, pRoot2)
def is_subtree(self, A, B):
"""
判斷是否時(shí)子樹
:param A:
:param B:
:return:
"""
if not B:
return True
# 判斷a不為空或者a的值與b的值不相等
if not A or A.val != B.val:
return False
return self.is_subtree(A.left, B.left) \
and self.is_subtree(A.right, B.right)
合并兩個(gè)排序的鏈表
題目描述
輸入兩個(gè)單調(diào)遞增的鏈表添瓷，輸出兩個(gè)鏈表合成后的鏈表梅屉，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則
分析
我們使用其中的一個(gè)結(jié)點(diǎn)將兩個(gè)鏈表拼接起來，換句話說鳞贷，就是將一個(gè)鏈表合并到另一個(gè)鏈表上坯汤，所以并不能創(chuàng)建一個(gè)新鏈表去進(jìn)行操作。
當(dāng)其中某一個(gè)鏈表為空時(shí)搀愧，只需要返回另一個(gè)鏈表即可惰聂，這種情況需要單獨(dú)討論
當(dāng)兩個(gè)鏈表均不為空時(shí)疆偿，我們需要去比較結(jié)點(diǎn)兩個(gè)鏈表中結(jié)點(diǎn)的大小，當(dāng)l1的結(jié)點(diǎn)值小于l2的結(jié)點(diǎn)時(shí)搓幌，我們就需要將l2合并到l1上杆故，把l2的結(jié)點(diǎn)一個(gè)一個(gè)拼到l1上，知道l2為為空時(shí)溉愁，循環(huán)就可以結(jié)束了反番。這個(gè)過程是重復(fù)的，所以我們這里可以使用遞歸操作叉钥，反之罢缸，當(dāng)l2的結(jié)點(diǎn)小于l1時(shí)，就把l1拼接到l2上
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
"""
倒置鏈表
:param pHead:
:return:
"""
# 判斷當(dāng)前節(jié)點(diǎn)是否為空或者下一個(gè)節(jié)點(diǎn)為空
if not pHead or not pHead.next:
return pHead
# 初始化未節(jié)點(diǎn)為空
last = None
# 循環(huán)迭代頭節(jié)點(diǎn)
while pHead:
# 創(chuàng)建一個(gè)中間節(jié)點(diǎn)接受頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
tmp = pHead.next
# 將尾節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
pHead.next = last
# 將頭節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
last = pHead
# 將中間節(jié)點(diǎn)賦值給頭節(jié)點(diǎn)
pHead = tmp
return last
二叉樹的鏡像
題目描述
操作給定的二叉樹投队，將其變換為源二叉樹的鏡像枫疆。
二叉樹的鏡像定義：源二叉樹
8
/
6 10
/ \ /
5 7 9 11
鏡像二叉樹
8
/
10 6
/ \ /
11 9 7 5
分析
一般看到樹的題都是使用遞歸處理最簡(jiǎn)單明了，轉(zhuǎn)變?yōu)殓R像數(shù)敷鸦，我們很容易想到去交換樹的左右子樹息楔，然后遞歸左子樹和右子樹即可
class Solution:
def Mirror(self, root):
"""
返回鏡像樹的根節(jié)點(diǎn)
:param root:
:return:
"""
# 如果跟節(jié)點(diǎn)為空
if not root:
return None
# 交換左子樹和右子樹
root.left, root.right = root.right, root.left
# 遞歸左右子樹
self.Mirror(root.left)
self.Mirror(root.right)
順時(shí)針打印矩陣
題目描述
輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字扒披，例如值依，如果輸入如下矩陣： 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.
分析
找出邊界條件，將矩陣分為四個(gè)方向碟案，注意每個(gè)方向上的結(jié)束條件
class Solution:
# matrix類型為二維列表愿险，需要返回列表
def printMatrix(self, matrix):
if matrix is None:
return
rows = len(matrix)
cols = len(matrix[0])
start = 0
result = []
while rows > 2 * start and cols > 2 * start:
endx = rows - 1 - start
endy = cols - 1 - start
for i in range(start, endy + 1):
result.append(matrix[start][i])
if start < endx:
for i in range(start + 1, endx + 1):
result.append(matrix[i][endy])
if start < endx and start < endy:
for i in range(endy - 1, start - 1, -1):
result.append(matrix[endx][i])
if start < endx - 1 and start < endy:
for i in range(endx - 1, start, -1):
result.append(matrix[i][start])
start += 1
return result
包含min函數(shù)的棧
題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)价说。
分析
得到最小元素的關(guān)鍵就是怎么去保存這個(gè)最小元素辆亏，這里在push的時(shí)候?qū)⒉迦氲闹底鳛殒I，當(dāng)前最小值作為值作為一個(gè)元素插入棧鳖目。就可以得到每個(gè)元素插入的時(shí)候最小值是什么
(當(dāng)然也可以使用單獨(dú)的字段保存最小值)
class Solution:
def __init__(self):
self.stack = []
def push(self, node):
"""
推入元素
使當(dāng)前元素的值作為鍵扮叨，當(dāng)前最小值作為值
:param node:
:return:
"""
curMin = self.min()
if curMin is None or node < curMin:
curMin = node
self.stack.append((node, curMin))
def pop(self):
self.stack.pop()
def top(self):
"""
彈出頂部元素的值
:return:
"""
if len(self.stack) == 0:
return None
else:
return self.stack[len(self.stack) - 1][0]
def min(self):
"""
得到最小棧中最小的元素
:return:
"""
if len(self.stack) == 0:
return None
else:
return self.stack[len(self.stack) - 1][1]
重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹领迈。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字彻磁。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回狸捅。
分析
在前序遍歷中找到跟節(jié)點(diǎn)衷蜓，根據(jù)中序遍歷中的跟節(jié)點(diǎn)的左右找到左右子樹的元素，進(jìn)行遞歸即可
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):
"""
根據(jù)前序和中序遍歷重建二叉樹
:param pre:
:param tin:
:return:
"""
if not pre and not tin:
return None
# 根據(jù)前序遍歷獲取到根節(jié)點(diǎn)
root = TreeNode(pre[0])
# 根據(jù)中序遍歷得到根節(jié)點(diǎn)的索引
i = tin.index(pre[0])
# 遞歸得到左子樹（前序遍歷的第１位到根節(jié)點(diǎn)索引＋１位薪贫，中序遍歷的第０位到根節(jié)點(diǎn)的索引位）
root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i])
# 遞歸得到左子樹（前序遍歷的第根節(jié)點(diǎn)＋１位到最后一位恍箭，中序遍歷的第根節(jié)點(diǎn)＋１到最后一位）
root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:])
return root
用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作瞧省。 隊(duì)列中的元素為int類型扯夭。
分析
在入隊(duì)的時(shí)候均使用棧1存儲(chǔ)鳍贾，出隊(duì)的時(shí)候先判斷棧2是否為空，如果為空交洗，將棧1的元素依次彈出到棧2骑科，然后彈出棧2的元素
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
# 直接向棧1壓入元素
self.stack1.append(node)
def pop(self):
# return xx
# 如果棧2位空的情況
if not self.stack2:
# 迭代棧1，將棧1的元素彈出并壓入棧2
while self.stack1:
self.stack2.append(self.stack1.pop())
# 此時(shí)彈出棧2的元素
return self.stack2.pop()
# 如果棧1不為空构拳，說明已經(jīng)將元素壓入棧2咆爽，直接彈出即可
return self.stack2.pop()
旋轉(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
分析
使用py的內(nèi)建函數(shù)直接求得最小值
class Solution:
def minNumberInRotateArray(self, rotateArray):
"""
旋轉(zhuǎn)數(shù)組的最小值
:param rotateArray:
:return:
"""
if not rotateArray:
return 0
return min(rotateArray)
棧的壓入漾稀、彈出序列
題目描述
輸入兩個(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è)序列的長(zhǎng)度是相等的）
分析
使用一個(gè)輔助棧來存儲(chǔ)晾咪，遍歷入棧順序依次添加到輔助棧收擦，判斷棧的長(zhǎng)度且棧頂是都等于彈出序列
class Solution:
def IsPopOrder(self, pushV, popV):
if not pushV:
return False
# 創(chuàng)建一個(gè)輔助棧
stack = []
for i in pushV:
# 將遍歷入棧順序贮配，添加到輔助棧中
stack.append(i)
# 如果棧不為空，且棧頂元素等于彈出序列
while len(stack) and stack[-1] == popV[0]:
# 出棧
stack.pop()
popV.pop(0)
# 如果輔助棧為空
if len(stack):
return False
return True
從上往下打印二叉樹
題目描述
從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)塞赂，同層節(jié)點(diǎn)從左至右打印泪勒。
分析
使用隊(duì)列去存儲(chǔ)中間值,使用while循環(huán)去遍歷即可
class Solution:
# 返回從上到下每個(gè)節(jié)點(diǎn)值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
result = []
# 如果根節(jié)點(diǎn)為空
if not root:
return result
# 將根節(jié)點(diǎn)放入列表中
q = [root]
# 當(dāng)ｑ列表不為空
while len(q):
# 將ｑ列表的第一個(gè)元素賦值給新節(jié)點(diǎn)
node = q.pop(0)
# 將節(jié)點(diǎn)的值添加到結(jié)果列表中
result.append(node.val)
# 如果節(jié)點(diǎn)有左子樹
if node.left:
# 將節(jié)點(diǎn)的左子樹放入ｑ列表
q.append(node.left)
if node.right:
# 將節(jié)點(diǎn)的右子樹放入ｑ列表
q.append(node.right)
return result
二叉搜索樹的后序遍歷序列
題目描述
輸入一個(gè)整數(shù)數(shù)組宴猾，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果圆存。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同仇哆。
分析
根據(jù)后序遍歷的特點(diǎn)沦辙，我們可以知道數(shù)組中的最后宇哥元素時(shí)根節(jié)點(diǎn)，有了根節(jié)點(diǎn)讹剔，我們可以找到列表中最后一個(gè)小于根節(jié)點(diǎn)的值的元素油讯。遍歷這個(gè)元素到數(shù)組的最后一個(gè)元素之間的元素(元素為根節(jié)點(diǎn)的右子樹)详民，右子樹的所有元素應(yīng)該大于根節(jié)點(diǎn)，如果有小于根節(jié)點(diǎn)的元素陌兑，返回false沈跨，接下來遞歸數(shù)組中的左右元素
class Solution:
def VerifySquenceOfBST(self, sequence):
length = len(sequence)
if length == 0:
return False
if length == 1:
return True
# 數(shù)組的最后元素是該樹的根節(jié)點(diǎn)
root = sequence[-1]
left = 0
# 找到最后一個(gè)小于根節(jié)點(diǎn)的元素
while sequence[left] < root:
left += 1
# 遍歷最后一個(gè)小于根節(jié)點(diǎn)的元素到根節(jié)點(diǎn)之前
for i in range(left, length - 1):
# 判斷是否大于根節(jié)點(diǎn)(右子樹元素)
if sequence[i] < root:
return False
# 遞歸左右子樹
return self.VerifySquenceOfBST(sequence[:left]) \
or self.VerifySquenceOfBST(sequence[left:length - 1])
二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑兔综。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑饿凛。
分析
首先對(duì)特殊邊界條件進(jìn)行判斷，然后分別遞歸左右子樹软驰，向下遞歸時(shí)需要使用目標(biāo)值減去根節(jié)點(diǎn)的值涧窒，最后將左右子樹的遞歸結(jié)果拼接為一個(gè)列表進(jìn)行遍歷，使用一個(gè)新列表去接受根節(jié)點(diǎn)加上遍歷的元素值
class Solution:
# 返回二維列表锭亏，內(nèi)部每個(gè)列表表示找到的路徑
def FindPath(self, root, expectNumber):
# 如果是個(gè)空樹
if not root:
return []
# 如果根節(jié)點(diǎn)不為空杀狡，并且根節(jié)點(diǎn)的值等于指定值而且左右子樹均為空
if root and not root.left and not root.right and root.val == expectNumber:
return [[root.val]]
res = []
# 遞歸左子樹
left = self.FindPath(root.left, expectNumber - root.val)
# 遞歸右子樹
right = self.FindPath(root.right, expectNumber - root.val)
# 遍歷拼接左右子樹的結(jié)果
for i in left + right:
# 將根節(jié)點(diǎn)的值+i添加到res數(shù)組上
res.append([root.val] + i)
return res
注：
- 上述測(cè)試在Python3.5中成功
- 上述文字皆為個(gè)人看法，如有錯(cuò)誤或建議請(qǐng)及時(shí)聯(lián)系我
