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

編程語言為python

1.面試題3-數組中的重復數字

在一個長度為n的數組里，所有的數字都在0-n-1的范圍內，數組中某些數字是重復了的，但是不知道有幾個數字是重復了的，也不知道每個數組的重復次數。請找出數組中任意一個重復的數字：
hash表存儲遍歷過的數字，如果表中已經存在，直接返回。

class Solution(object):def findRepeatNumber(self, nums):""":type nums: List[int]:rtype: int"""vis_has={}for val in nums:if vis_has.get(val):   #訪問字典的鍵值都用這個方法return valelse:vis_has[val]=True

leetcode 287.尋找重復數字
給定一個包含n+1個整數的數組，其中數字都在1-n之間，可知至少存在一個重復數字。假設只存在一個重復整數，找出這個重復的數。
要求：
不能更改原數組（假設數組是只讀的）。
只能使用額外的 O(1) 的空間。–不能用hash表
時間復雜度小于 O(n2) 。–暴力法的時間復雜度是o(n2)
數組中只有一個重復的數字，但它可能不止重復出現一次。
–弗洛伊德兔子烏龜。如果有重復數字，那么就會有至少兩個索引指向相同的數字，這就是鏈表中成環的條件。檢驗鏈表入環節點就是重復的數字。
vi=nums[i],指向下一個索引

class Solution(object):def findDuplicate(self, nums):""":type nums: List[int]:rtype: int"""t=nums[0]r=nums[0]while True:t=nums[t]r=nums[nums[r]]if t==r:breakr=nums[0]while t!=r:t=nums[t]r=nums[r]return t

2.面試題04-二維數組中的查找

在一個nm的二維數組中，每一行都按照從左往右遞增的順序，每一行都按從左到右遞增順序排序，每一列都按照從上到下遞增順序排列，完成在二維數組中查找指定數，在返回true,不在返回false.（與leetcode240一致）
思路1:暴力搜索，忽略有序條件，時間復雜度o(nm)
思路2:線性查找，從數組的右上角開始搜索：

• nums[0][n-1]==target: return true
• nums[0][n-1]<target: 去更大的區域查找,行坐標加1，
• nums[0][n-1]>taget: 去更小的區域查找，列坐標減1
  直至行列索引不符合條件，時間復雜度o(n+m)

class Solution(object):def findNumberIn2DArray(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""m=len(matrix)if m==0:return Falsen=len(matrix[0])i,j=0,n-1while(-1<i<m and -1<j<n):if matrix[i][j]==target:return Trueelif matrix[i][j]<target:i+=1else:j-=1return False

3.面試題05-替換空格

請實現一個函數，把字符串中的空格替換成“%20”。
考察的是字符串可變不可變，轉義字符的輸出？
直接想法：新建一個res_str，遍歷原字符串，按要求復制一份。–python操作十分方便

class Solution(object):def replaceSpace(self, s):""":type s: str:rtype: str"""res_str=""for char in s:if char==" ":res_str+="%20"else:res_str+=charreturn res_str

4.面試題06-從尾到頭打印鏈表

輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。
思路1：先將鏈表反轉，然后打印輸出就可以了。

class Solution(object):def reversePrint(self, head):""":type head: ListNode:rtype: List[int]"""if head==None:return []pre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_noderes=[]new_node=pre_nodewhile(new_node):res.append(new_node.val)new_node=new_node.nextreturn res

思路2：將鏈表正序輸出，將結果res逆序輸出就好。

class Solution(object):def reversePrint(self, head):""":type head: ListNode:rtype: List[int]"""if head==None:return []res=[]cur_node=headwhile(cur_node):res.append(cur_node.val)cur_node=cur_node.nextreturn res[::-1]

5.面試題07-重建二叉樹

leetcode 105:從前序與中序遍歷序列構二叉樹

6.面試題09-兩個堆棧實現隊列

用兩個堆棧實現一個隊列。請實現它的兩個函數appendTail和deleteHead,分別完成在隊列尾部插入整數和在隊列頭部刪除整數（若隊列中沒有元素，deleteHead操作返回-1）

堆棧先進后出，隊列先進先出

方案1:
兩個棧
主棧：存隊列。需要添加元素時，將原有的所有元素押入輔助棧，將元素押入棧底，然后將輔助棧的元素押回主棧。刪除元素，直接彈出棧頂元素
輔助棧：輔助主棧實現存元素操作，這個思路主要保證：先存入的元素在棧頂。

class CQueue(object):def __init__(self):self.main_stack=[]self.help_stack=[]def appendTail(self, value):""":type value: int:rtype: None"""if self.main_stack==[]:self.main_stack.append(value)else:while(self.main_stack):self.help_stack.append(self.main_stack.pop())self.main_stack.append(value)while(self.help_stack):self.main_stack.append(self.help_stack.pop())def deleteHead(self):""":rtype: int"""if self.main_stack==[]:return -1return self.main_stack.pop()

4024ms 17.3MB

方案1主要費時在添加一個新元素的時候，需要移動主棧內的所有元素，然后將所有元素押回來，保證最先存入的元素在主棧頂。
改進方案：
插入元素：維護一個主堆棧，每次加元素，往堆棧頂添加元素就可以了
刪除元素：維護一個輔助堆棧，需要彈出元素時將主棧的元素彈入輔助棧，那么第一個入主棧的元素將出現在輔助棧頂，直接將其彈出。重點：此時不需要將剩余元素彈回主棧，因為下一次刪除操作對象還是在輔助棧棧頂。所以彈出操作：檢查輔助棧是否為空，為空將主棧中元素彈入輔助棧中，彈出輔助棧棧頂即可。時間快了3倍數。

class CQueue(object):def __init__(self):self.main_stack=[]self.help_stack=[]def appendTail(self, value):""":type value: int:rtype: None"""self.main_stack.append(value)def deleteHead(self):""":rtype: int"""if self.main_stack==[] and self.help_stack==[]:return -1if self.help_stack==[]:while(self.main_stack):self.help_stack.append(self.main_stack.pop())return self.help_stack.pop()

1816ms 17.4MB

7.面試題10-1-斐波那契數列

寫一個函數，求輸入n的斐波那契數列的第n項。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n==0:return 0if n==1:return 1prepre_f=0pre_f=1f=0for i in range(2,n+1):   f=pre_f+prepre_fprepre_f=pre_fpre_f=freturn f%(10**9+7)

循環求余法用于解決大數越界問題，python可以不用考慮大數越界問題。

8.面試題10-2-青蛙跳臺階問題

一只青蛙一次可以跳一階臺階，也可以跳2階臺階。求該青蛙跳上一個n階臺階總共有多少總跳法。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

f(i)表示跳到第i個臺階的方法數，它可以由i-1個臺階跳上來，也可以從i-2個臺階跳上來。所以這兩種方式所擁有的方法數相加就是跳上第i階臺階有的方法數，即$f(i)=f(i?1)+f(i?2)$。看到這個表達式，不就是斐波那契數列么？再求一次斐波那契數列就好了，唯一的區別就是初始條件prepre_f應該初始化為1，pre_f初始化為1。

class Solution(object):def numWays(self, n):""":type n: int:rtype: int"""if n==0:return 1if n==1:return 1prepre_f=1pre_f=1for i in range(2,n+1):f=pre_f+prepre_fprepre_f=pre_fpre_f=freturn f%(10**9+7)

9.面試題11-旋轉數組的最小數字

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為1。

思路1:暴力找一個數組最小o(n)

class Solution(object):def minArray(self, numbers):""":type numbers: List[int]:rtype: int"""n=len(numbers)res=float("INF")for val in numbers:res=min(res,val)return res

思路2:二分查找，初始化l=0，r=len(numbers)，用中點mid=(l+r)//2將數組分成兩個部分。判斷是否兩邊都有序：旋轉點在無序的那一邊

class Solution(object):def minArray(self, numbers):""":type numbers: List[int]:rtype: int"""n=len(numbers)if n==0:return Nonel,r=0,n-1while(l<r):mid=(l+r)//2if numbers[mid]>numbers[r]:  # 右邊無序，旋轉點在右邊，numbers[mid]比右端點都大，最小肯定不是它l=mid+1elif numbers[mid]<numbers[r]: # 右邊有序，最小可能是numbers[mid]r=midelse:r-=1return numbers[r]

10.面試題12-矩陣中的路徑

請設計一個函數，用來判斷在一個矩陣是否存在一條包含某字符串所有字符的路徑。路徑可以總矩陣的任意一個格子開始，每一步可以在矩陣中向左、向右、向上、向下移動一格。如果一條路徑經過了某一格子，那么該路徑不能再次進入該格子。

dfs遞歸遍歷。以每個位子開始，尋找該匹配的字符串。有一個visted矩陣用于記錄哪些格子已經遍歷過了:
保護現場和恢復現場的問題

class Solution(object):def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""m=len(board)if m==0:return Falsen=len(board[0])visted=[]visted=[[False]*n for _ in range(m)]def dfs(string,i,j):if len(string)==1 and string[0]==board[i][j]:return Trueif string[0]==board[i][j]:visted[i][j]=Trueif i-1>-1 and visted[i-1][j]==False:if  dfs(string[1:],i-1,j):return Trueif i+1<m  and visted[i+1][j]==False:if dfs(string[1:],i+1,j):return Trueif j-1>-1 and visted[i][j-1]==False:if dfs(string[1:],i,j-1):return Trueif j+1<n and visted[i][j+1]==False:if dfs(string[1:],i,j+1):return Truevisted[i][j]=Falsereturn Falsefor i in range(m):for j in range(n):if dfs(word,i,j):return Truereturn False