ARTS 打卡 第 9 周

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

ARTS简介

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

Algorithm

力扣(LeetCode)30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。



示例 1:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2:
输入:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出:[]


解题思路:

当第一次看到这道题时,我的想法是将words中的单词排序,然后在s中搜索排序后的单词,不过将words排序时间消耗在n!,这有点不可取,所以我想换一种思路。如何在不将words中数组排序的情况下获取其可能的组合,可以考虑使用Map存储所有单词,因为单词长度相同(len),所以可以循环截取s中的len长度的字符,判断是否存在与Map中。

  1. 首先判断边界条件,如果s==null或words==null或words.length==0则返回空链表

  2. 如果s中剩余的字符串长度小于words中所有长度的总和,则也不需要继续判断

  3. 如果Map中没有s中截取的子串,也不需要继续判断

  4. words中可能有重复的单词,所以在Map中还需要记录相同单词的个数,同样在查找时也需要对重复的单词进行判断避免有遗漏

class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
if (s == null || s.length() == 0 || words == null || words.length == 0) {
return ans;
}
int wordNum = words.length;
int wordLen = words[0].length();
HashMap<String, Integer> allWords = new HashMap<>();
for (String word : words) {
Integer value = allWords.getOrDefault(word, 0);
allWords.put(word, ++value);
}
//s的剩余必须大于子串长度小于wordNum*wordLen
int limit = s.length() - wordNum * wordLen;
for (int i = 0; i <= limit; i++) {
//将子串中出现的和words中相等的单词及其出现次数存入HashMap
HashMap<String, Integer> hasWords = new HashMap<>();
//记录字串中和words中相等单词数量
int count = 0;
//统计字串中连续和words中相等的单词
while (count < wordNum) {
String wordInS = s.substring(i + count * wordLen, i + (count + 1) * wordLen);
//如果wordInS匹配words中的单词且不超过可用单词的数量,就统计其出现次数
if (allWords.containsKey(wordInS)
&& allWords.get(wordInS) > hasWords.getOrDefault(wordInS, 0)) {
Integer value = hasWords.getOrDefault(wordInS, 0);
hasWords.put(wordInS, ++value);
} else {
break; //都不匹配,结束
}
count++;
}
if (count == wordNum) {
ans.add(i);
}
}
return ans;
}
}

Review

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

微服务架构-Pattern: Saga

这篇文章的主要介绍了微服务架构下如何进行持久化:Sega模式

问题:如何在多个服务之间实现事务

强制要求:不能使用二段式提交

解决方法,Sega模式:

  1. 使用一系列的本地事务

  2. 每个服务的操作都具有补偿操作,用于回滚操作

  3. 每个服务数据操作都发布消息,成功执行下一个事务,失败执行一系列补偿操作

好处: 在不使用分布式事务的情况下实现数据一致性

缺点: 使得程序模型很复杂

需要解决的问题:每个服务必须无状态的更新数据

Tips

记录我对于Linux的学习,文件相关的命令:

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

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

删除移动复制等命令

rm 用于删除一个文件或者目录

格式:rm [options] name…

常用参数:

  1. -i 删除前逐一询问确认。

  2. -f 强制删除即使原档案属性设为唯读,亦直接删除,无需逐一确认。

  3. -r 递归地移除目录及它们的内容

  4. -d 删除空目录

rm tody.txt
rm:是否删除普通空文件 'tody.txt'?n
# 不加r参数无法删除目录
mkdir md
rm md
rm: 无法删除 'md': 是一个目录
rm -r md
rm:是否删除目录 'md'?y

mv 可以将文件或目录改名、或将文件或目录移入其它位置

格式:

mv [选项]… 源文件 目标文件

mv [选项]… 源文件… 目录

常用命令:

  1. -i 覆盖前提示

  2. -f 覆盖前永不提示

# 重命名
mv tody.txt todx.txt
# 移动文件到目录中
mv todx.txt subdir/

ps: mv 源目录名 目标目录名 目标目录已存在,将源目录移动到目标目录;目标目录不存在则将源目录改名

cp 主要用于复制文件或目录

格式:

cp [选项]… 源文件 目标文件

cp [选项]… 源文件… 目录

常用命令:

  1. -i 覆盖前提示

  2. -f 覆盖前永不提示

  3. -r 若给出的源文件是一个目录文件,此时递归复制目录及它们的内容

  4. a 此选项通常在复制目录时使用,它保留链接、文件属性,并复制目录下的所有内容。其作用等于dpr参数组合

  5. -d 复制时保留链接

  6. -p 除复制文件的内容外,还把修改时间和访问权限也复制到新文件中。

cp -r test/ newtest

file 用于辨识文件类型

格式:file [ -bcnsvzL ] [ -f 命名文件 ] [ -m 幻数文件 ] file …

常用命令:

  1. -b  列出辨识结果时,不显示文件名称。

  2. -c   检查时打印输出幻数文件的解析结果.常与 -m 一起使用,用来在安装幻数文件之前调试它

  3. -f<名称文件>  指定名称文件,其内容有一个或多个文件名称时,让file依序辨识这些文件,格式为每列一个文件名称。

  4. -L  直接显示符号连接所指向的文件的类别。

  5. -m<幻数文件>  指定魔法数字文件。

  6. -v  显示版本信息。

  7. -z  尝试去解读压缩文件的内容。

  8. [文件或目录…] 要确定类型的文件列表,多个文件之间使用空格分开,可以使用shell通配符匹配多个文件。

file add.c
add.c: C source, ASCII text
file -b add.c
C source, ASCII text
file add.o
add.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

Share

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



发布于: 2020 年 07 月 26 日 阅读数: 22
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 27 日 17:01
回复
没有更多了
ARTS打卡 第9周