左耳听风 ARTS 打卡第二周

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Algorithm: LeetCode 27. Remove Element
Review: IBM 的 Data Science Community 中的一篇文章 A landscape diagram for Python data
Tip: Linux 中的 /bin，/sbin，/usr/bin，/usr/sbin，/usr/local/bin 和 /usr/local/sbin
Share: 自己对《A landscape diagram for Python data》这篇文章的翻译

Algorithm

难度：Easy

题意：给定一个数组 nums 和一个值 val，原地移除数组中包含的所有的 val 值，然后返回新的数组的长度。要求不能给另一个数组分配额外的内存空间，所以必须以 O(1) 的空间复杂度原地更改输入的数组。元素的顺序可以改变，超出新数组长度的情况可以不考虑。

例子 1：

Given nums = [3,2,2,3], val = 3,

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

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

例子 2：

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

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

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

在 LeetCode 的环境下，你的输出应是一个整数，但输出的答案是一个数组。因为在实际生产过程中，数组是以「引用（Reference）」的方式传递的，这也就意味着，在函数中修改输入数组对调用者可见。为了避免这种「可见」性，LeetCode 内部有如下操作：

// nums is passed in by reference. (i.e., without making a copy)

int len = removeElement(nums, val);

// 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]);
}

解法：

创建一个 i，使用一个 for 循环，没有碰到 val 的时候，直接借用当前数字替换原有数组中的 nums[i]，累加 i，最后返回 i 即可

 class Solution(object):
     def removeElement(self, nums, val):
         """
         :type nums: List[int]
         :type val: int
         :rtype: int
         """
         i = 0
         for num in nums:
             if num != val:
                 nums[i] = num
                 i += 1

         return i

时间复杂度 O(n)，空间复杂度 O(1)。最坏的情况是，待移除的元素都在数组最末尾的时候，num 需要移动到数组末尾，nums[i] 也需要移动到自己的末尾，一共是 2n 步。

考虑一些需要移除的元素比较少的情况，比如 nums = [1,2,3,5,4], val = 4，如果按照上面的算法，需要对前四个元素做一个不必要的拷贝操作；另外一个例子，nums = [4,1,2,3,5], val = 4，按照之前的算法我们需要将 1,2,3,5 这几个元素全部往前移一位，但是根据题目描述，我们其实不需要保留原来的元素顺序，所以我们只需要在遇到目标元素的时候，把数组最后的元素拿来覆盖当前的元素，然后将数组长度减 1 即可，这样即使最后一个元素也是目标元素，我们也会在下一个循环中检查它。
```
 class Solution(object):
     def removeElement(self, nums, val):
         """
         :type nums: List[int]
         :type val: int
         :rtype: int
         """
         i = 0
         length = len(nums)
         while i < length:
             if nums[i] == val:
                 nums[i] = nums[length - 1]
                 length -= 1
             else:
                 i += 1

         return i
```
时间复杂度 O(n)，空间复杂度 O(1)。

注：不使用 Python 内部自带的一些函数，可以锻炼思考能力。

Review

A landscape diagram for Python data

这周的文章选择的是 IBM 的 Data Science Community 中的一篇文章。文章列举说明了当下最流行的 Python 库和数据科学框架。这个景观图中显示了 50 个左右的 Python 库和框架，以及它们之间的相互关系。 A landscape diagram for Python data 中文翻译版可以参考 Share 部分中我自己的翻译。

Tips

理解 Linux 中的 /bin，/sbin，/usr/bin，/usr/sbin，/usr/local/bin 和 /usr/local/sbin

在清理电脑中 Python 版本时发现的两个链接，完全理解了这几个路径的意义和区别：

/usr/bin vs /usr/local/bin on Linux

Differences between /bin, /sbin, /usr/bin, /usr/sbin, /usr/local/bin, /usr/local/sbin

《A landscape diagram for Python data》翻译

Python 数据科学的风景图

Contents:

Algorithm

Review

Tips

Share