Algorithm

本周选择的算法题是：Global and Local Inversions

规则如下：

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

Solution

我实现的方案：

Runtime：384 ms，快过 91.86%。

Memory：14.1 MB，低于 50%。

class Solution:
    def isIdealPermutation(self, A: List[int]) -> bool:
        for i in range(len(A)):
            if abs(A[i] - i) > 1:
                return False
        return True

规则上有很多可以利用的空间：

序列是无序的等差序列：
- N = 3 时，A 的取值范围为 0 - 2
- N = 5 时，A 的取值范围为 0 - 4
- …
通过规则可以发现 Global 的置换数量一定是大于等于 Local 置换数量，而 Local 置换数量可以通过以下方式简单计算得出：
```
for i in range(1, len(A)):
    if A[i] > A[i - 1]:
        # The number of local inversions += 1
```
所以排除掉 Global 与 Local 相同的置换后，只有一种情况会出现 Global 大于 Local，就是有的数字越了1个位置以上，而数字与数字之间的差是1，所以只用判断当前数字和当前索引的差大于1时，一定会有一个非 Local 的 Global 置换

Review

Modularising iOS apps into powerful reusable kits
该文与其说是模块化的实践，不如说是代码是如何组织的。模块化和组件化不是对仓库、代码目录结构提出要求，而是对组件之间的关系以及使用方式提出要求，一般来讲，它要求：

组件之间独立编译，互不依赖
代码隔离，组件只对属于自己的业务线可见，避免误修改和版本管理的问题
可重用、可组合
可监控、可跟踪

然后在实践过程中会面临代码组织的问题，现在流行的组织方式有：

multrepo - 所有的组件和模块都独立仓库，然后用依赖来管理，但是这种方式在业务上会切换的很繁琐
monorepo - 一个仓库，管理和效率上是比较舒服，但是组件的版本不好控制、代码的安全性不好

或者全部使用 CocoaPods 来管理，也有劣势：

CocoaPods 对修改体验不好，需要切到其他项目里经历：修改 -> 提交 -> 发布，然后在主项目里更新依赖
CocoaPods 对源码组织形式也不好，sub spec 只有单层，这意味着你大多数代码都是线性排列下来，毫无章法：

文章中的实践采用的是用一个 Xcode Workspace 集成多个 Projects 的方式，这种方式有几个明显的优势：

首先，非业务模块/组件（也可以称为二方库）和第三方组件用 Cocoapods 管理比较合适，这些代码普遍是读多写少，版本号稳定
可热插拔的业务模块用子工程引用，它们也是独立仓库，但是修改体验好，通过建立和主工程相同的分支名，实现版本管理

先在此结合文章和自己思考记录一部分。

Tip

git-lfs（Git Large File Storage）是一个开源软件，作用是将仓库内的大文件，如音视频、数据集、图片等，替换为一个指针，以减少仓库的体积：

传统的做法会带来仓库体积增长过快的问题：

GitHub 和 GitLab 都支持该功能。

详细用法可参考：Learn Version Control with Git。

Chrome 下不使用插件进行全屏截图的方法：

打开 DevTools
打开 Command 菜单
- Windows and Linux: Control+Shift+P
- Mac: Command+Shift+P
选择你需要的截图方式：

Algorithm

Solution

Review

Tip

Share