ARTS-第26周

发表于

ARTS （第26周）

适时回顾，巩固知识

Algorithm 算法

链表小练习（反转、求中间）

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package algorithm.demo.linked;

public class LinkedNode {
	public static void main(String[] args) {
		Node n = new Node(0);
		Node last = n.setNext(1).setNext(2).setNext(3).setNext(4).setNext(5).setNext(6);
		System.out.println("====reverse====");
		System.out.println(n);
		reverse(n);
		System.out.println(last);
		System.out.println("===middle===");
		n = new Node(0);
		n.setNext(1).setNext(2).setNext(3).setNext(4).setNext(5).setNext(6);
		System.out.println("node:"+n);
		System.out.println("middle:"+middle(n));
	}
	//链表的中间节点
	public static int middle(Node head) {
		Node p1 = head;
		Node p2 = head;
		while (p2 != null) {
			p2 = p2.next;
			if (p2 == null) {
				break;
			}
			p2 = p2.next;
			p1 = p1.next;
		}
		return p1.val;
	}
	//反转
	public static void reverse(Node head) {
		Node n = head.next;
		Node c = head;
		head.next = null;
		while (c != null && n != null) {
			Node next = n.next;
			n.next = c;
			c = n;
			n = next;
		}

	}

	static class Node {
		Node next;
		int val;

		public Node() {
		}

		public Node(int v) {
			this.val = v;

		}

		@Override
		public String toString() {
			return val + "" + (next == null ? "" : "," + next.toString());
		}

		public Node setNext(int v) {
			Node n = new Node();
			n.val = v;
			this.next = n;
			return n;
		}
	}

}

Leetcode

1、判断链表是否有环

​ 我这里使用的是双指针的标准做法，双指针一起走，如果存在环，链表就会死循环，使用双指针一定会有两个指针是指向同一个的时候。

​ 除此之外
​ 1、哈希表法
​ 用哈希储存遍历过的数据，这个比较容易理解，就是另外找个空间保存遍历过的，而使用hash性能较好。
​ 2、还可以破坏链表法 (java是个强类型的语言 不太适用，而且会破坏链表，但也是个思路
​ 即该题目中，节点是数字类型的值。
​ 每次遍历将节点的值修改为其它值，如string类型的
​ 遍历的时候 遇到string类型的值就代表着存在环
​ 3、循环次数和链表数量的累积比较
​ 首先需要知道一点，就是如果存在环进行遍历会出现死循环的情况，那么根据这个特点，我们就可以继续。
​ 根据评论里有人测试过，题目中最大的节点数量数是8029，
​ 这个有点取巧，只要循环超过8029次，并且节点还不是空的话那就是存在环。其它情况就是不存在环

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package algorithm.demo.linked;

public class Leetcode {
	// Definition for singly-linked list.
	static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}

		public ListNode setNext(int v) {
			ListNode n = new ListNode(v);
			this.next = n;
			return n;
		}

		@Override
		public String toString() {
			return val + "" + (next == null ? "" : "," + next.toString());
		}
	}

	// 双指针法
	// 快慢指针法，如果快慢指针相遇了那就代表着存在环 如果没有相遇就代表着没有环
	// 执行用时:1 ms,在所有 Java 提交中击败了 96.00%内存消耗:40.3 MB,在所有 Java 提交中击败了 39.90%的用户
	public boolean hasCycle(ListNode head) {
		ListNode p1 = head;
		ListNode p2 = head;
		while (p2 != null && p1 != null) {
			p1 = p1.next;
			p2 = p2.next;
			if (p2 == null) {
				break;
			}
			p2 = p2.next;
			if (p1 == p2)
				return true;
		}

		return false;
		// 除此之外
		// 1、哈希表法
		// 用哈希储存遍历过的数据，这个比较容易理解，就是另外找个空间保存遍历过的，而使用hash性能较好。
		// 2、还可以破坏链表法 (java是个强类型的语言 不太适用，而且会破坏链表，但也是个思路
		// 即该题目中，节点是数字类型的值。
		// 每次遍历将节点的值修改为其它值，如string类型的
		// 遍历的时候 遇到string类型的值就代表着存在环
		// 3、循环次数和链表数量的累积比较
		// 首先需要知道一点，就是如果存在环进行遍历会出现死循环的情况，那么根据这个特点，我们就可以继续。
		// 根据评论里有人测试过，题目中最大的节点数量数是8029，
		// 这个有点取巧，只要循环超过8029次，并且节点还不是空的话那就是存在环。其它情况就是不存在环
	}

	// 执行用时 : 4 ms , 在所有 Java 提交中击败了 98.94% 的用户
	// 内存消耗 : 40.3 MB , 在所有Java 提交中击败了 85.29% 的用户
	//双路归并法
	public ListNode mergeKLists(ListNode[] lists) {
		if (lists != null && lists.length == 0)
			return null;
		if (lists.length == 1)
			return lists[0];
		int e = lists.length - 1;
		return merge(lists, 0, e);
		//除此之外还可以使用最小队列来做，也可以自己实现一个简单的小顶堆来实现这道题
		//除次之外,将节点放在一个数组/集合里，然后使用各种排序算法进行排序也是可行的。
	}

	private ListNode merge(ListNode[] lists, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			int estart = mid + 1;
			// 以中点进行双路归并
			ListNode l1 = merge(lists, start, mid);
			ListNode l2 = merge(lists, estart, end);
			// 归并完成后 进行融合
			return mergeTwo(l1, l2);
		}
		return lists[start];

	}

	public ListNode mergeTwo(ListNode l1, ListNode l2) {
		if (l1 == null)
			return l2;
		if (l2 == null)
			return l1;
		if (l1.val < l2.val) {

			l1.next = mergeTwo(l1.next, l2);
			return l1;
		}
		// if (l1.val > l2.val) {
		else {
			l2.next = mergeTwo(l2.next, l1);
			return l2;
		}

	}

}

Review 英文文章

https://docs.spring.io/sts/nan/v399/NewAndNoteworthy.html

STS的介绍

ps：因为本周自己家里的电脑换了个硬盘，就打算换成STS当IDE，结果启动的时候报错exit code 13（64位不兼容32位JDK），更换环境变量里的JDK的64/32版本即可。

Tip 技巧

尚硅谷springboot整合篇

springboot整合各类组件的整合的简易demo视频

以及一部分spring源码的介绍（spring的IOC本质的核心是一个容器，保存各类Bean和管理这些bean）

一、Spring Boot与缓存
二、Spring Boot与消息
三、Spring Boot与检索
四、Spring Boot与任务
五、Spring Boot与安全
六、Spring Boot与分布式
七、Spring Boot与监控管理
八、Spring Boot与部署

Share 分享

https://me.csdn.net/bjweimengshu

程序员小灰，将各种算法和其它技术作成漫画方式来表现的一个作者。