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

43.面試題43-1～n整數中1出現的次數

輸入一個整數 n ，求1～n這n個整數的十進制表示中1出現的次數。
例如，輸入12，1～12這些整數中包含1 的數字有1、10、11和12，1一共出現了5次。
完全參考：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
分請情況討論某一位中1出現次數的計算方法。

class Solution(object):def countDigitOne(self, n):""":type n: int:rtype: int"""digit,res=1,0high,cur,low=n//10,n%10,0while(high!=0 or cur!=0):if cur==0:res+=high*digitelif cur==1:res+=high*digit+low+1else:res+=(high+1)*digitlow+=cur*digitcur=high%10high=high//10digit*=10return res

44.面試題44-數字序列中某一位的數字

數字以0123456789101112131415…的格式序列化到一個字符序列中。在這個序列中，第5位（從下標0開始計數）是5，第13位是1，第19位是4，等等。
請寫一個函數，求任意第n位對應的數字。
思路：尋找n 與對應數字的關系，應該有對應的公式規律。
數字：num=123
數字中一位數的數量：n=3
一個數字的位數：digit，123為3位數，dight=3
digit 位數的起始數字：1，10，100，記為start

數字范圍$start?end$以上三個量的遞推公式為：
digit=digit+1
start=start10
count=9start*dight

求解可以分為三步：
1.確定n所在的數字的位數，記為digit
2.確定n所在的數字，記為num
3.確定n是num中的哪一位，并返回結果

class Solution(object):def findNthDigit(self, n):""":type n: int:rtype: int"""digit,start,count=1,1,9# 1.計算n所在的位數區間[1-9]是一位數一共9個，[10,99]兩位數一共90個while(n>count):n-=countstart*=10digit+=1count=9*start*digit# 計算在該開始區間內所對應的數字num=start+(n-1)//digit# 確定是數字的哪一位index=(n-1)%digitreturn int(str(num)[index])

45.面試題45-把數組排成最小的數-快排變種

輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。
問題：能拼接的數字很多么？找最小的一個

[10,2] 可以拼接成102，210，明顯102最小

本質是一個排序問題：排序的目的是使得量級最小的數字排在最前面，使得最后按順序拼接的時候，拼接的數字最小.

10,5兩個數字誰在前？按位數來比較，如果放了5，組成的3位數以5開頭，所以不能放5，所以應該先放10
總之就是按位排序，誰小誰先放（數字左對齊比較，看看誰小，先比的數字對比較結果起決定性作用）

比如30和3，30的量級比3小，30應該在3前面。將數字轉換成字符串，拼接后比較：（“30”+“3”=“303”）<(“3”+“30”)=>“30”<“3”

改造快排排序規則：

class Solution(object):def minNumber(self, nums):""":type nums: List[int]:rtype: str"""def quick_sort_str(l,r,data):if l<r:p=patition(l,r,data)quick_sort_str(l,p-1,data)quick_sort_str(p+1,r,data)def patition(i,j,data):pivort=data[i]while(i<j):while(i<j and data[j]+pivort>pivort+data[j]): # 比較規則需要修改j-=1data[i]=data[j]while(i<j and data[i]+pivort<=pivort+data[i]):i+=1data[j]=data[i]data[i]=pivortreturn inums_str=[]for val in nums:nums_str.append(str(val))quick_sort_str(0,len(nums_str)-1,nums_str)res=""for char in nums_str:res+=charreturn res

46.面試題46-把數字翻譯成字符串

給定一個數字，我們按照如下規則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l”，……，25 翻譯成 “z”。一個數字可能有多個翻譯。請編程實現一個函數，用來計算一個數字有多少種不同的翻譯方法。
dp[i] 表示nums[0]-nums[i-1] 能夠翻譯成的數字總數
dp 由前面的狀態推導后面的狀態。

這題有點類似與爬樓梯

class Solution(object):def translateNum(self, num):""":type num: int:rtype: int"""num_lis=[]while(num):num_lis.append(num%10)num//=10num_lis.reverse()n=len(num_lis)if n<2:return 1dp=[0]*(n+1)dp[0]=1dp[1]=1for i in range(2,n+1):val=10*num_lis[i-2]+ num_lis[i-1]    # 此位置和下一位置構成的數字[0,9],[10,15],[25,99]if 0<=val<10 or 26<=val<=99:     # 09,26,  nums[i]自己翻譯，只有一種翻譯方式dp[i]=dp[i-1]if 10<=val <26:                  # num=12, 2自己單獨翻譯，12一起翻譯， dp[i]=dp[i-1]+dp[i-2]return dp[-1]

47.面試題47-禮物的最大價值-dp

在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角。給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

遞歸所有的路徑，時間超出限制（20/61）。最值問題，應該有最有子結構。

class Solution(object):def __init__(self):self.res=0def maxValue(self, grid):""":type grid: List[List[int]]:rtype: int"""m=len(grid)n=len(grid[0])def dfs(i,j,val):if i>=m or j>=n:return val+=grid[i][j]if i==m-1 and j==n-1:self.res=max(self.res,val)return # 要不要return 呢dfs(i+1,j,val)dfs(i,j+1,val)dfs(0,0,0)return self.res

動態規劃解題：dp[i][j]到單元格(i,j) 的最大價值。

48.面試題48-最長不含重復字符的子字符串-滑動窗口法

請從字符串中找出一個最長的不包含重復字符的子字符串，計算該最長子字符串的長度。
滑動窗口法：[l,r] 中有一個hash表，統計每個字符的個數，當存在時，窗口變小，直至個數減為1.
再移動右端。

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""win={}left,right=0,0res=0m=len(s)while(right<m):c1=s[right]if win.get(c1)==None:win[c1]=1else:win[c1]+=1right+=1while(win[c1]>1):c2=s[left]win[c2]-=1left+=1res=max(res,right-left) # 上面right+ 了1，所以直接減去return res

49.面試題49-丑數-自底向上遞歸

我們把只包含質因子 2、3 和 5 的數稱作丑數（Ugly Number）。求按從小到大的順序的第 n 個丑數。（質因子：因子是質數）
說明:
1 是丑數。
n 不超過1690。
思路：丑數的遞歸性質，丑數只包含質因子2，3，5，因此 丑數=某較小的丑數*某因子
暴力解法：時間超出限制404/595

class Solution(object):def nthUglyNumber(self, n):""":type n: int:rtype: int"""i=1num=1isun_hash={1:True,2:True,3:True,5:True}def is_UN(num):for val in [2,3,5]:if num%val==0 and isun_hash.get(num//val):return Truereturn Falsewhile(i<n):num+=1if is_UN(num) :isun_hash[num]=Truei+=1# print(i,num)return num

動態規劃： 設動態規劃列表 dp ，dp[i]代表第 i + 1個丑數。
利用狀態更新求解dp[n-1] 即可。
用a,b,c 三個索引指向num[a]*2,nums[b]*3,nums[c]*5第一次超過dp[i-1]索引，dp[i] 就更新為最小的那個數。將a,b,c初始化為0，0，0，依次填充dp 序列

class Solution(object):def nthUglyNumber(self, n):""":type n: int:rtype: int"""dp=[1]*na,b,c=0,0,0for i in range(1,n):n2,n3,n5=dp[a]*2,dp[b]*3,dp[c]*5   dp[i]=min(n2,n3,n5)if dp[i]==n2:  # 只能用if ,n2,n3,n5可能會相等，這時需要同時更新下標a+=1if dp[i]==n3:b+=1if dp[i]==n5:c+=1return dp[-1]

50.面試題50-第一個只出現一次的字符-hash表

在字符串 s 中找出第一個只出現一次的字符。如果沒有，返回一個單空格。 s 只包含小寫字母。

class Solution(object):def firstUniqChar(self, s):""":type s: str:rtype: str"""win_hash={}for char in s:if win_hash.get(char)==None:win_hash[char]=1else:win_hash[char]+=1for char in s: # 重新遍歷一遍，使得返回的字符是最左邊第一個出現的字符串if win_hash.get(char)==1:return charreturn " "

51.面試題52-兩個鏈表的第一個公共節點-雙指針技巧

輸入兩個鏈表，找出它們的第一個公共節點。
雙指針技巧
注意點：先判斷兩個鏈表是否相交，如果相交，在尋找交點

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""if headA==None or headB==None:return Nonepa,pb=headA,headBwhile(pa.next):pa=pa.nextwhile(pb.next):pb=pb.nextif pa!=pb:return Noneelse:pa,pb=headA,headBwhile(pa!=pb):if pa.next:pa=pa.nextelse:pa=headBif pb.next:pb=pb.nextelse:pb=headAreturn  pa

52.面試題53-在排序數組中找數字

統計一個數字在排序數組中出現的次數。
暴力求解：通過了！！

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""res=0for num in nums:if num==target:res+=1return res

大佬說還可以用二分法做。

54.面試題53-2-0～n-1中的缺失數字–二分

一個長度為n-1的遞增排序數組中的所有數字都是唯一的，并且每個數字都在范圍0～n-1之內。在范圍0～n-1內的n個數字中有且只有一個數字不在該數組中，請找出這個數字。
[0,1,3],n=4,l=4-1=3,數字范圍[0,3] 一共n 中情況.
缺失數字的左邊：nums[i]==i
缺失數字的位置上：nums[i]!=i
暴力：

class Solution(object):def missingNumber(self, nums):""":type nums: List[int]:rtype: int"""l=len(nums)for i in range(l):if nums[i]!=i:return ireturn l

二分查找：

class Solution(object):def missingNumber(self, nums):""":type nums: List[int]:rtype: int"""l=len(nums)i,j=0,l-1while(i<=j):      # 搜索到i>j的那個點就缺失點mid=(i+j)//2if nums[mid]==mid:i=mid+1   # 左邊沒有缺失else:j=mid-1   # 缺失已經發生，在左半段return i