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

59.面試題59-隊列的最大值

請定義一個隊列并實現函數 max_value 得到隊列里的最大值，要求函數max_value、push_back 和 pop_front 的均攤時間復雜度都是O(1)。

若隊列為空，pop_front 和 max_value 需要返回 -1

思路1:直接定義一個隊列，

import Queue
class MaxQueue(object):def __init__(self):self.deque=Queue.deque()def max_value(self):""":rtype: int"""return max(self.deque) if self.deque else -1def push_back(self, value):""":type value: int:rtype: None"""self.deque.append(value)def pop_front(self):""":rtype: int"""return self.deque.popleft() if self.deque else -1

時間復雜度：插入操作o(1),刪除操作o(1),取最大值o(n)

思路2:維護一個輔助雙端隊列，用于存儲最大值，每次插入元素時，將輔助雙端隊列的尾部小于插入元素的值去除，然后加入該元素。每次彈出隊列頭部時，比較彈出元素與輔助隊列的頭是否一致，如果一致，更新雙端隊列頭部（ 彈出該頭部）

import Queue
class MaxQueue(object):def __init__(self):self.helper=Queue.deque()   # deque[0] 最大值，deque[-1]最小值self.queue=Queue.Queue()def max_value(self):""":rtype: int"""return self.helper[0] if self.helper else -1def push_back(self, value):""":type value: int:rtype: None"""while(self.helper and self.helper[-1]<value):self.helper.pop()    # 彈出雙端隊列尾部的元素self.helper.append(value) # 在雙端隊列尾部加入元素self.queue.put(value)  # 在隊列尾加入元素def pop_front(self):""":rtype: int"""if not self.helper:  # 為什么要是helper queue不行return -1ans=self.queue.get()  # 彈出隊列頭if ans==self.helper[0]:self.helper.popleft()  # 雙端隊列彈出隊列頭部元素return ans
# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()

時間復雜度：刪除o(1)，最大o(1),求最大值：均攤時間復雜度o(1)，做一個插入操做最多會有n次出隊操作，但是每個數字只會出隊一次，所以維護n個元素最大值的總出隊操作也就是n，即均攤時間復雜度為0（1）。

60.面試題64-求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。

思路1：求和公式，使用到了乘除法，不可用
$$1+2+3,...,n=(1+n)?n/2$$

思路2：迭代要使用循環語句，不可

思路3:遞歸，遞歸出口時需要用到判斷語句，但是判斷語句可以使用邏輯運算符的短路作用，開啟遞歸或結束遞歸：
$$n>1andsumNums(n?1)$$

當n>1 時會開啟下一層遞歸，當n=1,不執行遞歸，執行之后的操作

class Solution(object):def __init__(self):self.res=0def sumNums(self, n):""":type n: int:rtype: int"""def rec(num):num>1 and rec(num-1)self.res+=numrec(n)return self.res

61.面試題65-不用加減乘除做加法

寫一個函數，求兩個整數之和，要求在函數體內不得使用 “+”、“-”、“*”、“/” 四則運算符號。
思路：不用加減乘除做加法，借助位運算。
經過觀察可以發現，兩個數字的二進制和，對應位置上的結果運算規律和異或一致，進位位置上的結果和and運算相同。將兩數異或 的結果和and 的結果相加，等價于求原來兩個數字的和。又出現兩數求和操作，重復兩數求和求異或。直至進位為0，不存在加法操作。
注意點：python 中的數字以補碼的形式存儲，python中的數字沒有長度，依據題目要求，需要舍去大于32位以上的數字。
補碼還原：～（a^x）

class Solution(object):def add(self, a, b):""":type a: int:type b: int:rtype: int"""x = 0xffffffffa, b = a & x, b & xwhile b != 0:a, b = (a ^ b), (a & b) << 1 & xreturn a if a <= 0x7fffffff else ~(a ^ x)

62.面試題66-構建乘積數組

給定一個數組 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]。不能使用除法。
思路：暴力解法43/44時間超出限制

class Solution(object):def constructArr(self, a):""":type a: List[int]:rtype: List[int]"""n=len(a)b=[1]*nfor i in range(n):for j in range(n):if j!=i:b[i]*=a[j]return b

思路2：左右乘積數組
l[i]=a[0]*…a[i-1]
r[i]=a[i+1]*…a[n-1]

在這里插入代碼片class Solution(object):def constructArr(self, a):""":type a: List[int]:rtype: List[int]"""n=len(a)b=[1]*nleft=[1]*nright=[1]*nfor i in range(1,n):left[i]=left[i-1]*a[i-1]for i in range(n-2,-1,-1):right[i]=right[i+1]*a[i+1]for i in range(n):b[i]=left[i]*right[i]return b

63.面試題68-1二叉樹搜索樹的最近公共祖先

給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

思路：一個節點為最近祖先：pq 在該節點的兩棵子樹/p=root 或者q=root。

首先判斷 p 和 q 是否相等，若相等，則直接返回 p 或 q 中的任意一個，程序結束
若不相等，則判斷 p 和 q 在向左還是向右的問題上，是否達成了一致
如果 p 和 q 都小于root, 哥倆一致認為向左👈，則 root = root.left
如果 p 和 q 都大于root, 哥倆一致認為向右👉，則 root = root.right
如果 p 和 q 哥倆對下一步的路線出現了分歧，說明 p 和 q 在當前的節點上就要分道揚鑣了，當前的 root 是哥倆臨別前一起走的最后一站
返回當前 root
迭代：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if root==None:return rootif p.val==q.val:return pnode=rootwhile(node):if node.val>p.val and node.val>q.val:node=node.leftelif node.val<p.val and node.val<q.val:node=node.rightelse:return node

遞歸：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if root.val<p.val and root.val<q.val:return self.lowestCommonAncestor(root.right,p,q)if root.val>p.val and root.val>q.val:return self.lowestCommonAncestor(root.left,p,q)return root

64.面試題68-2二叉樹的最近公共祖先

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

思路1：記錄父親節點
先遍歷一遍樹，記錄每個點的父親節點。然后去找從p開始去找其父親節點路徑：vis_has，接著從q開始去找其父親，在vis_hash 中第一次出現的就為最近公共祖先。

class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""def dfs(node):if node==None:returnif node.left:fa_hash[node.left]=nodeif node.right:fa_hash[node.right]=nodedfs(node.left)dfs(node.right)fa_hash={root:None}vis_hash={}dfs(root)        while (p!=None):# print(p)vis_hash[p]=True     # 要記得把自己放進去p=fa_hash[p]while(q!=None):if vis_hash.get(q):  # 記得自己也要驗證return qq=fa_hash[q]

思路2:遞歸 從葉子節點往上遞歸，找到一個節點，其左右子樹中包含p或者q，該節點為最近的父親節點。

class Solution(object):def __init__(self):self.res=Nonedef lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""def dfs(node,p,q):if node==None:return Falseleft=dfs(node.left,p,q)right=dfs(node.right,p,q)mid=(p==node or q==node)if mid+left+right==2:self.res=nodereturn mid or left or rightdfs(root,p,q)return self.res

65.面試題67-把字符串轉換成數字-自動機

字符串處理相關的題目往往涉及復雜的流程以及條件情況，如果直接上手寫程序，一不小心就會寫成及其臃腫的代碼。

因此，為了有條理的分析每一個輸入字符的處理方法。可以使用自動機方法

程序在每一個時刻有一個狀態s，每次總序列中輸入一個字符串c ，并根據字符串c 轉到下一個狀態s’ .我們要做的就是簡歷一個覆蓋所有情況的從s 與c 的映射到s‘ 的表格。

用表格來表示自動機：
表格的第一列為狀態，第一行為輸入，表格體內部為下一個狀態。

編程時，將狀態轉換表轉換進代碼里。

題目要求，輸出處轉換后的數字。因此在s’=in_number 時，更新我們的輸入數字，即可得到最終的答案。

INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31class Automaton:def __init__(self):self.state = 'start'self.sign = 1self.ans = 0self.table = {'start': ['start', 'signed', 'in_number', 'end'],'signed': ['end', 'end', 'in_number', 'end'],'in_number': ['end', 'end', 'in_number', 'end'],'end': ['end', 'end', 'end', 'end'],}def get_col(self, c):if c.isspace():return 0if c == '+' or c == '-':return 1if c.isdigit():return 2return 3def get(self, c):self.state = self.table[self.state][self.get_col(c)]if self.state == 'in_number':self.ans = self.ans * 10 + int(c)self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)elif self.state == 'signed':self.sign = 1 if c == '+' else -1class Solution:def strToInt(self, str):automaton = Automaton()for c in str:automaton.get(c)return automaton.sign * automaton.ans

66.面試題20-表示數值的字符串-自動機

請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示數值，但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。

自動機解題：
1.畫狀態轉移圖
2.列狀態轉移表
3.確定輸入字符串對應的列
4.迭代所有的輸入，進行狀態轉移，如果遇到不合理狀態就返回

class Solution(object):def isNumber(self, s):""":type s: str:rtype: bool"""if not s:return FalsetransTable=[[1,2,7,-1,-1,0],[-1,2,7,-1,-1,-1],[-1,2,3,4,-1,9],[-1,3,-1,4,-1,9],[6,5,-1,-1,-1,-1],[-1,5,-1,-1,-1,9],[-1,5,-1,-1,-1,-1],[-1,8,-1,-1,-1,-1],[-1,8,-1,4,-1,9],[-1,-1,-1,-1,-1,9]]cols={"sign":0,"number":1,".":2,"exp":3,"other":4,"blank":5}def get_col(c):if c.isdigit():return "number"elif c in {"+","-"}:return "sign"elif c==".":return "."elif c in {"e","E"}:return "exp"elif c==" ":return "blank"else:return "other"legal_state={2,3,5,8,9}state=0for c in s:state=transTable[state][cols[get_col(c)]]if state==-1:return Falsereturn True if state in legal_state else False