leetcode contest 151 writeup

 

概要

leetcode第151周周赛

题目 难度 知识点
查询无效交易 简单
比较字符串最小字母出现频次 简单
从链表中删去总和值为零的连续节点 中等 链表
餐盘栈 困难 设计/无

注:思路是理想思路,代码有可能是我比赛时写的,就不那么理想.

所以代码与思路不一定等价

第一题

思路

将数据处理后,双重map,然后去重。当然直接做也可以,我在比赛时就是直接做的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
transactions_after: [str, int, int, str] = []
results: List[str] = []
for t in transactions:
name, time, num, local = str.split(t, ",")
num = int(num)
time = int(time)
if num > 1000:
results.append(t)
transactions_after.append((name, time, num, local))
for (n1, t1, num1, l1) in transactions_after:
for (n2, t2, num2, l2) in transactions_after:
if n1 == n2 and abs(t2 - t1) <= 60 and l1 != l2:
results.append(n1 + "," + str(t1) + "," + str(num1) + "," + l1)
return list(set(results))

第二题

思路

  1. 将字符串根据f处理成数据
  2. 对word排序(代码中,我没有
  3. 依次迭代处理(对于排序过得数据可以用二分法确认有几个比较大,由于py中的stl很弱,所以代码中我没有

代码

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
class Solution:
def f(self, s: str) -> int:
if s == "":
return 0
i = 1
min_c = s[0]
min_n = 1
while i != len(s):
c = s[i]
if c < min_c:
min_c = c
min_n = 1
elif c == min_c:
min_n += 1
i += 1
return min_n

def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
queries_n: List[int] = []
words_n: List[int] = []
for n in queries:
queries_n.append(self.f(n))
for n in words:
words_n.append(self.f(n))
result = []
for i, n in enumerate(queries_n):
low = 0
for n2 in words_n:
if n < n2:
low += 1
result.append(low)
return result

第三题

思路

  1. 求出前缀和。例 12 3 -3 1 求出 0 1 3 6 3 4。
  2. 可以发现前缀和序列中相等的值对,其序号对应的范围在原序列中的子序列恰好值为零。
  3. 不停迭代删除子序列,直到有不存在这样的值对

动归也可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
unordered_map<int, ListNode*> prefixSum;
// 因为头结点也有可能会被消掉,所以这里加一个虚拟节点作为头结点
ListNode* dummy = new ListNode(0), *p = dummy;
dummy->next = head;

prefixSum[0] = p;
int cur = 0;
while (p = p->next) {
cur += p->val;
if (prefixSum.find(cur) != prefixSum.end()) {
prefixSum[cur]->next = p->next;
} else {
prefixSum[cur] = p;
}
}

return dummy->next;
}
};

第四题

思路

  1. 使用栈数组
  2. 保存最后一个可以插入的位置一提高push速度

代码

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
from typing import List


class DinnerPlates:

def __init__(self, capacity: int):
self.stacks: {int: List[int]} = dict()
self.size = 0
self.capacity = capacity
self.last_not_full = 0

def push(self, val: int) -> None:
if self.last_not_full not in self.stacks:
self.stacks[self.last_not_full] = [val]
self.size += 1
else:
self.stacks[self.last_not_full].append(val)
i = self.last_not_full
while i < self.size and len(self.stacks[i]) == self.capacity:
i += 1
self.last_not_full = i

def pop(self) -> int:
if self.size == 0:
return -1
last = self.stacks[self.size - 1]
r = last.pop()
if len(last) == self.capacity - 1:
self.last_not_full = self.size - 1
if len(last) == 0:
self.size -= 1
return r


def popAtStack(self, index: int) -> int:
if index >= self.size or len(self.stacks[index]) == 0:
return -1
self.last_not_full = index
return self.stacks[index].pop()

后记

这次的题目翻译差一点,竞赛的时候看错了好几次。设计题对于性能的限制比预想的低,不需要hack技巧就可以通过,所以其实比第三题简单。第三题想通了其实也挺简单的。还需努力