Shauby

分类

/ 注册

全部文章（共12篇）

题解 | #旋转数组#

旋转数组，完全基于两两交换实现数组移位，时间O(n)，空间O(1) 思路：不断让前m和尾m个元素交换，维护一个指针start，它是交换完元素的终点，未交换元素的起点。每交换完成m个元素，start往右移动m。要注意的边界条件是，当start靠近尾部时，交换区间会重叠，此时交换之后，重叠区域会被错误的...

数组模拟 Python3

2022-08-18

0 236

题解 | #最长无重复子数组#

最长无重复子数组极简实现——8行方法1：主要借助列表的in属性，内部属性更快，自己手写查找会超时。借助index属性可以直接跳到重复元素后，提升速度。双指针，如果不在子数组内，右边扩张，如果在子数组内，左边跳到重复元素后。 class Solution: def maxLength(sel...

Python3 数组双指针哈希表

2022-08-18

0 304

题解 | #把数字翻译成字符串#

把数字翻译成字符串，动态规划，时间O(n)，空间O(1) 数组任何一个位置的数字，既可以只看当前位置组成个位数，也可以结合之前位置构成多位数。由于字母编码只在1-26之间，所以只有两种方式——只取当前数字组成1位数编码或者取当前位置+前一个位置组成两位数编码。如果以nums[:i+1]译成字符串的...

字符串数组动态规划 Python3

2022-08-16

0 262

题解 | #最长上升子序列(一)#

最长上升子序列(一)，动态规划当前的元素，只有与之前的某个元素相接时才能组成最长上升子序列。只要之前元素比当前元素小，就可以相接，但最终与谁相接，则要看以谁结尾的上升子序列最长。相接即状态转移，若以元素i结尾的最长上升子序列长度为状态dp[i]，则它可能与之前i-1个状态相关，需遍历取满足条件的最...

动态规划数组 Python3

2022-08-16

0 345

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

用集合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: def ...

数组 Python3

2022-08-02

0 213

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

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

数组 Python3

2022-08-02

0 248