ARTS #14

Algorithm

本周选择的算法题是：Max Points on a Line

规则如下：

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

我实现的方案：

Runtime：88 ms，快过 65.27%。

Memory：13.9 MB，低于 42.86%。

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        points_length = len(points)
        if points_length <= 2:
            return points_length 

        # 计算最大公约数
        def calc_gcd(x: int, y: int) -> int:
            if y == 0: return x
            return calc_gcd(y, x % y)
        
        lengths = {}
        max_points = 0
        for i in range(points_length - 1):
            lengths.clear()

            max_line = 0
            same_point = 0
            for j in range(i + 1, points_length):
                x = points[j][0] - points[i][0]
                y = points[j][1] - points[i][1]

                gcd = calc_gcd(x, y)
                if gcd == 0:
                    same_point += 1
                    continue

                key = f"{x // gcd}-{y // gcd}"

                length = lengths.get(key, 0) + 1
                lengths[key] = length
                max_line = max(max_line, length)
            max_points = max(max_points, max_line + same_point + 1)

        return max_points

Review

Clean AppDelegate

很简短的一篇文章，描述了如何构建一个干净、整洁的 AppDelegate，文章是用服务化的思想将 AppDelegate 的职责剥离出去，保持 AppDelegate 自身的单一原则。

在组件化的设计里，其实还可以将 AppDelegate 自身也剥离出去：

创建一个组件或模块，将工程的 AppDelegate 放置进去
修改工程的 main.m，将 AppDelegate 的类名替换掉

比如组件名叫 Entrance，这实际上就是一个 App 的抽象，主工程被空壳化，主工程之间只有 Bundle ID、证书这些配置不同，依赖、逻辑这些由 Entrance 接管，这样开发一个新的 App 时，只需要创建另外一个 Entrance 就好。

好处就是主工程几乎不再需要修改，团队之间减少了冲突的可能，在实践过程中可以借助一些工具，比如给 Git 的 commit 添加 hook，强制不允许修改主工程。

Tip

在 Shell 环境下临时对某一条命令设置环境变量： [env] TEST=foo your-application

Python 3’s f-Strings: An Improved String Formatting Syntax (Guide)

f-Strings 不仅语法更简洁、直观，可读性更强，性能也比传统的方式要好：

>>> import timeit
>>> timeit.timeit("""name = "Eric"
... age = 74
... '%s is %s.' % (name, age)""", number = 10000)
0.003324444866599663

>>> timeit.timeit("""name = "Eric"
... age = 74
... '{} is {}.'.format(name, age)""", number = 10000)
0.004242089427570761

>>> timeit.timeit("""name = "Eric"
... age = 74
... f'{name} is {age}.'""", number = 10000)
0.0024820892040722242

更多 f-Strings 的优势和细节参见原文。

Algorithm

Solution

Review

Tip

Share