ARTS 第34周

发表于

ARTS （第34周）

千里之行，起于累土。

硬件、软件都是一层一层，逐层向上构成的。

上层依赖下层，下层依赖下下层。

Algorithm 算法

正则表达式匹配

https://leetcode-cn.com/problems/regular-expression-matching/

leetcode 10

正则表达式

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
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法 回溯

ps:大部分用回溯的算法都可以用动态规划来解决，下周有空就做个动态规划的。

主要就是整理转移方程。

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
// 执行用时:1146ms,在所有java提交中击败了5.00%的用户
	// 内存消耗:35.1MB,在所有java提交中击败了91.53%的用户
	// 主串、模式串、主串索引、模式串索引
	public void pattern(char[] t, char[] p, int i, int j) {
		if (match) {
			return;
		}
		if (j == p.length) {
			if (i == t.length) {
				match = true;
			}
			return;
		}
		if (i == t.length) {
			int temp = j;

			while (temp <= p.length - 2 && p[temp + 1] == '*') {// 末尾部分匹配
				// match=true;
				temp += 2;
			}
			if (temp == p.length) {
				match = true;
			}
			return;// false
		}
		if (j + 1 < p.length && p[j + 1] == '*') {
			pattern(t, p, i, j + 1);
			return;
		}
		// 匹配部分
		if (p[j] == '.') {
			pattern(t, p, i + 1, j + 1);
		} else if (p[j] == '*' && j > 0) {// 第二个起
			// char c = p[j - 1];// 应该匹配的字符
			if (p[j - 1] == t[i] || p[j - 1] == '.') {// 或者前一个字符也是.
				pattern(t, p, i + 1, j + 1);
				pattern(t, p, i + 1, j);
			}
			// 零匹配
			pattern(t, p, i, j + 1);
		} else if ((i < t.length) && p[j] == t[i]) {
			pattern(t, p, i + 1, j + 1);
		}

	}

Review 英文文章

https://spring.io/guides/gs/accessing-data-mongodb/

spring整合mongodb

Tip 技巧

OSI七层模型

物理层：是参考模型的最低层。该层是网络通信的数据传输介质，由连接不同结点的电缆与设备共同构成。主要跟功能是：利用传输介质为数据链路层提供物理连接，负责处理数据传输并监控数据出错率，以便数据流的透明传输。

数据链路层：四参考模型的第二层。主要功能是：在物理层提供的服务基础上，在通信的实体间建立数据链路连接，传输以“帧”为单位的数据包，并采用差错控制与流量控制方法，使有差错的物理线路变成无差错的数据链路。

网络层：是参考模型的第三层。主要功能是：为数据在节点之间传输创建逻辑链路，通过路由选择算法为分组通过通信子网选择最适当的路径，以及实现拥塞控制、网络互连等功能。

传输层：是参考模型的第四层。主要功能是：向用户提供可靠地端到端服务，处理数据包错误、数据包次序，以及其他一些关键传输问题。传输层向高层屏蔽了下层数据通信的细节。因此，它是计算机通信体系结构中关键的一层。

会话层：是参考模型的第五层。主要功能是：负责维扩两个结点之间的传输连接，以便确保点到点传输不中断，以及管理数据交换等功能。

表示层：是参考模型的第六层。主要功能是：用于处理在两个通信系统中交换信息的表示方法，主要包括数据格式变换、数据加密与解密、数据压缩与恢复等功能。

应用层：是参考模型的最高层。主要功能是：为应用软件提供了很多服务，比如文件服务器、数据库服务、电子邮件与其他网络软件服务。

https://baijiahao.baidu.com/s?id=1623342279899809678&wfr=spider&for=pc

Share 分享

https://baijiahao.baidu.com/s?id=1623342279899809678&wfr=spider&for=pc OSI七层协议

https://www.cnblogs.com/onepixel/p/7092302.html 深入浅出 TCP/IP 协议栈

http://tool.oschina.net/commons http常用属性查询