ARTS #51

Algorithm

本周选择的算法题是：Maximum Number of Occurrences of a Substring

规则如下：

Given a string s, return the maximum number of ocurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

Constraints:

1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s only contains lowercase English letters.

Solution

Runtime：184 ms，快过 82.28%。

Memory：15.9 MB，低于 75%。

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        counts = {}
        end = minSize

        while end <= len(s):
            substring = s[end-minSize:end]
            letters_count = len(set(substring))
            if letters_count <= maxLetters:
                counts[substring] = counts.get(substring, 0) + 1
            end += 1
        return max(counts.values()) if counts else 0

此题的关键在于 maxSize 包含了 minSize 结果，只需要考虑 minSize 的取值即可。

Review

View Communication Patterns in SwiftUI 这篇文章介绍了 SwiftUI 下的几种视图之间的通信方式：

从父到子（直接） - 使用 Initializer
从父到子（间接） - 使用 @Environment
从子到父（直接）
- 单向通信 - 回调
- 双向通信 - 使用 @Binding
从子到父（间接） - 使用 PreferenceKey

我觉得这样的设计有点复杂了，上述方式在不同的场景下都有自己使用场景，这就导致视图层级变化会潜在影响通信方式，然而本质上这些通信都是为了同步状态。

Tip

在 CR 过程中想到一个问题：condition_signal 和 unlock 的顺序不同会有什么影响？

在 Stackoverflow 上找到了一个讨论：signal and unlock order，这里有一个生产者/消费者的例子，其中 A 线程为消费者，B、C 线程为生产者，在此例中 A 线程被多余地唤醒了一次。

这篇文章也很有价值，指出了一个在不持有锁的情况下发生 bug 的场景。

附一个写优先的伪代码：

mutex;
rw_cond;
readers = 0;
writers = 0;
writer_active = false;

r_lock {
    pthread_lock(mutex);
    while writers > 0 {
        pthread_condition_wait(rw_cond, mutex);
    }
    ++readers;

    pthread_unlock(mutex);
}

r_unlock {
    pthread_lock(mutex);
    --readers;
    if readers == 0 {
        pthread_condition_signal(rw_cond);
    }
    pthread_unlock(mutex);
}

w_lock {
    pthread_lock(mutex);
    ++writers;
    while readers > 0 or writer_active {
        pthread_condition_wait(rw_cond, mutex);
    }
    --writers;
    writer_active = true;
    pthread_unlock(mutex);
}

w_unlock {
    pthread_lock(mutex);
    writer_active = false;
    pthread_condition_broadcast(rw_cond);
    pthread_unlock(mutex);
}

Readers–writer lock

笔记

macos / iOS 内核(XNU)中的主要模块：

Mach - 服务层
- 提供基本的抽象
  - task - 任务
  - thread - 线程
  - port - 端口
  - message - 消息
  - memory - 内存
- 处理器管理
- 抢占式多任务，包括对任务和线程的支持
- 虚拟内存的管理
- IPC 通信
- …
BSD - 系统编程接口提供者
I/O Kit - 驱动程序的运行时环境
libkern - 内核库

Algorithm

Solution

Review

Tip

Share

笔记