Fork me on GitHub
image frame

EightyNinth

力扣 85. 最大矩形

leetcode

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def maximalRectangle(matrix):
    if len(matrix) < 1 or len(matrix[0]) < 1:
        return 0
    
    m, n = len(matrix), len(matrix[0])

    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if j == 0 and matrix[i][j] == "1":
                dp[i][j] = 1
            elif matrix[i][j] == "0":
                dp[i][j] = 0
            elif matrix[i][j] == "1":
                dp[i][j] = dp[i][j - 1] + 1
    # print(dp)
    # 可转化为84. 柱状图中最大的矩形
    ret = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "0":
                continue
            width, area = dp[i][j], dp[i][j]
            for k in range(i - 1, -1, -1):
                width = min(width, dp[k][j])
                area = max(area, (i - k + 1) * width)
            ret = max(ret, area)
    return ret

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def maximalRectangle(matrix):
    if len(matrix) < 1 or len(matrix[0]) < 1:
        return 0
    
    m, n = len(matrix), len(matrix[0])

    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if j == 0 and matrix[i][j] == "1":
                dp[i][j] = 1
            elif matrix[i][j] == "0":
                dp[i][j] = 0
            elif matrix[i][j] == "1":
                dp[i][j] = dp[i][j - 1] + 1
    # print(dp)
    # 可转化为84. 柱状图中最大的矩形
    ret = 0
    for j in range(n):
        left, right = [0] * m, [0] * m

        tmp = []
        for i in range(m):
            while tmp and dp[tmp[-1]][j] >= dp[i][j]:
                tmp.pop()
            left[i] = tmp[-1] if tmp else -1
            tmp.append(i)
        tmp = []
        for i in range(m - 1, -1, -1):
            while tmp and dp[tmp[-1]][j] >= dp[i][j]:
                tmp.pop()
            right[i] = tmp[-1] if tmp else m
            tmp.append(i)
        
        for i in range(m):
            ret = max(ret, (right[i] - left[i] - 1) * dp[i][j])
        
    return ret

力扣 84. 柱状图中最大的矩形

leetcode

双指针 + 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def largestRectangleArea(heights):
    # 类似接雨水
    res, h_len = 0, len(heights)
    dp_left, dp_right = [i for i in range(h_len)], [i for i in range(h_len)]
    for i in range(1, h_len):
        while dp_left[i] > 0 and heights[i] <= heights[dp_left[i] - 1]:
            dp_left[i] = dp_left[dp_left[i] - 1]
    # print(dp_left)
    for i in range(h_len - 2, -1, -1):
        while dp_right[i] < h_len - 1 and heights[i] <= heights[dp_right[i] + 1]:
            dp_right[i] = dp_right[dp_right[i] + 1]
    # print(dp_right)
    for i in range(h_len):
        res = max(res, (dp_right[i] - dp_left[i] + 1) * heights[i])
    return res

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestRectangleArea(heights):
    # 类似接雨水
    res, h_len = 0, len(heights)
    left, right = [0] * h_len, [0] * h_len

    tmp = []
    for i in range(h_len):
        while tmp and heights[tmp[-1]] >= heights[i]:
            tmp.pop()
        left[i] = tmp[-1] if tmp else -1
        tmp.append(i)
    tmp = []
    # print(left)
    for i in range(h_len - 1, -1, -1):
        while tmp and heights[tmp[-1]] >= heights[i]:
            tmp.pop()
        right[i] = tmp[-1] if tmp else h_len
        tmp.append(i)
    # print(right)
    for i in range(h_len):
        res = max(res, (right[i] - left[i] - 1) * heights[i])
    return res

力扣 79. 单词搜索

leetcode

回溯思想 + dfs 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def exist(board, word):
    def dfs(i, j, k):
        # 首先判断完成匹配与否
        if k == s_len:
            return True
        # 判断是否在数组内
        if i >= m or j >= n or i < 0 or j < 0:
            return False
        # 判断是否匹配过
        if dp[i][j] == True:
            return False
        # 判断是否匹配得上
        if board[i][j] != word[k]:
            return False 
        # 标记当前路线已匹配
        dp[i][j] = True
        # 匹配上了
        if dfs(i - 1, j, k + 1) or dfs(i + 1, j, k + 1) or dfs(i, j - 1, k + 1) or dfs(i, j + 1, k + 1):
            return True
        # 准备下一路线匹配
        dp[i][j] = False
        # 没匹配上
        return False
        
    m, n = len(board), len(board[0])
    dp = [[False] * n for _ in range(m)]
    k, s_len = 0, len(word)

    # 寻找起始点
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                # 找到起始点后, dfs
                if dfs(i, j, 0):
                    return True
    return False

力扣 78. 子集

leetcode

回溯思想 + dfs实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def subsets(nums):
    def dfs(i, tmp):
        if i >= n_len:
            return

        tmp.append(nums[i])
        res.append(tmp)

        for j in range(i + 1, n_len):
            dfs(j, tmp.copy())

        
    n_len = len(nums)
    res = [[]]
    for i in range(n_len):
        dfs(i, [])
    
    return res

力扣 76. 最小覆盖子串

leetcode

hash表 + 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minWindow(s, t):
    if len(s) < len(t):
        return ""
    # 构建hash表
    hash_t, hash_s, count = {}, {}, 0
    for c in t:
        hash_t[c] = hash_t.get(c, 0) + 1
    
    j, t_len, res = 0, len(t), ""
    for i in range(len(s)):
        hash_s[s[i]] = hash_s.get(s[i], 0) + 1
        if hash_s[s[i]] <= hash_t.get(s[i], 0):
            count += 1
        while j <= i and hash_s.get(s[j], 0) > hash_t.get(s[j], 0):
            hash_s[s[j]] -= 1
            j += 1
        if count == t_len:
            if not res or i - j + 1 < len(res):
                res = s[j: i + 1]
    return res

力扣 75. 颜色分类

leetcode

双指针 + 快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sortColors(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    # 双指针 + 快排
    def quick_sort(left, right):
        if left >= right: return
        i, j = left, right
        while i < j:
            while i < j and nums[left] < nums[j]: j -= 1
            while i < j and nums[left] >= nums[i]: i += 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[left], nums[i] = nums[i], nums[left]
        quick_sort(left, i - 1)
        quick_sort(i + 1, right)
    
    quick_sort(0, len(nums) - 1)

单指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sortColors(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    def recover(n_len, p, target):
        for i in range(n_len):
            if nums[i] == target:
                nums[i], nums[p] = nums[p], nums[i]
                p += 1
        return p
    # 单指针遍历
    n_len, point = len(nums), 0
    # 复位0
    point = recover(n_len, point, 0)
    # 复位1
    point = recover(n_len, point, 1)

双指针1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sortColors(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    # 双指针遍历
    p0, p2, i = 0, len(nums) - 1, 0
    while i <= p2:
        if nums[i] == 0:
            nums[i], nums[p0] = nums[p0], nums[i]
            p0 += 1
        elif nums[i] == 2:
            nums[i], nums[p2] = nums[p2], nums[i]
            p2 -= 1
            if nums[i] != 1:
                i -= 1
        i += 1

双指针2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sortColors(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    # 双指针遍历
    p0, p1 = 0, 0
    for i in range(len(nums)):
        if nums[i] == 1:
            nums[i], nums[p1] = nums[p1], nums[i]
            p1 += 1
        elif nums[i] == 0:
            nums[i], nums[p0] = nums[p0], nums[i]
            if p0 < p1:
                nums[i], nums[p1] = nums[p1], nums[i]
            p0 += 1
            p1 += 1

力扣 1143. 最长公共子序列

leetcode

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonSubsequence(text1, text2):
    m, n = len(text1) + 1, len(text2) + 1

    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if i != 0 and j != 0:
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # print(dp)
    return dp[-1][-1]

力扣 72. 编辑距离

leetcode

动态规划

编辑距离: 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
     
    if m * n == 0:
        return m + n
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0 and j == 0:
                dp[i][j] = 0
            elif i == 0:
                dp[i][j] = dp[i][j - 1] + 1
            elif j == 0:
                dp[i][j] = dp[i - 1][j] + 1
            else:
                if word2[i - 1] != word1[j - 1]:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                else:
                    dp[i][j] = dp[i - 1][j - 1]
    # print(dp)
    return dp[-1][-1]

力扣 70. 爬楼梯

leetcode

动态规划 + 一维数组

1
2
3
4
5
6
7
8
9
10
11
def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    dp = [0] * n
    dp[0], dp[1] = 1, 2
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[-1]

动态规划 + 两个数

1
2
3
4
5
6
7
8
9
10
def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    a, b = 1, 2
    for i in range(2, n):
        a, b = b, a + b
    
    return b

力扣 64. 最小路径和

leetcode

动态规划 + 二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = grid[i][j]
            elif i == 0:
                dp[i][j] = grid[i][j] + dp[i][j - 1]
            elif j == 0:
                dp[i][j] = grid[i][j] + dp[i - 1][j]
            else:
                dp[i][j] = grid[i][j] + min(dp[i][j - 1], dp[i - 1][j])
    
    return dp[-1][-1]

动态规划 + 一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n 
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j] = grid[i][j]
            elif i == 0:
                dp[j] = grid[i][j] + dp[j - 1]
            elif j == 0:
                dp[j] = grid[i][j] + dp[j]
            else:
                dp[j] = grid[i][j] + min(dp[j - 1], dp[j])
    
    return dp[-1]
  • Copyrights © 2022 eightyninth
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信