Home

题目链接 啊目测这个题是要用开辟一个二维dp数组的，但是题目要求用一维的，就是说可以优化成一维了，就和01背包那样反过来处理就行。这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。 python: class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: size = len(triangle) dp = [0]*size dp[0] = triangle[0][0] for i in range(1, size): for j in range(i, -1, -1): ...

题目链接 类似于斐波那契数列的那种动态规划？方案数？或者是像上阶梯的方案数一类的题目？dp感觉状态转移还比较好搞清楚，就是要在各种情况的分类讨论搞清楚之后，那就不困难了。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 python: class Solution: def numDecodings(self, s: str) -> int: if s.startswith('0'): # 开头有‘0’直接返回 return 0 n = len(s) dp = [1] * (n + 1) # 重点是dp[0],dp[1] = 1, 1 for i in r...

题目链接 这个题是华为面试的时候给我出的，我就直接用bfs做出来了，当然那样做时间复杂度比较高为O(mn min(m,n)^2)，空间复杂度为O（1）。就不多说了。讲一下动态规划怎么做，首先我们用dp(i, j)表示以(i, j)为右下角，且只包含1的正方形的边长的最大值。如果我们能计算出所有dp(i, j)的值，那么其中的最大值即为矩阵中只包含1的正方形的边长的最大值，其平方为最大正方形的面积。那么如何计算dp中每个元素呢？对于每个位置(i, j)，检查在矩阵中该位置的值：如果该位置的值是0，则dp(i, j)=0，因为当前位置不可能在由1组成的正方形中。如果该位置的值是1，则dp(i, j)的值由其上方，左方和左上方的三个相邻位置的dp值决定。具体而言，当前位置的元素值大于三个相...

题目链接 给定一个有序序列1…n，为了构建出一棵二叉搜索树，我们可以遍历每个数字i，将该数字作为树根，将1…(i-1)序列作为左子树，将(i+1)…n序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。在上述构建过程中由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此我们可以想到用动态规划来解决这个问题。 题目要求是计算不同的二叉搜索树的个数。为此，我们可以定义两个函数：1. G(n)：长度为n的序列能构成的不同二叉搜索树的个数。2. F(i, n)：以i为根，序列长度为n的不同二叉搜索树个数(1<=i<=n)。可见，G(n)是我们求解需要的函数。我们将会看到，G(n)可以从F(...

题目链接 相比于lc062来说在网格中又加入了障碍物。只要处理好第一行和第一列的情况，就比较好做了，在有障碍物的时候把相应位置的方案数清零。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 python: class Solution: def uniquePathsWithObstacles1(self, obstacleGrid: List[List[int]]) -> int: rows, cols = len(obstacleGrid), len(obstacleGrid[0]) if rows == 0: return 0 dp = [1]*cols for i ...

题目链接 一个简单的dp题，空间可以优化到一维。这个算法的时间复杂度是O（MN），空间复杂度是O（N）。 python: class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [1]*n for i in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[-1]

题目链接 上次面字节AI Lab居然挂在这个上面了，来做一下。我在面试的时候没有想清楚动态规划的思路，匆忙开始做题了，导致没有做出来，一定要先把状态定义和状态转移彻底想清楚才开始做。对于这个题，我们定义dp[i]为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度，注意nums[i]必须被选取！关于这个最后一个元素是否要被选取好像也是有点讲究的。我们从小到大计算dp数组的值，在计算dp[i]之前，我们已经计算出了dp[0…i-1]的值，则状态转移方程为：dp[i] = max(dp[j]) + 1其中0<=j<i且nums[j]<nums[i]即考虑往dp[0…i-1]中最长的上升子序列后面再加一个nums[i]。由于dp[j]代表nums[0…j]中以nums...

题目链接 啊经典的N皇后问题，套用了一下自己总结的回溯的模板，就做掉了，还行。这个算法的时间复杂度是O(N!)，空间复杂度是O（N）。 python: import copy class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def isConfict(x, y, others): if y in others: return False for i, j in enumerate(others): if x - i == y - j or x - i ...

题目链接 复习一下前缀树。实现如下所示。Trie树是一个有根的树，其结点具有以下字段：1.最多R个指向字节点的链接，其中每个链接对应字母表数据集中的一个字母。这里假定R为26为小写拉丁字母的个数。2.布尔字段，以指定节点是对应键的结尾还是只是键前缀。Trie树中最常见的两个操作是键的插入和查找。先说向Trie树中插入键，我们通过搜索Trie树来插入一个键，我们从根开始搜索它对应于第一个键字符的链接。有两种情况：1.链接存在。沿着链接移动到下一个树的下一个子层。算法继续搜索下一个键字符。2.链接不存在。创建一个新的结点，并将它与父结点的链接相连，该链接与当前的键字符相匹配。重复以上步骤直到到达键的最后一个字符，然后将当前结点标记为结束结点，算法完成。插入的时间复杂度和空间复杂度都为O（...

题目链接 这个题又是经典的并查集题目。所以话不多说，但是一开始没有很多头绪，因为这个题里的name，email啥的比较复杂，需要引入一些哈希表才能更好更清晰地处理。如实现1所示，然后再在其中加入按秩排序（如实现2）。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。 python: class UnionFind2: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def union(self, x, y): x_par, y_par = self.find(x), self.find(y) self...