ARTS 第3周

发表于

ARTS （第3周）

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

摘自百度百科

https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057

本周：

算法、数据结构基础

Algorithm 算法

1、简易的LRU链表

2、利用链表做回文判断

出处为极客时间的专栏《数据结构与算法之美》（作者：王争）

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

简易的LRU链表

这个做的是一个简易的LRU链表 最大6个元素

在插入的时候，进行去重以及最近最少使用策略 LRU（Least Recently Used）进行剔除大于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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
package jdk8test;

/**
 * 简易LRU单向链表
 * 
 * @author lfy
 * @return
 */
public class LinkedObj<T> {

	private int max = 6;// 最大数量
	private int size = 0;// 集合大小
	private Item start;// 首个
	
	/**
	 * 获取首个节点
	 * 
	 * @author lfy
	 * @return
	 */
	public Item getStart(){
		return start;
	}
	/**
	 * 新增
	 * 
	 * @author lfy
	 * @return
	 */
	public void add(T value) {
		if (isRepeat(value)) {
			return;
		}
		if (size >= max) {
			removeOne();
		}

		if (size == 0) {
			// 首个
			this.start = new Item(value);
		} else {
			// 非首个
			Item v = start;
			for (int i = 0; i < size - 1; i++) {
				v = v.next;
			}
			// 末尾添加链表
			v.setNext(value);
		}
		size++;
	}
	/**
	 * 验证重复
	 * 
	 * @author lfy
	 * @return
	 */
	private boolean isRepeat(T value) {
		Item v = start;
		for (int i = 0; i < size ; i++) {
			if (v.getValueWithOutCount().equals(value)) {
				return true;
			}
			v = v.next;
		}
		return false;
	}
	/**
	 * LRU策略移出多余
	 * 
	 * @author lfy
	 * @return
	 */
	private void removeOne() {

		Item prev = null;// 目标的前一个
		Item target = start;// 目标
		Item current = start;// 当前
		// 先比对使用次数 如果存在相同的 则删除首个
		for (int i = 0; i < size - 1; i++) {
			// 如果后一个比前一个多 则替换
			/*
			 * if ( target.getTimes() > current.getNext().getTimes()) { //
			 * 当前次数比下一个多 prev = current; target = current.getNext();// 比较后替换 }
			 */
			// 如果当前循环的数据的次数更少
			if (target.getTimes() > current.getNext().getTimes()) {
				prev = current;
				target = current.next;
			}
			current = current.next;
		}
		// 判断是否是第一个
		if (prev != null) {
			prev.next = target.next;
		} else {
			this.start = target.next;
		}
		size--;
	}

	/**
	 * 获取
	 * 
	 * @author lfy
	 * @return
	 */
	public T get(int index) {
		Item v = start;
		for (int i = 0; i < index; i++) {
			v = v.next;
		}
		return v.getValue();
	}
	
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer("[");
		Item target = start;
		if (target != null) {
			// 拼接首个
			sb.append(target.getValueWithOutCount());
			while (target.next != null) {
				sb.append(",");
				// 拼接下一个
				target = target.next;
				sb.append(target.getValueWithOutCount());
			}
		}
		sb.append("]");
		return sb.toString();
	}
	/**
	 * 链表对象类
	 * 
	 * @author lfy
	 * @return
	 */
	class Item {
		private Item next;// 单向链表 指向的下一个
		private int times;// 使用次数
		private T value;// 值

		public Item(T value) {
			this.value = value;
		}

		/**
		 * 取值 并累加
		 * 
		 * @author lfy
		 * @return
		 */
		public T getValue() {
			times++;// 累加
			return value;
		}

		/**
		 * 取值
		 * 
		 * @author lfy
		 * @return
		 */
		public T getValueWithOutCount() {
			return value;
		}

		/**
		 * 设置下一节点
		 * 
		 * @author lfy
		 * @return
		 */
		public void setNext(T value) {
			this.next = new Item(value);
		}
		/**
		 * 获取使用次数
		 * 
		 * @author lfy
		 * @return
		 */
		public int getTimes() {
			return times;
		}

		/**
		 * 获取下一个链表对象类
		 * 
		 * @author lfy
		 * @return
		 */
		public Item getNext() {
			return next;
		}

	}
}

测试demo

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
public static void main(String[] args) {
	LinkedObj<Integer> lo = new LinkedObj<Integer>();
	System.out.println("do repeat---------");
	for (int i = 0; i < 6; i++) {
		lo.add(-1);
	}
	System.out.println(lo);
	for (int i = 0; i < 6; i++) {
		lo.add(i);
	}
	System.out.println("do 0---------");
	System.out.println(lo);
	lo.get(0);// 获取下标0
	lo.add(11);
	System.out.println("do 1---------");
	System.out.println(lo);
	lo.get(1);// 获取 下标1
	for (int i = 20; i < 26; i++) {
		lo.add(i);
	}
	System.out.println("do 2---------");
	System.out.println(lo);

	for (int i = 50; i < 56; i++) {
		lo.add(i);
	}
	System.out.println("do 3---------");
	System.out.println(lo);

	for (int i = 2; i < 6; i++) {
		lo.get(i);
	}

	for (int i = 60; i < 66; i++) {
		lo.add(i);
	}
	System.out.println("do 4---------");
	System.out.println(lo);
	for (int i = 5; i < 8; i++) {
		lo.add(i + 66);
		System.out.println("do " + i + "---------");
		System.out.println(lo);
	}
}

运行结果符合预期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
do repeat---------
[-1]
do 0---------
[0,1,2,3,4,5]
do 1---------
[0,2,3,4,5,11]
do 2---------
[0,2,22,23,24,25]
do 3---------
[0,2,52,53,54,55]
do 4---------
[2,52,53,54,55,65]
do 5---------
[2,52,53,54,55,71]
do 6---------
[2,52,53,54,55,72]
do 7---------
[2,52,53,54,55,73]

如何判断一个字符串是否是回文字符串(采用单链表的方式实现，链表里每一个元素，都是一个char)

我的思路：

1、 快慢指针寻找中间节点，慢指针一边前进一边进行链表的反转。
2、 从中间节点开始，用逆序的前半部分节点和中间节点的后一个节点进行匹配
3、 还需要区分字符串是奇数还是偶数

PS:使用的是之前我自己写的简易LRU链表。

代码如下：

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
   /**
 * 链表回文判断
 * @author lfy
 * @param start 链表起点
 * @return
 */
public boolean isReverse(LinkedObj<String>.Item start){
	LinkedObj<String>.Item fast = start;
	LinkedObj<String>.Item slow = start;
	LinkedObj<String>.Item prev = null;
	LinkedObj<String>.Item next = null;
	//找中点
	while(fast !=null && fast.next != null){
		//每次前进2步
		fast = fast.next.next;
		//暂存 要前进一步的对象
		next =slow.next;
		//将当前慢指针的next指向前一个对象 如果是首个 则next为空 即链表末尾
		//实现反转
		slow.next = prev;
		//前一个对象赋值为当前对象
		prev=slow;
		//慢指针指向下一步对象
		slow=next;
	}
	//fast是否为空 为空则为偶数
	if(fast != null){
		//奇数情况下，向后走一步 
		//如 1，2，3，2，1 从中点的3 走到第二个2的点 
		slow=slow.next;
	}
	//////////////////////////////////
	//prev 代表着：
	//偶数情况 当前链表的2个中点的前一个中点
	//奇数情况 当前链表的中点的前一个点
	//slow 代表着：
	//偶数情况 当前链表的2个中点的后一个中点
	//奇数情况 当前链表的中点
	///////////////////////////////
	while(prev!=null &&slow!=null){
		if(!prev.getValue().equals(slow.getValue())){
			return false;
		}
		prev=prev.next;
		slow=slow.next;
	}
	
	return true;
}

调用如下

PS：因为回文必定有重复的情况，在这里我将链表的去重功能去掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
		Solution s = new Solution();
		LinkedObj<String> lb =new LinkedObj<>();
		lb.add("1");
		lb.add("2");
		lb.add("3");
		lb.add("3");
		lb.add("2");
		lb.add("1");
		LinkedObj<String>.Item start = lb.getStart();
		System.out.println("-->"+s.isReverse(start));
  		//运行结果为：-->true 符合预期
	}

Review 英文文章

http://hadoop.apache.org/

Apache Hadoop的官网，大概介绍了hadoop。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的0-9篇

学习了时间复杂度、空间复杂度、数组、链表、堆结构、队列结构。

出处：《数据结构与算法之美》（作者：王争）

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

自定义starter

内容较多，就不一一贴上来了，大概说一下思路。

需要创建2个项目或者模块

第一个模块就是我们的启动器，里面只需要引入其它依赖，不需要有任何的代码。

另一个模块就是我们的自动配置模块，从类路径下创建META-INF/spring.factories，在里面根据自己的需要配置初始化器、监听器或者bean（可以用条件注解进行环境判断），达到自动配置的效果。

学习自尚硅谷

http://www.atguigu.com/

Share 分享

本周的分享也就是我当前所学习的算法专栏

《数据结构与算法之美》（作者：王争）

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