wowowo123 - 个人主页动态 - 牛客网

发布(99) 评论刷题

2021-04-04 17:28

清华大学算法工程师

leetcode 90 子集2

其中数组包含重复的元素，在迭代的时候需要先将数组进行排序，然后判断是否重复。 class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: res=[[]] nums=sorted(nums) for i in nums: res+=[[i]+num for num in res if [i]+num not in res] return res 通过递归方法，控制形成顺序，同时控制同一层不出现相...

0 点赞评论收藏

分享

2021-04-04 16:13

清华大学算法工程师

leetcode 78 子集

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

0 点赞评论收藏

分享

2021-04-04 15:35

清华大学算法工程师

leetcode 216 组合总和3

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

0 点赞评论收藏

分享

2021-04-04 14:37

清华大学算法工程师

leetcode 40 组合总和2

这道题不光要判断组合的顺序问题，因为数组中存在重复的元素，所以应该避免会有重复的结果。使用47全排列的方法，先将数组进行排序，然后判断数组当前元素是否与之前元素相同，如果相同判断一下之前元素是否有遍历过马，没遍历过算是在同层的元素，如果遍历过不是同层的元素。 class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(i,path,result,visit,target): if tar...

0 点赞评论收藏

分享

2021-04-04 12:28

已编辑

清华大学算法工程师

leetcode 39 组合总和

通过回溯，以及按大小剪枝，因为组合问题所以需要固定一个顺序遍历，因为不同顺序也被视为一个组合。保证path数组中的顺序是升序的。 遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(path,result,target): i...

0 点赞评论收藏

分享

2021-04-04 11:49

清华大学算法工程师

leetcode 77 组合

通过回溯加判断条件剪枝，如果加入路径的值不能比前一个值小。 组合问题通常需要通过某种顺序展开 组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。 作者：liweiwei1419链接：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/。 class Solution: def combine(...

0 点赞评论收藏

分享

2021-04-04 10:48

清华大学算法工程师

leetcode 47 全排列2

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

0 点赞评论收藏

分享

2021-04-03 23:38

清华大学算法工程师

leetcode 113 路径总和2

通过回溯深搜，因为题目要求的是路径，所以当节点的值满足目标值以及没有左右子节点（为叶子节点）返回，每次将当前遍历的节点放入path数组，同时目标进行作差。 同样需要注意path数组的浅复制path[:],否则result中的结果为空，因为会随着递归后path数组为空而变化。 python数组可以使用pop。因为有负数，所以不要加大于target的剪枝操作。注意在当前节点值等于target时，也要把结果回溯，每一次的结果都要回溯，否则就会出错。 # Definition for a binary tree node. # class TreeNode: # def __init__(s...

0 点赞评论收藏

分享

2021-04-03 23:55

已编辑

清华大学算法工程师

leetcode 46 全排列

通过回溯算法，在纸上画出求解问题的树形图，想清递归结构考虑如何剪枝。 做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。 在画图的过程中思考清楚： 分支如何产生；题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？ ！！！#需要注意得到数组的浅复制，尤其是python class Solution: def per...

0 点赞评论收藏

分享

2021-04-03 14:43

清华大学算法工程师

leetcode 120 三角形最小路径和

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

0 点赞评论收藏

分享

2021-04-03 12:57

清华大学算法工程师

leetcode213 打家劫舍2

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

0 点赞评论收藏

分享

2021-04-03 12:13

清华大学算法工程师

leetcode 198 打家劫舍

使用动态规划，看第几间屋子是偷还是不偷，偷的话由之前的没偷的状态转移过来，不偷的话之前可能偷了也可能没偷。 class Solution: def rob(self, nums: List[int]) -> int: dp=[[0,0] for _ in range(len(nums))] dp[0][0]=0 dp[0][1]=nums[0] for i in range(1,len(nums)): dp[i][0]=max(dp[i-1][0],dp[i-1][1]) ...

0 点赞评论收藏

分享

2021-04-03 11:07

清华大学算法工程师

leetcode 64 最小路径和

动态规划的想法，dp数组中存储的位置代表每一条路径到达当前位置的最小路径和，每一个状态进行转移的时候只和左面和上面的位置有关。 class Solution: def minPathSum(self, grid: List[List[int]]) -> int: dp=[[0 for _ in range(len(grid[0]))]for _ in range(3)] dp[0][0]=grid[0][0] for i in range(1,3): dp[i][0]=dp[i-1][0]+grid[i][...

0 点赞评论收藏

分享

2021-04-02 23:14

已编辑

清华大学算法工程师

leetcode 714 股票手续费问题

使用动态规划方法，dp数组的状态和之前多次买卖的状态数量一样，一种是天数，一种是持有还是不持有，当股票卖出（买入也可以）需要减去手续费用，注意这个手续费用只能计算一次。 class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: dp=[[0,0] for _ in range(len(prices))] dp[0][0]=0 dp[0][1]=-prices[0] for i in range(1,len(prices)):...

0 点赞评论收藏

分享

2021-04-02 23:07

清华大学算法工程师

leetcode 309 股票买卖冷冻期

状态主要分为两种，一种是天数，一种是是否持股以及是否处在冷冻期，这两种状态是复合的，要么持有，要么不持有不冷冻，要么不持有在冷冻。所以设置dp数组，状态转移如下 dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]) dp[i][2]=max(dp[i-1][1],dp[i-1][2]) dp[i][1]=dp[i-1][0]+prices[i]其中处在冷冻期只有一种情况就是昨天持有，今天卖掉 class Solution: def maxProfit(self, prices: L...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务