ARTS 第41周

发表于

ARTS （第41周）

1.简略过程，去除无用计算（动态规划）

2.引申就能得到更多方法（做算法题得出的体会，并非完整的排序数组才适用于二分法）

Algorithm 算法

用两个栈来实现一个队列

题目

1
2
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&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
public class Solution_2StackToQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
  
    public void push(int node) {
        stack1.push(node);
    }
    //利用栈结构先入后出的特性
    //一个专门入 一个专门出
    //
    public int pop() {
    	if(stack2.size()==0) {
    		while(!stack1.isEmpty()) {
    			//核心
    			stack2.push(stack1.pop());
    		}
    	}
    	return stack2.pop();
    }
}

旋转数组的最小数字

题目

1
2
3
4
 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&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
// 暴力法
	public int minNumberInRotateArray_force(int[] array) {
		if (array == null || array.length == 0) {
			return 0;
		}
		if (array.length == 1)
			return array[0];

		for (int i = 0; i < array.length - 1; i++) {
			if (array[i] > array[i + 1])
				return array[i + 1];
		}

		return array[0];
	}

解法2

二分法

二分法的变种写法

下面这个array[m] == a0的情况的判断，是因为1,0,1,1,1这种情况，然后一直想不明白，看题解得来的写法

1
2
3
if (array[m] == a0) {
	l++;
｝

完整如下：

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 int minNumberInRotateArray(int[] array) {
		if (array == null || array.length == 0) {
			return 0;
		}
		if (array.length == 1)
			return array[0];
		int l = 0;
		int r = array.length - 1;
		if (array[l] < array[r]) {
			return array[l];
		}
		int m = 0;
		// array[0]
		int a0 = array[0];
		// 从左到右 等于找到第一个小于 array[0]的数字
		while (l <= r) {
			m = l + (r - l) / 2;
			//System.out.println("l:" + l + ",m:" + m + ",r:" + r);
			// [4,5,1,2,3]
			if (array[l] > array[l + 1]) {
				return array[l + 1];
			}

			if (array[m] > a0) {
				l = m;
			}
			if (array[m] < a0) {
				r = m;
			}
			if (array[m] == a0) {
				// Orz 1,0,1,1,1这种情况的解法一直想不明白 看题解得来的写法
				l++;
				if(l==array.length-1) {
					//最后一个了，代表全部一样
					break;
				}
			}
		}
		return a0;
	}

Review 英文文章

https://vuejs.org/v2/guide/components.html

VUE的基础组件

Tip 技巧

最近看的书籍以硬件、系统低层为主。

得出了一个简单的看法：

基于硬件构架出

报文、数据结构、算法

以此向上构架更上层的软件。

Share 分享

https://bbs.csdn.net/topics/391901425 java se和java ee

https://blog.csdn.net/ThinkWon/article/details/103804387 深入理解Java虚拟机-走近Java

https://blog.csdn.net/ThinkWon/article/details/103827387 深入理解Java虚拟机-Java内存区域与内存溢出异常