https://leetcode.com/problems/integer-break/

Medium

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

Medium

https://leetcode.com/problems/longest-increasing-subsequence/

Medium

https://leetcode.com/problems/ugly-number-ii/

Medium

https://leetcode.com/problems/maximal-square/

Medium

问题描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

1
2
3
4
5
6
7
8

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

思路及代码：

这一题是从一个二维数组中找出由1构成的最大的正方形的面积，可以通过动态规划的方法来解决，维护一个二维数组dp，dp[i][j]表示以当前点为右下角顶点能够构造的正方形最大边长。

dp数组的第一行和第一列与原数组相同，从第二行开始更新，在遍历过程中，首先判断matrix[i][j]是否为0，若为零，则当前点不能作为正方形的右下顶点，dp[i][j]设置为零；接着从dp[i][j]左边dp[i-1][j]、上边dp[i][j-1]以及斜上方dp[i-1][j-1]中选取最小值加一作为dp[i][j]的值。

拿题中例子来说，输入
$$
1 \quad 0\quad 1 \quad 0\quad 0\
1 \quad 0\quad 1 \quad 1\quad 1\
1 \quad 1\quad 1 \quad 1\quad 1\
1 \quad 0\quad 0 \quad 1\quad 0
$$
dp数组为：
$$
1 \quad 0\quad 1 \quad 0\quad 0\
1 \quad 0\quad 1 \quad 1\quad 1\
1 \quad 1\quad 1 \quad 2\quad 2\
1 \quad 0\quad 0 \quad 1\quad 0
$$
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0: return 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        res = 0
        for i in range(len(matrix[0])): 
            dp[0][i] = int(matrix[0][i])
            res = max(res, dp[0][i])
        for j in range(len(matrix)): 
            dp[j][0] = int(matrix[j][0])
            res = max(res, dp[j][0])
            
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if int(matrix[i][j]):
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
                    res = max(dp[i][j], res)

        return res ** 2
        

https://leetcode.com/problems/house-robber-ii/

Medium

https://leetcode.com/problems/house-robber/

Easy

https://leetcode.com/problems/maximum-product-subarray/

Medium

https://leetcode.com/problems/word-break-ii/

Hard

https://leetcode.com/problems/word-break/

Medium