ARTS 第55周

发表于

ARTS （第55周）

“看懂”和“会用”是两回事，而“用好”更是难上加难。

实际上，不管是应用设计原则还是设计模式，最终的目的还是提高代码的可读性、可扩展性、复用性、可维护性等。我们在考虑应用某一个设计原则是否合理的时候，也可以以此作为最终的考量标准。

出处：极客时间《设计模式之美》（作者：王争）

https://time.geekbang.org/column/intro/250

Algorithm 算法

孩子们的游戏(圆圈中最后剩下的数)

1
2
3
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 将数组视为环，逐个遍历。并创建个数组保存是否去除

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
// 环形遍历数组 记录已遍历的数据
	public int LastRemaining_Solution_(int n, int m) {
		int r = -1;
		if (n <= 0 || m < 0)
			return -1;
		// 剩余数量
		int size = n;
		// 当前索引
		int idx = 0;
		// 记录当前位置是否去除
		boolean[] ex = new boolean[n];
		// 环形遍历数组 记录确认的数据
		// 0 1 2 3 4
		// 3 1 r 2 4
		while (size > 1) {
			int count = m;
			while (true) {
				if (!ex[idx]) {
					if (--count == 0) {
						ex[idx] = true;
						size--;

						break;
					}
				}
				if (++idx == n) {
					idx = 0;
				}
			}

		}

		// 找出没有记录的那个
		for (int i = 0; i < ex.length; i++) {
			if (!ex[i]) {
				r = i;
				break;
			}
		}
		return r;

	}

解法2

这个是解法1的优化，依旧将数组视为环，通过计算快速找出索引。并创建个数组保存是否去除

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
// 根据索引快速找到位置
public int LastRemaining_Solution__(int n, int m) {
	int r = -1;
	if (n <= 0 || m < 0)
		return -1;
	// 剩余数量
	int size = n;
	int count = 0;
	int idx = 0;
	// 记录当前位置是否去除
	boolean[] ex = new boolean[n];
	// 环形数组 记录已遍历的数据
	// 0 1 2 3 4
	// 3 1 r 2 4
	while (size > 1) {
		idx = (m - 1) % (size) + idx;
		idx = idx % size;
		count = -1;//
		int i = 0;
		for (; i < ex.length; i++) {
			if (!ex[i]) {
				if (++count == idx) {
					break;
				}
			}

		}
		// 记录为已遍历
		ex[i] = true;
		size--;

	}
	// 找出没有记录的那个
	for (int i = 0; i < ex.length; i++) {
		if (!ex[i]) {
			r = i;
			break;
		}
	}
	return r;

}

解法3 动态规划

在题解里看到，这个其实是个约瑟夫环问题

通过最后一个来逐个找到上一个。原本看到的是递归写法的动态规划，后面我改成这种。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int LastRemaining_Solution(int n, int m) {
	int r = -1;
	if (n <= 0 || m < 0)
		return -1;
	// int[] dp = new int[n];
	int dp = 0;
	for (int i = 2; i <= n; i++) {java
		dp = (dp + m) % i;
		// System.out.print(dp+",");
	}
	// System.out.println();
	return dp;
}

求1+2+3+…+n

1
2
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
https://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1?tpId=13&tqId=11200&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 递归+短路

这题的重点是需要判断，而大部分判断语句都禁止使用，然后这里是使用&&短路的写法实现了判断。

1
2
3
4
5
// 递归短路
	public int Sum_Solution(int n) {
		boolean x = (n > 0) && (n += Sum_Solution(n - 1)) > 0;
		return n;
	}

不用加减乘除做加法

1
2
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 二进制计算

1
2
3
4
5
6
7
8
9
10
11
12
13

// 二进制解法
public int Add(int num1, int num2) {
	int temp = 0;
	int r = num1 ^ num2;
	int p = (num1 & num2) << 1;// 进位
	while (p != 0) {
		temp = r ^ p;
		p = (p & r) << 1;
		r = temp;
	}
	return r;
}

把字符串转换成整数

1
2
3
4
5
6
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

逐个字符获取，然后旧值*10后进行累加的解法。但因为需要判断正负数、INT_MAX值的判断，加入了很多判断语句。

核心语句就是:

//cur代表当前字符

res = res * 10 + cur;//正数

res = res * 10 - cur;//负数

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
// 逐个累加
	public int StrToInt(String str) {
		if (str == null || "".equals(str.trim()))
			return 0;
		int res = 0;
		int i = 0;
		char[] cs = str.toCharArray();
		boolean position = true;// 正数
		if (cs[0] == '-') {
			// 负数
			position = false;
			i++;
		} else if (cs[0] == '+') {
			i++;
		}

		if (position) {
			for (; i < cs.length; i++) {
				if (StrToInt_NotNum(cs[i])) {
					return 0;
				}
				int cur = (cs[i] - '0');
				if ((res > Integer.MAX_VALUE / 10 || res == Integer.MAX_VALUE / 10 && cur > 7)) {
					return 0;
				}
				res = res * 10 + cur;
			}
		} else {
			for (; i < cs.length; i++) {
				if (StrToInt_NotNum(cs[i])) {
					return 0;
				}
				int cur = (cs[i] - '0');
				if ((res < Integer.MIN_VALUE / 10 || res == Integer.MIN_VALUE / 10 && cur > 8)) {
					return 0;
				}
				res = res * 10 - cur;
			}

		}
		return res;
	}

	public static boolean StrToInt_NotNum(char c) {
		return c <= '0' || c >= '9';
	}

数组中重复的数字

1
2
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 排序法

排序后，判断数组的前后位置是否相等，相等即可返回。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean duplicate_(int numbers[], int length, int[] duplication) {
		if (numbers == null || numbers.length == 0)
			return false;
		Arrays.sort(numbers);
		for (int i = 1; i < numbers.length; i++) {
			if (numbers[i] == numbers[i - 1]) {
				duplication[0] = numbers[i];
				return true;
			}
		}
		return false;
	}

解法2 索引位置交换位置法

交换法也是一个很经常在数组中用到的解法。

遍历数组，将每个数都放到对应索引位置上，交换位置，这样最多一次遍历就可以找出重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 重复查找
	public boolean duplicate(int numbers[], int length, int[] duplication) {
		if (numbers == null || numbers.length == 0)
			return false;
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] != i) {
				if (numbers[i] == numbers[numbers[i]]) {
					duplication[0] = numbers[i];
					return true;
				}
			}
			int temp = numbers[i];
			numbers[i] = numbers[temp];
			numbers[temp] = temp;
		}
		return false;
	}

构建乘积数组

1
2
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=11204&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 前后缀解法

其实就B[i]等于 A数组的乘积和 /A[i];

因为 B[i]=A[1] A[2] … A[i-1]A[i-1]…A[n]

所以整理两个数组，分别保存A[1] A[2] … * A[i-1]和A[i-1]…A[n]。

来快速计算

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
public int[] multiply(int[] A) {
		if (A == null || A.length == 0) {
			return null;
		}
		int[] b = new int[A.length];
		// 前后缀数组
		int[] prefix = new int[A.length];
		int[] suffix = new int[A.length];
		prefix[0] = A[0];
		suffix[A.length - 1] = A[A.length - 1];
		// 前缀数组
		for (int i = 1; i < A.length; i++) {
			prefix[i] = prefix[i - 1] * A[i];
		}
		// 后缀数组
		for (int i = A.length - 2; i >= 0; i--) {
			suffix[i] = suffix[i + 1] * A[i];
		}
		// 构建结果
		for (int i = 1; i < b.length - 1; i++) {
			b[i] = prefix[i - 1] * suffix[i + 1];
		}
		b[A.length - 1] = prefix[A.length - 2];
		b[0] = suffix[1];
		return b;
	}

正则表达式匹配

1
2
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 动态规划

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
// 动态规划
	public boolean match(char[] str, char[] pattern) {
		if (str == null || pattern == null)
			return false;
		int sl = str.length;
		int pl = pattern.length;
		boolean[][] dp = new boolean[sl + 1][pl + 1];
		dp[0][0] = true;
		for (int i = 0; i <= sl; i++) {
			for (int j = 1; j <= pl; j++) {
				if (pattern[j - 1] == '*') {
					if (i > 0 && dp[i - 1][j]) {// 单字符的情况
						if (pattern[j - 2] == '.' || (pattern[j - 2] == str[i - 1])) {
							dp[i][j] = true;
						}
					}
					// 当前字符当成空的情况
					if (dp[i][j - 2]) {
						// 直接判断本字符前的东西是否为true
						dp[i][j] = true;
					}
				} else {
					// 字符直接匹配和'.'的判断
					// 先判断i-1和j-1是否已经匹配了 即之前的字符串是否匹配
					if (i > 0 && dp[i - 1][j - 1]) {
						// 字符直接匹配和'.'的判断
						if (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]) {
							dp[i][j] = true;
						}
					}
				}
			}
		}
		return dp[sl][pl];
	}

Review 英文文章

https://spring.io/guides/gs/managing-transactions/

spring 的事务管理器,以及搭配jdbctempleta使用。

Tip 技巧

面向对象特性分析

接口和抽象类定义。区别（是什么），存在意义（从哪来），应用（到哪去）。
1、定义：
抽象类：不允许实例化，只能被继承；可包含属性和方法，包含抽象方法；子类继承抽象类必须重写抽象方法。
接口：不允许实例化，只能被实现；不包含属性和普通方法，包含抽象方法、静态方法、default 方法；类实现接口时，必须实现抽象方法。
2、意义：
抽象类：解决复用问题，适用于is-a的关系。
接口：解决抽象问题，适用于has-a的关系。
3、应用：
例如：
解决复用问题：java中的子类FileInputStream和PipeInputStream等继承抽象类InputStream。重写了read(source)方法，InputStream 中还包含其他方法，FileInputStream继承抽象类复用了父类的其他方法。
解决抽象问题：抽象类InputStream实现了Closeable接口，该接口中包含close()抽象方法。Closeable这个接口还在很多其他类中实现了，例如Channel，Socket中都有close() 关闭这个功能，但具体实现每个类又各有不同的实现，这个就是抽象。
来源：极客时间 https://time.geekbang.org/column/article/165103
用户：辣么大

面向对象的实现

面向对象分析、设计、实现
面向对象分析、设计、实现，每个环节的界限划分都比较清楚。而且，设计和实现基本上是按照功能点的描述，逐句照着翻译过来的。这样做的好处是先做什么、后做什么，非常清晰、明确，有章可循，即便是没有太多设计经验的初级工程师，都可以按部就班地参照着这个流程来做分析、设计和实现。

出处：极客时间《设计模式之美》（作者：王争）

https://time.geekbang.org/column/intro/250

单一职责原则

类中的代码行数、函数或属性过多，会影响代码的可读性和可维护性，我们就需要考虑对类进行拆分；类依赖的其他类过多，或者依赖类的其他类过多，不符合高内聚、低耦合的设计思想，我们就需要考虑对类进行拆分；私有方法过多，我们就要考虑能否将私有方法独立到新的类中，设置为 public 方法，供更多的类使用，从而提高代码的复用性；比较难给类起一个合适名字，很难用一个业务名词概括，或者只能用一些笼统的 Manager、Context 之类的词语来命名，这就说明类的职责定义得可能不够清晰；类中大量的方法都是集中操作类中的某几个属性，比如，在 UserInfo 例子中，如果一半的方法都是在操作 address 信息，那就可以考虑将这几个属性和对应的方法拆分出来。

出处：极客时间《设计模式之美》（作者：王争）

https://time.geekbang.org/column/intro/250

开闭原则

如何理解“对扩展开放、对修改关闭”？

添加一个新的功能，应该是通过在已有代码基础上扩展代码（新增模块、类、方法、属性等），而非修改已有代码（修改模块、类、方法、属性等）的方式来完成。关于定义，我们有两点要注意。第一点是，开闭原则并不是说完全杜绝修改，而是以最小的修改代码的代价来完成新功能的开发。第二点是，同样的代码改动，在粗代码粒度下，可能被认定为“修改”；在细代码粒度下，可能又被认定为“扩展”。

如何做到“对扩展开放、修改关闭”？

我们要时刻具备扩展意识、抽象意识、封装意识。在写代码的时候，我们要多花点时间思考一下，这段代码未来可能有哪些需求变更，如何设计代码结构，事先留好扩展点，以便在未来需求变更的时候，在不改动代码整体结构、做到最小代码改动的情况下，将新的代码灵活地插入到扩展点上。很多设计原则、设计思想、设计模式，都是以提高代码的扩展性为最终目的的。特别是 23 种经典设计模式，大部分都是为了解决代码的扩展性问题而总结出来的，都是以开闭原则为指导原则的。最常用来提高代码扩展性的方法有：多态、依赖注入、基于接口而非实现编程，以及大部分的设计模式（比如，装饰、策略、模板、职责链、状态）。

出处：极客时间《设计模式之美》（作者：王争）

https://time.geekbang.org/column/intro/250

里式替换

而里式替换是一种设计原则，是用来指导继承关系中子类该如何设计的，子类的设计要保证在替换父类的时候，不改变原有程序的逻辑以及不破坏原有程序的正确性。

子类在设计的时候，要遵守父类的行为约定（或者叫协议）。父类定义了函数的行为约定，那子类可以改变函数的内部实现逻辑，但不能改变函数原有的行为约定。这里的行为约定包括：函数声明要实现的功能；对输入、输出、异常的约定；甚至包括注释中所罗列的任何特殊说明。

出处：极客时间《设计模式之美》（作者：王争）

https://time.geekbang.org/column/intro/250

Share 分享

https://blog.csdn.net/C_envelope/article/details/87920146 DDD四种模型
https://www.jianshu.com/p/b0379067c978 DDD介绍

https://time.geekbang.org/column/intro/250极客时间《设计模式之美》7~17章