1. 二維數組中的查找
題目描述
在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
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. 替換空格
題目描述
請實現一個函數，將一個字符串中的每個空格替換成“%20”。例如，當字符串為We Are Happy.則經過替換之后的字符串為We%20Are%20Happy。
class Solution:
# s 源字符串
def replaceSpace(self, s):
return s.replace(" ", "%20")
3. 從頭到尾打印鏈表
題目描述
輸入一個鏈表，按鏈表值從尾到頭的順序返回一個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. 重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
思路：前序遍歷的第一個節點即為樹的root，然后在中序遍歷中找到這個節點，這個節點左邊的即為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:
# 返回構造的TreeNode根節點
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. 用兩個棧實現隊列
題目描述
用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為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. 旋轉數組的最小數字
題目描述
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。
思路：如果后一個數比前一個數小，則其為最小的數。
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. 斐波那契數列
題目描述
大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。
參考：斐波那契數列的5種python寫法
class Solution:
def Fibonacci(self, n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a
8. 跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。
思路：Fibonacci的應用
class Solution:
def jumpFloor(self, number):
a, b = 0, 1
for i in range(number+1):
a, b = b, a+b
return a
9. 變態跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
思路：算出通項公式。f(n) = 2f(n - 1)
class Solution:
def jumpFloorII(self, number):
return 2**(number - 1)
10. 矩形覆蓋
題目描述
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個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. 二進制中1的個數
題目描述
輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。
思路：python的負數的補碼表示方法。
參考：Python小技巧：負數的補碼表示
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. 數值的整數次方
題目描述
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。
class Solution:
def Power(self, base, exponent):
return base ** exponent
13. 調整數組順序使奇數位于偶數前面
題目描述
輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。
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. 鏈表中倒數第k個節點
題目描述
輸入一個鏈表，輸出該鏈表中倒數第k個結點。
思路：兩個指針，一個先走k步，當第一個指針到最后了，第二個指針即為倒數第k個節點。
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. 反轉鏈表
題目描述
輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。
參考 https://www.javazhiyin.com/32787.html
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. 合并兩個排序的鏈表
題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。
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. 樹的子結構
題目描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
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:
# 返回鏡像樹的根節點
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. 順時針打印矩陣
題目描述
輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數字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函數的棧
題目描述
定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為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. 棧的壓入、彈出序列
題目描述
輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
構造一個輔助棧來判斷彈出序列是不是和壓棧序列對應。首先遍歷壓棧序列的元素push到輔助棧，判斷是不是彈出序列的首元素，如果是，則彈出序列pop首元素（指針后移），如果不是，則繼續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. 從上往下打印二叉樹
題目描述
從上往下打印出二叉樹的每個節點，同層節點從左至右打印。
class Solution:
# 返回從上到下每個節點值列表，例：[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. 二叉搜索樹的后序遍歷序列
題目描述
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
二叉搜索樹是對一個有序數組進行二分查找形成的搜索樹，它指一棵空樹或者具有下列性質的二叉樹：
- 若任意節點的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
- 若任意節點的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；
- 任意節點的左、右子樹也分別為二叉查找樹；'
特點：左子樹結點的值都小于根節點的值，右子樹結點的值都大于根節點的值
后序遍歷：先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根節點
后序遍歷得到的序列，最后一個數是樹的根節點的值 ，序列中最后一個數前面的數可以分為兩部分：一部分是左子樹節點的值，它們都比根節點的值??；第二部分是右子樹節點的值，它們都比根節點的值要大。
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. 二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹的根節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前)
思路：
- 如果只有根節點或者找到葉子節點，我們就把其對應的val值返回
- 如果不是葉子節點，我們分別對根節點的左子樹、右子樹進行遞歸，直到找到葉子結點。然后遍歷把葉子結點和父節點對應的val組成的序列返回上一層；如果沒找到路徑，其實也返回了序列，只不過是[]
class Solution:
# 返回二維列表，內部每個列表表示找到的路徑
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. 復雜鏈表的復制
題目描述
輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的head。（注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）
思路：第一步在原鏈表的基礎上復制節點，將節點復制在原節點的后面。第二步復制隨機節點。 第三步將新舊鏈表分離。
三步
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. 二叉搜索樹與雙向鏈表
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。
思路：核心算法依舊是中序遍歷；不是從根節點開始，而是從中序遍歷得到的第一個節點開始；定義兩個輔助節點listHead(鏈表頭節點)、listTail(鏈表尾節點)。事實上，二叉樹只是換了種形式的鏈表；listHead用于記錄鏈表的頭節點，用于最后算法的返回；listTail用于定位當前需要更改指向的節點。
參考：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. 字符串的排列
題目描述
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。
思路：化繁為簡，像青蛙跳臺階的思想那樣，無論輸入的字符串有多長，其排列出來的組合式樣式均可分為“第一個字符串+剩下的字符串”的樣式，可以通過遍歷賦予第一位上不同的字符。那剩下的字符串又可以如上分解。
注意：ss的索引字符串會超出范圍，不過python在對字符串做切片操作時，當索引位置超出長度，python不會報錯只會跳出本次循環。當然我們還要考慮字符串中是否包含重復元素，因為在輸入中有重復值時就會生產相同的字符串，因此在代碼中加一個判斷即可。
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. 數組中出現次數超過一半的數字
題目描述
數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出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個數
題目描述
輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
return sorted(tinput)[:k] if len(tinput) >= k else []
30. 連續子數組的最大和
題目描述
HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會后，他又發話了：在古老的一維模式識別中，常常需要計算連續子向量的最大和，當向量全為正數的時候，問題很好解決。但是，如果向量中包含負數，是否應該包含某個負數，并期望旁邊的正數會彌補它呢？例如：{6,-3,-2,7,-15,1,2,2}，連續子向量的最大和為8(從第0個開始，到第3個為止)。給一個數組，返回它的最大連續子序列的和，你會不會被他忽悠??？(子向量的長度至少是1)
有個最優子結構性質：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. 整數中1出現的次數（從1到n整數中1出現的次數）
題目描述
求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。
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. 把數組排成最小的數
題目描述
輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為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. 丑數
題目描述
把只包含質因子2、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個丑數。求按從小到大的順序的第N個丑數。
參考：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. 第一個只出現一次的字符
題目描述
在一個字符串(0<=字符串長度<=10000，全部由字母組成)中找到第一個只出現一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區分大小寫）.
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. 數組中的逆序對
題目描述
在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數組中沒有的相同的數字
數據范圍：
對于%50的數據,size<=10^4
對于%75的數據,size<=10^5
對于%100的數據,size<=2*10^5
示例1
輸入：1,2,3,4,5,6,7,0
輸出：7
超過運行時間限制。
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. 兩個鏈表的第一個公共結點
題目描述
輸入兩個鏈表，找出它們的第一個公共結點。
思路：
- 如果兩個鏈表長度一樣，則正常遍歷，找到相同的或者不存在。
- 如果兩個鏈表長度不同，則首先短的遍歷結束后會從另一個鏈表開頭開始遍歷，而當另一個節點遍歷結束后從另一個鏈表頭開始遍歷時，這兩個鏈表的差則會消除。
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. 數字在排序數組中出現的次數
題目描述
統計一個數字在排序數組中出現的次數。
class Solution:
def GetNumberOfK(self, data, k):
return data.count(k)
38. 二叉樹的深度
題目描述
輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
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. 數組中只出現一次的數字
題目描述
一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。
class Solution:
# 返回[a,b] 其中ab是出現一次的兩個數字
def FindNumsAppearOnce(self, array):
result = []
for each in array:
if array.count(each) == 1:
result.append(each)
return result
41. 和為s的連續正數序列
題目描述
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列：18,19,20,21,22?，F在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!
輸出描述
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序
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的兩個數字
題目描述
輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，使得他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的。
輸出描述
對應每個測試案例，輸出兩個數，小的先輸出。
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. 左旋轉字符串
題目描述
匯編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字符串模擬這個指令的運算結果。對于一個給定的字符序列S，請你把其循環左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環左移3位后的結果，即“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. 翻轉單詞順序列
題目描述
?？妥罱鼇砹艘粋€新員工Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。同事Cat對Fish寫的內容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來才意識到，這家伙原來把句子單詞的順序翻轉了，正確的句子應該是“I am a student.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他么？
class Solution:
def ReverseSentence(self, s):
s_list = s.split(' ')
return ' '.join(str(i) for i in s_list[::-1])
45. 撲克牌順子
題目描述
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的運氣如何， 如果牌能組成順子就輸出true，否則就輸出false。為了方便起見,你可以認為大小王是0。
得到hash表后只需計算最大的鍵值和最小的鍵值的差，若小于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. 孩子們的游戲（圓圈中最后剩下的數）
題目描述
每年六一兒童節,?？投紩蕚湟恍┬《Y物去看望孤兒院的小朋友,今年亦是如此。HF作為?？偷馁Y深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!! _ )。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)
約瑟夫環問題
參考：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等關鍵字及條件判斷語句（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. 不用加減乘除做加法
題目描述
寫一個函數，求兩個整數之和，要求在函數體內不得使用+、-、*、/四則運算符號。
參考：https://www.acwing.com/activity/content/code/content/21074/
class Solution:
def Add(self, num1, num2):
while True:
# 不進位加法
s = num1 ^ num2
# 計算進位
carry = num1 & num2
# 手動把高于 32 位的部分變成 0
num1 = s & 0xFFFFFFFF
num2 = carry << 1
if carry == 0:
break
# 如果是正數和 0 ，就直接返回這個正數
if num1 >> 31 == 0:
return num1
# 如果是負數
return num1 - (1 << 32)
49. 把字符串轉換成整數
題目描述
將一個字符串轉換成一個整數(實現Integer.valueOf(string)的功能，但是string不符合數字要求時返回0)，要求不能使用字符串轉換整數的庫函數。 數值為0或者字符串不是一個合法的數值則返回0。
輸入描述:
輸入一個字符串,包括數字字母符號,可以為空
輸出描述:
如果是合法的數值表達則返回該數字，否則返回0
示例1
輸入
+2147483647
1a33
輸出
2147483647
0
50. 數組中重復的數字
題目描述
在一個長度為n的數組里的所有數字都在0到n-1的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字2。
class Solution:
# 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]
# 函數返回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. 構建乘機數組
題目描述
給定一個數組A[0,1,...,n-1],請構建一個數組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. 正則表達式匹配
題目描述
請實現一個函數用來匹配包括'.'和'*'的正則表達式。模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"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. 表示數值的字符串
題目描述
請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
54. 字符流中第一個不重復的字符
題目描述
請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"。當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"。
輸出描述:
如果當前字符流沒有存在出現一次的字符，返回#字符。
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. 鏈表中環的入口結點
題目描述
給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null。
56. 刪除鏈表中重復的結點
題目描述
在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
57. 二叉樹的下一個結點
題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
分三種情況：
- 給定的節點為空——返回空；
- 給定的節點有右子樹——沿著該右子樹，返回右子樹的第一個左葉子節點；
- 給定的節點沒有右子樹——如果位于某個節點的左子樹中，則上溯直至找到該節點；否則就返回空。
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. 對稱的二叉樹
題目描述
請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
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. 按之字形順序打印二叉樹
題目描述
請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。
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. 把二叉樹打印成多行
題目描述
從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。
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. 序列化二叉樹
題目描述
請實現兩個函數，分別用來序列化和反序列化二叉樹
序列化是將數據結構或對象轉換為一系列位的過程，以便它可以存儲在文件或內存緩沖區中，或通過網絡連接鏈路傳輸，以便稍后在同一個或另一個計算機環境中重建。
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個結點
題目描述
給定一棵二叉搜索樹，請找出其中的第k小的結點。例如， （5，3，7，2，4，6，8）中，按結點數值大小順序第三小結點的值為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. 數據流中的中位數
題目描述
如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。我們使用Insert()方法讀取數據流，使用GetMedian()方法獲取當前讀取數據的中位數。
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. 滑動窗口的最大值
題目描述
給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{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]}。
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. 矩陣中的路徑
題目描述
請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則之后不能再次進入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。
回溯法
參考：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
<= 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. 機器人的運動范圍
題目描述
地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
回溯法
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
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
