【leetcode刷题之路】面试经典150题（8）——位运算+数学+一维动态规划+多维动态规划

20 位运算

20.1 【位运算】二进制求和

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

  按位逆序运算。

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 【位运算】颠倒二进制位

题目地址：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 【位运算】位1的个数

题目地址：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 【位运算】只出现一次的数字

题目地址：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 【哈希表】【位运算】只出现一次的数字 II

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

  方法一：哈希表

  方法二：模3运算

# 方法一：哈希表
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运算
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 【位运算】数字范围按位与

题目地址：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 数学

21.1 【双指针】回文数

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

  将数字的每一位取出来，然后双指针前后分别判断是否相等。

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 【数学】加一

题目地址：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 【数学】阶乘后的零

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

  统计因子中5的个数即可。

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 【暴力】直线上最多的点数

题目地址：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 一维动态规划

22.1 【动态规划】爬楼梯

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

  斐波那契数列求值。

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 【动态规划】打家劫舍

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

利用动态规划，首先定义数组$dp[i][2]$，状态转移如下所示：

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

最后在第$i$家的时候取被偷和未被偷之间的最大值即可。

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 【动态规划】单词拆分

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

  将$wordDict$中的单词看成一个个的跳跃长度，代表如果首字母匹配上了，一步可以跳多远，那么最远的距离就是$True$，最后只需查看满足了所有跳跃规则之后能否到达字符串$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 【动态规划】零钱兑换

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

  动态规划题目的基本做题策略：

• 确定$dp$数组以及下标的含义（$dp[j]$为凑齐总额为j的钱币的最小次数）；
• 确定递推公式（$dp[j]=min(dp[j],dp[j-coin]+1)$）；
• $dp$数组如何初始化（$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 【动态规划】【二分】最长递增子序列

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

  方法一：动态规划，构造$dp[i]$表示$i$索引为序列末尾元素的最长序列长度。

  方法二：二分查找，维护一个递增序列$arr$，遍历时取小的放入序列中，最后返回序列长度。

# 动态规划
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 多维动态规划

23.1 【动态规划】三角形最小路径和

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

  自底向上进行动态规划，每次都选择下一层的$k$和$k+1$之间最小的数与该层的数相加，最后返回$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 【动态规划】最小路径和

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

  每次遍历时找出两个步骤的最小值，然后相加，也是自顶向下的思路。

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 【动态规划】不同路径 II

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

  计算可以走到每个格子的路线数，最后相加。

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 【动态规划】最长回文子串

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

  $dp[i][j]$表示$s[i:j+1]$是否为回文子串，状态转移的思路是，如果$dp[i+1][j-1]$为$True$并且$s[i]==s[j]$的话，那么$dp[i][j]$也为$True$，在每个为$True$的情况下记录此时字符串的长度，同时更新初始坐标，最后选择最长的子串即可。

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 【动态规划】交错字符串

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

  $dp[i][j]$表示$s_1$的前$i$个字符和$s2$的前$j$个字符能否构成$s3$的前$i+j$个字符。

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 【动态规划】编辑距离

题目地址：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]所需要转换的次数dp = [[0]*(l2+1) for _ in range(l1+1)]# 此时word2为空，则word1需要转换的次数为此时的长度for i in range(l1+1):dp[i][0] = i# 此时word2为空，则word1需要转换的次数为此时的长度for j in range(l2+1):dp[0][j] = j# 首先判断i和j索引处的字符是否相同，如果相同，则dp[i][j]=dp[i-1][j-1]# 否则不管是删除还是替换，都会在之前的基础上改变一位字符，# 则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】买卖股票的最佳时机 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[第几天][是否持有股票][已经卖了几次股票]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')# 接下来几天状态更新for i in range(1,l):# 未持有股票，已经卖了0次股票dp[i][0][0] = 0# 未持有股票，已经卖了1次股票：可能是今天卖的，也可能是前几天卖的dp[i][0][1] = max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])# 未持有股票，已经卖了2次股票：可能是今天卖的，也可能是前几天卖的dp[i][0][2] = max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])# 已持有股票，已经卖了0次股票：可能是今天买的，也可能是前几天买的dp[i][1][0] = max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])# 已持有股票，已经卖了1次股票：可能是今天买的，也可能是前几天买的dp[i][1][1] = max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])# 已持有股票，已经卖了2次股票dp[i][1][2] = -float('inf')return max(dp[l-1][0][1],dp[l-1][0][2],0)

23.8 【三维dp】买卖股票的最佳时机 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[第几天][已经完成几笔交易][是否持股]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]的正方形最大边长dp = [[0]*(col+1) for _ in range(row+1)]# 状态转移为在左、上、左上中取最小值+1，因为需要保证正方形内所有元素均为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