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

編程語言為python

11.面試題13-機器人的運動范圍-廣度優先搜索

地上有一個m行n列的方格，從坐標[0,0]到坐標[m-1,n-1].一個機器人從坐標[0,0]開始移動，它每一次可以向左右上下移動一格，機器人不能進入行列坐標位數之和大于k的格子（k=18,機器人能夠進入方格[35,37],因為3+5+3+7=18）。請問機器人能夠達到多少個格子。–需要從左上角開始的連續的區域。當一個方向不可以走時，設置一個flag，如果當flag==3時，停止向下遍歷。

廣度優先搜索：將不能走的格子堪稱障礙物，這是一道搜索題，可以使用深度優先或廣度優先來解決。本題隱含條件要求從左上角到右下角的聯通集。（k=1,[10,0]是滿足可走條件，但是機器人首先到不了[9,0].)廣度優先遍歷先將（0，0）放入隊列，判讀是否可達，可達就將它右邊和下邊的格子（下一步備選可達點）坐標[0,1] 和[1,0]放入到隊列中，不斷判斷隊列備選可達的點是否可達。直至隊列為空。（如果一個點不可達，他的右邊下邊就不能從這個點出發達到，但可能可以從其他點出發得到）

class Solution(object):def movingCount(self, m, n, k):""":type m: int:type n: int:type k: int:rtype: int"""def is_available(i,j):sum_ij=0# 取出一個數字每位上的數while(i>0):mod=i%10sum_ij+=modi=(i-mod)/10while(j):mod=j%10sum_ij+=modj=(j-mod)/10if sum_ij<=k:return Trueelse:return Falseres=0que=[(0,0)]visted_dit={}while(que):i,j=que.pop(0)if 0<=i<m and 0<=j<n and is_available(i,j):if not visted_dit.get((i,j)): # 一些已經走過的點需要標記,避免重復遍歷visted_dit[(i,j)]=Trueres+=1que.append((i+1,j))que.append((i,j+1))   return res

12.面試題14-1-剪繩子

給你一根長度為n的繩子，請把繩子堅稱整數長度的m段（n，m都是整數），每段繩子的長度記為k[0],k[1],…,k[m-1]。請問k[0]k[1]…k[m-1]可能的最大乘積是多少。（2 <= n <= 58）
完全背包問題：繩子的長度是背包容量，每次剪掉一段，讓乘積最大嘛。
dp[i]表示長為i的繩子至少切了一次的最大乘積，則dp[i]的更新表達式為：dp[i]=max(dp[i],dp[j]*(i-j),j*(i-j))
dp[j]與j的區別:dp[j]至少剪過一次，j表示一次沒剪。

class Solution(object):def cuttingRope(self, n):""":type n: int:rtype: int"""dp=[0]*(n+1)dp[1]=1for i in range(2,n+1): for j in range(1,i):# print("i:",i,"j:",j,"i-j:",i-j,"dp[j]:",dp[j],dp[j]*(i-j),j*(i-j))dp[i]=max(dp[i],dp[j]*(i-j),j*(i-j))print dpreturn dp[-1]

13.面試題14-2-剪繩子2

本題與上一題題目一致只是輸入數據n的范圍變大了，可能回造成大數越界的問題。之前的dp可能回造成超時或出錯。
（2 <= n <= 1000）
和上一題寫的一毛一樣，勉強過了，擊敗24.73%用戶。

class Solution(object):def cuttingRope(self, n):""":type n: int:rtype: int"""dp=[0]*(n+1)dp[1]=1for i in range(2,n+1): for j in range(1,i):# print("i:",i,"j:",j,"i-j:",i-j,"dp[j]:",dp[j],dp[j]*(i-j),j*(i-j))dp[i]=max(dp[i],dp[j]*(i-j),j*(i-j))return dp[-1]%(10**9+7)

基于數學推到的方案
算術幾何均值不等式：
$$\frac{n_1+n_2+...+n_a}{a}>=\sqrt[a]{n_1{n}_2...n_a}$$
a個數字的算術平均值，大于等于，這a個數的幾何平均值。
a=2時:
$$\frac{n_1+n_2}{2}>=\sqrt[2]{n_1{n}_2}$$
右邊取得最大值的當且僅當$n_1=n_2=,...,n_a$
即可得到推論1:將繩子 以相等的長度 等分多段，得到的乘積最大。

將繩子按照長度x分成a段，$n=ax$,乘積最大為$x^a$(x和a都是變量).因為$a=\frac{n}{x}$,即最大值為：
$$x^a=x^{\frac{n}{x}}=[x^{\frac{1}{x}}{]}^n$$
問題轉換為求上式子的最大值，對上式求導讓其為0，求得極大值點為e。因為切分長度必須為整數，比較x=2,x=3的大小。x=3時$x^{\frac{1}{x}}$更大。
所以推論2為：將繩子盡量分為長度為3的多個等分段時，乘積最大。

綜上：
推論1說的是需要將繩子繩子分為k段，這k段的長度是等分時這個k段的乘積最大。
推論2說的是每段的長度最好是3，對應的等分方式乘積最大。

n的取整依據能不能被3整除，可以分為($n=3a+b$)-確定的方法有貪心選擇的性質：
b=0：最大乘積$3^a$
b=1：前面切出的a段3中拿出一段來，和1湊成長度為4子段，切成22=4>13
b=2：最大值為$3^a?2$

class Solution(object):def cuttingRope(self, n):""":type n: int:rtype: int"""if n<=3:return n-1       # 初始條件n=2 res=1; n=3,res = 2a,b=n//3,n%3res=0if b==0:res=3**aelif b==1:res=3**(a-1)*4else:res=3**(a)*2return res%(10**9+7)

14.面試題16-二進制中1的個數-布萊恩·克尼根

請實現一個函數，輸入一個整數，輸出該數二進制表示中 1 的個數。例如，把 9 表示成二進制是 1001，有 2 位是 1。因此，如果輸入 9，則該函數輸出 2。
（461.漢明距離：兩個數字二進制表示形式的對應位置不同的數目。–將兩個數據取異或，然后統計異或結果的個數）

布萊恩·克尼根算法：利用特定的比特位和算術運算符移除最右邊的1。

class Solution(object):def hammingWeight(self, n):""":type n: int:rtype: int"""res=0while(n):res+=1n=n &(n-1)return res

15.面試題16-數值的整數次方-快速冪解析法

實現函數double Power(double base, int exponent)，求base的exponent次方。不得使用庫函數，同時不需要考慮大數問題。

class Solution(object):def myPow(self, x, n):""":type x: float:type n: int:rtype: float"""res=1if  n<0:flag=-1n*=-1else:flag=1for i in range(n):res*=xreturn res if flag==1 else 1/res

291.304 最后執行輸入：0.00001，2147483647 ，報錯memotyError

參考思路：
快速冪解析法（二進制）：略
快速冪解析法（二分）：$x^n$可以轉換為以下兩種情況：
$x^n=(x^2{)}^{n//2}$ ,n為偶數
$x^n=x(x^2{)}^{n//2}$,n為奇數
可以通過以上操作，將冪從n降到n//2,不斷重復，直至冪將為0.

class Solution(object):def myPow(self, x, n):""":type x: float:type n: int:rtype: float"""if x==0:return 0if n<0:x,n=1/x,-nres=1while(n):if n%2==1:    # n&1res*=xx*=xn=n//2   # n>>=1return res

16.面試題17-打印從1到最大的n位數

輸入數字 n，按順序打印出從 1 到最大的 n 位十進制數。比如輸入 3，則打印出 1、2、3 一直到最大的 3 位數 999。

也不是很明白考察的什么！！！

class Solution(object):def printNumbers(self, n):""":type n: int:rtype: List[int]"""l=10**nres=[]for i in range(1,l):res.append(i)return res

17.面試題18-刪除鏈表的節點

給定單向鏈表的頭指針和一個要刪除的節點的值，定義一個函數刪除該節點。返回刪除后的鏈表的頭節點。
說明：題目保證鏈表中節點的值互不相同

刪除鏈表節點注意dummy節點技巧，避免需要刪除的節點是頭節點。

class Solution(object):def deleteNode(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""dummy=ListNode(0)dummy.next=headpre_node=dummycurr_node =headwhile(curr_node):next_node=curr_node.nextif curr_node.val==val:pre_node.next=next_nodereturn dummy.nextpre_node=curr_nodecurr_node=next_nodereturn dummy.next

18.面試題19-正則匹配-回溯

請實現一個函數用來匹配包含’. ‘和’‘的正則表達式。模式中的字符’.‘表示任意一個字符，而’'表示它前面的字符可以出現任意次（含0次）。在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但與"aa.a"和"ab*a"均不匹配。

回溯方法：如果沒有星號，問題就會很簡單–只需要從左往右檢查匹配串s是否能夠匹配模式串p中的每一字符。
當模式串中有星號時，我們需要檢查匹配串s中的不同后綴，判斷它們是否能匹配模式串中的剩余部分，回溯方法可以用來解決這一類問題。當模式串中的星號出現在pattern[1]的位置時，可以將問題更新為（1）s與pattern[2:]的匹配問題（2）s[1:]與pattern的匹配問題（s[0]與pattern[0]匹配，pattern[1]的星號可以復制patern前面的字符。）

class Solution(object):def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""if not p:return not sfirst_match=bool(s) and  p[0] in {s[0],"."}if len(p)>=2 and p[1]=="*":return (self.isMatch(s,p[2:])) or (first_match and self.isMatch(s[1:],p))else:return first_match and self.isMatch(s[1:],p[1:])

19.面試題20-表示數值的字符串

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

參考思路：有限狀態機器DFA
有限狀態機可以先寫正則表達式，然后轉換成DFA/直接寫，大概率不是最簡的。
有限狀態機：對于每個狀態接收下一個字符，DFA能夠確定一條唯一的轉換路徑，簡單的表驅動的一些方法就能實現，只需要讀一遍輸入流。
真不會寫！！！

20.面試題21-調整數組的順序使得奇數位于偶數的前面-雙指針

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位于數組的前半部分，所有偶數位于數組的后半部分。
暴力法：時間超出限制：15/17

class Solution(object):def exchange(self, nums):""":type nums: List[int]:rtype: List[int]"""n=len(nums)flag=ni=0while(i<flag):if nums[i]%2==0:    for j in range(i,flag-1):nums[j],nums[j+1]=nums[j+1],nums[j]# print(i,j,j+1,nums)flag-=1 # 用于控制已經操作過的偶數,換完可能還是偶數else:i+=1return nums

不要逐個換，直接用右指針指向結尾

class Solution(object):def exchange(self, nums):""":type nums: List[int]:rtype: List[int]"""n=len(nums)flag=n-1i=0while(i<flag):if nums[i]%2==0:    nums[i],nums[flag]=nums[flag],nums[i]flag-=1 # 用于控制已經操作過的偶數,換完可能還是偶數else:i+=1return nums

注意點：換過之后的索引是不增加的。