Problem Description:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution:

Solution1:

Dynamic Programming
Time Complexity: O(n*sqrt(n))
Space: O(n)

Solution2:

Number Theory

  • Legendre’s three-square theorem
  • Lagrange’s four-square theorem

Time Complexity: O(sqrt(n))
Space: O(1)

Code

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
package com.zane.algorithm.leetcode;
/**
* Author: luojinping
* Date: 15/9/23
* Time: 17:23
* <p/>
* <p/>
* Given a positive integer n, find the least number of perfect square numbers
* (for example, 1, 4, 9, 16, ...) which sum to n.
* For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13,
* return 2 because 13 = 4 + 9.
*/
public class PerfectSquares_279 {
/**
* cannot use greedy algorithm, counter example:
* 98=81+16+1=49+49
* 101=100+1=49+1+49+2
* 7=4+1+1+1
* 12=4+4+4=9+1+1+1
* 思路:
* 使用DP, dp[]数组记录历史使用最少平方数的情况.例如dp[5]=2,记录的是使用最少(1+4)平方数的数量,即2.
*
* @param n
* @return
*/
public int numSquares(int n) {
if (n <= 2) {
return n;
}
// record the least number of perfect numbers when index = i
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
int leastNum = i;
for (int j = 1; j * j <= i; j++) {
leastNum = Math.min(leastNum, dp[i - j * j] + 1);
}
dp[i] = leastNum;
}
return dp[n];
}
private boolean isSquare(int n) {
int sqrt_n = (int) (Math.sqrt(n));
return (sqrt_n * sqrt_n == n);
}
/**
* Legendre's three-square theorem:
* The three squares theorem tells you that a positive integer n can be represented as the sum
* of 3 squares (n = x^2 + y^2 + z^2) if and only if it is not of the form n = 4^a * (8 * b+7)
* <p/>
* Lagrange's four-square theorem:
* Every natural number can be represented as the sum of four integer squares:
* n= a^2 + b^2 + c^2 + d^2
* <p/>
* <p/>
* So the are only 4 possible results: 1, 2, 3, 4.
* <p/>
* Refer:
* https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics
*/
public int numSquaresByMath(int n) {
// If n is a perfect square, return 1.
if (isSquare(n)) {
return 1;
}
// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}
// Check whether 2 is the result.
int sqrt_n = (int) (Math.sqrt(n));
for (int i = 1; i <= sqrt_n; i++) {
if (isSquare(n - i * i)) {
return 2;
}
}
return 3;
}
public static void main(String[] args) {
PerfectSquares_279 perfectSquares279 = new PerfectSquares_279();
System.out.println(perfectSquares279.numSquares(4));
System.out.println(perfectSquares279.numSquares(7));
System.out.println(perfectSquares279.numSquares(12));
System.out.println(perfectSquares279.numSquares(61));
System.out.println(perfectSquares279.numSquares(100));
System.out.println(perfectSquares279.numSquares(101));
}
}

Refer:

https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

Problem Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
    There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

problem link:
https://leetcode.com/problems/the-skyline-problem/

Solution

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 class TheSkylineProblem_218 {
public List<int[]> getSkylineSimpleSolution(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
// height < 0: the height of building started
// height > 0: the height of building ended
for (int[] b : buildings) {
height.add(new int[]{b[0], -b[2]});
height.add(new int[]{b[1], b[2]});
}
// sorted by x value, if x equals then sorted by y value
Collections.sort(height, (a, b) -> {
if (a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
// record the height of visited buildings by reverse order
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int prevHeight = 0;
for (int[] h : height) {
if (h[1] < 0) {
// save the height of building
pq.offer(-h[1]);
} else {
// remove the height of building
pq.remove(h[1]);
}
int curHeight = pq.peek();
if (prevHeight != curHeight) {
// find the turn point
result.add(new int[]{h[0], curHeight});
prevHeight = curHeight;
}
}
return result;
}
}

算法解释

算法思路

  1. 遍历所有的点,height用来存放每个顶点,左顶点的高度转为负数,右顶点的高度仍然是正数
  2. 对height数组排序,首先按x的值排序,当x的值相等时按z排序,这样保证了即使矩形的起点一样,也是最先处理最高的点。对于[{1,2,1},{1,2,2},{1,2,3}]这样的情况会优先处理{1,2,3}这个点。
  3. 使用优先级队列pq来保存当前最近buildings的高度,这个结构很重要!
  4. 遍历height数组,碰到左顶点时,将高度放入pq中,否则,碰到右顶点时则将高度从pq从移除。这样做的好处是,每次走完一个矩形时,高度能回归到之前的buildings的高度。
  5. 获取当前的最高高度,因为如果比当前矮的话,是不需要放入拐点中的,这点很重要!
  6. 如果当前的最高高度和之前的高度不一致,说明出现了拐点。**如果当前的最高高度矮于之前的值,说明之前的很高的建筑遇到了它的右顶点从而被移除了,所以目前的最高高度即使矮于之前的点,但是是新的隔离的building了,所以可以加入。那么如果高呢?当前高度比之前高,那肯定会是拐点了。

总结

几个关键点:

  1. 对顶点进行排序保存,对左右顶点根据正负号来加以区分
  2. 使用一个优先级队列来保存目前最高的建筑
  3. 碰到右顶点时消除目前的建筑高度
  4. 根据之前的高度和处理目前顶点以后(可能是加入了高度也可能是消除了之前的高度)的高度,对两者进行比较来找到拐点

Reference

https://leetcode.com/discuss/54201/short-java-solution

扔瓶子测楼层

一栋楼有n层,需要测试某种材质的玻璃瓶从哪一层掉下来恰好会碎。现在仅有两个这样的瓶子。请问怎样仍才能最快的测出楼层的临界值?

A. 只用一个瓶子从第一层扔到第n层

找到临界值的扔瓶子次数的期望为每一层的期望次数之和

1
E(x) = 1/n * 1 + 1/n * 2 + 1/n * 3 + ... + 1/n * n = (1+n)/2

所以时间复杂度是O(n)

B. 用贪心的思维

第一个瓶子从第1层开始扔,每次层数翻倍,依次为,1,2,4,8,16,直至在第 2^k 层碎掉。
第二个瓶子从第 2^(k-1) 层开始扔,直至第 2^k 层为止,中间肯定能找到临界值。
所以时间复杂度是O(lgn)

C. 用二分法

第一个瓶子每次以(i, j)为区间,扔的位置为(i+j)/2, 初始情况, i=0,j=n, 如果瓶子没碎,则i=j,直至碎掉。
第二个瓶子从第 i 层开始扔,直至第 j 层为止,中间肯定能找到临界值。

对于第 i 层,扔的情况为:

  • 第一个瓶子:n/2, $/2+n/4 i, n/2+n/4+n/8
  • 第二个瓶子:n/2+n/4, (n/2+n/k+1), …, i

显而易见,时间复杂度是O(n)

D. 数学推算

这个题目是需要最快的找出临界值,可以转换为,即使在最坏的情况下,也能最快地找出临界值。

我们先假设最坏情况下,瓶子下落次数为x,即我们为了找出N,一共用瓶子做了x次的实验。

那么,我们第一次应该在哪层楼往下扔瓶子呢?

先让我们假设第一次是在第y层楼扔的瓶子,如果第一个瓶子在第一次扔就碎了,我们就只剩下一个瓶子,要用它准确地找出N,只能从第一层向上,一层一层的往上测试,直到它摔坏为止,答案就出来了。

由于第一个瓶子在第y层就摔破了,所以最坏的情况是第二个瓶子要把第1到第y-1层的楼都测试一遍,最后得出结果,噢,原来瓶子在第y-1层才能摔破(或是在第y-1层仍没摔破,答案就是第y层。) 这样一来测试次数是1+(y-1)=x,即第一次测试要在第x层。

OK,那如果第一次测试鸡蛋没摔破呢,那N肯定要比x大,要继续往上找,需要在哪一层扔呢?我们可以模仿前面的操作,如果第一个瓶子在第二次测试中摔破了,那么第二个瓶子的测试次数就只剩下x-2次了(第一个瓶子已经用了2次)。这样一来,第二次扔瓶子的楼层和第一次扔瓶子的楼层之间就隔着x-2层。

我们再回过头来看一看,第一次扔瓶子的楼层在第x层,第1层到第x层间共x层;第1次扔鸡蛋的楼层到第2次扔瓶子的楼层间共有x-1层(包含第2次扔瓶子的那一层),同理继续往下,我们可以得出,第2次扔瓶子的楼层到第3次扔瓶子的楼层间共有x-2层,最后把这些互不包含的区间数加起来,应该大于等于总共的楼层数量100,即

1
2
3
x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100
得出答案是14

即我先用第1个瓶子在以下序列表示的楼层数不断地向上测试,直到它摔破。 再用第2个瓶子从上一个没摔破的序列数的下一层开始,向上测试,即可保证在最坏情况下也只需要测试14次,就能用2个瓶子找出从哪一层开始,往下扔鸡蛋,瓶子就会摔破。

1
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

E. DP的解法

假设f(n)表示从第n层楼扔下鸡蛋,没有摔碎的最少尝试次数。第一个鸡蛋,可能的落下位置[1,n],第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,第二个鸡蛋,需要从第一层开始试验,有i-1次机会
  • 没碎,两个鸡蛋,还有n-i层。这个就是子问题了f(n-i)

所以,当第一个鸡蛋,由第i个位置落下的时候,要尝试的次数为 1 + max{i - 1, f(n - i)},那么对于每一个i,尝试次数最少的,就是f(n)的值。
状态转移方程如下:

1
f(n) = min{1 + max{i - 1, f(n - 1)}}

其中: i的范围为[1, n], f(1) = 1.

F. 推广到一般化的问题

为n层楼,m个鸡蛋。
如下分析: 假设f(n,m)表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,还剩m-1个鸡蛋,为确定下面楼层中的安全楼层,还需要f(i-1,m-1)次,找到子问题
  • 不碎,上面还有n-i层,还需要f(n-i,m)次,又一个子问题。

状态转移方程如下:

1
f(n, m) = min{1 + max{f(n - 1, m - 1), f(n - i, m)}}

其中: i为[1, n], f(i, 1) = 1

Reference

http://www.cricode.com/3558.html
https://gist.github.com/sing1ee/5971946

快速排序的思路

1
2
3
4
5
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)

快速排序的partition方式

一种是Lomuto partition scheme,另外一种是Hoare partition scheme。

Lomuto partition

This scheme is attributed to Nico Lomuto and popularized by Bentley in his book

lomuto的partition实现方式

i指示最前面的大于pivot的元素位置,j从前往后滑动来调整元素位置。每次j碰到小于pivot的元素,则swap i位置的元素和j位置的元素,再i指向下一个大于pivot的元素。
最后,记得swap i位置的元素和最末尾的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
private int lomutoPartition(int nums[], int lo, int hi) {
int pivot = nums[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, hi); // replace the guard element
return i;
}

Hoare partition scheme

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion.

Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.

hoare的partition实现方式

i从前往后找到大于pivot的元素,j从后往前找到小于pivot的元素,然后两者swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int hoarePartition(int nums[], int lo, int hi) {
int pivot = nums[lo];
int i = lo, j = hi;
while (true) {
while (nums[i] < pivot) {
i++;
}
while (nums[j] >= pivot) {
j--;
}
if (i >= j) {
return j;
}
swap(nums, i, j);
}
}

硬币找零问题(Coin Change)

Question

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

DP求解

如果是用DP求解,那么思路首先就是找到子问题。子问题很容易确定,那就是amount-x是子问题的amount。比较容易想到的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int coinChange(int[] coins, int amount) {
if (amount == 0)
return 0;
int n = amount + 1; // the answer must smaller than [amount+1], nice!
for (int coin : coins) {
int curr = 0;
if (amount >= coin) {
int next = coinChange(coins, amount - coin);
if (next >= 0)
curr = 1 + next;
}
if (curr > 0)
n = Math.min(n, curr);
}
return (n == amount + 1) ? -1 : n;
}

上述算法的时间复杂度为O(c^n),c是coin的数量,n是amount的值。

时间复杂度较大的原因是,中间存在很多重复计算。那么需要用到DP的备忘录,不用全局变量来保存计算过的值,也不用递归的方法来实现,而是只用一个一维数组,再用循环来实现。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount <= 0)
return 0;
int[] minNumber = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
minNumber[i] = amount + 1;
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)
minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
}
}
if (minNumber[amount] == amount + 1)
return -1;
else
return minNumber[amount];
}

题目

输入二维数组,a[i][j]=1 表示从i结点指向j结点。

eg1

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

是一棵树,树为:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/
d

eg2

0 1 1 0

1 0 0 1

1 0 1 0

0 1 1 0

不是一颗树,是有环(a-b-d-c-a)的图:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/ /
d - — -

关键点

判断一张图是否是一颗树的两个关键点:

  • 不存在环路(对于有向图,不存在环路也就意味着不存在强连通子图)
  • 满足边数加一等于顶点数的规律(不考虑重边和指向自身的边)

方法

  1. DFS

  2. 如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。时间复杂度O(ve),v是顶点数,e是边数。

    第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。

    第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点,则存在环,否则没有环。这个复杂度也很高

  3. 结合树的特性(边数+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
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
import java.util.ArrayList;
import java.util.List;
public class TreeJudgeUnionB {
private static class Edge {
int start;
int end;
public Edge(int start, int end) {
this.start = start;
this.end = end;
}
}
// the number of edges
private int n;
// edge list
private List<Edge> edges = new ArrayList<>();
// the index of group
private int[] group;
// the size of tree
private int[] size;
public TreeJudgeUnionB(int n, List<Edge> edges) {
this.n = n;
this.edges = edges;
group = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
group[i] = i;
size[i] = 1;
}
}
private int find(int i) {
// find the root of a tree which contains i node
while (i != group[i]) {
i = group[i];
}
return i;
}
private boolean union(int groupI, int groupJ) {
int iRoot = find(groupI);
int jRoot = find(groupJ);
if (iRoot != jRoot) {
if (size[iRoot] < size[jRoot]) {
group[iRoot] = jRoot;
size[jRoot] += size[iRoot];
} else {
group[jRoot] = iRoot;
size[iRoot] += size[jRoot];
}
return true;
} else {
return false;
}
}
public boolean isTree() {
for (Edge edge : edges) {
if (!union(edge.start, edge.end)) {
System.out.println("input two nodes in the same tree");
return false;
}
}
boolean hasRoot = false;
for (int i = 0; i < group.length; i++) {
if (i == group[i]) {
if (!hasRoot) {
hasRoot = true;
} else {
System.out.println("exist more than one tree root");
return false;
}
}
}
printGroup();
return hasRoot;
}
public void printGroup() {
for (int i = 0; i < n; i++) {
System.out.print(group[i] + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 5;
List<Edge> edges = new ArrayList<>();
addEdge(edges, 0, 1);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // true
n = 5;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // false
n = 4;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 2, 3);
isTree(n, edges); // false
n = 7;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 4, 5);
addEdge(edges, 3, 4);
addEdge(edges, 2, 3);
addEdge(edges, 0, 6);
isTree(n, edges); // true
}
protected static void addEdge(List<Edge> edges, int i, int j) {
edges.add(new Edge(i, j));
}
protected static void isTree(int n, List<Edge> edges) {
TreeJudgeUnionB treeJudgeUnionA = new TreeJudgeUnionB(n, edges);
boolean isTree = treeJudgeUnionA.isTree();
System.out.println("This is a tree? " + isTree);
}
}

介绍

在计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:

Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

Union:将两个子集合并成同一个集合。

适用场景

适合于判断,给出一组结点,判断他们是否联通。

实现思路

  1. 建立n个分组,每个分组代表一堆可以互相联通的结点。
  2. 遍历每对结点,找到他们各自所属的分组A, B
  3. 如果A != B,则将A, B分组union起来,表示A, B分组联通了
  4. 如果A == B,则跳过

Simple Find 操作

用 group[] 数组来判断某个id属于的组。初始状态时,每个id都属于不同的组。

1
2
for(int i = 0; i < size; i++)
group[i] = i;

Simple Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q) {
// get the groupId of every node
int pId = find(p);
int qId = find(q);
// the two nodes are connected, return
if (pId == qId) {
return;
}
// union the two nodes, change groupId
for (int i = 0; i < id.length; i++) {
if (group[i] == pId) {
group[i] = qId;
}
}
}

优化

上面最后一步的union操作存在性能问题,即每次都需要改变其中一个分组中的所有结点的分组id。优化的做法是,用一颗树来表示每个分组,树的根节点表示当前组的id。

但如果用树来表示会引入一个问题,即可能存在树退化为链表的情况,这样一来,每一次加入一个结点再找根结点也会很耗时,没有达到优化的目的。
针对树可能退化为链表的解决方案是,每次合并树时,总是将矮的树挂到高的树下。这种方式也称为「按秩合并」

除了使用树来优化union性能以外,还有一种方式,称为「路径压缩」,即 Find 递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者间接引用节点的操作加速。

总结:

  1. 使用树来存储分组,Union时「按秩合并」
  2. 「路径压缩」,Find时改变每一个节点的引用到根节点

Find 操作

1
2
3
// store every tree's size
for (int i = 0; i < N; i++)
size[i] = 1;
1
2
3
4
5
6
7
8
private int find(int p)
{
if(p != group[p]){
group[p] = find(group[p])
}
return group[p]
}

Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q)
{
int i = find(p);
int j = find(q);
if (i == j) {
return;
}
if (size[i] < size[j]) {
group[i] = j;
size[j] += size[i];
} else {
group[j] = i;
size[i] += size[j];
}
}

时间复杂度

Statement: If m operations, either Union or Find, are applied to n elements, the total run time is O(m logn), where log is the iterated logarithm.
Proof of O(logn) time complexity of union-find: https://en.wikipedia.org/wiki/Proof_of_O\(logn)_time_complexity_of_union%E2%80%93find

Refer

https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
http://blog.csdn.net/dm_vincent/article/details/7655764
https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

避免使用 GroupByKey

当调用 groupByKey 时,所有的键值对(key-value pair) 都会被移动。在网络上传输这些数据非常没有必要。

以下函数应该优先于 groupByKey :

  • combineByKey
    组合数据,但是组合之后的数据类型与输入时值的类型不一样。

  • foldByKey
    合并每一个 key 的所有值,在级联函数和“零值”中使用。

combineByKey

combineByKey的定义

1
2
3
4
5
6
7
8
9
def combineByKey[C](
createCombiner: V => C,
mergeValue: (C, V) => C,
mergeCombiners: (C, C) => C,
partitioner: Partitioner,
mapSideCombine: Boolean = true,
serializer: Serializer = null): RDD[(K, C)] = {
// do something
}

combineByKey函数主要接受了三个函数作为参数,分别为createCombiner、mergeValue、mergeCombiners。这三个函数足以说明它究竟做了什么。理解了这三个函数,就可以很好地理解combineByKey。

createCombiner

createCombiner:在遍历RDD的过程中,对于遍历到的(k,v),如果是第一次遇到,则对这个(k,v)调用createCombiner函数,它的作用是将v转换为c(类型是C,即聚合对象的类型,c作为聚合对象的初始值)

mergeValue

mergeValue:在遍历RDD的过程中,对于遍历到的(k,v),如果不是第一次(而是第i次, 1 < i <= n)遇到,那么将对这个(k,v)调用mergeValue函数,它的作用是将v累加到聚合对象(类型C)中,mergeValue的类型是(C,V)=>C,参数中的C遍历到此处的聚合对象,然后对v进行聚合得到新的聚合对象值

mergeCombiners

mergeCombiners:因为combineByKey是在分布式环境下执行,RDD的每个分区单独进行combineByKey操作,最后需要对各个分区的结果进行最后的聚合。它的函数类型是(C,C)=>C,每个参数是分区聚合得到的聚合对象。

combineByKey的流程

  • 假设一组具有相同 K 的 records 正在一个个流向 combineByKey(),createCombiner 将第一个 record 的value 初始化为 c (比如,c = value),然后从第二个 record 开始,来一个 record 就使用 mergeValue(c,
  • record.value) 来更新 c,比如想要对这些 records 的所有 values 做 sum,那么使用 c = c + record.value。等到records 全部被 mergeValue(),得到结果 c。假设还有一组 records(key 与前面那组的 key 均相同)一个个到来,
  • combineByKey() 使用前面的方法不断计算得到 c’。现在如果要求这两组 records 总的 combineByKey() 后的结果,那么可以使用 final c = mergeCombiners(c, c’) 来计算。

Example

1
2
3
4
5
6
7
var rdd1 = sc.makeRDD(Array(("A",1),("A",2),("A",3),("B",1),("B",2),("C",3)))
// result: ((A,1_$2_@3), (B,1_$2_), (C,3_))
rdd1.combineByKey(
(v : Int) => v + "_",
(c : String, v : Int) => c + "@" + v,
(c1 : String, c2 : String) => c1 + "$" + c2 ).collect

combineByKey应用举例

求均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
val rdd = sc.textFile("气象数据")
val rdd2 = rdd.map(x=>x.split(" ")).map(x => (x(0).substring("从年月日中提取年月"),x(1).toInt))
val createCombiner = (k: String, v: Int)=> {
(v,1)
}
val mergeValue = (c:(Int, Int), v:Int) => {
(c._1 + v, c._2 + 1)
}
val mergeCombiners = (c1:(Int,Int),c2:(Int,Int))=>{
(c1._1 + c2._1, c1._2 + c2._2)
}
val vdd3 = vdd2.combineByKey(
createCombiner,
mergeValue,
mergeCombiners
)
rdd3.foreach(x=>println(x._1 + ": average tempreture is " + x._2._1/x._2._2)

Step1 Find the resource

search in Google, steam 上已经没有了。

Step2 Fix the Max OS 10.11 bug

An error occured while starting the X11 server:
Failed to activate core devices”
Click Quit to quit X11. Click Report to see more details or send a report to Apple.

https://www.reddit.com/r/OSXElCapitan/comments/3d64sd/wineskin/ 找到解决方法。即:
open terminal:

mkdir/lib
cp -r /Applications/aoeHD.app/Contents/Frameworks/* /lib

此时再打开游戏,成功运行,听到了熟悉的声音。

Reference
https://www.reddit.com/r/OSXElCapitan/comments/3d64sd/wineskin/

将数据转成json格式:python -m json.tool

$ echo '{"json":"obj"}' | python -m json.tool
{
"json": "obj"
}

查看gzip数据

使用python的zlib库来解压

s='\x1F\x8B\x08\x00\x00\x00\x00\x00\x00\x005N\xCD\x0A\xC3 \x18{\x97\xEF,\xE5s\xF3gz\xAB\xA0/1z\x18\xC31\x87m\xA5\xEA\xA1\x94\xBE\xFB\xBE\xC3vJHB\x92\x03z\x8D\xDBXJ\x05{?\xA0,`\xE1\xB9\xCEC\xEB\x9F\xF4\x18\xDEk\x8B\x19\x18\xD4\x99d\xC9/\xCE\xF9\x10Ft\xE1\xAA\x9DFm\x8C\x92B)w\xF3\x02\xBD\xA1\x5C\xA3\x16.\x84\xE4\x5CHD\x94\x82Ao`\x97\x9E3\x83Df\xDBzdP\xD2_{\x11C\x06\xB9\x13\x9C\x13\x0D\xED\xF5\xF7e:\xBF\xAB \xDB\x10\x9B\x00\x00\x00' 

import zlib
d=zlib.decompressobj(16+zlib.MAX_WBITS) 
data=d.decompress(s)

统计服务器上的历史登录记录

last -ad | awk '{print $1}' | sort | uniq -c | sort -t$'\t' -k1,1 -nr 

linux文件格式转换

在linux下,不可避免的会用VIM打开一些windows下编辑过的文本文件。我们会发现文件的每行结尾都会有一个^M符号,这是因为DOS下的编辑器和Linux编辑器对文件行末的回车符处理不一致,
对于回车符的定义:

  • windows:0D0A
  • unix\linux: 0A
  • MAC: 0D
    去除这些符号的方法有:
  • vim下 :set fileformat=unix
  • 终端 dos2unix filename

git图形化提交历史

git log --pretty=format:"%h %an %s" --graph

echo 总结

  1. echo默认是带换行符做结尾的
  2. echo -n 可以去掉换行符
  3. printf是没有换行符结尾的
  4. tr可以删掉一个字符,如 tr -d ‘\n’

删除空行

  1. grep: grep -v ‘^$’ file
  2. sed: sed ‘/^$/d’ file 或 sed -n ‘/./p’ file
  3. awk: awk ‘/./ {print}’ file

shell读文件

读取 md5s 文件,对每行做处理。

cat md5s | while read line 
do 
     md5=$line 
     level2Path=`expr substr "$md5" 30 2` #50 
     level1Path=`expr substr "$md5" 32 1` #a 
     storagePath=hdfs:///ljp/apk/path/$level1Path/$level2Path/$md5 
     echo $storagePath
done