ARTS打卡：第十周

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

ARTS打卡：第十周

每周完成一个ARTS：

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

Algorithm

66. Plus One(Easy)

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

题意：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

解题思路：

这道题就非常简单了，利用数学的加法运算思想，倒序遍历数组，如果当前值不等于9，直接加1，然后返回数组，若等于 9，9 + 1 = 10，需要进位，把当前值设为 0，继续遍历数组，依次类推，若最后数组能遍历完，则表明输入数组的值全为9，+1 后，位数发生变化，结果一定是首位为 1，余位为 0 的数组， 所以要重新创建一个数组 result，大小为输入数组的长度 +1，result[0] 设为 1，然后返回数组 result。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] plusOne(int[] digits) {
    //倒序遍历
        for (int i = digits.length - 1; i >= 0; i--) {
            // 不为9，则直接+1，返回结果数组
            if (digits[i] != 9) {
                digits[i] += 1;
                return digits;
            }else {
                // 为9，9+1=10，需进位，当前值设为 0
                digits[i] = 0;
            }
        }
        // 输入数组的值全为 9，+1 后位数也要 +1，结果一定是首位为 1，余位为 0 的数组
        int[] result = new int[digits.length + 1];
        // 利用整形数组初始化后，值为0的特性，只需对数组首位赋值
        result[0] = 1;
        return result;
    }
}

结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.
Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Plus One.

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

283. Move Zeroes(Easy)

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

题意：

给定一个数组 nums，写一个函数将所有 0 移动至数组末尾，同时保持数组内非零元素的相对顺序。
注意：

  1. 必须在原数组上操作，不能拷贝额外的数组
  2. 尽量减少操作次数

解题思路：

由于题目要求要在原数组上操作，不能用额外的数组空间，那我们可以先从如何复用原数组空间出发，结合要求，去解题。

因为要将所有 0 移动至数组末尾且不可改变非零元素的相对位置，那么逐步交换 0 与非零元素的位置即可实现；考虑到要复用原数组空间且减少操作步骤，我们可以不交换位置，逐步将非零元素覆盖 0，直至所有 0 都被覆盖，最后末尾补零即可。

细节请参看代码实现

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void moveZeroes(int[] nums) {
    // 边界条件
    if (nums == null || nums.length == 0) {
        return;
    }
    // 设置一个锚点，从 0 开始
    int anchor = 0;
    // 遍历输入数组
    for (int num : nums) {
        // 判断当前元素是否为非零元素
        if (num != 0) {
            //不为零，则用当前的值覆盖锚点对应的数组的值，并将锚点往前移动一位
            nums[anchor++] = num;
        }
        // 为零，锚点不移动，数组继续遍历，依次类推，就能实现非零元素覆盖 0 元素
    }
    // 经过上述遍历覆盖之后，锚点之前，皆为非零元素，锚点之后，应该全为零
    while (anchor < nums.length) {
        nums[anchor++] = 0;
    }
}

结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Move Zeroes.
Memory Usage: 36.8 MB, less than 99.94% of Java online submissions for Move Zeroes.

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

Review

本周阅读是：《Introduction to Concurrency in Spring Boot》

作者在文中提供了一些在 Spring Boot 中的处理多线程的实用建议，以及如何避免它可能产生的问题。

  1. Spring Boot 并发基础知识
    在考虑Spring Boot应用程序中的并发性时，值得考虑的关键领域是：
    • 最大线程数：分配给应用处理请求的最大线程数。
    • 共享外部资源：调用外部共享资源，例如数据库。
    • 异步方法调用：这些方法调用在等待响应时将线程释放回线程池。
    • 共享内部资源：调用内部共享资源，例如缓存和潜在的应用共享状态。
  2. Spring Boot Application 中的最大线程数
    首先我们应该注意，正在处理的线程是有限的。
    如果使用的是tomcat，你可以使用属性server.tomcat.max-threads去控制希望允许多少线程，缺省值是 0，意味着使用 Tomcat 的缺省值 200。
  3. 使用异步方法调用去解决共享外部资源花费大量等待时间的问题
  4. 在 Spring Boot 中进行异步调用
    在主程序类中的注解 @SpringApplication 之上加注解@EnableAsync，加上之后，可以在你的 Service 方法上加 @Asyn，并将返回结果改为CompletableFuture<>，这样@Asyn的方法将后台线程池中运行，合理使用，可以降低性能损耗，提高服务效应效率。
  5. 控制内部资源，避免与共享相关问题的最佳建议是不要共享它们。
  6. 如果要共享某些状态，以下是一些建议：
    • 处理不可变的对象，如果对象是不可变的，将会避免许多并发问题。如果你需要改变一些东西，那就创建一个新的对象。
    • 了解你的集合是否是线程安全的，如果需要并发访问，请使用ConcurrentHashMap或者其他线程安全的解决方法。
    • 不要假设第三方库是线程安全的。大多数代码都不是，并且必须控制对共享状态的访问。

想要了解更多细节的小伙伴们，请点击原文，查看详情。

Tip

本周分享一个在梁大的知识星球中看到的，有关 lombok 的知识点，不知道 lombok 的小伙伴们，可以查看ARTS 第二周分享中 Tip 那小节。
lombok

Share

本周分享：《基于支付场景下的微服务改造与性能优化》，深度好文。