ARTS-第13周

发表于

ARTS （第13周）

其实知识总是互通的。

很多算法和结构，进行一点变种，就可以是另一个问题的答案。

本周：

堆结构

Algorithm 算法

1、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题，我又发现了一个归并排序思路的解法可以使用的场景。

所以这里也是利用归并排序的解法进行解答的。

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 static void merge(int[] nums1, int m, int[] nums2, int n) {
		if(n<1){
			return;
		}
		int s = m + n - 1;
		m--;
		n--;
		while (true) {
			if (m >= 0 && n >= 0 && nums1[m] >= nums2[n]) {
				nums1[s--] = nums1[m--];
			} else if (m >= 0 && n >= 0 && nums2[n] >= nums1[m]) {
				nums1[s--] = nums2[n--];
			} else {
				break;
			}
		}
		while (m >= 0) {
			nums1[s--] = nums1[m--];

		}
		while (n >= 0) {
			nums1[s--] = nums2[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
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
public class Heap {

	public int getSize() {
		return size;
	}

	public static void main(String[] args) throws Exception {
		
		Heap h = new Heap(50);
		System.out.println("========");
		System.out.println();
		for (int i = 50; i > 0; i--) {
			h.add(i);
		}

		h.print();
		System.out.println("");
		System.out.println("============");
		
		for (int i = 15; i > 0; i--) {
			h.removeTop();
		}
		h.print();
		System.out.println("");
		System.out.println("============");
		for (int i = 15; i > 0; i--) {
			h.removeTop();
		}
		h.print();
		
	}

	// 小顶堆
	int[] arr;
	int max;
	int size;

	public Heap(int max) {
		// 从第二个数字开始
		this.max = max + 1;
		arr = new int[this.max];
	}

	/**
	 * 新增
	 * 
	 * @author lfy
	 * @param v
	 */
	public void add(int v) {
		if (size >= max)// 满
			return;
		arr[++size] = v;// 从第二个数字开始存起
		int c = size;// 当前
		while (c / 2 > 0 && arr[c] < arr[c / 2]) {
			swap(arr,c, c / 2);
			c = c / 2;
		}
	}

	/**
	 * 交换
	 * 
	 * @author lfy
	 * @param i
	 * @param j
	 */
	public void swap(int[]arr,int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	/**
	 * 删除顶部
	 * 
	 * @author lfy
	 * @throws Exception
	 */
	public int removeTop() throws Exception {
		if (size == 0)// 空
			throw new Exception("堆顶已空");
		// 交换第一个和末尾
		swap(arr,1, size);
		int c = 1;
		int top = c;
		while (true) {

			if (c * 2 < size && arr[c] > arr[c * 2]) {
				top = c * 2;
			}
			if (c * 2 + 1 < size && arr[top] > arr[c * 2 + 1]) {
				top = c * 2 + 1;
			}
			if (c == top)
				break;
			swap(arr,c, top);
			c = top;
		}

		return arr[size--];

	}

	
	public void print() {
		int max = 1;
		int left = 1;
		for (int i = 1; i <= size; i++) {
			System.out.print(arr[i] + " ");
			left--;
			if (left == 0) {
				System.out.println();
				left = max = max * 2;
			}

		}

	}


	
}

Review 英文文章

https://lucene.apache.org/solr/resources.html

solr的简易介绍。

Tip 技巧

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

本周学习了该专栏中的31-33篇

1、深度和广度优先搜索

这二类算法可以放在树结构或者图结构以及其他类似的由多个节点互相关联构成的结构中使用。

深度优先搜索：

从起始节点出发，查找和当前节点直接广联的节点，查找完了再去查找下一层点。

学习完了这篇专栏，让我发现树结构的按层遍历，就是一个深度优先的搜索。

广度优先搜索：

广度优先就是从当前节点开始遍历当前节点的关联节点，然后继续关联有关联的节点，当没有关联节点了，就回退上一个节点重新开始关联关联节点。这个也就对应着树结构的前序、中序、后序遍历。

这个让我发现，其实知识总是互通的。

2、字符串匹配算法

2个字符串进行匹配，一个为主串，而另一个为模式串。

BF算法：简单粗暴简单的算法，逐个匹配2个字符串。

RK算法：用hash算法计算模式串，然后逐个计算主串的hash进行匹配。还可以在此基础上统计规律简化hash的计算。

BM算法：分为好字符原则和坏字符原则，匹配到了坏字符或者好字符，就可以根据规则进行一个较长长度的跳跃。

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

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

Share 分享

平方根倒数速算法中的神奇数字 0x5f3759df

https://blog.csdn.net/zdy0_2004/article/details/52477640

数学真是神奇