劍指offer 手刷python 彙總整理版本~
0.遞迴&腦力
斐波那契數列
# -*- 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級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
dp[n]=dp[n−1]+dp[n−2]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]123456789101112131415
變態跳臺階
一隻青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
思考：在dp[n] = dp[n-1] + dp[n-2] + … + dp[1] + 1(直接跳n)步驟
即dp[n]=∑n−1i=1dp[i]+1dp[n]=∑i=1n−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 12345678910
矩形覆蓋
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2n的大矩形，總共有多少種方法？
思考： 21 1 種； 22 2種 23 3種 2*4 5種
dp[n]=dp[n−1]+dp[n−2]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]
數值的n次方
思考：，用二分
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
if exponent ==0:
return 1
if exponent ==1:
return base
ans,pos=1,1
if exponent <0:
pos=-1
exponent = - exponent
if exponent %2 ==0: # 偶數
ans = self.Power(base,exponent//2)*self.Power(base,exponent//2)
else: # 奇數
ans = base * self.Power(base,exponent//2)*self.Power(base,exponent//2)
return ans if pos==1 else 1.0/ans
二分法和牛頓迭代法求平方根
##二分法
import math
from math import sqrt
def sqrt_binary(num):
x=sqrt(num)
y=num/2.0
low=0.0
up=num*1.0
count=1
while abs(y-x)>0.00000001:
print count,y
count+=1
if (y*y>num):
up=y
y=low+(y-low)/2
else:
low=y
y=up-(up-y)/2
return y
print(sqrt_binary(5))
## 牛頓法 二次方
## https://zhuanlan.zhihu.com/p/111598542
def sqrt_newton(num):
x=sqrt(num)
y=num/2.0
count=1
while abs(y-x)>0.00000001:
print count,y
count+=1
y=((y*1.0)+(1.0*num)/y)/2.0000
return y
print(sqrt_newton(5))
print(sqrt(5))
### 牛頓法 三次方
def cube_newton(num):
x=num/3.0
y=0
count=1
while abs(x-y)>0.00000001:
print count,x
count+=1
y=x
x=(2.0/3.0)*x+(num*1.0)/(x*x*3.0)
return x
print(cube_newton(27))
醜數
只包含因子2、3和5的數稱作醜數（Ugly Number），求按從小到大的順序的第N個醜數。因為醜數只包含質因子2，3，5，假設我們已經有n-1個醜數，按照順序排列，且第n-1的醜數為M。那麼第n個醜數一定是由這n-1個醜數分別乘以2，3，5，得到的所有大於M的結果中，最小的那個數。
事實上我們不需要每次都計算前面所有醜數乘以2，3，5的結果，然後再比較大小。因為在已存在的醜數中，一定存在某個數T2T2，在它之前的所有數乘以2都小於已有醜數，而T2×2T2×2的結果一定大於M，同理，也存在這樣的數T3，T5T3，T5，我們只需要標記這三個數即可。
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index == 0:
return 0
# 1作為特殊數直接儲存
baselist = [1]
min2 = min3 = min5 = 0
curnum = 1
while curnum < index:
minnum = min(baselist[min2] * 2, baselist[min3] * 3, baselist[min5] * 5)
baselist.append(minnum)
# 找到第一個乘以2的結果大於當前最大丑數M的數位，也就是T2
while baselist[min2] * 2 <= minnum:
min2 += 1
# 找到第一個乘以3的結果大於當前最大丑數M的數位，也就是T3
while baselist[min3] * 3 <= minnum:
min3 += 1
# 找到第一個乘以5的結果大於當前最大丑數M的數位，也就是T5
while baselist[min5] * 5 <= minnum:
min5 += 1
curnum += 1
return baselist[-1]
正規表示式匹配
請實現一個函數用來匹配包括’.‘和’*‘的正規表示式。模式中的字元’.‘表示任意一個字元，而’*'表示它前面的字元可以出現任意次（包含0次）。 在本題中，匹配是指字串的所有字元匹配整個模式。例如，字串」aaa」與模式」a.a」和」abaca」匹配，但是與」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.陣列
調整陣列順序使奇數位於偶數前面
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
def isOdd(a):
return (a & 1) == 1
answer = [i for i in array if isOdd(i)]
answer.extend([i for i in array if not isOdd(i)])
return answer
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
return sorted(array, key = lambda x: x % 2 == 0)
二分查詢（九章演演算法)
題目：給定一個排好序的證書陣列nums，和一個整數target，尋找target在nums中任何一個/第一次出現/最後一次出現的位置，不存在return-1。
思路：基本上看到時間複雜度要求O（logN）基本就是要用二分法，二分法的本質是保留有解的一半。
3.通用的二分法模板(四個要素)
①start+1<end
②start+(end-start)/2
③A[mid]==,<,>
④A[start] A[end] ? target
class Solution:
# @param nums: The integer array
# @param target: Target number to find
# @return the first position of target in nums, position start from 0
def binarySearch(self, nums, target):
if not nums:
return -1
start, end = 0, len(nums) - 1
# 用 start + 1 < end 而不是 start < end 的目的是為了避免死迴圈
# 在 first position of target 的情況下不會出現死迴圈
# 但是在 last position of target 的情況下會出現死迴圈
# 樣例：nums=[1，1] target = 1
# 為了統一模板，我們就都採用 start + 1 < end，就保證不會出現死迴圈
while start + 1 < end:
# python 沒有 overflow 的問題，直接 // 2 就可以了
# java和C++ 最好寫成 mid = start + (end - start) / 2
# 防止在 start = 2^31 - 1, end = 2^31 - 1 的情況下出現加法 overflow
mid = (start + end) // 2
# > , =, < 的邏輯先分開寫，然後在看看 = 的情況是否能合併到其他分支裡
if nums[mid] < target:
# 寫作 start = mid + 1 也是正確的
# 只是可以偷懶不寫，因為不寫也沒問題，不會影響時間複雜度
# 不寫的好處是，萬一你不小心寫成了 mid - 1 你就錯了
start = mid
elif nums[mid] == target:
end = mid
else:
# 寫作 end = mid - 1 也是正確的
# 只是可以偷懶不寫，因為不寫也沒問題，不會影響時間複雜度
# 不寫的好處是，萬一你不小心寫成了 mid + 1 你就錯了
end = mid
# 因為上面的迴圈退出條件是 start + 1 < end
# 因此這裡迴圈結束的時候，start 和 end 的關係是相鄰關係（1和2，3和4這種）
# 因此需要再單獨判斷 start 和 end 這兩個數誰是我們要的答案
# 如果是找 first position of target 就先看 start，否則就先看 end
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
class Solution:
"""
@param nums: the array of integers
@param target:
@return: the starting and ending position
"""
def searchRange(self, nums, target):
# Write your code here.
if not nums:
return [-1, -1]
first_index = self.binarySearch(nums, target, True)
if first_index == -1:
return [-1, -1]
last_index = self.binarySearch(nums, target, False)
return [first_index, last_index]
def binarySearch(self, nums, target, isFindFirst):
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if target > nums[mid]:
start = mid
elif target < nums[mid]:
end = mid
else:
if isFindFirst:
end = mid
else:
start = mid
if isFindFirst:
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
else:
if nums[end] == target:
return end
if nums[start] == target:
return start
return -1
旋轉陣列的最小數位
思考：二分判斷
# -*- 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]
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, nums):
# write code here
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] > nums[end]:
start = mid
else:
end = mid
return min(nums[start], nums[end])
和為S的連續正數序列
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數位從小到大的順序
思考：
解法：1.窮舉法，2.滑動視窗法
，3.數位規律法(往下看)
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
數位在排序陣列中出現的次數
數位在排序陣列中出現的次數
思考：原來是可以用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
陣列中只出現一次的數位
一個整型陣列裡除了兩個數位之外，其他的數位都出現了兩次。請寫程式找出這兩個只出現一次的數位
思考：用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
和為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
第一個只出現一次的字元
思考：用dict 最多256個來空間換時間
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if s=='':
return -1
ret = [0,-1]
chars = {}
for i,c in enumerate(s):
if c in chars:
chars[c][0] = chars[c][0] +1
else:
chars[c] =[1,i]
for k,v in chars.items():
if v[0] ==1:
if ret[1] ==-1:
ret = v
elif v[1] <= ret[1]:
ret = v
return ret[1]
陣列中的逆序對
在陣列中的兩個數位，如果前面一個數位大於後面的數位，則這兩個數位組成一個逆序對。輸入一個陣列,求出這個陣列中的逆序對的總數P。並將P對1000000007取模的結果輸出。 即輸出P%1000000007
方法1：思考：這邊的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
方法2：歸併排序的思路
連續子陣列的最大和
可以用動態規劃的思想來分析這個問題。如果用函數f(i)表示以第i個數位結尾的子陣列的最大和，那麼我們需要求出max[f(i)]，其中0 <= i < n。我們可用如下邊歸公式求f(i):
這個公式的意義：當以第i-1 個數位結尾的子陣列中所有數位的和小於0時，如果把這個負數與第i個數累加，得到的結果比第i個數位本身還要小，所以這種情況下以第i個數位結尾的子陣列就是第i個數位本身。如果以第i-1 個數位結尾的子陣列中所有數位的和大於0 ,與第i 個數位累加就得到以第i個數位結尾的子陣列中所有數位的和。
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
最小的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
陣列中出現次數超過一半的數位
思考：摩爾投票法
# -*- 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
把陣列排成最小的數
輸入一個正整數陣列，把陣列裡所有數位拼接起來排成一個數，列印能拼接出的所有數位中最小的一個。例如輸入陣列{3，32，321}，則列印出這三個數位能排成的最小數位為321323。
str 化
連結：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)
陣列中重複的數位
在一個長度為n的陣列裡的所有數位都在0到n-1的範圍內。 陣列中某些數位是重複的，但不知道有幾個數位是重複的。也不知道每個數位重複幾次。請找出陣列中第一個重複的數位。 例如，如果輸入長度為7的陣列{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數位2。
返回描述：
如果陣列中有重複的數位，函數返回true，否則返回false。
如果陣列中有重複的數位，把重複的數位放到引數duplication[0]中。（ps:duplication已經初始化，可以直接賦值使用。）
# -*- 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
構造乘積陣列
B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]
思考：分為下三角和上三角DP計算B
下三角
上三角（從最後往前）
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
二維陣列中的查詢
在一個二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數。
思考：從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
撲克牌順子
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
孩子們的遊戲
每年六一兒童節,我都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小遊戲。其中,有個遊戲是這樣的:首先,讓小朋友們圍成一個大圈。然後,他隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然後可以在禮品箱中任意的挑選禮物,並且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數…這樣下去…直到剩下最後一個小朋友,可以不用表演,並且拿到牛客名貴的「名偵探柯南」典藏版(名額有限哦!!_)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)
如果沒有小朋友，請返回-1
為了討論方便，先把問題稍微改變一下，並不影響原意：
我們知道第一個人（編號一定是（m-1）) 出列之後，剩下的n-1個人組成了一個新的約瑟夫環（以編號為k=m mod n的人開始）：
k, k+1, k+2, … n-2,n-1,0,1,2,… k-2
並且從k開始報0。
我們把他們的編號做一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
變換後就完完全全成為了（n-1）個人報數的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那麼根據上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x’=(x+k) mod n
如何知道（n-1）個人報數的問題的解？對，只要知道（n-2）個人的解就行了。（n-2）個人的解呢？當然是先求（n-3）的情況 —- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩遊戲報m退出最後勝利者的編號，最後的結果自然是f[n]
遞推公式
讓f[i]為i個人玩遊戲報m退出最後的勝利者的編號，最後的結果自然是f[n]
f[1] = 0;
f[i] = (f[i - 1] + m) mod i;
有了這個公式，我們要做的就是從1-n順序算出f的數值，最後結果是f[n]。
# 正經思路
# -*- 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
# 數學思路
class Solution{
def LastRemaining_Solution(self,n,m):
if n <1 : return -1
ans=0;
for i in range(1,n+1):
ans = (ans + m) %i
return ans
}
#include<cstdio>
int main(){
int n,m;
while(scanf("%d %d",&n,&m)==2&&n&&m){
int ans = 0;
for(int i = 1;i <= n;++i){
ans = (ans + m) % i;
}
printf("總人數:%d 每次出列的人喊的號數:%d 最後一個出列的人的序號:%d\n",n,m,ans+1);
}
return 0;
}
2.位運算
二進位制中1的個數
思考：python沒有無符號移動，需要處理下；python的int是不會溢位的，達到界限後會自己轉為long，所以很麻煩。
# -*- 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+…+n
思考：遞迴 or 公式法
# -*- coding:utf-8 -*-
class Solution:
# def Sum_Solution(self, n):
# # write code here
# if n ==1:
# return n
# else:
# return n+self.Sum_Solution(n-1)
def Sum_Solution(self, n):
# write code here
if n == 1:
return n
return n*(n+1)/2
不用加減乘除做加法
思考：不計進位的和為 a^b，進位就是 a&b；python是用的二補數來存的，不過python二補數有一些問題；
python會講二補數存成正數 需要 -1 & num
https://blog.csdn.net/qq_16949707/article/details/106399430
a+b = a^b + (a&b)<<1;
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
xorNum = num1 ^ num2
andNum = num1 & num2 << 1
while andNum:
tmp1 = xorNum ^ andNum
tmp2 = (xorNum & andNum) << 1
tmp1 = tmp1 & 0xFFFFFFFF
xorNum = tmp1
andNum = tmp2
return xorNum if xorNum <= 0x7FFFFFFF else ~(-1 & xorNum ^ 0xffffffff)
從1到n整數中1出現的次數
思考：可以從n的每個位上入手，pos來記錄位，ans來記錄當前1的個數，last來記錄前面的數（這樣講好複雜，舉個例子好了）
xxxxYzzzz （假設9位）
在Y上1的個數由xxxx,zzzz和Y來決定
首先至少有xxxx0000個
其次看Y
如果Y大於1那麼會多了10000個
如果Y等於1那麼會多了（zzzz+1）個
設N = abcde ,其中abcde分別為十進位制中各位上的數位。
如果要計算百位上1出現的次數，它要受到3方面的影響：百位上的數位，百位以下（低位）的數位，百位以上（高位）的數位。
① 如果百位上數位為0，百位上可能出現1的次數由更高位決定。比如：12013，則可以知道百位出現1的情況可能是：100 ~ 199，1100 ~ 1199,2100 ~ 2199，，…，11100 ~ 11199，一共1200個。可以看出是由更高位數位（12）決定，並且等於更高位數位（12）乘以 當前位數（100）。
② 如果百位上數位為1，百位上可能出現1的次數不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現的情況是：100 ~ 199，1100 ~ 1199,2100 ~ 2199，，…，11100 ~ 11199，一共1200個。和上面情況一樣，並且等於更高位數位（12）乘以 當前位數（100）。但同時它還受低位影響，百位出現1的情況是：12100~12113,一共114個，等於低位數位（113）+1。
③ 如果百位上數位大於1（2~9），則百位上出現1的情況僅由更高位決定，比如12213，則百位出現1的情況是：100 ~ 199,1100 ~ 1199，2100 ~ 2199，…，11100 ~ 11199,12100 ~ 12199,一共有1300個，並且等於更高位數位+1（12+1）乘以當前位數（100）。
——參考牛客網@藍裙子的百合魂
# -*- 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 # pos來記錄位，ans來記錄當前1的個數，last來記錄前面的數(右邊的數)
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
3.字串
翻轉單詞順序列
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
ret = s.split(" ")
ret.reverse()
return ' '.join(ret)
左旋轉字串
對於一個給定的字元序列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]
把字串轉換成整數
將一個字串轉換成一個整數，要求不能使用字串轉換整數的庫函數。 數值為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
判斷一個字串是否表示數值
請實現一個函數用來判斷字串是否表示數值（包括整數和小數）。例如，字串"+100",「5e2」,"-123",「3.1416"和」-1E-16"都表示數值。 但是"12e",「1a3.14」,「1.2.3」,"±5"和"12e+4.3"都不是。
# -*- 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
字串的排列
思考：dfs
輸入一個字串,按字典序列印出該字串中字元的所有排列。例如輸入字串abc,則按字典序列印出由字元a,b,c所能排列出來的所有字串abc,acb,bac,bca,cab和cba。
#https://www.jiuzhang.com/problem/permutations/#tag-lang-python
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
if not nums:
return [[]]
permutations = []
self.dfs(nums, [], set(), permutations)
return permutations
def dfs(self, nums, permutation, visited, permutations):
if len(nums) == len(permutation):
permutations.append(list(permutation))
return
for num in nums:
if num in visited:
continue
permutation.append(num)
visited.add(num)
self.dfs(nums, permutation, visited, permutations)
visited.remove(num)
permutation.pop()
# subsets
# https://www.jiuzhang.com/problem/subsets/#tag-lang-python
class Solution:
"""
@param nums: A set of numbers
@return: A list of lists
"""
def subsets(self, nums):
res = []
# 排序
nums.sort()
# dfs搜尋
self.dfs(nums, 0, [], res)
return res
def dfs(self, nums, k, subset, res):
# 當前組合存入res
res.append(subset[:])
# 為subset新增一位元素
for i in range(k, len(nums)):
subset.append(nums[i])
# 下一層搜尋
self.dfs(nums, i + 1, subset, res)
# 回溯
del subset[-1]
替換空格
# -*- coding:utf-8 -*-
import re
class Solution:
# s 源字串
def replaceSpace(self, s):
# write code here
return re.sub(" ","%20",s)
字元流中第一個不重複的字元
思考：用個佇列和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)
4.連結串列
連結串列中環的入口結點
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
而尋找環的入口，假設入口結點距離頭結點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
翻轉連結串列
https://blog.csdn.net/songyunli1111/article/details/79416684
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
if not pHead or not pHead.next:
return pHead
last = None #指向上一個節點
while pHead:
#先用tmp儲存pHead的下一個節點的資訊，
#保證單連結串列不會因為失去pHead節點的next而就此斷裂
tmp = pHead.next
#儲存完next，就可以讓pHead的next指向last了
pHead.next = last
#讓last，pHead依次向後移動一個節點，繼續下一次的指標反轉
last = pHead
pHead = tmp
return last
連結串列中倒數第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
合併兩個排序的連結串列
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 = p1
p1 = p1.next
else:
tmp.next = p2
p2 = p2.next
tmp = tmp.next
if p1:
tmp.next = p1
if p2:
tmp.next = p2
return ret.next
複雜連結串列的複製
輸入一個複雜連結串列（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標指向任意一個節點），返回結果為複製後複雜連結串列的head。（注意，輸出結果中請不要返回引數中的節點參照，否則判題程式會直接返回空）
- 將原連結串列所有的結點拷貝一份，並且每個拷貝的結點和原來的結點連續出現，如下圖：
- 此時，原來結點指向下一個結點的指標都可以先連結上，原來的random指標也還在；但是每個複製新建的node的random區域還是空的
- 找出規律：A.next.random = a.random.next
理解：如上圖：A.next.raomd，是指第二個「1結點」的random指標，它應該指向 第一個「1結點」的random（第一個「3結點」）後一個結點（即第二個「3結點」），所以有上述變化通式 - 讓每兩個相同的結點斷開，具體做法為：比如第一個「1結點」 讓它指向 第一個「2結點」，random也跟著原來的指向變化，後面的結點重複操作，就能達到下圖示意的，複製了複雜連結串列的操作
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
if pHead is None:
return None
# 為每一個結點複製一個node，並插入到原連結串列中
pTemp = pHead
while pTemp:
node = RandomListNode(pTemp.label)
node.next = pTemp.next # 如下圖2-1
pTemp.next = node # 如下圖 2-2
pTemp = node.next # 如下圖2-3：完成第一個新node插入，移動pTemp，重複上述，完成第二個
# 實現新建node的random指向
pTemp = pHead
while pTemp:
if pTemp.random: # 如果random指標存在
pTemp.next.random = pTemp.random.next # 圖2-4：通過前一個random找到node的random
pTemp = pTemp.next.next # 完成一個，移動pTemp幫助找到下一個的random
# 斷開 原來node 和新 node 間 的連結
pTemp = pHead
newHead = pHead.next # 這個是新連結串列的頭，到最後返回，一般要保留
pNewTemp = pHead.next # 再新建一箇中間變數來儲存新的node
while pTemp:
pTemp.next = pTemp.next.next # 改變前一個node的指向，讓它不要指向新建的node
if pNewTemp.next: # 如果下個一的新node存在 （備註 1）
pNewTemp.next = pNewTemp.next.next # （備註 2）
pNewTemp = pNewTemp.next # （備註 3）
pTemp = pTemp.next # （備註 4） 備註（1~4）見下備註圖解
return newHead
# 測試一下
if __name__ == '__main__':
n1 = RandomListNode(1)
n2 = RandomListNode(2)
n3 = RandomListNode(3)
n4 = RandomListNode(4)
n5 = RandomListNode(5)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
s = Solution()
new_head = s.Clone(n1)
res = new_head
while res:
print(res.label)
res = res.next # 輸出結果 1 2 3 4 5 說明覆製成功
兩個連結串列的第一個公共結點
思考：設連結串列pHead1的長度為a,到公共結點的長度為l1；連結串列pHead2的長度為b,到公共結點的長度為l2，有a+l2 = b+l1
### 思路：第一次迴圈 while(pa!=pb)會將長度自動對齊；
### 第二次迴圈，就正常去判斷了；一個trick
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
5.二元樹
二元樹的映象（Symmetric Tree）
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
二元樹的先序、中序、後續遍歷 遞迴和非遞迴
# 先序列印二元樹（遞迴）
def preOrderTraverse(node):
if node is None:
return None
print(node.val)
preOrderTraverse(node.left)
preOrderTraverse(node.right)
# 先序列印二元樹（非遞迴）
def preOrderTravese(node):
stack = [node]
while len(stack) > 0:
print(node.val)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
node = stack.pop()
# 中序列印二元樹（遞迴）
def inOrderTraverse(node):
if node is None:
return None
inOrderTraverse(node.left)
print(node.val)
inOrderTraverse(node.right)
# 中序列印二元樹（非遞迴）
def inOrderTraverse(node):
stack = []
pos = node
while pos is not None or len(stack) > 0:
if pos is not None:
stack.append(pos)
pos = pos.left
else:
pos = stack.pop()
print(pos.val)
pos = pos.right
# 後序列印二元樹（遞迴）
def postOrderTraverse(node):
if node is None:
return None
postOrderTraverse(node.left)
postOrderTraverse(node.right)
print(node.val)
# 後序列印二元樹（非遞迴）
# 使用兩個棧結構
# 第一個棧進棧順序：左節點->右節點->跟節點
# 第一個棧彈出順序： 跟節點->右節點->左節點(先序遍歷棧彈出順序：跟->左->右)
# 第二個棧儲存為第一個棧的每個彈出依次進棧
# 最後第二個棧依次出棧
def postOrderTraverse(node):
stack = [node]
stack2 = []
while len(stack) > 0:
node = stack.pop()
stack2.append(node)
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
while len(stack2) > 0:
print(stack2.pop().val)
# 先進先出選用佇列結構
import queue
def layerTraverse(head):
if not head:
return None
que = queue.Queue() # 建立先進先出佇列
que.put(head)
while not que.empty():
head = que.get() # 彈出第一個元素並列印
print(head.val)
if head.left: # 若該節點存在左子節點,則加入佇列（先push左節點）
que.put(head.left)
if head.right: # 若該節點存在右子節點,則加入佇列（再push右節點）
que.put(head.right)
# 求二元樹節點個數
def treeNodenums(node):
if node is None:
return 0
nums = treeNodenums(node.left)
nums += treeNodenums(node.right)
return nums + 1
平衡二元樹的判斷
思考：BST的定義為，原問題拆分為計算樹高度和判斷高度差
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
if not pRoot: return True
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
if abs(left - right) > 1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def TreeDepth(self, pRoot):
if not pRoot: return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left, right) + 1
二元樹的深度
# -*- 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
二元樹的下一個結點
給定一個二元樹和其中的一個結點，請找出中序遍歷順序的下一個結點並且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標。
思路：中序遍歷的順序為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
對稱的二元樹
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
[
1->null,
2->3->null,
4->null
]
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {ListNode[]} a lists of linked list
def binaryTreeToLists(self, root):
# Write your code here
#二元樹的層次遍歷
res_list = []
if not root:
return []
q = [root]
while q:
new_q = []
dummy = ListNode(0)
pre = dummy
for node in q:
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
pre.next = ListNode(node.val)
pre = pre.next
q = new_q
res_list.append(dummy.next)
return res_list
把二元樹列印成多行
從上到下按層列印二元樹，同一層結點從左至右輸出。每一層輸出一行。
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
之字形列印二元樹
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
序列化和反序列化二元樹
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()
二叉平衡樹中的第k小數
二元搜尋樹中的第k大結點
Leetcode 230. Kth Smallest Element in a BST
思路：BST的中序遍歷就是一個有序陣列，需要注意到Leetcode中限制了k在[1,樹結點個數]而牛客網沒有，所以需要考慮k的值有沒有超出
class Solution: # 中序遍歷 + cnt 計數
# 返回對應節點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
重建二元樹
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
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
二元搜尋樹與雙向連結串列
輸入一棵二元搜尋樹，將該二元搜尋樹轉換成一個排序的雙向連結串列。要求不能建立任何新的結點，只能調整樹中結點指標的指向。
思考：左子樹上最右結點 -> root -> 右子樹上的最左結點
分情況討論：1. 本節點結束；
2.本節點有左右節點；
2.1 有左子樹，那本節點是左子樹的最右側的下一個
2.1 有右子樹，那本節點是右子樹的最左側的下一個（遞迴返回的保證是最左側節點）
# -*- 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 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
判斷樹B是否是樹A的子結構
輸入兩棵二元樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
兩個邏輯，一個是找到一個之後判斷是否完全一樣，另外一個是遞迴找到第一個一樣的；
class Solution:
# 給定兩個二元樹（的根節點）A、B，判斷B 是不是A 的二元樹
def HasSubtree(self, pRoot1, pRoot2):
if pRoot1 == None or pRoot2 == None:
return False
result = False
if pRoot1.val == pRoot2.val:
result = self.isSubtree(pRoot1, pRoot2)
if result == False:
result = self.HasSubtree(pRoot1.left, pRoot2) | self.HasSubtree(pRoot1.right, pRoot2)
return result
def isSubtree(self, root1, root2):
if root2 == None:
return True
if root1 == None:
return False
if root1.val == root2.val:
return self.isSubtree(root1.left, root2.left) & self.isSubtree(root1.right, root2.right)
return False
二元樹中和為某一值的路徑
輸入一顆二元樹和一個整數，列印出二元樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。
思考：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
二元搜尋樹的後序遍歷序列
輸入一個整數陣列，判斷該陣列是不是某二元搜尋樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的陣列的任意兩個數位都互不相同。
思考：後序遍歷意味著num[-1]為root，那麼根據這個值和二元搜尋樹的性質，可以把陣列劃分成兩個部分，left 和 right ，再遞迴判斷
# coding:utf-8
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence==None or len(sequence)==0:
return False
length=len(sequence)
root=sequence[length-1]
# 在二叉搜尋 樹中 左子樹節點小於根節點
for i in range(length):#迴圈的值設定得很巧妙，和下方的left、right初始值對應
if sequence[i]>root:
break
# 二元搜尋樹中右子樹的節點都大於根節點
for j in range(i,length):
if sequence[j]<root:
return False
# 判斷左子樹是否為二元樹
left=True
if i>0:#說明存在左子樹，求左子樹是否為後續遍歷，然後更新left的值
left=self.VerifySquenceOfBST(sequence[0:i])
# 判斷右子樹是否為二元樹
right=True
if j<length-1:#說明存在右子樹，判斷右子樹是否為後續遍歷。如果不存在右子樹，預設為真。
right=self.VerifySquenceOfBST(sequence[i:-1])
return left and right
6.複雜資料結構
順時針列印矩陣
# -*- coding:utf-8 -*-
class Solution:
# matrix型別為二維列表，需要返回列表
def printMatrix(self, matrix):
# write code here
ans=[]
m=len(matrix)
if m==0:
return ans
n=len(matrix[0])
# 邊界範圍
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
資料流中的中位數
from heapq import *
#heapq預設就是最小堆，large 是最小堆，但是都是正數所以比較大的最小堆，small是最大堆，但是都是負數，所以是比較小的最大堆；
#1.首先將large 跟當前num做判斷，然後彈出最小的那個，放入最大堆；這裡large的個數並沒有增加，只是增加了小的，
#2.如果large個數比較小，就在向large裡面放，
#3.中位數如果是奇數個，那麼它一定在large裡面；如果是偶數個，那就求個平均數；
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
滑動視窗的最大值
給定一個陣列和滑動視窗的大小，找出所有滑動視窗裡數值的最大值。例如，如果輸入陣列{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]的最大值。
視窗的滑動過程中數位的進出類似一個佇列中元素的出隊入隊，這裡我們採用一個佇列queue儲存可能成為最大值的元素下標(之所以佇列中存元素下標而不是元素值本身，是因為佇列並不儲存所有元素，而我們需要知道什麼時候隊首元素已經離開滑動視窗)。當遇到一個新數時，將它與隊尾元素比較，如果大於隊尾元素，則丟掉隊尾元素，繼續重複比較，直到新數小於隊尾元素，或者佇列為空為止，將新數下標放入佇列。同時需要根據滑動視窗的移動判斷隊首元素是否已經離開。
# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
# 存放可能是最大值的下標
maxqueue = []
# 存放視窗中最大值
maxlist = []
n = len(num)
# 引數檢驗
if n == 0 or size == 0 or size > n:
return maxlist
for i in range(n):
# 判斷隊首下標對應的元素是否已經滑出視窗
if len(maxqueue) > 0 and i - size >= maxqueue[0]:
maxqueue.pop(0)
# 判斷新入的是否比第0 index的要大，如果是就要全部替換掉；
while len(maxqueue) > 0 and num[i] > num[maxqueue[-1]]:
maxqueue.pop()
maxqueue.append(i)
if i >= size - 1:
maxlist.append(num[maxqueue[0]])
return maxlist
用兩個棧實現佇列
思考：棧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()
包含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是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
# -*- 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
矩陣中的路徑
思考：dfs加記憶化搜尋
class Solution:
def dfs(self, matrix, flag, rows, cols, 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 flag[x][y] and matrix[x * cols + y] == s[0]:
flag[x][y] = False # 修改當前格子的標識
if self.dfs(matrix, flag[:], rows, cols, x, y, s[1:]): # 遞迴
return True
flag[x][y] = True
# 如果上一個判斷條件返回的是False，那麼就說明這個格子目前還不是路徑上的格子，再把當前格子的標識修改回來。
return False
def hasPath(self, matrix, rows, cols, path):
if path == '':
return True
flag = [[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]:
flag[r][c] = False
if self.dfs(matrix, flag[:], rows, cols, r, c, path[1:]):
return True
flag[r][c] = True
return False
機器人的運動範圍
地上有一個m行和n列的方格。一個機器人從座標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行座標和列座標的數位之和大於k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
思考：dfs+記憶化搜尋，注意雖然說是可以向左右上下走動，但是因為是從座標0，0開始，所以只需要向左或者向下走動就行；
# -*- 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)