ARTS打卡：第七周

发表于 | 分类于 | 本文总阅读量 次

ARTS打卡：第七周

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

Algorithm

189. Rotate Array(Easy)

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

题意：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
需要注意是只允许使用 O(1)的额外空间，效果如 Example 所示。

解题思路1：使用暴力破解。
循环 K 次，每次遍历数组，让数组的每一位元素往前移动一位。

解题代码如下：

1
2
3
4
5
6
7
8
9
public void rotate(int[] nums, int k) {
    for (int i = 0; i < k; i++) {
        for (int j = 1; j < nums.length; j++) {
            int temp = nums[j];
            nums[j] = nums[0];
            nums[0] = temp;
        }
    }
}

复杂度分析：
时间复杂度分析：O(k * n)
空间复杂度分析：O(1)

解题思路2：
仔细观察 Example ，我们可以发现一个事实，旋转数组 K 次，K 个元素从数组后端挪动到前端，其余元素从前端挪到后端。
在这种方法中，我们首先翻转数组，然后再次翻转数组前 k 个元素，最后翻转 n - k 个元素，即其余的元素，n 为数组长度；这样就能得出答案。
例子：

1
2
3
4
原始数组                           : 1 2 3 4 5 6 7
首先翻转整个数组                    : 7 6 5 4 3 2 1
其次翻转数组前 k 个元素             : 5 6 7 4 3 2 1
最后翻转数组后 n - k 个元素         :5 6 7 1 2 3 4 --> Result

解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void rotate(int[] nums, int k) {
    k = k % nums.length;
    // 翻转整个数组
    reverse(nums, 0, nums.length - 1);
    // 翻转数组前 k 个元素
    reverse(nums, 0, k - 1);
    // 翻转数组后 n - k 个元素
    reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

217. Contains Duplicate(Easy)

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

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

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

题意：
给一个 int 类型的数组，如果数组内有重复的元素，返回 true，无则返回 false。

思路1：结合set集合进行判重。

代码如下：

1
2
3
4
5
6
7
8
9
10
public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)){
            return true;
        }
        set.add(num);
    }
    return false;
}

复杂度：
时间复杂度：O(n)，set的查找和插入消耗的时间都是常量。
空间复杂度：O(n)，额外消耗的空间就是set的大小，取决于有多少元素加入到集合中。

思路2：先对数组进行排序，然后遍历进行判重。

代码如下：

1
2
3
4
5
6
7
8
9
public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

复杂度：
时间复杂度：O(nlogn)。Array.sort() 时间复杂度是 O(nlogn)，遍历是 O(n)，不过遍历的次数是基于排序的情况来决定的，所以时间复杂度是 O(nlogn)。
空间复杂度：O(1)。空间复杂度取决于 Arrays.sort()的内部实现，如果是使用heapsort，通常会花费 O(1) 的辅助空间。

思路3：利用 Java 8 的 distinct() 和 count() 来做。

代码如下：

1
2
3
4
public boolean containsDuplicate(int[] nums) {
    long count = Arrays.stream(nums).distinct().count();
    return nums.length == count;
}

这种方法从 leetcode 给出结果上来看，消耗时间最长，空间消耗也最大，时间和空间的复杂度不知如何分析(:з」∠)，不过代码更简洁易懂。

Review

本周阅读的是《UNIX® Network Programming Volume 1, Third Edition: The Sockets Networking 》中的 6.2 I/O Models。

作者 Stevens 在这节中详细说明了五种 IO Model 的特点和区别。

这五种 IO Model 分别是：BIO（blocking IO）、NIO（non-blocking IO）、 IO multiplexing、signal driven IO 和 AIO（asynchronous IO）。

Tip

分享一篇我在学习《左耳听风》专栏做的笔记，有关于如何高效学习的：97 - 高效学习：深度，归纳和坚持实践

Share

本周分享梁大组织维护的一个知识仓库：服务端思维，里面有每周答疑周报、每月精读等内容，非常值得小伙伴们关注~