ARTS-第60周

发表于

ARTS （第60周）

无知和弱小不是生存的障碍，傲慢才是。

要谦虚和学习。

Algorithm 算法

数据流中的中位数

1
2
3
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&tPage=4&rp=4&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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


import java.util.Comparator;
import java.util.PriorityQueue;


//双堆动态维护大小
public class Solution {
	
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
	PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});
	int count = 0;

	public void Insert(Integer num) {
		count++;
		if (count % 2 == 0) {
			if (!maxHeap.isEmpty() && num < maxHeap.peek()) { 
				maxHeap.add(num);
				num = maxHeap.poll();
			}
			minHeap.add(num);
		} else {
			if (!minHeap.isEmpty() && num > minHeap.peek()) {
				minHeap.add(num);
				num = minHeap.poll();
			}
			maxHeap.add(num);
		}
	}

	public Double GetMedian() {
		if (minHeap.size() == maxHeap.size())
			return (minHeap.peek() + maxHeap.peek()) / 2.0;
		else if (maxHeap.size() > minHeap.size())
			return maxHeap.peek() / 1.0;
		else
			return minHeap.peek() / 1.0;
	}

}

滑动窗口的最大值

1
2
3
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=4&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

import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
   public ArrayList<Integer> maxInWindows(int[] num, int size) {
		ArrayList<Integer> res = new ArrayList<>();
		if (num == null || num.length < 1 || size <= 0 || size > num.length)
			return res;
		LinkedList<Integer> list = new LinkedList<>();
		for (int i = 0; i < num.length; i++) {
			//索引范围超出了
			while (!list.isEmpty() && list.peek() < i - size + 1) 
				list.poll();
			//前面的值太小了
			while (!list.isEmpty() && num[i] >= num[list.getLast()])
				list.removeLast();
			list.add(i);
			if (i >= size - 1) { 
				//前size个无效
				res.add(num[list.peek()]);
			}
		}
		return res;
	}
}

Review 英文文章

Tip 技巧

docker详细教程

https://www.bilibili.com/video/BV1og4y1q7M4?p=1

DockerFile构建过程

基础知识：

1、每个保留关键字(指令）都是必须是大写字母

2、执行从上到下顺序

3、#表示注释

4、每一个指令都会创建提交一个新的镜像曾，并提交！

Share 分享

https://blog.csdn.net/qdujunjie/article/details/18711167 ORDER BY RAND() 低效的mysql随机查询方式

https://www.jianshu.com/p/c14547dfbb79 VO，BO，PO，DO，DTO的区别

https://www.cnblogs.com/woshimrf/p/docker-container-lawyer.html 理解Docker镜像分层