ARTS #40

Algorithm

本周选择的算法题是：Subsets II

规则如下：

Given a collection of integers that might contain duplicates, *nums*, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution

我实现的方案：

Runtime：28 ms，快过 96.57%。

Memory：12.8 MB，低于 100%。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        nums.sort()
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:
                start = len(result)
            for j in range(len(result) - start, len(result)):
                result.append(result[j] + [nums[i]])
        return result

常规的解法是先生成各种排列然后再去重：

result += [subset + [num] for subset in result]

但是去重的效率很低。

Review

Project LightSpeed: Rewriting the Messenger codebase for a faster, smaller, and simpler messaging app

Facebook Messenger 团队发布的文章，记录了他们重写 Messenger 的主要思路：

使用原生功能
重用 UI
使用 SQLite
使用服务器
防止未来代码增长

我对前两点深有感触，一般来说团队会倾向于两种做法：

UI & 交互全套自定义
- 优点：可以针对不同版本提供相近的体验
- 缺点：维护成本、团队学习成本过高
使用系统 UI & 交互
- 优点：简单、快速、稳定，标准化的设计
- 缺点：也受限于系统，需要在产品上考虑取舍

两种方式我都尝试过，就前者来说，前期工作量比较大，而且替换一个系统组件，很可能会带来“一发不可收拾”的后果，直接导致大量的组件被替代；在交互设计上还要考虑和系统风格接近；View 层自身的特点不便于迁移，跨项目基本不可用。

所以就我个人而言，我更偏好于后者。

使用 SQLite 和使用服务器是一起形成的解决方案，其中的 trade-off 我还需要思考。

为功能/需求增加预算的机制挺不错，这需要工具链的支撑和团队价值观的统一，值得尝试推行（并不容易）。

最后说下本文中我最喜欢的话：

Completing features on time is important, but hitting quality targets (including but not limited to binary size budgets) is even more important.

Tip

python3 中得到一个扁平列表的方法：

import itertools
test = [[-1, -2], [30, 40], [25, 35]]
print(list(itertools.chain.from_iterable(test)))

#-> [-1, -2, 30, 40, 25, 35]

如果原始列表同时包含了数组和元组：

def unifylist(l_input, l_target):
    for it in l_input:
        if isinstance(it, list):
            unifylist(it, l_target)
        elif isinstance(it, tuple):
            unifylist(list(it), l_target)
        else:
            l_target.append(it)
    return l_target

test =  [[-1, -2], [1,2,3, [4,(5,[6,7])]], (30, 40), [25, 35]]

print(unifylist(test,[]))

#Output => [-1, -2, 1, 2, 3, 4, 5, 6, 7, 30, 40, 25, 35]

有一个三方包 more_itertools 也能做到类似的事：

import more_itertools

test = [[-1, -2], [1, 2, 3, [4, (5, [6, 7])]], (30, 40), [25, 35]]

print(list(more_itertools.collapse(test)))

#Output=> [-1, -2, 1, 2, 3, 4, 5, 6, 7, 30, 40, 25, 35]

读《答疑解惑：渴望、热情和选择》有感。

学习是反人性的。我认为无论是什么事情，要想长期坚持，有两个套路：

有渴望、有反馈，付出得到回报，收获快乐，这是一种套路
把过程变得简单、可重复，这是另一种套路

能长期坚持一件事，就已经超过了大多数。

从自身来看，一个人优秀的成本变得越来越高，不过还是有一些方法的。持续、保持提升的一些建议：

客观地审视自己
确定自己想要什么
注重长期的可能性，而不是短期的功利
尽量关注自己会得到的东西，而不是自己失去的东西
不要和大众的思维一样

Algorithm

Solution

Review

Tip

Share