随缘更新，无固定刷题频率、顺序，仅作简单记录。
文章更新记录
No.15—三数之和—中等
No.146—LRU缓存—中等
No.215—数组中的第K个最大元素—中等
No.3—无重复字符的最长子串—中等
No.206—反转链表—简单
No.636—函数的独占时间—中等
No.761—特殊的二进制序列—困难
No.3—无重复字符的最长子串—中等
- 点击此处跳转到题目
- 使用滑动窗口，暴力遍历。需要两重循环，外层为左边界，内层为右边界，使用set来记录当前窗口内的字符，用于判断重复。
- 先是左边固定，右边一直向右，直到出现重复字符，卡住。此时的情况是，窗口内刚好无重复，但右边不能再加入了，因为它与窗口内有重复，此为局部最优解，与当前全局最优解比对，优胜劣汰。
- 然后左边开始向右逐步移动，每次移动完删除已不再窗口的那一位字符，直到右边可以恢复移动。
- 不断重复直到遍历完字符串。
1 | class Solution: |
- 关于代码上的思考1：感性上，每次右边界卡住时，左边界其实需要移动至能够剔除与右边将要加入字符产生重复的那一位，但是在代码实现过程中，使用原有for循环一步一步移动，既保持了代码的优雅，其实理性上也没有造成更大的开销。即没有必要加入一段实现一步到位的代码。
- 关于代码上的思考2：感性上，右边界遍历完，程序就可结束了，但代码实现上，依然将左侧边界for循环走完，多了不必要的步骤。然而，如果频繁的测试右端是否遍历完，也需要开销，且代码不甚优雅，故此处需要取舍。
No.15—三数之和—中等
- 点击此处跳转到题目
- 三数之和问题，可以理解为先确定一位，然后在剩余数中做
两数之和的问题。 - 题目要求不重复，故先对原数组nums排序，这样相同的数会在空间上连续，去重变得方便。
- 如果暴力使用三重循环，时间复杂度必然很高，在确定第二位和第三位时，既然已经排好序了，可以采用双指针来遍历，降低时间复杂度。
- 需要注意的是，如果从左向右遍历第一个数，那么第二第三个数仅需在第一个数右侧区域遍历寻找，即三数的相对位置关系不能变。且不论改变三个数中哪个数的指针，都要考虑跳过空间邻域上的重复数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
first = None
nums.sort() # 排序
for i in range(len(nums) - 2): # 从左向右遍历第一个数
if nums[i] == first: # 第一个数跳过重复的数
continue
first, l, r, = nums[i], i + 1, len(nums) - 1 # 双指针法，在第一个数右侧区域找第二第三个数
while(l < r):
num_l, num_r = nums[l], nums[r]
if num_l + num_r > 0 - first: # 若第二第三个数的和过大，使第三个数变小
while(l < r and nums[r] == num_r): # 第三个数跳过重复数
r -= 1
elif num_l + num_r < 0 - first: # 若第二第三个数的和过大，使第二个数变大
while(l < r and nums[l] == num_l): # 第二个数跳过重复数
l += 1
else:
ans.append([first, num_l, num_r]) # 找到一组符合的结果
while(l < r and nums[r] == num_r): # 继续寻找第二第三个数的其余可能组合，注意去重
r -= 1
while(l < r and nums[l] == num_l):
l += 1
return ans
No.146—LRU缓存—中等
- 点击此处跳转到题目
- 普通的模拟LRU很简单，但是本题要求
get和put必须以O(1)的平均时间复杂度运行，也就是要在O(1)时间内定位一个key-value对，所以需要用到hashmap。同时为了知晓最近使用情况，可以维护一个双向链表，越靠近头节点，说明越在近期使用过。 - 具体的模拟思路不再赘述，代码足以说明，仅记录三个值得注意的点：
- 一是为什么链表要双向。链中某节点重新被访问时，需要将其移动到链头，此时需要将其左右节点连起来，不能断链。如果使用单向链表，在快速定位到此节点后，只能访问到其后节点，而不能访问其前节点，至少在O(1)时间内不行，故需要双向链表。
- 二是既然hashmap中已经有key，链表中节点为何key-value都要，而不能只存value。主要是考虑LRU置换时，即删除双向链表尾节点时，需要能从尾节点反向定位到hashmap中相应项并删除之。链表中无key的话无法实现。
- 三是代码上的技巧，虚拟头尾节点，降低编码难度，使真正的头尾可以与中间节点作相同处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
self.head = self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.pre = self.head
def get(self, key: int) -> int:
if key in self.hashmap:
self.move_to_head(key)
return self.hashmap[key].value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.hashmap: # 已有此条目，更新value后置于头部
self.hashmap[key].value = value
self.move_to_head(key)
else: # 尚无此条目
if len(self.hashmap) >= self.capacity: # 容量满了要先删尾节点
self.hashmap.pop(self.tail.pre.key)
self.tail.pre.pre.next = self.tail
self.tail.pre = self.tail.pre.pre
addnode = Node(key, value) # 头部添加新节点
addnode.next = self.head.next
addnode.pre = self.head
self.head.next.pre = addnode
self.head.next = addnode
self.hashmap[key] = addnode
# 代码复用
def move_to_head(self, key: int):
movenode = self.hashmap[key]
movenode.pre.next = movenode.next
movenode.next.pre = movenode.pre
movenode.next = self.head.next
movenode.pre = self.head
self.head.next.pre = movenode
self.head.next = movenode
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.pre = None
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
No.206—反转链表—简单
从头结点开始遍历单链表，时刻保持对前一节点的可访问，便于将当前节点的next指向前一节点，当然在改变next时也要先记录后续节点，防止断链。依次重新赋值，迭代前进，找准边界条件，适时结束。
1 | # Definition for singly-linked list. |
- 在Leetcode评论区看到一段巧妙利用多元赋值来简化赋值的代码，值得学习。优雅，永不过时。
1 | class Solution: |
No.215—数组中的第K个最大元素—中等
- 点击此处跳转到题目
- 最直接的做法就是把数组排序后，取第k大的，但排序的平均时间复杂度达不到O(n)。
一种思路是采用堆（优先队列），假定有一个小顶堆，遍历数组，每次向小顶堆中push一个元素，如果堆中个数超过k，就pop。这样当遍历完成后，堆中仅有最大的k个元素，堆顶即为第K个最大元素。
1
2
3
4
5
6
7
8
9
10import heapq as hq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
minq = []
for x in nums:
hq.heappush(minq, x)
if len(minq) > k:
hq.heappop(minq)
return hq.heappop(minq)另一种思路是采用快速选择算法。较为熟知的快速排序算法，平均时间复杂度为O(nlogn)，每次先把基准元素放在正确位置，左右两侧要么全大于基准，要么全小于基准，再分别递归进行。受此启发，使用快速选择算法，在放好基准后，就知道基准是第几大的元素（记为p），只需比较k与p，便可知道第k大的元素落在哪个区域，逐步夹逼，缩小范围，最终得到精确值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
l, r = 0, len(nums) - 1
while (l < r):
pindex = self.partition(nums, l, r) # 基准元素是第几大元素
# 比较k-1与基准元素索引，缩小区域，通过while循环逐步夹逼，当然也可采用递归方式。
if k - 1 < pindex:
r = pindex - 1
elif k - 1 > pindex:
l = pindex + 1
else:
return nums[pindex]
return nums[l]
# 与快排的partition相同
def partition(self, nums, lo, ri):
p = nums[lo]
while (lo < ri):
while (lo < ri and nums[ri] <= p):
ri -= 1
nums[lo] = nums[ri]
while (lo < ri and nums[lo] > p):
lo += 1
nums[ri] = nums[lo]
nums[lo] = p
return lo
No.636—函数的独占时间—中等
使用栈记录函数调用的过程，某函数start，将其放入栈中，某函数end，栈顶元素出栈，二者湮灭。
对于本条目是start的情况，若栈中已有条目，二者相减，计入栈中函数的独占时间。不论栈是否空，都将本条目入栈，时间戳无需特殊处理。
对于本条目是end的情况，栈中一定不空，且必是此条目的start，时间相减再+1，计入独占时间，并出栈，二者湮灭。关键的是：若出栈后栈中不空，要将此刻栈顶的时间戳更改为现在的时间戳，即此条目（end）的时间+1，因为这之间的时间，此刻栈顶的函数调用了别人，不是独占时间，后续独占时间应该从它重见天日（重新成为栈顶）的那一刻开始算。
1 | class Solution: |
No.761—特殊的二进制序列—困难
不会做。。。。。。看官解（此处尽量写得更加通俗易懂）。
总体上采用分治法。
首先从特殊序列的定义可以看出：特殊序列必然以1开头、以0结尾。
特殊序列面临两种情况，较简单的一种情况是特殊序列P不可完整拆分成多个特殊序列。解题的关键是，看出如下这点：这种不可再完整拆分的特殊序列，首位的1和末尾的0是不可能出现在题目中描述的那种相邻特殊子串的交换操作中的（其证明通过反推即可得到，假如P的首位1也是交换操作中左特殊子串A的首位，由题目知，作为特殊序列的A中1与0个数相同，P也是，那么P-A的部分中0和1个数也要相同，且P-A的每个前缀中1 的数量大于等于 0 的数量，（此结论也是反证法得到，不满足的话那么P也将不满足每个前缀中1 的数量大于等于 0 的数量，这与P为特殊序列矛盾），也就是说，P可以拆分为A 与P-A两个特殊序列了，与初始假设矛盾，得证），所以首位1和末位0不可能参与交换，可以不考虑这两位，进一步深入考虑中间部分。
另一种情况是P可以完整拆分成多个特殊序列，那么就分而治之，接下来与上一种情况相同。
递归后再合并，将不可再分的最小特殊序列们排序后拼接，得到字典序最大的字符串。
操作细节上，每层递归中，都遍历此时处理的字符串，用计数器记录1与0，遇1递增，遇0递减，计数器每次到0了，说明前一段遍历中1与0个数相同，即分离出了一个不可再分的特殊子串，入列表，并对其除去首位1与末位0后递归调用函数。
1 | # Leetcode官解 |