Shauby

分类

/ 注册

全部文章（共44篇）

题解 | #最长公共前缀#

遍历数组找到长度最短字符串作为初始前缀再次遍历数组，根据初始前缀与字符串的匹配情况更新初始前缀，遍历完成即得到前缀 class Solution: def longestCommonPrefix(self ...

字符串 Python3

2022-08-10

0 218

题解 | #三数之和#

将三数和，转换成n个两数和问题求解。时间O(n^2)，空间O(n)。以排序后的元组作为集合元素，自带去重效果。用取值的剩余次数来避免重复取值，和避免多次出现的值的漏选。 class Solution: def ...

哈希表 Python3

2022-08-09

3 327

题解 | #缺失的第一个正整数#

用集合set极简实现，空间复杂度伪O(1) class Solution: def minNumberDisappeared(self , nums: List[int]) ->&n...

Python3 哈希表数组

2022-08-09

0 240

题解 | #数据流中的中位数#

从零开始实现堆，获取数据流中的中位数。中位数可能由两位数决定，所以需要两个堆。中位数特点：对于排好序的序列，它是左半部分的最大值，是右半部分的最小值。当元素个数是偶数时，左右半部分元素个数相等，中位数是左边最大和右边最小的平均，当元素个数是奇数时，让左半部分多一个元素，那么中位数就是左半部分...

数组堆(优先队列) Python3

2022-08-08

0 241

题解 | #寻找第K大#

时间复杂度O(nlogk)，空间复杂度O(1)。用类似寻找k个最大数的思路，在原列表上维护一个长度为k的小根堆。遍历列表a[K:]，如果存在比堆里元素大的值（只要比堆顶元素（最小值）大），就换掉原堆顶，然后调整堆。遍历完列表之后，长度为k的堆内的值均不小于外部的值，且堆顶为堆...

数组堆(优先队列) Python3

2022-08-08

0 268

题解 | #最小的K个数#

堆排序实现最小k个数 class Solution: # 小根堆调整函数，静态方法 @staticmethod def h...

堆(优先队列) 数组 Python3

2022-08-07

0 243

题解 | #滑动窗口的最大值#

从零开始，用堆实现求滑动窗口最大值。通过维护一个大堆来获取最大值及其下标。遇到一个值就加入堆，在新添加元素后，如果堆顶元素的下标还在滑动窗口范围内，则获取其值。否则弹出堆顶元素，至堆顶元素的下标在滑动窗口范围内。 class Solution: &n...

Python3 堆(优先队列)

2022-08-07

0 273

题解 | #表达式求值#

双栈+递归支持加减乘除，整除，取余和次幂运算。 def solve(s): priority = {'+':0, '-':0, '*':1, '/':1, '//':1,...

字符串 Python3 递归

2022-08-05

0 229

题解 | #数组中重复的数字#

维护数组下标与值一一对应：遍历数组，当值与下标不等时，当前位置与值对应下标处的值重复交换，直到当前位置的值等于下标。如果在交换过程中遇到位置上的值已经满足条件，表明该值重复 class Solution: def ...

数组 Python3

2022-08-02

0 213

题解 | #数组中出现次数超过一半的数字#

所求数出现次数超过一半，占绝对数量优势。无论被多少其它数消除过，所求数剩下的数量还是超过一半的。把其它数都耗死，剩下所求数遗世独立。 # 关键条件：数出现次数超过数组长度的一半，即大于其他所有数出现次数之和。 # 遍历时，我们选定第一个数作为候选，并记该数出...

数组 Python3

2022-08-02

0 248