ARTS 打卡 第 16 周

ARTS 简介

Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

Algorithm

力扣（LeetCode）41. 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

提示：你的算法的时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。

示例 1:
输入: [1,2,0]输出: 3示例 2:
输入: [3,4,-1,1]输出: 2示例 3:
输入: [7,8,9,11,12]输出: 1

解题思路：

首先对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。这是因为如果 [1, N] 都出现了，那么答案是 N+1，否则答案是 [1, N] 中没有出现的最小正整数。

如果使用 Set 存储每个元素的值，然后循环遍历 Set，则时间复杂度为 O(N)，空间复杂度也是 O(N)，不满足要求。

在《剑指 Offer：名企面试官精讲典型编程题（第 2 版）》中面试题 3 中有介绍空间复杂度为 O(1)的方法，以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置

class Solution {    public int firstMissingPositive(int[] nums) {        int n = nums.length;        for (int i = 0; i < n; ++i) {            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {                int temp = nums[nums[i] - 1];                nums[nums[i] - 1] = nums[i];                nums[i] = temp;            }        }        for (int i = 0; i < n; ++i) {            if (nums[i] != i + 1) {                return i + 1;            }        }        return n + 1;    }}

ps:参考资料《剑指Offer：名企面试官精讲典型编程题（第2版）》

Review

学习-微服务架构模式系列，网站地址是：https://microservices.io

微服务架构-Pattern: Polling publisher

这篇文章的主要介绍了微服务架构下如何进行发布数据更新：轮询发布者模式

问题：你实现了事务发件箱模式，那么如何将事件发布到发件箱然后到事件代理

解决方法，通过轮询发件箱表发布消息

好处：

1. 适用于任何 SQL 数据库

不足

1. 很难按顺序发布事件

2. 不是所有 NoSQL 数据库都支持该模式

ps:《微服务架构设计模式》

Tips

记录我对于 Linux 的学习，文件相关的命令：

ps:”~” 表示为 home 目录，”.” 则是表示目前所在的目录，”..” 则表示当前目录的上一层目录

-h 用人类可读的格式展示(G（千兆字节），M（兆字节）,K（千字节）)，大部分命令有这个参数

文件内容查找

grep 命令用于查找文件里符合条件的字符串，如果发现某文件的内容符合所指定的范本样式，预设 grep 指令会把含有范本样式的那一列显示出来。

grep 有两个变种变种，egrep 和 fgrep 。 Egrep 与 grep -E 相同。 Fgrep 与 grep -F 相同。

格式：grep [options] PATTERN [FILE…]

常用选项：

1. -a 或 –text : 不要忽略二进制的数据。

2. -A<显示行数> 或 –after-context=<显示行数> : 除了显示符合范本样式的那一列之外，并显示该行之后的内容。

3. -b 或 –byte-offset : 在显示符合样式的那一行之前，标示出该行第一个字符的编号。

4. -B<显示行数> 或 –before-context=<显示行数> : 除了显示符合样式的那一行之外，并显示该行之前的内容。

5. -c 或 –count : 计算符合样式的列数。

6. -C<显示行数> 或 –context=<显示行数>或-<显示行数> : 除了显示符合样式的那一行之外，并显示该行之前后的内容。

7. -d <动作> 或 –directories=<动作> : 当指定要查找的是目录而非文件时，必须使用这项参数，否则 grep 指令将回报信息并停止动作。

8. -e<范本样式> 或 –regexp=<范本样式> : 指定字符串做为查找文件内容的样式。

9. -E 或 –extended-regexp : 将样式为延伸的正则表达式来使用。

10. -f<规则文件> 或 –file=<规则文件> : 指定规则文件，其内容含有一个或多个规则样式，让 grep 查找符合规则条件的文件内容，格式为每行一个规则样式。

11. -F 或 –fixed-regexp : 将样式视为固定字符串的列表。

12. -G 或 –basic-regexp : 将样式视为普通的表示法来使用。

13. -h 或 –no-filename : 在显示符合样式的那一行之前，不标示该行所属的文件名称。

14. -H 或 –with-filename : 在显示符合样式的那一行之前，表示该行所属的文件名称。

15. -i 或 –ignore-case : 忽略字符大小写的差别。

16. -l 或 –file-with-matches : 列出文件内容符合指定的样式的文件名称。

17. -L 或 –files-without-match : 列出文件内容不符合指定的样式的文件名称。

18. -n 或 –line-number : 在显示符合样式的那一行之前，标示出该行的列数编号。

19. -o 或 –only-matching : 只显示匹配 PATTERN 部分。

20. -q 或 –quiet 或–silent : 不显示任何信息。

21. -r 或 –recursive : 此参数的效果和指定”-d recurse”参数相同。

22. -s 或 –no-messages : 不显示错误信息。

23. -v 或 –revert-match : 显示不包含匹配文本的所有行。

24. -V 或 –version : 显示版本信息。

25. -w 或 –word-regexp : 只显示全字符合的列。

26. -x –line-regexp : 只显示全列符合的列。

27. -y : 此参数的效果和指定”-i”参数相同。

1.grep match_pattern file_name # 在文件中搜索一个单词2.grep "match_pattern" file_1 file_2 file_3 #在多个文件中查找3.grep -v "match_pattern" file_name #输出除之外的所有行4.5.grep –e "正则表达式" 文件名 #使用正则表达式

Share

分享最近对计算机基础的复习，这次分享的是程序的机器级表示 - 异构的数据结构，可能会有不足之处，之后会根据理解继续修改。