ARTS-第44周

发表于

ARTS （第44周）

没有压力，就容易放纵放松。

Algorithm 算法

调整数组顺序使奇数位于偶数前面

1
2
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

插入排序的思路

最初是按快排的思路做的，做到后面发现，其实思路应该是更贴近选择排序或者插入排序，没有达到快排的logn的复杂度。

后面看到别人有一个说按快排做的，其实也应该是选择排序，复杂度也是n^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
public void reOrderArray2(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int o = 0;// offset
		if (isOdd(array[0])) {
			o++;
		}
		// 本质应该是选择排序
		for (int i = 1; i < array.length; i++) {
			if (isOdd(array[i])) {
				if (i != o) {
					int temp = array[i];
					// 右移
					// 假设[0,1,2,3,4,5] 移动5到索引0的位置 那就是 从索引0开始向右位移5个位置 即i-o
					System.arraycopy(array, o, array, o + 1, i - o);
					array[o] = temp;
					o++;
				} else {
					o++;// 连续的奇数
				}
			}

		}
	}

空间换时间的解法

时间复杂度n，空间复杂度n的解法。

本质应该是归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 本质应该是归并排序
	public void reOrderArray(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int idx = 0;
		int[] temp = new int[array.length];
		for (int i = 0; i < array.length; i++) {
			temp[i] = array[i];
		}

		for (int i = 0; i < temp.length; i++) {
			if (isOdd(temp[i])) {
				array[idx++] = temp[i];
			}
		}
		for (int i = 0; i < temp.length; i++) {
			if (!isOdd(temp[i])) {
				array[idx++] = temp[i];
			}
		}
	}

输入一个链表，输出该链表中倒数第k个结点。

1
2
输入一个链表，输出该链表中倒数第k个结点。
https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&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
	public ListNode FindKthToTail(ListNode head,int k) {
	if(head ==null ||k < 0)
		return null;
	ListNode cur = head;
	ListNode res = null;
	//先循环k个 
	//这里原本是i<k+1的，以为k的索引是从0开始，结果是从1开始的
	for (int i = 0; i < k; i++) {
		if(cur==null){
			return res;
		}
		cur=cur.next;
	}
	//循环k+1~n个
	//每循环一次 
	res = head;
	while(cur!=null) {
		cur =cur.next;
		res = res.next;
	}
	return res;
}

合并两个单调递增的链表

1
2
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public ListNode Merge2(ListNode list1, ListNode list2) {
		if (list1 == null)
			return list2;// 这里隐含2个null的判断
		if (list2 == null)
			return list1;
		// 归并排序的思路
		ListNode cur = null;
		ListNode p1 = list1;
		ListNode p2 = list2;
		ListNode result = null;
		if (p1.val < p2.val) {
			cur = list1;
			result=list1;
			p1=p1.next;
		} else {
			cur = list2;
			result=list2;
			p2=p2.next;
		}
		while (p1!=null && p2!=null) {
			if (p1.val < p2.val) {
				cur.next = p1;
				cur=cur.next;
				p1=p1.next;
			} else {
				cur.next=p2;
				cur=cur.next;
				p2=p2.next;
			}

		}
		//剩下的
		if(p1!=null) {
			cur.next = p1;
		}
		if(p2!=null) {
			cur.next = p2;
		}
		
		return result;
	}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode Merge(ListNode list1, ListNode list2) {
		if (list1 == null)
			return list2;// 这里隐含2个null的判断
		if (list2 == null)
			return list1;
		if(list1.val<list2.val) {
			list1.next = Merge(list1.next, list2); 
			return list1;
		}else {
			list2.next = Merge(list1, list2.next); 
			return list2;
		}
	}

Review 英文文章

http://zookeeper.apache.org/doc/r3.5.6/zookeeperStarted.html

zk 3.5.6版本的简易介绍

Tip 技巧

如果下载3.5.5以后的版本的Zookeeper安装包，我们需要下载带有bin标识的包，不带bin的是源码包。

Share 分享

http://blog.sina.com.cn/s/blog_960c60920102z5pz.html 公司和自我价值

https://blog.csdn.net/lzuacm/article/details/103173344 知乎高赞：中国有什么拿得出手的开源软件产品？

https://blog.csdn.net/weixin_34356310/article/details/93197026 一些堪称神器却少为人知的网站或软件(整理自知乎)