wowowo123

题解

动态规划(1) 未归档(4)

/ 注册

全部文章 / 题解（共93篇）

leetcode_733 图像渲染

对图像进行染色,一圈一圈的为周围点上***fs其中需要注意给上同样颜色时,判断一下,直接输出.否则一直在循环中. from collections import deque class Solution: def floodFill(self, image: List[List[int]]...

2021-04-11

0 593

丑数与快速幂

丑数1，判断是否是丑数除了对非正整数的判断，就是将2，3，5质因数从数字中抽取出来，然后看数字里如果只剩下1，那么就是丑数，否则就不是丑数，能除就做除，不能做除就判断。其实是把每个需要判断的数字看成2^x13^x25^x3 就是丑数。两种方式 class Solution: def isU...

2021-04-10

0 637

bfs_leetcode 310 最小高度树

由于遍历每一个节点为根节点树的高度，再去求最小时间复杂度为O(n^2),超时 class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: def...

2021-04-10

0 711

bfs_leetcode 1162 地图分析

将海洋到最近陆地的最长距离，转换为陆地到海洋bfs 最后那个结果的距离。同理 01矩阵那个题也是一样，将每个元素（0，1）到最近的0的距离，看成0到1的bfs这两个问题都是正向去思考没办法找到最小。有时候在纸上画一画就知道将哪个作为源点***更好以下节选自leetcode题解你可以想象成你从每个...

2021-04-10

0 576

leetcode542 01 矩阵求最短路径

通过动态规划，从四个方向进行状态转移。 class Solution: def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]: dp=[[10000 for _ in range(len(...

2021-04-09

0 1085

leetcode 1578 重复字母

遍历发现重复字母的区域，然后将对应cost数组片段进行排序，将其中代价小的均加起来。 class Solution: def minCost(self, s: str, cost: List[int]) -> int: count=0 j=0 ...

2021-04-07

0 528

leetcode 45 跳跃游戏2

贪心的方法，从后往前找到哪些值可以跳到终点，取离终点最远的点，然后在接着找哪些点可以到这个点，那个点离这个点最远。注意从一个点到另一个点是算一步。通过一步一步的局部最优，达到全局最优。 end=len(nums) count=0 while end...

2021-04-07

0 550

leetcode 322 零钱兑换

通过动态规划方法，dp[amount]为金钱为amount时需要的最少硬币数目，状态转移公式，当最后一枚硬币是ci的时候，d[amount]=dp[amount-ci]+1,最后这枚硬币是多少需要遍历。 class Solution: def coinChange(self, coins:...

2021-04-07

0 539

leetcode 455 分发饼干

贪心法则，自己的做法，先将两个数组进行排序，然后遍历饼干列表，当前的饼干列表只能在已经满足了当前胃口了的，如果满足条件则数量增加1，然后当前胃口也继续检测下一个。注意如果是嵌套循环的话， break 可以跳出最深的循环，打破最小的循环。而continue是跳过当前循环的下面语句，继续循环，br...

2021-04-07

0 478

leetcode 37 数独

判断数字是否填写正确没那么困难，通过check函数。减少时间复杂度，通过传入i,j。！！！注意然后只返回一个解即可，需要 return。唯一不同的变化是，题解的回溯函数有一个返回值，它是布尔类型，一旦返回 True，在递归那边就会把 True 传递上去，终止回溯。这一点值得注意。 class S...

2021-04-07

0 442