股票系列问题这样两种方法求解。采用和股票问题3一样的方法，假设股票一天可以多次买卖，因为多次买卖利润为0,所以不会影响结果。注意所有的题都是 买和卖其中选择一个算一次操作就可以。 class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices)==0: return 0 buy=[-prices[0] for _ in range(k+1)] sell=[0 for _ in range(k+1)] ...

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

这里同样使用和股票利润1差不多的动态规划方法，由于允许股票多次交易，但不允许股票同时交易，所以每天的状态只能有两个，要么手里有一只股票，要么手里没有股票。通过当天是否有股票，可以由前一天是否有股票推断出，如果当天没有股票的话，可能前一天也没有股票，或者前一天有股票但是今天卖了。如果当天有股票的话，可能前一天没有股票但是今天买了，也可能是前一天就有股票。 PS.这里与股票利润1不同的地方在于，前一天没有股票但是今天卖了这个状态，如果是只允许操作一次，那么买股票都是从0元开始买，但是如果允许操作多次可能之前有利润。 class Solution: def maxProfit(self, ...

由于股票利润本质是在求解当前元素，与之前最小值之间的差值，所以维护一个单调递增的栈，入栈的值都为可能为后面买入股票的历史最低值，当遇到比栈顶元素小的元素证明栈顶元素已经没办法成为后面的最小元素了，所以将栈顶元素与栈底元素进行求差值，最后判断得出最大值。需要注意的是 栈内保存的是下标，需要取对应的数组值 class Solution: def maxProfit(self, prices: List[int]) -> int: stack=[] prices.append(0) maxvalue=0 for i in...

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

按照矩阵行，每一行为基准线，将矩阵中1的数字看作条形统计图中的柱体，计算最大的矩形。每一行迭代。利用前缀和思想，当当前元素为1，则加上之前的元素，当为0,则清零。计算的柱体面积按照之前最大矩形面积的题目，构造递增单调栈，但遇到比栈顶元素低的元素，就可以计算以栈顶元素高度的面积。 class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: if len(matrix)==0: return 0 result=0 hei...

使用单调栈，寻找第一个比当前元素大的元素。使用单调递减栈，然后当当前元素比栈顶元素大，栈顶pop,并计算位置。这样可以把前面比当前元素小的元素都计算出来，如果当前元素小于栈顶，那说明它的结果（右侧第一个比自己大的元素）还在后面，把它先放到栈中。由于有一些元素找不到比它大的元素所以应该初始化时就置为0,这样如果可以找到结果就修改结果值，如果找不到就直接为0。 如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。 class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: s...

因为如果有两个相邻的 j 值对应的高度不满足 < 关系，那么后者会「挡住」前者，前者就不可能作为答案了。也就是前面的元素和后面的元素小于当前元素(pop出来的元素)那么当前高度没办法扩展到后面和前面。 这道题其实就是去找当前位置元素左右两边第一个小于自己本身高度位置元素，然后通过位置元素相减与当前高度乘积得到当前的面积，如果位置元素相减大于1那么证明中间有多个元素，这些元素是pop出去的，所以都比当前元素大，以当前高度计算面积是没问题的。 需要再数组元素前面加上[0]，在后面也加上[0] 因为如果当元素小于三个，或者元素一直递增，也可以保证栈中元素可以pop。 其中递归栈尤其是单调递减...

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

因为两个链表长度可能不相等，所以不能仅仅一个一个节点的遍历链表找到相同节点。但是a+b=b+a 可以把两个链表连接起来，这样就算是公共长度，所以长度相等。于是，当某一个链表的遍历节点为空的时候，就把他置为另一个链表的头部。这样遍历出来的结果就是公共节点 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param pHead1 ListNode类 # @param pHead2 ListNode类 # @return ListN...

通过hashmap求解，也可以通过异或求解。由于这道题是两个唯一的数字，所以第一轮异或结束，结果一定是非0的，根据异或结果中非0的一位来和数组中其他元素做与运算，然后分成两个数组，这样可以把两个唯一的元素分到两个数组中然后再进行异或得出答案。为了写法更简洁些，可以不使用append,可以在开始的时候就初始化好result=[0,0]，然后根据result[0],result[1] 做异或操作，结果直接放在result数组中。再根据大小调整一下就可以。 也可以将第一次异或结果与一个为1的变量进行与运算，然后左移1变量，这样就可以每次不用调整元素的值进行移位操作，直接与即可，但是比如2与2 会输...

可以通过循环O(n)，二分O(logn) 二分可以直接递归，也可以直接找左右边界，做差。 # -*- coding:utf-8 -*- class Solution: # def __init__(self): # self.count=0 def GetNumberOfK(self, data, k): # write code here # count=0 # for i in range(len(data)): # if data[i]==k: # w...

通过环形链表模拟，解决这道题，时间复杂度O(mn),如果m,n太大，时间太长。 class Solution: def LastRemaining_Solution(self, n, m): # write code here result=head=ListNode(0) i=0 if n==0 or m==0: return -1 while i<n: node=ListNode(i) head.next=node ...

通过短路效应，不用if语句做判断。 class Solution: def __init__(self): self.res=0 def Sum_Solution(self, n): # write code here n>1 and self.Sum_Solution(n-1) self.res+=n return self.res #return n and (n+self.Sum_Solution(n-1)) #return (n+1)*(n&...