本系列博文為題庫刷題筆記，（僅在督促自己刷題）如有不詳之處，請參考leetcode官網：https://leetcode-cn.com/problemset/lcof/

45.面試題55- 二叉樹的深度

輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。
自頂向下遞歸：父親節點給葉子節點提供信息,不斷往下遞歸；到達每一個葉子節點之后，更新目前的最大深度。遞歸出口還是：if node==None： return ，框架是不變的。從上往下靈魂：底層出口。

class Solution(object):def __init__(self):self.deep=0def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def top_down(node,l):if node==None:returnif node.left==None and node.right==None: # 靈魂self.deep=max(self.deep,l)top_down(node.left,l+1)top_down(node.right,l+1)top_down(root,1)return self.deep

自底向上：對于某一個節點，只要左右子樹的深度知道了(l,r)，該節點的深度為max(l,r)+1
不斷從下往上，最終輸出根節點的深度。從下往上的靈魂，最底層信息如何傳遞給上層，本質是后序遍歷。

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def bottom_up(node):if node==None:return 0    l_deep=bottom_up(node.left)r_deep=bottom_up(node.right)return max(l_deep,r_deep)+1return bottom_up(root)

46.面試題55-2-平衡二叉樹

輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。
思路：要確認每個節點的左右子樹的深度，然后比較兩個的大小相差不超過1。自底向上的可解釋性高。
1.當節點root 左 / 右子樹的深度差 ≤1 ：則返回當前子樹的深度，即節點 2.root 的左 / 右子樹的深度最大值 +1（ max(left, right) + 1 ）；
當節點root 左 / 右子樹的深度差 >=2 ：則返回 ?1 ，代表 此子樹不是平衡樹 。

class Solution(object):def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""def bottom_up(node):if node==None:return 0l_deep=bottom_up(node.left)if l_deep==-1:return -1r_deep=bottom_up(node.right)if r_deep==-1:return -1if abs(l_deep-r_deep)>1: # 返回值的類型應該要一致 如何將這兩個統一在一起return -1else:return max(l_deep,r_deep)+1return bottom_up(root)!=-1

自頂向下：檢查每個節點的是否滿足平衡二叉樹的要求，在遞歸遍歷左右子樹的情況。設置單獨的函數求解二叉樹節點的深度。–效率低，運行時間是自底向上的70倍

class Solution(object):def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""if root==None:return True # 空節點默認為是符合平衡二叉樹的要求的flag1=abs(self.tree_deep_bu(root.left)-self.tree_deep_bu(root.right))flag2=self.isBalanced(root.left)flag3=self.isBalanced(root.right)return  flag1<2 and flag2 and flag3def tree_deep_bu(self,node):if node==None:return 0return max(self.tree_deep_bu(node.left),self.tree_deep_bu(node.right))+1

47.面試題57-1-和為s的兩個數字-雙指針

輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等于s，則輸出任意一對即可。
雙指針技巧：兩個指針分別指向數組的頭和尾，如果兩數之和大于目標值，則移動右指針；兩數之和小于目標值，則移動左指針。直至找到目標值。
正確性：所有和為上三角，移動i->i+1,會消除不符合要求的一行數字，移動j->j-1會消除不滿足要求的一列數字。直至搜索到正確答案。

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""l,r=0,len(nums)-1while(l<r):if nums[l]+nums[r]==target:return (nums[l],nums[r])elif nums[l]+nums[r]<target:l+=1else:r-=1return (-1,-1)

48.面試題57-2-和為s 的連續正數序列-雙指針

輸入一個正整數 target ，輸出所有和為 target 的連續正整數序列（至少含有兩個數）。
序列內的數字由小到大排列，不同序列按照首個數字從小到大排列。
例如：
輸入：target = 9
輸出：[[2,3,4],[4,5]]
連續序列：雙指針技巧，快慢指針分別指向序列的兩個端點，利用求和公式求此時的和:如果和小于目標值，移動右指針；如果和大于目標值，更新起始左指針；和等于目標值，更新左指針。退出條件為l>r。

循環結束條件l<r,當l == r 說明r 后面沒有兩個數字的和可以比target小。

class Solution(object):def findContinuousSequence(self, target):""":type target: int:rtype: List[List[int]]"""res=[]l,r=1,2while(l<r):sum_val=(l+r)*(r-l+1)/2#print(l,r,sum_val,target)if sum_val==target:res.append([])for j in range(l,r+1):res[-1].append(j)l+=1elif sum_val<target:r+=1else:l+=1return res

49.面試題56-數組中出現數字的次數-位運算

位運算系列題目：leetcode 260,136,137,645 異或操作解題思路
異或操作： 數字a與數字b的異或操作為兩個數字的二進制上每一位進行對位異或操作，如果同一位置上兩個數字相同，異或結果為0，否則為1.
異或規律：
1.任何數字和本身異或為0，
2.任何數字和0異或為本身，
3.異或滿足交換律
異或草用于檢測出現1，3，5次的數字。

leetcode-136 只出現一次的數字I

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素

解題思路：異或操作的三條性質保證使用對所有數字進行異或操作可以找到不同的那個數字，因為異或滿足交換律，所以可以看成將所有的相同數字進行異或得到0再與不同數字進行異或操作，得到不同的那個數字。

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""single_num=0for val in nums:single_num^=valreturn single_num

leetcode-137 只出現一次的數字II

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現了三次。找出那個只出現了一次的元素。
解題思路1: 位運算
為了區分出現一次的數字和出現三次的數字，使用兩個位掩碼：seen_once 和 seen_twice。兩個掩碼的變換規則為：（不是很懂）
僅seen_twice 為0時，改變seen_once
僅seen_once 為0時，改變seen_twice

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""seen_once,seen_twice=0,0for num in nums:seen_once=~seen_twice&(seen_once^num)seen_twice=~seen_once&(seen_twice^num)return seen_once

解題思路2:數學計算
[a,b,b,b]->set 操作：[a,b]-> 求和：a+b-> 乘三：3(a+b)-> 減原數組的和3(a+b)-(a+3b)-> 除以2即可得到a

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: List[int]"""temp=set(nums)return (sum(temp)*3-sum(nums))//2

leetcode-260 只出現一次的數字III

一個整型數組 nums 里除兩個數字（a，b表示）之外，其他數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n)，空間復雜度是O(1)。
思路：時間復雜度是o(n), 要求一次遍歷。空間復雜度是o(1) 只能有常數個空間限制。

分組異或：將只出現了一次的兩個數字分到兩組，每組中其他元素為成對出現的相同數字。

核心是如何分組：全部數字異或的結果將是ab兩個數字異或的結果。異或結果中某一位為1，主要是由于a，b在該位置二進制表示不同導致的。所以可以依據該位置將數字分為兩組，其分組滿足上面的要求，因為相同的數字在該位肯定要么同時為0，要么同時為1.

異或結果如何取到為1的那一位呢：不為零的最低位

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: List[int]"""bitmask=0for num in nums:bitmask=bitmask^num   # 保存兩個出現一次數字x，y的異或結果diff=bitmask&(-bitmask)   # 異或結果中最每個位置上的1要么來自x 要么來自y，取最右邊的1.x=0for num in nums:if num & diff: # 將最右邊有1的所有數字拿出來，再做一次異或，就能找到xx=x^numreturn (x,x^bitmask)

50.面試題51-數組中的逆序對-歸并排序

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。
思路：歸并排序解逆序數。在歸并的過程中，計算逆序對的數量。

歸并是分治思想的典型應用，不斷二分到單個元素，然后兩兩合并。在求逆序數的情況下就是兩個兩個求逆序數，然后四個四個求逆序數，把所有的逆序數相加即可。
核心在兩個需要合并（merge）的序列中逆序數如何求？如下：
在左指針lPtr 發生右移動的時候，當前 lPtr 指向的數字比 rPtr 小，但是比 R 中 [0 … rPtr - 1] 的其他數字大，[0 … rPtr - 1] 的其他數字本應當排在 lPtr 對應數字的左邊，但是它排在了右邊，所以這里就貢獻了 rPtr 個逆序對。

class Solution(object):def reversePairs(self, nums):""":type nums: List[int]:rtype: int"""def merge_sort(nums,l,r):if l<r:mid=(l+r)//2count=merge_sort(nums,l,mid)+merge_sort(nums,mid+1,r)#print("a",count)i,j,tmp=l,mid+1,[]while(i<=mid and j<=r):if nums[j]<nums[i]:tmp.append(nums[j])count+=mid-i+1j+=1else:tmp.append(nums[i])i+=1while(i<=mid):tmp.append(nums[i])i+=1while(j<=r):tmp.append(nums[j])j+=1nums[l:r+1]=tmp#print(nums,count)return countelse:return 0res=merge_sort(nums,0,len(nums)-1)return res

class Solution(object):def reversePairs(self, nums):""":type nums: List[int]:rtype: int"""def cout_rev(l,r):if l < r:mid = (l + r) // 2count = cout_rev(l,mid) + cout_rev(mid+1, r)i, j, tmp = l, mid+1, []while(i<=mid or  j <= r):if i > mid or (j <= r and nums[i] > nums[j]):tmp.append(nums[j])j += 1else:count += j - (mid + 1)tmp.append(nums[i])i += 1                        nums[l:r+1] = tmp[:]return countelse:return 0res = cout_rev(0, len(nums)-1)return res

51.面試題54-二叉搜索樹的第k大節點-中序遍歷

給定一棵二叉搜索樹，請找出其中第k大的節點。
思路：二搜索樹的中序遍歷序列為升序，中序遍歷res返回res[-k] 即可。

class Solution(object):def kthLargest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""def in_order_dfs(node):if node==None:return in_order_dfs(node.left)res.append(node.val)in_order_dfs(node.right)res=[]in_order_dfs(root)return res[-k]

52.面試題58-翻轉單詞的順序-庫函數

調用內置函數：

class Solution(object):def reverseWords(self, s):""":type s: str:rtype: str"""s_lis=s.split() # 將字符串按空格劃分成列表，多個空格看作一個s_lis.reverse() # 將列表逆序res=" ".join(s_lis) # 將鏈表中字符串按空格鏈接return res

53.面試題58-左旋轉字符串

字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部。請定義一個函數實現字符串左旋轉操作的功能。比如，輸入字符串"abcdefg"和數字2，該函數將返回左旋轉兩位得到的結果"cdefgab"。
左移沒有順序變換問題。
思路1：每次左移動一位， 移動k次

class Solution(object):def reverseLeftWords(self, s, n):""":type s: str:type n: int:rtype: str"""l=len(s)n=n%lfor i in range(n):s=s[1:]+s[0]return s

思路2:拼接s[n:]與s[:n]

class Solution(object):def reverseLeftWords(self, s, n):""":type s: str:type n: int:rtype: str"""l=len(s)n=n%ls_r=s[n:]s_l=s[:n]return s_r+s_l

54.面試題59-滑動窗口的最大值-左右dp

給定一個數組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。
leetcode 239動態規劃法-那題標為困難，這里標為簡單，神奇。
左右兩個dp 數組，比較得到答案。

        n=len(nums)if n*k==0:return []if k==1:return numsleft=[nums[0]]*nright=[nums[-1]]*nfor i in range(1,n): # i:[0,n-1]if i%k==0:left[i]=nums[i]else:left[i]=max(left[i-1],nums[i])ind=n-i-1if ind%k==0:right[ind]=nums[ind]else:right[ind]=max(right[ind+1],nums[ind])res=[]for i in range(n-k+1):res.append(max(left[i+k-1],right[i]))return res

55.面試題60-n個骰子的點數-dp

把n個骰子扔在地上，所有骰子朝上一面的點數之和為s。輸入n，打印出s的所有可能的值出現的概率。

你需要用一個浮點數數組返回答案，其中第 i 個元素代表這 n 個骰子所能擲出的點數集合中第 i 小的那個的概率。

class Solution(object):def twoSum(self, n):""":type n: int:rtype: List[float]"""dp=[[0]*(6*11+1) for _ in range(n)]for j in range(1,7):dp[0][j]=1               #  一個骰子，價值為j 的個數for i in range(1,n):         # i+1個骰子for j in range(i+1,6*(i+1)+1): # i+1個骰子點數和的范圍 [i+1,6(i+1)]for k in range(max(j-6,1),j): # dp[i][j]=sum_{i=1}^{j-1}dp[i-1][j-i]#print(i,j,k)dp[i][j]+=dp[i-1][k]res=[]#print(dp)for j in range(6*11+1):if dp[n-1][j]!=0:res.append(dp[n-1][j]/ float(6**n))return res

56.面試題61-撲克牌中的順子

從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續的。2～10為數字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，可以看成任意數字。A 不能視為 14。
輸入：數組長度為 5 ，數組的數取值為 [0, 13] 。
思路：判斷所給的5個數字是否能構成一個順子
身為大小王的0可以為任何數字,將數組排序后，檢查缺失數字的個數，如果缺失數字的個數少于0的個數，則可以構成順子。

class Solution(object):def isStraight(self, nums):""":type nums: List[int]:rtype: bool"""nums.sort()num_0=0i,index_z=0,0while(i<5):if nums[index_z]==0:num_0+=1index_z+=1i+=1gap=0for i in range(index_z,4):if nums[i+1]-nums[i]==1:continueelif nums[i+1]-nums[i]==0:return Falseelse:gap+=nums[i+1]-nums[i]-1print(num_0,gap,nums)if gap<=num_0:          # gap 可以比0的個數少，0可以無中生有return True         # [0,0,0,9,11]->[9,10,11,..]else:return False

class Solution(object):def isStraight(self, nums):""":type nums: List[int]:rtype: bool"""nums.sort()res = [nums[-1]] * 5l, r, res_Index = 0, 3, 3# l 指向nums左邊待處理元素# l 指向nums右邊待處理元素# res_index 當前這個元素應該為多少while(l <= r):if nums[r] + 1 == res[res_Index+1]:res[res_Index] = nums[r]r -=1res_Index-=1else:if nums[l] == 0:res[res_Index] = res[res_Index+1] -1l += 1 res_Index -= 1else:return Falsereturn True

57.面試題62-圓圈中最后剩下的數字–約瑟夫環問題

0,1,n-1這n個數字排成一個圓圈，從數字0開始，每次從這個圓圈里刪除第m個數字。求出這個圓圈里剩下的最后一個數字。

例如，0、1、2、3、4這5個數字組成一個圓圈，從數字0開始每次刪除第3個數字，則刪除的前4個數字依次是2、0、4、1，因此最后剩下的數字是3。
參考博文：遞歸https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/
核心是如何從n-1恢復到n的編號，f = (f+m)%n

class Solution(object):def lastRemaining(self, n, m):""":type n: int:type m: int:rtype: int"""pre_pos=0for i in range(1,n+1):pos=(pre_pos+m)%i    # 加m 是在右移動pre_pos=posreturn pos

58.面試題63-股票的最大利潤-最大谷峰值

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能獲取的最大利潤。
注意：你不能在買入股票前賣出股票。

解題思路：一次買賣，找最大的峰谷值

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""if len(prices)==0:return 0min_price=prices[0]max_pro=0for val in prices[1:]:max_pro=max(max_pro,val-min_price)min_price=min(min_price,val)return max_pro