ARTS #21

Algorithm

本周选择的算法题是：Remove Duplicates From Sorted Array

规则如下：

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution

我实现的方案：

Runtime：96 ms，快过 79.5%。

Memory：15.4 MB，低于 5.74%。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1: return len(nums)
        length = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[length] = nums[i]
                length += 1
        return length

Review

A General Overview of What Happens Before main()

超详细的分析了 main 函数执行前系统的处理步骤。

以 C/C++ 程序为例，真正的入口函数不是 main，一些系统、编译器和标准库会使用 _start 函数作为入口，然后从中调用 main 函数，_start 往往是通过汇编来实现。_start 函数会在 main 执行前做一些前置工作：

一些低级初始化的操作：
1. 配置寄存器
2. 初始化外部存储器
3. 配置 MMU
4. …
栈初始化，确保栈与 ABI 是对齐的
栈帧指针(Frame Pointer)初始化
C/C++ Runtime 初始化
其他的必要操作，比如线程支持、Stack Logging、缓冲区溢出检测等
执行 main 函数：exit(main(argc, argv))

OS X 虽然也有 _start，但是初始化逻辑不在里面。系统会先 fork 一个进程，然后再 exec 加载和执行一个 Mach-O。

exec 会调用到家族方法 execve，后续执行包括：

加载文件到内存
分析 mach_header 结构，以确认它是一个有效的 Mach-O 文件
理解 header 中的 load commands，以正确的 flag 将程序加载到分配好的地址空间里，如 __TEXT 段是只读的
加载 load commands 中指定的动态链接器
在程序文件上执行动态链接器

动态链接器被调用，也就是：

__dyld_start 被调用
做一些程序初始化的工作，比如栈初始化、ABI 对齐、C Runtime 初始化等
将链接到的所有共享库加载进程序的地址空间
Rebase & Bind，这个过程中完成 ObjC 的初始化
执行各种 Initializers
找到 LC_MAIN，并通过 _start 来调用

这是一个系列文章，目前更到了第三篇（总共6篇），从理论到代码全方位的分析，不枯燥，干货多多。

Tip

iOS 的视图运行时调试工具除了 FLEX，还有两个免费好用的：

TeamCity 下生成 CHANGE_LOG 的几种方式：

通过 Pull Request

通过代码库（如 GitHub）的 API 获取 commit 或者说明描述。值得一提的是 API 不一定会返回所有的记录。

通过本地代码库

有两种取的方式：

git log --pretty="- %s (%an)" --no-merges "master..@"，注意 git 软件的版本号，低版本不支持用 @ 表示 HEAD，可以改成 "master..HEAD"
上面的版本是直接从 master 比较，然而 master 不一定存在，可以从最新的 log 记录里动态找出两个 commit：
```
git log -1 --pretty="%s"
  
# Merged xxxx from xxxx
```
解析出两个 commit 后就能使用上面的方式来取了：
```
git log --pretty="- %s (%an)" --no-merges $TO_COMMIT..
# or
git log --pretty="- %s (%an)" --no-merges $TO_COMMIT..$FROM_COMMIT
```

本地取的方式会带上不相关的 commit：

You: 	c1..c2..c3 		(你期望得到的结果)
Other:	..c4..
		c1..c4..c2..c3	(最终得到的结果)

Algorithm

Solution

Review

Tip

Share

通过 Pull Request

通过本地代码库