ARTS （第35周）

越理解底层，基础越扎实，程序的构建越容易。

Algorithm 算法

###正则表达式(DP解法)

leetcode 10

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

给你一个字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法(DP)

// DP
	//执行用时:2 ms,在所有java提交中击败了99.88%的用户
	//内存消耗:36.3 MB,在所有java提交中击败了87.64%的用户
	public boolean isMatch(String s, String p) {
		if (s == null || p == null)
			return false;
		int sl = s.length();
		int pl = p.length();
		boolean[][] dp = new boolean[sl + 1][pl + 1];
		dp[0][0] = true;
		for (int i = 0; i <= sl; i++) {
			// 这里i = 0 代表着 第0个字符 即什么都没有 i=1 代表第一个字符
			// 原本我觉得i应该从1开始匹配起，
			// 后面发现 如果模式串是a*之类开头的情况，i=0就必须考虑进去
			// 也可以将这部分 另写一个循环判断 这里就可以从1判断起
			for (int j = 1; j <= pl; j++) {
				// '*'的情况
				// 这里默认当成传入的是合法的字符 如果模式串以*开头 这里就会报错
				if (p.charAt(j - 1) == '*') {
					// 分支情况1 直接匹配
					// 判断之前的字符串是否匹配
					// ps连续匹配单字符就是多字符的匹配， 多字符也是在这里匹配
					if (i > 0 && dp[i - 1][j]) {// 单字符的情况
						if (p.charAt(j - 2) == '.' || (p.charAt(j - 2) == s.charAt(i - 1))) {
							dp[i][j] = true;
						}
					}
					// 分支情况2 当前字符当成空的情况
					if (dp[i][j - 2]) {
						// 直接判断本字符前的东西是否为true
						dp[i][j] = true;
					}
				} else {
					// 情况 字符直接匹配和'.'的判断
					// 先判断i-1和j-1是否已经匹配了 即之前的字符串是否匹配
					if (i > 0 && dp[i - 1][j - 1]) {
						// 字符直接匹配和'.'的判断
						if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
							dp[i][j] = true;
						}

					}

				}

			}
		}
		return dp[sl][pl];

	}

最小路径和

leetcode 64

https://leetcode-cn.com/problems/minimum-path-sum/

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

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

解法1 回溯


// 回溯
public int minPathSum(int[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;
	return minPathSumHelp(grid, 0, 0, 0);
}

// { 1, 3, 1 }
// { 1, 5, 1 }
// { 4, 2, 1 }
public int minPathSumHelp(int[][] grid, int i, int j, int t) {
	t += grid[i][j];
	int r = t;
	// 越界判断
	if (i < grid.length - 1) {
		// 有右 如果没有下t就是右边的值
		r = minPathSumHelp(grid, i + 1, j, t);
		if (j < grid[i].length - 1) {
			// 有右又有下
			r = Math.min(minPathSumHelp(grid, i, j + 1, t), r);
		}
	} else if (j < grid[i].length - 1) {
		// 没有右边 只有下
		r = minPathSumHelp(grid, i, j + 1, t);
	}
	// System.out.println("[" + i + "," + j + "]->" + t);
	// System.out.println("[" + i + "," + j + "]->" + r);
	// System.out.println();
	return r;

}

解法2 DP

public int minPathSum_dp(int[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;
	int[][] dp = new int[grid.length][grid[0].length];
	// 初始值
	dp[0][0] = grid[0][0];
	// 首列初始值
	for (int i = 1; i < grid.length; i++) {
		// 每行的首个 只可能从上面获取
		dp[i][0] = dp[i - 1][0] + grid[i][0];
	}
	// 首行初始值
	for (int i = 1; i < grid[0].length; i++) {
		// 首行的每个 只可能从左面获取
		dp[0][i] = dp[0][i - 1] + grid[0][i];

	}
	for (int i = 1; i < grid.length; i++) {
		for (int j = 1; j < grid[i].length; j++) {
			// 要么从左边获取 要么从上边获取
			dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
		}
	}
	// for (int i = 0; i < dp.length; i++) {
	// System.out.println(Arrays.toString(dp[i]));
	// }
	return dp[grid.length - 1][grid[0].length - 1];
}
//做了优化节省空间
public int minPathSum_dp2(int[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;
	int[] dp = new int[grid[0].length];
	// 初始值
	dp[0] = grid[0][0];
	// 首行初始值
	for (int i = 1; i < grid[0].length; i++) {
		// 首行的每个 只可能从左面获取
		dp[i] = dp[i - 1] + grid[0][i];

	}
	for (int i = 1; i < grid.length; i++) {
		dp[0] = dp[0] + grid[i][0];// 首列
		for (int j = 1; j < grid[i].length; j++) {
			// 要么从左边获取 要么从上边获取
			dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
		}
	}
	
	return dp[grid[0].length - 1];
}

Review 英文文章

spring跨域

https://spring.io/guides/gs/rest-service-cors/

除了全局配置还可以单独在某个控制器上加这个注解允许跨域访问。

1	@CrossOrigin(origins = "http://localhost:9000")

Tip 技巧

主要摘录自 https://blog.csdn.net/qq_38950316/article/details/81087809

3次握手和4次挥手

第一次握手：建立连接时，客户端发送syn包（syn=x）到服务器，并进入SYN_SENT状态，等待服务器确认；SYN：同步序列编号（Synchronize Sequence Numbers）。

第二次握手：服务器收到syn包，必须确认客户的SYN（ack=x+1），同时自己也发送一个SYN包（syn=y），即SYN+ACK包，此时服务器进入SYN_RECV状态；

第三次握手：客户端收到服务器的SYN+ACK包，向服务器发送确认包ACK(ack=y+1），此包发送完毕，客户端和服务器进入ESTABLISHED（TCP连接成功）状态，完成三次握手。

1）客户端进程发出连接释放报文，并且停止发送数据。释放数据报文首部，FIN=1，其序列号为seq=u（等于前面已经传送过来的数据的最后一个字节的序号加1），此时，客户端进入FIN-WAIT-1（终止等待1）状态。 TCP规定，FIN报文段即使不携带数据，也要消耗一个序号。
2）服务器收到连接释放报文，发出确认报文，ACK=1，ack=u+1，并且带上自己的序列号seq=v，此时，服务端就进入了CLOSE-WAIT（关闭等待）状态。TCP服务器通知高层的应用进程，客户端向服务器的方向就释放了，这时候处于半关闭状态，即客户端已经没有数据要发送了，但是服务器若发送数据，客户端依然要接受。这个状态还要持续一段时间，也就是整个CLOSE-WAIT状态持续的时间。
3）客户端收到服务器的确认请求后，此时，客户端就进入FIN-WAIT-2（终止等待2）状态，等待服务器发送连接释放报文（在这之前还需要接受服务器发送的最后的数据）。
4）服务器将最后的数据发送完毕后，就向客户端发送连接释放报文，FIN=1，ack=u+1，由于在半关闭状态，服务器很可能又发送了一些数据，假定此时的序列号为seq=w，此时，服务器就进入了LAST-ACK（最后确认）状态，等待客户端的确认。
5）客户端收到服务器的连接释放报文后，必须发出确认，ACK=1，ack=w+1，而自己的序列号是seq=u+1，此时，客户端就进入了TIME-WAIT（时间等待）状态。注意此时TCP连接还没有释放，必须经过2∗∗MSL（最长报文段寿命）的时间后，当客户端撤销相应的TCB后，才进入CLOSED状态。
6）服务器只要收到了客户端发出的确认，立即进入CLOSED状态。同样，撤销TCB后，就结束了这次的TCP连接。可以看到，服务器结束TCP连接的时间要比客户端早一些。
————————————————
版权声明：本文为CSDN博主「青柚_」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_38950316/article/details/81087809

https://www.cnblogs.com/milantgh/p/4075912.html 无类别域间路由选择

https://blog.csdn.net/qq_38950316/article/details/81087809 TCP的三次握手与四次挥手理解

ARTS （第35周）

Algorithm 算法

最小路径和

Review 英文文章

Tip 技巧

Share 分享