1. 剑指 Offer 42. 连续子数组的最大和


1
2
3
4
5
6
7
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_list=[nums[0]]
        for i in range(1,len(nums)):
            max_list.append(max(max_list[-1],0)+nums[i])
        print(max_list)
        return max(max_list)

2. 剑指 Offer 46. 把数字翻译成字符串


1
2
3
4
5
6
7
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a,b = (b+a if '10'<=s[i-2:i]<='25' else a),a
        return a

3. 剑指 Offer 47. 礼物的最大价值


1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for j in range(1, n): # 初始化第一行
            grid[0][j] += grid[0][j - 1]
        for i in range(1, m): # 初始化第一列
            grid[i][0] += grid[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
        return grid[-1][-1]

4. 剑指 Offer 49. 丑数


1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums,a,b,c = [1]*n,0,0,0
        for i in range(1,n):
            n2,n3,n5 = nums[a]*2,nums[b]*3,nums[c]*5
            nums[i]=min(n2,n3,n5)
            # 前面选择了最小的数作为nums[i]，剩下两个数肯定大于等于它，只要把等于这个数的数往前移一位就行
            if nums[i] == n2: a += 1
            if nums[i] == n3: b += 1
            if nums[i] == n5: c += 1
        return nums[-1]

5. 剑指 Offer 62. 圆圈中最后剩下的数字


1
2
3
4
5
6
7
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        x = 0
        for i in range(2, n + 1):
            x = (x + m) % i
        return x

6.剑指 Offer 63. 股票的最大利润


1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost, profit = float("+inf"), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit

7.剑指 Offer 48. 最长不含重复字符的子字符串


1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1) # 获取索引 i
            dic[s[j]] = j # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res

8. LeetCode 1143. 最长公共子序列

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1,len2 = len(text1)+1,len(text2)+1
        dp = [[0] * len2 for _ in range(len1)]
        for i in range(1,len1):
            for j in range(1,len2):
                c = dp[i-1][j-1]+1 if text1[i-1]== text2[j-1] else dp[i-1][j-1]
                dp[i][j] = max(dp[i-1][j],dp[i][j-1],c)
        return dp[-1][-1]