leetcode contest 151 writeup

概要

leetcode第151周周赛

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

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

第一题

思路

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

代码

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很弱，所以代码中我没有

代码

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. 不停迭代删除子序列，直到有不存在这样的值对

动归也可

代码

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速度

代码

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技巧就可以通过，所以其实比第三题简单。第三题想通了其实也挺简单的。还需努力