【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)-1
        ans = ""
        flag = 0
        while la>=0 or lb>=0:
            num_a = 1 if (la>=0 and a[la]=="1") else 0
            num_b = 1 if (lb>=0 and b[lb]=="1") else 0
            cur = num_a + num_b + flag
            if cur > 1:
                cur = cur-2
                flag = 1
            else:
                flag = 0
            ans += str(cur)
            if la>=0:
                la -= 1
            if lb>=0:
                lb -= 1
        if 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 = 0
        for i in range(32):
            ans = ans << 1
            ans += n & 1
            n = n >> 1
        return 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 = 0
        for i in range(32):
            if n & 1 :
                ans += 1
            n = n >> 1
        return 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 = 0
        for n in nums:
            ans = ans ^ n
        return 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] += 1
            else:
                ht[n] = 1
        for h in ht:
            if ht[h] == 1:
                return h
# 方法二：模3运算
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a,b = 0,0
        for 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 = 0
        while left < right:
            left = left >> 1
            right = right >> 1
            t += 1
        return 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 False
        num = []
        while x>0:
            n = x % 10
            num.append(n)
            x = x // 10
        left,right = 0,len(num)-1
        while left < right:
            if num[left] != num[right]:
                return False
            left += 1
            right -= 1
        return 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 = 1
        for i in range(l-1,-1,-1):
            digits[i] = digits[i] + t
            if digits[i] > 9:
                digits[i] -= 10
                t = 1
            else:
                t = 0
        if t == 1:
            return [1]+digits
        else:
            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 = 0
        while n>0:
            n = n//5
            ans += n
        return 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+1
        while left < right:
            m = (left+right)//2
            if m*m == x:
                return m
            elif m*m < x:
                left = m+1
            else:
                right = m
        return 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.0
        ans = 1
        if n < 0:
            x,n = 1/x,-n
        while n:
            if n & 1:
                ans *= x
            x *= x
            n = n >> 1
        return 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), 1
        for i, x in enumerate(points):
            for j in range(i + 1, n):
                y = points[j]
                cnt = 2
                for 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 += 1
                ans = 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 1
        dp_0,dp_1 = 1,1
        ans = 0
        for i in range(2,n+1):
            ans = dp_0 + dp_1
            dp_0,dp_1 = dp_1,ans
        return ans

22.2 【动态规划】打家劫舍

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

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

$d p [i] [0]$ 表示第 $i$ 家不被偷，则前一家可能被偷，也可能没有被偷，取最大值即可；
$d p [i] [1]$ 表示第 $i$ 家被偷，则前一家一定没有被偷，所以为 $d p [i - 1] [0] + n u m s [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_0
            dp_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

将 $w or d D i c t$ 中的单词看成一个个的跳跃长度，代表如果首字母匹配上了，一步可以跳多远，那么最远的距离就是 $T r u e$ ，最后只需查看满足了所有跳跃规则之后能否到达字符串 $s$ 的末尾即可。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        l = len(s)
        dp = [False]*(l+1)
        dp[0] = True

        for i in range(l+1):
            if dp[i]:
                for j in range(i+1,l+1):
                    if s[i:j] in wordDict:
                        dp[j] = True
        return dp[-1]

22.4 【动态规划】零钱兑换

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

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

确定 $d p$ 数组以及下标的含义（ $d p [j]$ 为凑齐总额为j的钱币的最小次数）；
确定递推公式（ $d p [j] = min (d p [j], d p [j - co in] + 1)$ ）；
$d p$ 数组如何初始化（ $d p [0]$ 为 $0$ ，剩下的初始化为最大钱币金额 $+ 1$ ）；
确定遍历顺序。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0

        for 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

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

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

# 动态规划
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [1]*l
        dp_max = 1

        for 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 = 0

        for num in nums:
            left,right = 0,ans
            while left < right:
                mid = (left+right) // 2
                if arr[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            arr[left] = num
            if right == ans:
                ans += 1
        return ans

23 多维动态规划

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

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

自底向上进行动态规划，每次都选择下一层的 $k$ 和 $k + 1$ 之间最小的数与该层的数相加，最后返回 $d p [0]$ 即可。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        l = len(triangle)
        dp = [0]*l

        for 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] = 1
                    else:
                        up = dp[i-1][j] if i>0 else 0
                        left = dp[i][j-1] if j>0 else 0
                        dp[i][j] = up + left
        return dp[-1][-1]

23.4 【动态规划】最长回文子串

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

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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        dp = [[0]*l for _ in range(l)]

        max_len = 1
        start = 0
        for j in range(1,l):
            for i in range(j):
                # (j-1)-(i+1) <= 0
                if j-i <= 2:
                    if s[i] == s[j]:
                        dp[i][j] = 1
                        cur_len = j-i+1
                else:
                    if s[i] == s[j] and dp[i+1][j-1]:
                        dp[i][j] = 1
                        cur_len = j-i+1
                if dp[i][j] and cur_len > max_len:
                    max_len = cur_len
                    start = i
        return s[start:start+max_len]

23.5 【动态规划】交错字符串

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

$d p [i] [j]$ 表示 $s_1$ 的前 $i$ 个字符和 $s 2$ 的前 $j$ 个字符能否构成 $s 3$ 的前 $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 False
        dp = [[False]*(l2+1) for _ in range(l1+1)]
        dp[0][0] = True

        for 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])+1
        for 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])+1
        return 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] = 0
        dp[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 = 0
        row = len(matrix)
        col = len(matrix[0])
        # dp[i][j]表示matrix[:i][:j]的正方形最大边长
        dp = [[0]*(col+1) for _ in range(row+1)]

        # 状态转移为在左、上、左上中取最小值+1，因为需要保证正方形内所有元素均为1
        for 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]) + 1
                    max_length = max(max_length,dp[i][j])
        return max_length*max_length