ARTS 第54

发表于

ARTS （第54周）

写出“能用”代码的人比比皆是，但是，并不是每个人都能写出“好用”的代码。只会写能用的代码，我们永远成长不成大牛，成长不成最优秀的那批人。
极客时间-《设计模式之美》 https://time.geekbang.org/column/article/160463

Algorithm 算法

平衡二叉树

1
2
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=2&rp=2&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
// 递归
	public boolean IsBalanced_Solution_(TreeNode root) {
		if (root == null)
			return true;
		int left = TreeDepth_IsBalanced_Solution(root.left);
		int right = TreeDepth_IsBalanced_Solution(root.right);
		int r = left - right;
		if (r > 1 || r < -1) {
			return false;
		}
		return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
	}

	public int TreeDepth_IsBalanced_Solution(TreeNode root) {
		// 空位0
		if (root == null)
			return 0;
		// 左
		int r1 = TreeDepth_IsBalanced_Solution(root.left);
		// 右
		int r2 = TreeDepth_IsBalanced_Solution(root.right);
		if (r1 < r2) {
			r1 = r2;
		}
		// 子树深度+1
		return r1 + 1;
	}

解法2 递归优化

其实本质是个后序遍历

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
// 递归 后序遍历
	public boolean IsBalanced_Solution(TreeNode root) {
		if (root == null)
			return true;

		return TreeDepth_IsBalanced_Solution2(root) != -1;
	}

	public int TreeDepth_IsBalanced_Solution2(TreeNode root) {
		// 空位0
		if (root == null)
			return 0;
		// 左
		int r1 = TreeDepth_IsBalanced_Solution2(root.left);
		// 右
		int r2 = TreeDepth_IsBalanced_Solution2(root.right);
		if (r1 == -1 || r2 == -1) {
			return -1;
		}
		if (r1 < r2) {
			int temp = r1;
			r1 = r2;
			r2 = temp;
		}
		// 高度相差过大
		if (r1 - r2 > 1) {
			return -1;
		}
		// 子树深度+1
		return r1 + 1;
	}

数组中只出现一次的数字

1
2
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

最简单的就是哈希表之类的key-value类型储存，这里我就不写了。

如果结果是只有1个数字，全部进行异或即可，但这里是2个数字，所以全部异或的结果，是两个数字的异或结果。

根据结果的二进制，找出为1的位，就代表2个数字的这个位是不一样的。根据这个位，将数组分成两组，分别进行异或，就能找出那两个不同的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
		// 不加验证了，必须是合理参数，否则题意不符
		int res = array[0];
		for (int i = 1; i < array.length; i++) {
			res ^= array[i];
		}
		// 二进制索引 找到任意一个二进制不为0的位置即可
		// 结果必定有至少一位不为0，为0 就代表2个数相同，题意不符
		int idx = 1;
		while ((idx & res) == 0) {
			idx = idx << 1;
		}
		//
		num2[0] = 0;
		num2[0] = 0;
		for (int v : array) {
			if ((v & idx) == 0)
				num1[0] ^= v;
			else
				num2[0] ^= v;
		}

	}

和为S的连续正数序列

1
2
3
4
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&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
// 穷举
	public ArrayList<ArrayList<Integer>> FindContinuousSequence_(int sum) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		for (int i = 1; i < sum; i++) {
			int max = i;
			int total = 0;
			while (total < sum) {
				total += max++;
			}
			if (total == sum) {
				ArrayList<Integer> r = new ArrayList<Integer>();
				for (int j = i; j < max; j++) {
					r.add(j);
				}
				res.add(r);
			}
		}
		return res;
	}

解法 双指针

通过大小两个指针之间的值进行判断

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 ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	int left = 1;
	int right = 2;
	int total = 3;
	while (right < sum) {
		if (total > sum) {
			total -= (left++);

		} else if (total < sum) {
			total += (++right);
		} else {
			// 找到
			total += (++right);
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j = left; j < right; j++) {
				r.add(j);
			}
			res.add(r);
		}

	}

	return res;
}

和为S的两个数字

1
2
3
4
5
6
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。

https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&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
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		int left = 0;
		int right = array.length-1;
		int total = Integer.MAX_VALUE;
		while (left < right) {
			int v = array[left] + array[right];
			if (v > sum) {
				right--;
			} else if (v < sum) {
				left++;
			} else {
				// 找到
				int newTotal = array[left] * array[right];
				if (newTotal < total) {
					res.clear();
					res.add(array[left]);
					res.add(array[right]);
				}
				//left++;
              	
				break;
			}

		}

		return res;
	}

左旋转字符串

1
2
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 用一个char数组接收到对应位置的char值后构建一个新的string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 简单
public String LeftRotateString_(String str, int n) {
	if (n < 0 || str == null)
		return null;
	if (n == 0)
		return str;
	if (n > str.length())
		n = n % str.length();
	char[] c = new char[str.length()];
	int idx = 0;
	for (int i = n; i < c.length; i++) {
		c[idx++] = str.charAt(i);
	}
	for (int i = 0; idx < c.length; i++) {
		c[idx++] = str.charAt(i);
	}

	return new String(c);
}

解法2 看到的精巧的做法

str += str;然后截取对应位置的数据即可，很精巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 精巧
	public String LeftRotateString__(String str, int n) {
		if (n < 0 || str == null)
			return null;
		if (n == 0)
			return str;

		int len = str.length();
		if (len == 0)
			return str;
		if (n > len)
			n = n % len;
		str += str;
		return str.substring(n, n + len);

	}

解法3 reverse方法

三次翻转之后，结果刚好就是自己想要的

1
2
3
4

str.Reverse(listS,0,n-1)
     str.Reverse(listS,n,len(s)-1)
     str.Reverse(listS,0,len(s)-1)

翻转单词序列

1
2
3
题目描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 用空格拆分数组后，从后向前拼接即可。

这里依然可以用reverse。一个一个单词reverse ，然后整体reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 反转
public String ReverseSentence(String str) {
	if (str == null || str.length() == 0 || str.trim().length() == 0)
		return str;
	String[] r = str.split(" ");
	StringBuilder sb = new StringBuilder();
	for (int i = r.length - 1; i >= 0; i--) {
		sb.append(r[i]);
		sb.append(" ");
	}
	sb.deleteCharAt(sb.length() - 1);
	return sb.toString();
}

扑克牌顺子

1
2
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。	
https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

其实这里的题目就是2个目的。做完后，看到的多种解法都是为了这两个目的，只是实现方式不太一样。

  1. 除0外没有重复的数

  2. max - min < 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isContinuous(int[] numbers) {
		if (numbers == null || numbers.length == 0) {
			return false;
		}
		Arrays.sort(numbers);
		int zero = 0;
		for (int i : numbers) {
			if (i == 0) {
				zero++;
			} else {
				break;
			}
		}
		for (int i = zero + 1; i < numbers.length; i++) {
			if (numbers[i] == numbers[i - 1]) {
				return false;
			}
			zero -= (numbers[i] - numbers[i - 1] - 1);
		}
		return zero >= 0;
	}

Review 英文文章

https://spring.io/guides/gs/messaging-jms/

spring整合jms，以及提供的JmsTemplate`

Tip 技巧

面向对象面的3W模型

封装

What：隐藏信息，保护数据访问。
How：暴露有限接口和属性，需要编程语言提供访问控制的语法。
Why：提高代码可维护性；降低接口复杂度，提高类的易用性。

抽象

What: 隐藏具体实现，使用者只需关心功能，无需关心实现。
How: 通过接口类或者抽象类实现，特殊语法机制非必须。
Why: 提高代码的扩展性、维护性；降低复杂度，减少细节负担。

继承

What: 表示 is-a 关系，分为单继承和多继承。
How: 需要编程语言提供特殊语法机制。例如 Java 的 “extends”，C++ 的 “:” 。
Why: 解决代码复用问题。

多态

What: 子类替换父类，在运行时调用子类的实现。
How: 需要编程语言提供特殊的语法机制。比如继承、接口类、duck-typing。
Why: 提高代码扩展性和复用性。

3W 模型的关键在于 Why，没有 Why，其它两个就没有存在的意义。从四大特性可以看出，面向对象的终极目的只有一个：可维护性。易扩展、易复用，降低复杂度等等都属于可维护性的实现方式。
摘自 极客时间,用户：Smallfly

Share 分享

极客时间《设计模式之美》1~6章

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