ARTS #18

Algorithm

本周选择的算法题是：Subarrays with K Different Integers

规则如下：

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Solution

这题我的解法超时了:sweat_smile: 我用的是类似于纸牌游戏的方法:sweat_smile:：

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        piles, num = [], 0
        for i in range(0, len(A)):
            delete_count = 0
            for j in range(0, len(piles)):
                pile = piles[j - delete_count]
                if not pile:
                    continue
                if len(pile) < K:
                    pile.add(A[i])
                elif len(pile) == K:
                    num += 1
                    if A[i] not in pile:
                        del piles[j - delete_count]
                        delete_count += 1

            piles.append(set())
            piles[-1].add(A[i])
        print(num, piles)
        return num + len([pile for pile in piles if len(pile) == K])

时间花费了1000+ms，结果应该是对的:anguished:

这题我看了 leetcode 上的解法和 YouTube 的视频，要点其实是需要两个滑动窗口。

有一个非常 elegant 的解法，本质上与 leetcode 是一样的，都是计算出 K 和 K-1 个子数组，然后取其差、过滤掉重复部分，剩下的就是原题解。

Runtime：508 ms，快过 80.99%。

Memory：16.3 MB，低于 100%。

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        def atMostK(A: List[int], K: int) -> int:
            count = [0] * (len(A) + 1)
            ans = left = 0
            for right in range(len(A)):
                count[A[right]] += 1
                if count[A[right]] == 1: K -= 1
                while K < 0:
                    count[A[left]] -= 1
                    if count[A[left]] == 0: K += 1
                    left += 1
                ans += right - left + 1
            return ans
        return atMostK(A, K) - atMostK(A, K - 1)

Review

What is Component-Oriented Programming (COP)?

面向组件编程并不是新话题。

作者有一个预测是未来都将采用 Web 原生的组件化技术来开发：Web Components，想想也是，组件化的隔离性和封装性让代码可重用度提高了不少，粒度降低又提高了可维护性，而现有的 React、Vue、Angular 都有自己的生态链，组件（代码）之间是不能互用的，这就很蛋疼了，同为 Web 的解决方案，你想要进入某一个生态就需要维护那个版本的代码，Vue 的组件不能用在 React 和 Angular 里。

除此之外，前端开发很”累”的一点是更新快，互相不兼容，出一个新框架就使旧的 Broken，如果写一个组件能与所有的框架兼容是一件挺美好也挺自然的事情，Web Components 看起来像是一个解决方案。

Tip

为祖国庆生！

清理 Xcode 的两个工具：

第一个是 FengNiao，LSUnusedResources 已经不再维护了，就目前看到的扫描结果，FengNiao 会更准确，但是删除前还是需要手工检查下，因为这些工具对运行时使用的资源检测是无能为力的：
```
UIImage(named: "\(iconName)\(iconSize.sizeString)")
```
第二个是 DevCleaner，可以清理：
- Device Support，不太建议删除，每个版本都对符号表的解析有帮助，空间实在不够用的话，建议找个硬盘之类的玩意儿存起来
- Archives，里面最有价值的是 dSYM 文件，一般来说我们会上传到服务器
- Derived Data，编译、打包过程中产生的中间文件

分享一篇关于基于 TeamCity 的 CI 集成方案：基于 TeamCity 的 CI 集成过程记录

Algorithm

Solution

Review

Tip

Share