ARTS 第39周

发表于

ARTS （第39周）

这几年互联网技术都绕不开并发，消息中间件，JVM模型，设计模式等。

Algorithm 算法

空格替换

1
2
3
4
题目：
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?

解法1

统计长度然后用新的char数组替换。

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
///////////////////////////////////////////////////////
	// 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
	// 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
	// https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&tqId=11155&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
	///////////////////////////////////////////////////////
	public String replaceSpace(StringBuffer str) {
		// 个人感觉这样的算法题目，应该给char数组更合适，可以直接对char直接操作
		// 既然已经给了StringBuffer，简单看了下源码，调用本身的API操作，时间复杂度和空间复杂度其实是一样的 ,都是O(n)的复杂度，
		// 比如直接转string调用replaceAll 或者JDK的其他的API。
		if (str == null)
			return null;
		int space = 0;// 累计空格数量
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == ' ') {
				space++;
			}
		}
		// 空格原本占用1个位置 现在占用3个 多占了2个
		char[] r = new char[2 * space + str.length()];
		int p = 0;// 新数组的指针
		char c = 0;// 用于迭代
		for (int i = 0; i < str.length(); i++) {
			c = str.charAt(i);
			if (c == ' ') {
				// 空格替换
				r[p++] = '%';
				r[p++] = '2';
				r[p++] = '0';

			} else {
				// 非空格直接填充
				r[p++] = c;
			}
		}

		return new String(r);
	}

在评论里看到的另一个解法，思路是一样的，写法不一样，更多的是使用api。

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
// 在品论里看到的 思路一致 写法和实现不一样
// 链接：https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423?answerType=1&f=discussion
// 来源：牛客网 用户：道阻且长z
public String replaceSpace_copy(StringBuffer str) {
	int spacenum = 0;
	for (int i = 0; i < str.length(); i++) {
		if (str.charAt(i) == ' ') {
			spacenum++;
		}
	}
	int oldLength = str.length();
	int oldIndex = oldLength - 1;
	int newLength = oldLength + spacenum * 2;
	str.setLength(newLength);
	int newIndex = newLength - 1;
	for (; oldIndex >= 0 && oldLength < newLength; oldIndex--) {
		if (str.charAt(oldIndex) == ' ') {
			str.setCharAt(newIndex--, '0');
			str.setCharAt(newIndex--, '2');
			str.setCharAt(newIndex--, '%');
		} else {
			str.setCharAt(newIndex--, str.charAt(oldIndex));
		}
	}
	return str.toString();
}

从尾到头打印链表

1
2
 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
// https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&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
// 反转链表
	public ArrayList<Integer> printListFromTailToHead_reversenode(ListNode listNode) {
		ArrayList<Integer> r = new ArrayList<Integer>();
		if (listNode == null)
			return r;
		// 链表节点反转
		ListNode prev = listNode;// 当前
		ListNode cur = listNode.next;// 后一个
		listNode.next = null;// 断掉
		ListNode temp = null;// 迭代用
		while (cur != null) {
			// 向前链接
			temp = cur.next;
			cur.next = prev;
			// 迭代
			prev = cur;
			cur = temp;
		}
		// 按新链表的顺序插入集合
		cur = prev;
		while (cur != null) {
			r.add(cur.val);
			cur = cur.next;
		}
		return r;
	}

解法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
// 递归1
	public ArrayList<Integer> printListFromTailToHead_recursive1(ListNode listNode) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		if (listNode == null)
			return al;
		printListFromTailToHeadHelp(al, listNode);
		return al;
	}

	// 辅助方法 -> printListFromTailToHead_recursive1
	public void printListFromTailToHeadHelp(ArrayList<Integer> l, ListNode node) {
		if (node.next != null) {
			printListFromTailToHeadHelp(l, node.next);
		}
		l.add(node.val);
	}

// 递归2
	// 将数组放到外部 看了评论写的 本质是和另一个递归一样
	ArrayList<Integer> printListFromTailToHeadArrayList = new ArrayList<Integer>();

	public ArrayList<Integer> printListFromTailToHead_recursive2(ListNode listNode) {
		if (listNode == null)
			return printListFromTailToHeadArrayList;
		if (listNode.next != null) {
			printListFromTailToHead_recursive2(listNode.next);
		}
		printListFromTailToHeadArrayList.add(listNode.val);
		return printListFromTailToHeadArrayList;
	}

重建二叉树

1
2
3
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解法

根据前序和中序遍历的特性出发做的解法。

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
// 自己没想到解法 只想到了根节点是pre[0]
	// 在以前觉得前序中序后序遍历都比较简单就没有深入去了解，
	// 现在发现这些数据结构的关联性非常强，也是这些关联性才有这题的这种解法，不要小瞧任何东西
	// 按题解做的 拆分左右子树的解法
	// 前序遍历的特征 根节点在第一个 然后左子树及其子节点都遍历之后才到右子节点
	// 中序遍历的特征 左子树及其子节点都在当前节点前遍历 而右子树及其子节点都在当前节点后遍历
	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		if (pre == null || pre.length == 0) {
			// 只判断一个数组即可 ，若一个空一个非空，那么题目是非法的
			return null;
		}
		// 前序的首个节点是二叉树的根节点
		TreeNode node = new TreeNode(pre[0]);
		for (int i = 0; i < in.length; i++) {
			if (pre[0] == in[i]) {
				// System.out.println("find:"+i);
				// 前序遍历的特征 根节点在第一个 然后左子树及其子节点都遍历之后，右子树进行遍历
				// 中序遍历的特征 左子树及其子节点都在当前节点前遍历 而右子树及其子节点都在当前节点后遍历
				// 所以pre的 1~i是左子树,(i+1) ~(len-1) 是右子树
				// 所以in的 0~(i-1) 是其左子树,(i+1) ~(len-1) 是右子树

				// 关于copyOfRange
				// 是包含from但不包含to的 所以这么写
				// 原本是直接使用Arrays.copyOfRange的，但牛客网编译器不识别，就自己写了个

				// 前序的左子树
				int[] preL = copyOfRange(pre, 1, i + 1);
				// 中序的左子树
				int[] inL = copyOfRange(in, 0, i);
				// 前序右子树
				int[] preR = copyOfRange(pre, i + 1, pre.length);
				// 中序右子树
				int[] inR = copyOfRange(in, i + 1, in.length);
				// 递归计算
				node.left = reConstructBinaryTree(preL, inL);
				node.right = reConstructBinaryTree(preR, inR);
				break;//
			}
		}
		return node;
	}

	// 牛客网编译器不识别 自己写一个数组复制的
	public static int[] copyOfRange(int[] original, int from, int to) {
		int newLength = to - from;
		int[] copy = new int[newLength];
		System.arraycopy(original, from, copy, 0, newLength);
		return copy;
	}

Review 英文文章

https://vuejs.org/v2/guide/class-and-style.html
vuejs类样式的绑定

Tip 技巧

以下全部摘自百度百科。

复杂指令集计算机

计算机处理器包含有实现各种功能的指令或微指令，指令集越丰富，为微处理器编写程序就越容易，但是丰富的微指令集会影响其性能。复杂指令集计算机（CISC）体系结构的设计策略是使用大量的指令，包括复杂指令。与其他设计相比，在CISC中进行程序设计要比在其他设计中容易，因为每一项简单或复杂的任务都有一条对应的指令。程序设计者不需要写一大堆指令去完成一项复杂的任务。 但指令集的复杂性使得CPU和控制单元的电路非常复杂。

精简指令集计算机

精简指令集计算机(RISC:Reduced Instruction Set Computing RISC)是一种执行较少类型计算机指令的微处理器，起源于80年代的MIPS主机（即RISC机），RISC机中采用的微处理器统称RISC处理器。这样一来，它能够以更快的速度执行操作（每秒执行更多百万条指令，即MIPS）。因为计算机执行每个指令类型都需要额外的晶体管和电路元件，计算机指令集越大就会使微处理器更复杂，执行操作也会更慢。纽约约克镇IBM研究中心的John Cocke证明，计算机中约20%的指令承担了80%的工作，于1974年，他提出RISC的概念。许多当前的微芯片都使用RISC概念。

汇编语言

汇编语言（assembly language）是一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。在汇编语言中，用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址。在不同的设备中，汇编语言对应着不同的机器语言指令集，通过汇编过程转换成机器指令。特定的汇编语言和特定的机器语言指令集是一一对应的，不同平台之间不可直接移植。

Share 分享

https://www.jianshu.com/p/4f905b3bc63f Java中的String有没有长度限制？

https://wenku.baidu.com/view/2e266970bf23482fb4daa58da0116c175e0e1e78.html 操作系统

https://www.cnblogs.com/jswang/p/9071847.html 硬盘基本知识（磁头、磁道、扇区、柱面）

https://www.cnblogs.com/my_life/articles/10614633.html 四大CPU体系结构：ARM、X86/Atom、MIPS、PowerPC

https://blog.csdn.net/wwlyqin/article/details/5729834 java的发展史（2010年的文章）