1. 二維數(shù)組中的查找
題目描述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同）导街，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序纤子。請(qǐng)完成一個(gè)函數(shù)搬瑰，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)控硼。
代碼
# -*- coding:utf-8 -*-
class Solution:
# array 二維列表
def Find(self, target, array):
# write code here
rows = len(array) - 1
cols = len(array[0]) - 1
i = rows
j = 0
while i >= 0 and j <= cols:
if target < array[i][j]:
i -= 1
elif target > array[i][j]:
j += 1
else:
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翼悴。
代碼
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
r = ''
for i in range(len(s)):
if s[i] == ' ':
r = r + '%20'
else:
r = r + s[i]
return r
思路
3. 從尾到頭打印鏈表
題目描述
輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè)ArrayList幔妨。
代碼
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回從尾部到頭部的列表值序列抄瓦，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
l = []
head = listNode
while head:
l.insert(0, head.val)
head = head.next
return l
思路
4. 重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果潮瓶，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字钙姊。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}毯辅，則重建二叉樹并返回。
代碼
# -*- coding:utf-8 -*-
# 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):
# write code here
# 基于前序遍歷序列煞额，查詢中序遍歷序列完成構(gòu)建
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
else:
flag = TreeNode(pre[0])
flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:] )
return flag
思路
5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列思恐，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型膊毁。
代碼
# -*- 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 self.stack2==[]:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.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力图。
代碼
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
pre = 0
for num in rotateArray:
if num < pre :
return num
pre = num
return rotateArray[0]
思路
7. 斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列步绸，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始吃媒，第0項(xiàng)為0）瓤介。
n<=39
代碼
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
s = []
s.append(1)
s.append(1)
for i in range(2, n):
s.append(s[i-1] + s[i-2])
return s[n-1]
思路
8. 跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)赘那。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）刑桑。
代碼
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
s = []
s.append(1)
s.append(1)
for i in range(2, number+1):
s.append(s[i-1] + s[i-2])
return s[number]
思路
9. 變態(tài)跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)募舟。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法漾月。
代碼
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
s = []
s.append(1)
s.append(1)
for i in range(2, number + 1):
s_temp = 0
for j in range(i):
s_temp += s[j]
s.append(s_temp)
return s[number]
思路
10. 矩形覆蓋
題目描述
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)2*1的小矩形無重疊地覆蓋一個(gè)2*n的大矩形胃珍，總共有多少種方法梁肿？
代碼
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
s = []
s.append(1)
s.append(1)
for i in range(2, number+1):
s.append(s[i-1] + s[i-2])
return s[number]
思路
11. 二進(jìn)制中1的個(gè)數(shù)
題目描述
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)觅彰。其中負(fù)數(shù)用補(bǔ)碼表示吩蔑。
代碼
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
return sum([(n >> i & 1) for i in range(32)])
思路
12. 數(shù)值的整數(shù)次方
題目描述
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方填抬。
代碼
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
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ì)位置不變。
代碼
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
odd = []
even = []
for item in array:
if item % 2 == 1:
odd.append(item)
else:
even.append(item)
return odd + even
思路
14. 鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
題目描述
輸入一個(gè)鏈表遣臼，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)性置。
代碼
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
l = []
while head != None:
l.append(head)
head = head.next
if k > len(l) or k < 1:
return
else:
return l[-k]
思路
15. 反轉(zhuǎn)鏈表
題目描述
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后揍堰，輸出新鏈表的表頭鹏浅。
代碼
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
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ī)則隐砸。
代碼
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
mergeHead = ListNode(0)
p = mergeHead
while pHead1 and pHead2:
if pHead1.val < pHead2.val:
mergeHead.next = pHead1
pHead1 = pHead1.next
else:
mergeHead.next = pHead2
pHead2 = pHead2.next
mergeHead = mergeHead.next
if pHead1:
mergeHead.next = pHead1
else:
mergeHead.next = pHead2
return p.next
思路
17. 樹的子結(jié)構(gòu)
題目描述
輸入兩棵二叉樹A，B蝙眶，判斷B是不是A的子結(jié)構(gòu)季希。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
代碼
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
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):
if not B:
return True
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)
思路
18. 二叉樹的鏡像
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像幽纷。
輸入描述
二叉樹的鏡像定義：源二叉樹
8
/ \
6 10
/ \ / \
5 7 9 11
鏡像二叉樹
8
/ \
10 6
/ \ / \
11 9 7 5
代碼
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回鏡像樹的根節(jié)點(diǎn)
def Mirror(self, root):
# write code here
if root != None:
root.left,root.right = root.right,root.left
self.Mirror(root.left)
self.Mirror(root.right)
思路
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.
代碼
# -*- coding:utf-8 -*-
class Solution:
# matrix類型為二維列表珊搀，需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
while matrix:
res += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop())
if matrix:
res += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
res.append(row.pop(0))
return res
思路
20. 包含min函數(shù)的棧
題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)冶忱，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））尾菇。
代碼
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, node):
# write code here
self.stack.append(node)
min = self.min()
if not min or node < min:
self.min_stack.append(node)
else:
self.min_stack.append(min)
def pop(self):
# write code here
if self.stack:
self.min_stack.pop()
return self.stack.pop()
def top(self):
# write code here
if self.stack:
return self.stack[-1]
def min(self):
# write code here
if self.min_stack:
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è)序列的長度是相等的）
代碼
# -*- 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(-1)
popV.pop(0)
elif pushV:
stack.append(pushV.pop(0))
else:
return False
return True
思路
22. 從上往下打印二叉樹
題目描述
從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)缆八，同層節(jié)點(diǎn)從左至右打印。
代碼
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回從上到下每個(gè)節(jié)點(diǎn)值列表疾捍，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
l=[]
if not root:
return []
q=[root]
while len(q):
t=q.pop(0)
l.append(t.val)
if t.left:
q.append(t.left)
if t.right:
q.append(t.right)
return l
思路
23. 二叉搜索樹的后序遍歷序列
題目描述
輸入一個(gè)整數(shù)數(shù)組奈辰，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No乱豆。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同奖恰。
代碼
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
k = len(sequence)
if k == 0:
return False
if k == 1:
return True
i = 0
while sequence[-1] > sequence[i]:
i += 1
if i < k-1 and sequence[-1] > min(sequence[i:k-1]):
return False
l_s = sequence[:i]
r_s = sequence[i:k-1]
return (self.VerifySquenceOfBST(l_s) or len(l_s)==0) \
and (self.VerifySquenceOfBST(r_s) or len(r_s)==0)
思路
24. 二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑瑟啃。(注意: 在返回值的list中论泛，數(shù)組長度大的數(shù)組靠前)
代碼
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二維列表，內(nèi)部每個(gè)列表表示找到的路徑
def FindPath(self, root, expectNumber):
# write code here
if not root:
return []
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)
for i in left+right:
res.append([root.val] + i)
return res
思路
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ì)直接返回空）
代碼
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return None
head = RandomListNode(pHead.label)
head.random = pHead.random
head.next = self.Clone(pHead.next)
return head
思路
26. 二叉搜索樹與雙向鏈表
題目描述
輸入一棵二叉搜索樹载绿，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)油航，只能調(diào)整樹中結(jié)點(diǎn)指針的指向崭庸。
代碼
非遞歸版本：
- 二叉樹的中序遍歷
- 中序遍歷中每個(gè)結(jié)點(diǎn)的鏈接
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return None
p = pRootOfTree
stack = []
resStack = []
while p or stack:
if p:
stack.append(p)
p = p.left
else:
node = stack.pop()
resStack.append(node)
p = node.right
resP = resStack[0]
while resStack:
top = resStack.pop(0)
if resStack:
top.right = resStack[0]
resStack[0].left = top
return resP
遞歸版本
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return None
if not pRootOfTree.left and not pRootOfTree.right:
return pRootOfTree
# 將左子樹構(gòu)建成雙鏈表，返回鏈表頭
left = self.Convert(pRootOfTree.left)
p = left
# 定位至左子樹的最右的一個(gè)結(jié)點(diǎn)
while left and p.right:
p = p.right
# 如果左子樹不為空谊囚，將當(dāng)前root加到左子樹鏈表
if left:
p.right = pRootOfTree
pRootOfTree.left = p
# 將右子樹構(gòu)造成雙鏈表怕享，返回鏈表頭
right = self.Convert(pRootOfTree.right)
# 如果右子樹不為空，將該鏈表追加到root結(jié)點(diǎn)之后
if right:
right.left = pRootOfTree
pRootOfTree.right = right
return left if left else pRootOfTree
思路
持續(xù)更新中...
