wowowo123

分类

动态规划(1) 未归档(4) 题解(94)

/ 注册

TA的专栏 7篇文章 0人订阅

7篇文章 559人学习

全部文章（共98篇）

leetcode 78 子集

通过递归，然后根据条件当当前元素的下标小于数组长度的时候，可以把他放到结果中。 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def dfs(i,path,result):...

2021-04-04

0 454

leetcode 216 组合总和3

避免顺序不同，同时控制长度与和 class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: def dfs(i,path,target,n,k,result): ...

2021-04-04

0 410

leetcode 40 组合总和2

这道题不光要判断组合的顺序问题，因为数组中存在重复的元素，所以应该避免会有重复的结果。使用47全排列的方法，先将数组进行排序，然后判断数组当前元素是否与之前元素相同，如果相同判断一下之前元素是否有遍历过马，没遍历过算是在同层的元素，如果遍历过不是同层的元素。 class Solution: ...

2021-04-04

0 463

leetcode 39 组合总和

通过回溯，以及按大小剪枝，因为组合问题所以需要固定一个顺序遍历，因为不同顺序也被视为一个组合。保证path数组中的顺序是升序的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。 clas...

2021-04-04

0 558

leetcode 77 组合

通过回溯加判断条件剪枝，如果加入路径的值不能比前一个值小。组合问题通常需要通过某种顺序展开组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。作者：liwei...

2021-04-04

0 559

leetcode 47 全排列2

使用递归，剪枝 class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: result=[] def dfs(i,path,visit,result): ...

2021-04-04

0 459

leetcode 113 路径总和2

通过回溯深搜，因为题目要求的是路径，所以当节点的值满足目标值以及没有左右子节点（为叶子节点）返回，每次将当前遍历的节点放入path数组，同时目标进行作差。同样需要注意path数组的浅复制path[:],否则result中的结果为空，因为会随着递归后path数组为空而变化。 python数组可以使...

2021-04-03

0 459

leetcode 46 全排列

通过回溯算法，在纸上画出求解问题的树形图，想清递归结构考虑如何剪枝。做题的时候，建议先画树形图，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。在画图的过程中思考清楚：分支如何产生；题目需要的解在哪里？是在叶子结点、还...

2021-04-03

0 513

leetcode 120 三角形最小路径和

把三角形看成一个上三角或者下三角(等腰三角形)，然后设置状态转移公式，当没到每行的最后一个的时候，以及每行的第一个，都可以有两种方法到达当前位置，选择最小的路径和。 class Solution: def minimumTotal(self, triangle: List[List[int...

2021-04-03

0 502

leetcode213 打家劫舍2

问题将数组改为循环数组，也就是头和尾不能一起偷盗，所以就进行两次计算，一次将数组去除头元素，一次将数组去掉尾元素。 class Solution: def rob(self, nums: List[int]) -> int: if len(nums)==0: ...

2021-04-03

0 637