月度归档:2019年12月

leetcode 第 168 场周赛总结笔记

本周总结:

对于条件比较多的问题,动手写代码之前要先做好规划

  1. 先做算法文学家,能规划并文字表达清楚思路之后
  2. 再做算法实践家,开始动手实现具体细节

按照这个思路去做题对于条件,变量比较繁杂的问题能够有一个比较清晰的思路,
如果一开始就写代码,脑袋的注意力会被这些细节牵着走,容易迷失方向。
其实大多数时候写代码都应该按照这个步骤来,但是有些大佬可能在心里面完成了这个过程,
而我需要手写一遍,这种方式我还是很受用的。

1297. 子串的最大出现次数

import collections

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt = collections.defaultdict(int)  # 1. 首先我们需要一个 k,v 计数工具“字典”
        n = len(s)
        start = end = 0  # 2. 我们的策略是采用滑窗的方式暴力过一遍字符串,所以定义了表示窗口起始和结束的变量
        while start < n:  # 3. 暴力滑窗 start 都要过一遍的,终止条件是 start == n
            tmp = set()  # tmp 存储 cur_start--val_end 内窗口内的字符集合

            # 4. 现在 start 固定, end 递增滑动,终止条件由这三个变量决定
            while len(tmp) <= maxLetters and end - start <= maxSize and end <= n:
                if end - start >= minSize:  # 4.1 如果大于最小长度就加入到字典或者计数 + 1
                    cnt[s[start:end]] += 1
                if end < n:  # 4.2 更新当前的字符集合
                    tmp.add(s[end])
                end += 1
            start += 1
            end = start
        return max(cnt.values()) if cnt else 0  # 5. 返回最大计数即可

1298. 你能从盒子里获得的最大糖果数

我写代码之前的计算机文学家工作如下

把 init_boxs 添加到 q
while q:
    cur_box = 打开 q 最开始的盒子
    1. 拿掉所有的 candies: res+candies
    2. 拿出 cur_box 中的所有钥匙 keys
    keys = set(keys):
    遍历 q2 
        如果 q2 中的元素有对应的 key 在 keys
        则添加到 q

    3. 将 cur_box 中所有 contain box 如果状态是开加入到队列末尾
        (没开的 contain_box 怎么办?好像要另外开一个 q2 来存放他们)

除了上面的主体思路,我开始写代码之后发现要需要把已经添加到 q 中的 box_id 设置为 used 否则
否则会发生重复添加 到 q 的情况,导致结果错误

我的代码实现

性能 996 ms 25.4 MB

from collections import deque

class Solution1(object):
    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        """
        :type status: List[int]
        :type candies: List[int]
        :type keys: List[List[int]]
        :type containedBoxes: List[List[int]]
        :type initialBoxes: List[int]
        :rtype: int
        """
        r = 0  # 我们的结果记录糖果数目
        q = deque()
        # 把 init_boxs 添加到 q
        key_set = set()
        used = set()
        not_yet_open_boxs = []
        for box_id in initialBoxes:
            if status[box_id]:
                q.append(box_id)
                used.add(box_id)
            else:
                not_yet_open_boxs.append(box_id)
        while q:
            cur_box_id = q.popleft()
            used.add(cur_box_id)
            # 1. 拿掉当前 box 所有的 candies: res +=candies
            r += candies[cur_box_id]
            # 2. 拿出 cur_box 中的所有钥匙 keys
            key_set.update(keys[cur_box_id])

            # 遍历 q2
            #    如果 q2 中的元素有对应的 key 在 keys
            #    则添加到 q
            for box_id in not_yet_open_boxs:
                if box_id in key_set and box_id not in used:
                    q.append(box_id)
                    used.add(box_id)  # 上一行添加到 q ,为了以后不重复添加,这里设置一下 used

            # 3. 将 cur_box 中所有 contain box 如果状态是开加入到队列末尾
            #     (没开的 contain_box 怎么办?好像要另外开一个 q2 来存放他们)
            for box_id in containedBoxes[cur_box_id]:
                if box_id in used:
                    continue
                if status[box_id] or box_id in key_set:
                    q.append(box_id)
                    used.add(box_id)
                else:
                    not_yet_open_boxs.append(box_id)
        return r

某大佬的代码

运行内存比我优化了 0.1 M,运行时间少了 52ms
用 usable 记录盒子是否可以访问到
用 unlocked 记录是否可以解锁
这个实现没有用 set 而是直接用数据 0 、1 来记录状态,
相比较我用集合判断和使用 not_yet_open_boxs 存储可访问但还没能打开的盒子,
他的很多 O(1 ) 是“真正的 O(1) ” 而且不引入过多其它存储结构,代码简洁,大道至简;
不过以我的资质,感觉我的代码更容易看懂,更小白一些,哈哈;

性能 944 ms 25.3 MB

from collections import deque
class Solution(object):
    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        n = len(status)
        unlocked = status
        usable = [0]*n
        r = 0
        q = deque()
        for u in initialBoxes:
            usable[u] = 1
            if unlocked[u]: q.append(u)
        # we can unlock a box
        # we can also reach a box
        # whichever happens second willl enqueue the box
        while q:
            u = q.popleft()
            r += candies[u]
            for v in keys[u]:
                if unlocked[v]: continue
                unlocked[v] = 1
                if usable[v]: q.append(v)
            for v in containedBoxes[u]:
                if usable[v]: continue
                usable[v] = 1
                if unlocked[v]: q.append(v)
        return r