Fork me on GitHub

ARTS(10)

ARTS 第十周

每周完成一个ARTS(也就是 Algorithm、Review、Tip、Share 简称ARTS):

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

Algorithm

力扣 792. 匹配子序列的单词数

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

1
2
3
4
5
6
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。

思路:

  1. Sequece 跟 subSequence 采用双指针的方式进行逐位比较,其实时间复杂度只有 O(n),但 words 数组也要逐个遍历,所以时间复杂度为 O(n2)。

  2. 因为 words 中可能存在重复元素,所以用 map 来保存之前的比较记录。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class 匹配子序列的单词数 {

@Test
public void testResult() {
String S = "abcde";
String[] words = {"a", "bb", "acd", "ace"};
int actual = numMatchingSubseq(S, words);
Assert.assertEquals(actual, 3);
}

public int numMatchingSubseq(String S, String[] words) {
int count = 0;
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; ++i) {
if (map.containsKey(words[i])) {
count += map.get(words[i]);
} else {
int num = 0;
if (isSubSeq(S, words[i])) {
num = 1;
++count;
}
map.put(words[i], num);
}
}
return count;
}

private boolean isSubSeq(String Str, String subStr) {
int i = 0, j = 0;
while (i < Str.length() && j < subStr.length()) {
if (Str.charAt(i) == subStr.charAt(j)) {
++j;
}
++i;
}
if (j == subStr.length()) {
return true;
}
return false;
}
}

效率记录:

执行用时 : 44 ms, 在Number of Matching Subsequences的Java提交中击败了100.00% 的用户

内存消耗 : 36.9 MB, 在Number of Matching Subsequences的Java提交中击败了100.00% 的用户

Review

本周继续第八周的 Review 未完成的内容进行解读,附在文末:K8s 入门笔记

所参考的英文文章为:Weekend read, Serverless, Docker, Kubernetes

Tip

chrome 中,command + R组合快捷键可以刷新页面,同样的组合键长按 5 秒,可以清除浏览器缓存。

Share

今天分享的是一篇关于 TopN 的搜索排序算法的文章,不是我写的,后续会增加我的理解,先看文章:

劈开迷雾:蘑菇街搜索架构及搜索排序实践

-------------The End-------------