wowowo123

分类

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

/ 注册

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

7篇文章 559人学习

全部文章（共98篇）

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

剑指找出唯一的两个数字

通过hashmap求解，也可以通过异或求解。由于这道题是两个唯一的数字，所以第一轮异或结束，结果一定是非0的，根据异或结果中非0的一位来和数组中其他元素做与运算，然后分成两个数组，这样可以把两个唯一的元素分到两个数组中然后再进行异或得出答案。为了写法更简洁些，可以不使用append,可以在开始的时候...

2021-03-26

0 603

剑指重复数字个数

可以通过循环O(n)，二分O(logn) 二分可以直接递归，也可以直接找左右边界，做差。 # -*- coding:utf-8 -*- class Solution: # def __init__(self): # self.count=0 def GetNumbe...

2021-03-26

0 497

剑指小朋友圆圈

通过环形链表模拟，解决这道题，时间复杂度O(mn),如果m,n太大，时间太长。 class Solution: def LastRemaining_Solution(self, n, m): # write code here result=head=Lis...

2021-03-26

0 459

剑指 1...n的和

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

2021-03-26

0 461

剑指整数中1的个数

对整数逐一进行比较，每一个数字大于0,则先进行取余操作，然后在进行/10，继续循环，看这一个数字里面有多少1。通过加入对1 和对10 的判断可以提升速度 class Solution: def NumberOf1Between1AndN_Solution(self, n): ...

2021-03-25

0 482

剑指矩阵路径中是否包含字符串

注意这个题将二维矩阵以一维数组的形式存储 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param matrix string字符串 # @param rows int整型 # @param cols int整型 # @param str ...

2021-03-24

0 537