20 位運(yùn)算

20.1 【位運(yùn)算】二進(jìn)制求和

題目地址：https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2&envId=top-interview-150

??按位逆序運(yùn)算。

class Solution:def addBinary(self, a: str, b: str) -> str:la,lb = len(a)-1,len(b)-1ans = ""flag = 0while la>=0 or lb>=0:num_a = 1 if (la>=0 and a[la]=="1") else 0num_b = 1 if (lb>=0 and b[lb]=="1") else 0cur = num_a + num_b + flagif cur > 1:cur = cur-2flag = 1else:flag = 0ans += str(cur)if la>=0:la -= 1if lb>=0:lb -= 1if flag:ans += "1"ans = ans[::-1]return ans

20.2 【位運(yùn)算】顛倒二進(jìn)制位

題目地址：https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼。

class Solution:def reverseBits(self, n: int) -> int:ans = 0for i in range(32):ans = ans << 1ans += n & 1n = n >> 1return ans

20.3 【位運(yùn)算】位1的個(gè)數(shù)

題目地址：https://leetcode.cn/problems/number-of-1-bits/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼。

class Solution:def hammingWeight(self, n: int) -> int:ans = 0for i in range(32):if n & 1 :ans += 1n = n >> 1return ans

20.4 【位運(yùn)算】只出現(xiàn)一次的數(shù)字

題目地址：https://leetcode.cn/problems/single-number/description/?envType=study-plan-v2&envId=top-interview-150

??異或操作。

class Solution:def singleNumber(self, nums: List[int]) -> int:ans = 0for n in nums:ans = ans ^ nreturn ans

20.5 【哈希表】【位運(yùn)算】只出現(xiàn)一次的數(shù)字 II

題目地址：https://leetcode.cn/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150

??方法一：哈希表

??方法二：模3運(yùn)算

# 方法一：哈希表
class Solution:def singleNumber(self, nums: List[int]) -> int:ht = {}for n in nums:if n in ht:ht[n] += 1else:ht[n] = 1for h in ht:if ht[h] == 1:return h
# 方法二：模3運(yùn)算
class Solution:def singleNumber(self, nums: List[int]) -> int:a,b = 0,0for n in nums:b = (b^n)&(~a)a = (a^n)&(~b)return b

20.6 【位運(yùn)算】數(shù)字范圍按位與

題目地址：https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150

??找公共前綴。

class Solution:def rangeBitwiseAnd(self, left: int, right: int) -> int:t = 0while left < right:left = left >> 1right = right >> 1t += 1return left << t

21 數(shù)學(xué)

21.1 【雙指針】回文數(shù)

題目地址：https://leetcode.cn/problems/palindrome-number/description/?envType=study-plan-v2&envId=top-interview-150

??將數(shù)字的每一位取出來，然后雙指針前后分別判斷是否相等。

class Solution:def isPalindrome(self, x: int) -> bool:if x < 0:return Falsenum = []while x>0:n = x % 10num.append(n)x = x // 10left,right = 0,len(num)-1while left < right:if num[left] != num[right]:return Falseleft += 1right -= 1return True

21.2 【數(shù)學(xué)】加一

題目地址：https://leetcode.cn/problems/plus-one/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼。

class Solution:def plusOne(self, digits: List[int]) -> List[int]:l = len(digits)t = 1for i in range(l-1,-1,-1):digits[i] = digits[i] + tif digits[i] > 9:digits[i] -= 10t = 1else:t = 0if t == 1:return [1]+digitselse:return digits

21.3 【數(shù)學(xué)】階乘后的零

題目地址：https://leetcode.cn/problems/factorial-trailing-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

??統(tǒng)計(jì)因子中5的個(gè)數(shù)即可。

class Solution:def trailingZeroes(self, n: int) -> int:ans = 0while n>0:n = n//5ans += nreturn ans

21.4 【二分】69. x 的平方根

題目地址：https://leetcode.cn/problems/sqrtx/description/?envType=study-plan-v2&envId=top-interview-150

??二分查找。

class Solution:def mySqrt(self, x: int) -> int:left,right = 0,x+1while left < right:m = (left+right)//2if m*m == x:return melif m*m < x:left = m+1else:right = mreturn left-1

21.5 【快速冪】50. Pow(x, n)

題目地址：https://leetcode.cn/problems/powx-n/description/?envType=study-plan-v2&envId=top-interview-150

??快速冪。

class Solution:def myPow(self, x: float, n: int) -> float:if x == 0.0:return 0.0ans = 1if n < 0:x,n = 1/x,-nwhile n:if n & 1:ans *= xx *= xn = n >> 1return ans

21.6 【暴力】直線上最多的點(diǎn)數(shù)

題目地址：https://leetcode.cn/problems/max-points-on-a-line/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼。

class Solution:def maxPoints(self, points: List[List[int]]) -> int:n, ans = len(points), 1for i, x in enumerate(points):for j in range(i + 1, n):y = points[j]cnt = 2for k in range(j + 1, n):p = points[k]s1 = (y[1] - x[1]) * (p[0] - y[0])s2 = (p[1] - y[1]) * (y[0] - x[0])if s1 == s2: cnt += 1ans = max(ans, cnt)return ans

22 一維動(dòng)態(tài)規(guī)劃

22.1 【動(dòng)態(tài)規(guī)劃】爬樓梯

題目地址：https://leetcode.cn/problems/climbing-stairs/?envType=study-plan-v2&envId=top-interview-150

??斐波那契數(shù)列求值。

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return 1dp_0,dp_1 = 1,1ans = 0for i in range(2,n+1):ans = dp_0 + dp_1dp_0,dp_1 = dp_1,ansreturn ans

22.2 【動(dòng)態(tài)規(guī)劃】打家劫舍

題目地址：https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-interview-150

利用動(dòng)態(tài)規(guī)劃，首先定義數(shù)組$dp[i][2]$，狀態(tài)轉(zhuǎn)移如下所示：

• $dp[i][0]$表示第$i$家不被偷，則前一家可能被偷，也可能沒有被偷，取最大值即可；
• $dp[i][1]$表示第$i$家被偷，則前一家一定沒有被偷，所以為$dp[i?1][0]+nums[i]$。

最后在第$i$家的時(shí)候取被偷和未被偷之間的最大值即可。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)dp_0,dp_1 = 0,nums[0]for i in range(1,n):last_0 = dp_0dp_0 = max(dp_0,dp_1)dp_1 = last_0 + nums[i]return max(dp_0,dp_1)

22.3 【動(dòng)態(tài)規(guī)劃】單詞拆分

題目地址：https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150

??將$wordDict$中的單詞看成一個(gè)個(gè)的跳躍長(zhǎng)度，代表如果首字母匹配上了，一步可以跳多遠(yuǎn)，那么最遠(yuǎn)的距離就是$True$，最后只需查看滿足了所有跳躍規(guī)則之后能否到達(dá)字符串$s$的末尾即可。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:l = len(s)dp = [False]*(l+1)dp[0] = Truefor i in range(l+1):if dp[i]:for j in range(i+1,l+1):if s[i:j] in wordDict:dp[j] = Truereturn dp[-1]

22.4 【動(dòng)態(tài)規(guī)劃】零錢兌換

題目地址：https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

??動(dòng)態(tài)規(guī)劃題目的基本做題策略：

• 確定$dp$數(shù)組以及下標(biāo)的含義（$dp[j]$為湊齊總額為j的錢幣的最小次數(shù)）；
• 確定遞推公式（$dp[j]=min(dp[j],dp[j?coin]+1)$）；
• $dp$數(shù)組如何初始化（$dp[0]$為$0$，剩下的初始化為最大錢幣金額$+1$）；
• 確定遍歷順序。

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [amount+1]*(amount+1)dp[0] = 0for j in range(1,amount+1):for coin in coins:if j >= coin:dp[j] = min(dp[j],dp[j-coin]+1)if dp[amount] < amount+1:return dp[amount]else:return -1

22.5 【動(dòng)態(tài)規(guī)劃】【二分】最長(zhǎng)遞增子序列

題目地址：https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

??方法一：動(dòng)態(tài)規(guī)劃，構(gòu)造$dp[i]$表示$i$索引為序列末尾元素的最長(zhǎng)序列長(zhǎng)度。

??方法二：二分查找，維護(hù)一個(gè)遞增序列$arr$，遍歷時(shí)取小的放入序列中，最后返回序列長(zhǎng)度。

# 動(dòng)態(tài)規(guī)劃
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:l = len(nums)dp = [1]*ldp_max = 1for i in range(1,l):for j in range(0,i):if nums[j] < nums[i]:dp[i] = max(dp[i],dp[j]+1)dp_max = max(dp_max,dp[i])return dp_max# 二分查找
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:arr = [0]*len(nums)ans = 0for num in nums:left,right = 0,answhile left < right:mid = (left+right) // 2if arr[mid] < num:left = mid + 1else:right = midarr[left] = numif right == ans:ans += 1return ans

23 多維動(dòng)態(tài)規(guī)劃

23.1 【動(dòng)態(tài)規(guī)劃】三角形最小路徑和

題目地址：https://leetcode.cn/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150

??自底向上進(jìn)行動(dòng)態(tài)規(guī)劃，每次都選擇下一層的$k$和$k+1$之間最小的數(shù)與該層的數(shù)相加，最后返回$dp[0]$即可。

class Solution:def minimumTotal(self, triangle: List[List[int]]) -> int:l = len(triangle)dp = [0]*lfor i in range(len(triangle[-1])):dp[i] = triangle[-1][i]for j in range(l-2,-1,-1):for k in range(j+1):dp[k] = min(dp[k],dp[k+1]) + triangle[j][k]return dp[0]

23.2 【動(dòng)態(tài)規(guī)劃】最小路徑和

題目地址：https://leetcode.cn/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150

??每次遍歷時(shí)找出兩個(gè)步驟的最小值，然后相加，也是自頂向下的思路。

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:row = len(grid)col = len(grid[0])for i in range(1,col):grid[0][i] += grid[0][i-1]for j in range(1,row):grid[j][0] += grid[j-1][0]for i in range(1,row):for j in range(1,col):grid[i][j] += min(grid[i][j-1],grid[i-1][j])return grid[row-1][col-1]

23.3 【動(dòng)態(tài)規(guī)劃】不同路徑 II

題目地址：https://leetcode.cn/problems/unique-paths-ii/description/?envType=study-plan-v2&envId=top-interview-150

??計(jì)算可以走到每個(gè)格子的路線數(shù)，最后相加。

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:row = len(obstacleGrid)col = len(obstacleGrid[0])dp = [[0]*col for _ in range(row)]for i in range(row):for j in range(col):if not obstacleGrid[i][j]:if i == j == 0:dp[i][j] = 1else:up = dp[i-1][j] if i>0 else 0left = dp[i][j-1] if j>0 else 0dp[i][j] = up + leftreturn dp[-1][-1]

23.4 【動(dòng)態(tài)規(guī)劃】最長(zhǎng)回文子串

題目地址：https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-interview-150

??$dp[i][j]$表示$s[i:j+1]$是否為回文子串，狀態(tài)轉(zhuǎn)移的思路是，如果$dp[i+1][j?1]$為$True$并且$s[i]==s[j]$的話，那么$dp[i][j]$也為$True$，在每個(gè)為$True$的情況下記錄此時(shí)字符串的長(zhǎng)度，同時(shí)更新初始坐標(biāo)，最后選擇最長(zhǎng)的子串即可。

class Solution:def longestPalindrome(self, s: str) -> str:l = len(s)dp = [[0]*l for _ in range(l)]max_len = 1start = 0for j in range(1,l):for i in range(j):# (j-1)-(i+1) <= 0if j-i <= 2:if s[i] == s[j]:dp[i][j] = 1cur_len = j-i+1else:if s[i] == s[j] and dp[i+1][j-1]:dp[i][j] = 1cur_len = j-i+1if dp[i][j] and cur_len > max_len:max_len = cur_lenstart = ireturn s[start:start+max_len]

23.5 【動(dòng)態(tài)規(guī)劃】交錯(cuò)字符串

題目地址：https://leetcode.cn/problems/interleaving-string/description/?envType=study-plan-v2&envId=top-interview-150

??$dp[i][j]$表示$s_1$的前$i$個(gè)字符和$s2$的前$j$個(gè)字符能否構(gòu)成$s3$的前$i+j$個(gè)字符。

class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:l1 = len(s1)l2 = len(s2)l3 = len(s3)if l1 + l2 != l3:return Falsedp = [[False]*(l2+1) for _ in range(l1+1)]dp[0][0] = Truefor i in range(1,l1+1):dp[i][0] = (dp[i-1][0] and s1[i-1]==s3[i-1])for i in range(1,l2+1):dp[0][i] = (dp[0][i-1] and s2[i-1]==s3[i-1])for i in range(1,l1+1):for j in range(1,l2+1):dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])return dp[-1][-1]

23.6 【動(dòng)態(tài)規(guī)劃】編輯距離

題目地址：https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼注釋。

class Solution:def minDistance(self, word1: str, word2: str) -> int:l1 = len(word1)l2 = len(word2)# 初始化dp，dp[i][j]表示從word1[:i]到word2[:j]所需要轉(zhuǎn)換的次數(shù)dp = [[0]*(l2+1) for _ in range(l1+1)]# 此時(shí)word2為空，則word1需要轉(zhuǎn)換的次數(shù)為此時(shí)的長(zhǎng)度for i in range(l1+1):dp[i][0] = i# 此時(shí)word2為空，則word1需要轉(zhuǎn)換的次數(shù)為此時(shí)的長(zhǎng)度for j in range(l2+1):dp[0][j] = j# 首先判斷i和j索引處的字符是否相同，如果相同，則dp[i][j]=dp[i-1][j-1]# 否則不管是刪除還是替換，都會(huì)在之前的基礎(chǔ)上改變一位字符，# 則dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1for i in range(1,l1+1):for j in range(1,l2+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1return dp[-1][-1]

23.7 【三維dp】買賣股票的最佳時(shí)機(jī) III

題目地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼注釋。

class Solution:def maxProfit(self, prices: List[int]) -> int:l = len(prices)# dp[第幾天][是否持有股票][已經(jīng)賣了幾次股票]dp = [[[0,0,0],[0,0,0]] for _ in range(l)]# 第一天初始化dp[0][0][0] = 0dp[0][0][1] = -float('inf')dp[0][0][2] = -float('inf')dp[0][1][0] = -prices[0]dp[0][1][1] = -float('inf')dp[0][1][2] = -float('inf')# 接下來幾天狀態(tài)更新for i in range(1,l):# 未持有股票，已經(jīng)賣了0次股票dp[i][0][0] = 0# 未持有股票，已經(jīng)賣了1次股票：可能是今天賣的，也可能是前幾天賣的dp[i][0][1] = max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])# 未持有股票，已經(jīng)賣了2次股票：可能是今天賣的，也可能是前幾天賣的dp[i][0][2] = max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])# 已持有股票，已經(jīng)賣了0次股票：可能是今天買的，也可能是前幾天買的dp[i][1][0] = max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])# 已持有股票，已經(jīng)賣了1次股票：可能是今天買的，也可能是前幾天買的dp[i][1][1] = max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])# 已持有股票，已經(jīng)賣了2次股票dp[i][1][2] = -float('inf')return max(dp[l-1][0][1],dp[l-1][0][2],0)

23.8 【三維dp】買賣股票的最佳時(shí)機(jī) IV

題目地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼注釋。

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:# dp[第幾天][已經(jīng)完成幾筆交易][是否持股]l = len(prices)dp = [[[0]*2 for _ in range(k+1)] for _ in range(l)]for i in range(1,k+1):dp[0][i][1] = -prices[0]for i in range(1,l):for j in range(1,k+1):# 未持股：今天賣掉了，或者昨天也未持股dp[i][j][0] = max(dp[i-1][j][1]+prices[i],dp[i-1][j][0])# 持股：今天買入股票，或者昨天持股dp[i][j][1] = max(dp[i-1][j-1][0]-prices[i],dp[i-1][j][1])return dp[l-1][k][0]

23.9 【二維dp】最大正方形

題目地址：https://leetcode.cn/problems/maximal-square/submissions/515490547/?envType=study-plan-v2&envId=top-interview-150

??詳見代碼注釋。

class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:max_length = 0row = len(matrix)col = len(matrix[0])# dp[i][j]表示matrix[:i][:j]的正方形最大邊長(zhǎng)dp = [[0]*(col+1) for _ in range(row+1)]# 狀態(tài)轉(zhuǎn)移為在左、上、左上中取最小值+1，因?yàn)樾枰ＷC正方形內(nèi)所有元素均為1for i in range(1,row+1):for j in range(1,col+1):if matrix[i-1][j-1] == "1":dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1max_length = max(max_length,dp[i][j])return max_length*max_length