ARTS打卡：第九周

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

ARTS打卡：第九周

每周完成一个ARTS：

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

Algorithm

350. Intersection of Two Arrays II(Easy)

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

大致题意：

给两个数组，写一个方法计算它们的交集。
注意：

  1. 结果中的每个元素应该出现在两个数组中显示的次数。
  2. 结果可以是任何顺序。

解题思路1：
假设输入的数组为 a、b，输出的数组为 r

  1. 对a、b进行排序
  2. 假设 i 为 a 的起始下标 0，j 为 b 的起始下标 0，k 为结果集的起始下标，从 0 开始
  3. 遍历数组，比较 a[i] 和 b[j]，如果 a[i] < b[j]，移动下标 i，即 i++；如果 a[i] > b[j]，移动下标 j，即 j++；如果 a[i] = b[j]，使得 r[k] = b[j]，且同时往前移动三个数组的下标。
  4. 以此类推，直至 i 等于数组a的长度且 j 等于数组b的长度，终止循环，数组 r 就是结果
  5. 输出数组 r 可以为 数组 a

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] intersect(int[] nums1, int[] nums2) {
    // 边界条件
    if (nums1.length == 0) {
        return nums1;
    }
    if (nums2.length == 0) {
        return nums2;
    }
    LinkedList<Integer> results = new LinkedList<>();
    // 1. 先排序
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            nums1[k++] = nums1[i];
            i++;
            j++;
        }
    }
    return Arrays.copyOf(nums1, k);
}

结果：
Runtime: 1 ms, faster than 100.00% of Java online submissions for Intersection of Two Arrays II.
Memory Usage: 35.5 MB, less than 73.31% of Java online submissions for Intersection of Two Arrays II.

复杂度分析：
时间复杂度：O(n)。Array.sort() 时间复杂度是 O(nlogn)，遍历是 O(n)，时间复杂度主要取决于遍历。
空间复杂度：O(k)。

解题思路2：
因为题目对结果的顺序没有要求，所以我们可以借助 map 来实现。

  1. 假设输入的数组为：数组a和数组b，i，j分别为数组a、b的下标；
  2. 借助一个容器 map，key 为数组的值，value 为值出现的次数和用一个 list 存储结果
  3. 遍历数组a，判断 map 的 key 集合中是否有 a[i]，有，则 value + 1，无，则把这个值加入到map中
  4. 遍历数组b，判断 map 的 key 集合中是否有 b[j]，且对应的value 是否大于 0，若是，将 b[j] 加入到结果 list 中，并将 value 减一。
  5. 遍历结束，将list转为数组，输出结果。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static int[] intersect(int[] nums1, int[] nums2) {
    // 边界条件
    if (nums1.length == 0) {
        return nums1;
    }
    if (nums2.length == 0) {
        return nums2;
    }
    Map map = new HashMap<Integer, Integer>(16);
    List<Integer> result = new ArrayList<>();
    for (int i : nums1) {
        // 判断 map 的 key 集合中是否有 a[i]，有，则 value + 1，无，则把这个值加入到map中
        if (map.containsKey(i)) {
            map.put(i, (int) map.get(i) + 1);
        } else {
            map.put(i, 1);
        }
        // 可以换成 java 8 的写法
        //map.put(nums1[i], (int) map.getOrDefault(nums1[i], 0) + 1);
        // 或
        //map.merge(nums1[i], 1, (a, b) -> (int) a + (int) b);
    }
    for (int i : nums2) {
    //判断 map 的 key 集合中是否有 b[j]，且对应的value 是否大于 0，若是，将 b[j] 加入到结果 list 中，并将 value 减一
        if (map.containsKey(i) && (int) map.get(i) > 0) {
            result.add(i);
            map.put(i, (int) map.get(i) - 1);
        }
    }
    int[] r = new int[result.size()];
    for (int i = 0; i < r.length; i++) {
        r[i] = result.get(i);
    }
    return r;
}

结果：
Runtime: 3 ms, faster than 54.64% of Java online submissions for Intersection of Two Arrays II.
Memory Usage: 35.7 MB, less than 66.55% of Java online submissions for Intersection of Two Arrays II.

Review

这周分享：《Spring Boot – Best Practices》
作者在文中结合了自己的工作经验和其他springboot专家著作，给出了如下15条实践建议：

  1. 使用自动配置
  2. 使用Spring Initializr来开始一个新的Spring Boot项目
  3. 考虑为常见的组织问题创建自己的自动配置
  4. 正确设计你的代码目录结构
  5. 保持你的 @Controller 的整洁和专一
  6. 围绕业务功能来构建你的 @Service
  7. 使数据库独立于核心业务逻辑之外
  8. 保持核心业务逻辑独立于 spring boot
  9. 推荐使用构造函数
  10. 熟悉并发模型
  11. 加强配置管理的外部化
  12. 提供全局异常处理
  13. 使用日志框架
  14. 测试你的代码
  15. 使用切片测试，让测试更容易，更专注

感兴趣的小伙伴们，可以点击原文，查看更多的详情~

Tip

这周分享一个在工作上用到的抓包工具：Wireshark，可以直接在网上下载，是个免费软件。
下载地址：https://www.wireshark.org/download.html
使用方法可以直接 google 或者度娘又或者看我在 Share 章节分享的笔记。

Share

本周分享：Wireshark使用详解以及HTTP抓包。

该笔记部分内容是我结合网上许多资料而来的，记录时间比较久远了，已经不清楚是从哪几篇文章上摘抄下来的了，如有侵权，联系删除。