wowowo123

题解

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

/ 注册

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

leetcode 188 股票买卖来自专栏

股票系列问题这样两种方法求解。采用和股票问题3一样的方法，假设股票一天可以多次买卖，因为多次买卖利润为0,所以不会影响结果。注意所有的题都是买和卖其中选择一个算一次操作就可以。 class Solution: def maxProfit(self, k: int, prices: Lis...

2021-04-02

0 559

leetcode 123 股票利润3 来自专栏

动态规划，分析会产生几种状态。哪天的股票，当天是否持有，当天已经买卖过几次,是否持有股票分两种情况，持有还是不持有；已经买卖过几次，分三种，因为题目要求至多2次买卖，分别是0次，1次，2次。也就是组合出来每天有6种情况。然后分别分析这六种情况的状态转移。dp[i][0][0]=dp[i-1][0][...

2021-04-02

0 455

股票利润2 来自专栏

这里同样使用和股票利润1差不多的动态规划方法，由于允许股票多次交易，但不允许股票同时交易，所以每天的状态只能有两个，要么手里有一只股票，要么手里没有股票。通过当天是否有股票，可以由前一天是否有股票推断出，如果当天没有股票的话，可能前一天也没有股票，或者前一天有股票但是今天卖了。如果当天有股票的话，可...

2021-04-02

0 477

leetcode 121 股票利润单调栈解法

由于股票利润本质是在求解当前元素，与之前最小值之间的差值，所以维护一个单调递增的栈，入栈的值都为可能为后面买入股票的历史最低值，当遇到比栈顶元素小的元素证明栈顶元素已经没办法成为后面的最小元素了，所以将栈顶元素与栈底元素进行求差值，最后判断得出最大值。需要注意的是栈内保存的是下标，需要取对应的数组...

2021-04-02

0 585

leetcode 503 下一个最大元素2

这次是循环数组，所以属于一共遍历两次，第一次到了结尾，把i置为0,继续遍历。 class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: result=[-1 for _ i...

2021-03-31

0 493

leetcode 85 最大矩形矩阵

按照矩阵行，每一行为基准线，将矩阵中1的数字看作条形统计图中的柱体，计算最大的矩形。每一行迭代。利用前缀和思想，当当前元素为1，则加上之前的元素，当为0,则清零。计算的柱体面积按照之前最大矩形面积的题目，构造递增单调栈，但遇到比栈顶元素低的元素，就可以计算以栈顶元素高度的面积。 class Sol...

2021-03-31

0 611

leetcode 739 今日温度

使用单调栈，寻找第一个比当前元素大的元素。使用单调递减栈，然后当当前元素比栈顶元素大，栈顶pop,并计算位置。这样可以把前面比当前元素小的元素都计算出来，如果当前元素小于栈顶，那说明它的结果（右侧第一个比自己大的元素）还在后面，把它先放到栈中。由于有一些元素找不到比它大的元素所以应该初始化时就置为0...

2021-03-31

0 434

leetcode84 单调栈矩形最大面积

因为如果有两个相邻的 j 值对应的高度不满足 < 关系，那么后者会「挡住」前者，前者就不可能作为答案了。也就是前面的元素和后面的元素小于当前元素(pop出来的元素)那么当前高度没办法扩展到后面和前面。这道题其实就是去找当前位置元素左右两边第一个小于自己本身高度位置元素，然后通过位置元素相减...

2021-03-31

0 438

leetcode 42 接雨水

暴力解法，每次根据当前值去寻找左右两边的最高值，然后根据min()的值减去当前值来计算当前位置能接多少雨水。时间O(n^2)，会超时。 class Solution: def trap(self, height: List[int]) -> int: sumval=0...

2021-03-30

0 469

剑指链表公共节点

因为两个链表长度可能不相等，所以不能仅仅一个一个节点的遍历链表找到相同节点。但是a+b=b+a 可以把两个链表连接起来，这样就算是公共长度，所以长度相等。于是，当某一个链表的遍历节点为空的时候，就把他置为另一个链表的头部。这样遍历出来的结果就是公共节点 # class ListNode: # ...

2021-03-30

0 377