Fork me on GitHub

ARTS(10)

Posted on | Edited on | In | Views:

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
50

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-------------