ARTS 打卡 第 16 周

用户头像
引花眠
关注
发布于: 2020 年 09 月 13 日

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

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



发布于: 2020 年 09 月 13 日 阅读数: 19
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
ARTS打卡 第16周