CoderMeng

发表于 更新于 分类于

问题描述

分形在一定的技术意义上说，是在所有标度显示自相似性的一个对象或数量。对象不必在所有标度上展示完全相同的结构，但在所有标度上显示同样的结构“类型”。
分型块的定义如下： 次数是1的分型块只是：
X
次数2的分型块是：

X X
 X 
X X

如果利用B(n-1)表示次数是n-1的分型块，那么次数是n的分型块递归定义如下： 

B(n-1)        B(n-1)
       B(n-1)
B(n-1)        B(n-1)

你的任务是画一个次数是n的分型块。

输入

输入有多组测试数据。每行有一个不大于7的正整数n 。最后一行的一个负整数-1表示输入结束。

输出

对每组测试数据，输出用大写字母‘X’标记的分型块。每组测试数据后输出一个破折号。

输入样例

1
2
3
4
-1

输出样例

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-

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
package dynamic.plan;

import java.util.Scanner;

public class Fractal {
	
	private int[][] arr;
	private int length;
	
	private void B(int x,int y, int n) {
		if (n == 1) {
			System.out.print("X");
		}else if ( n==2 ) {
			arr[x][y] = 1;
			arr[x-1][y-1] = 1;
			arr[x+1][y-1] = 1;
			arr[x-1][y+1] = 1;
			arr[x+1][y+1] = 1;
		} else {
			B(x, y, n-1);
			int tmp = (int) Math.pow(3, n-2);
			B(x-tmp, y-tmp, n-1);
			B(x-tmp, y+tmp, n-1);
			B(x+tmp, y-tmp, n-1);
			B(x+tmp, y+tmp, n-1);
		}
	}

	public void exe(int n) {
		length = (int) Math.pow(3, n-1);
		arr = new int[length][length];
		B(length/2, length/2, n);
		
		for(int i=0; i<length; i++){ 
			for(int j=0; j<length; j++){
				if (arr[i][j] == 1) {
					System.out.print("X");
				}else {
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Fractal f = new Fractal();
		int[] a = new int[8];
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		while(n>0 && n<8){
			a[n] = 1;
			n = in.nextInt();
		}
		for(int i=1; i<8; i++){
			if (a[i] == 1) {
				f.exe(i);
				System.out.println("-");
			}
		}
	}
}

发表于 更新于 分类于

输入

测试数据有3行：其第1行上有2个整数n和c，分别是物品个数n和背包所能容纳物品的重量，（n<=50,c<=500），第2行上有n个整数v1、v2、…、vn，依次是n个物品的价值，第3行上有n个整数w1、w2、…、wn,，分别是n个物品的重量。诸整数之间用一个空格分开。

输出

输出具体放物品的最大价值

输入样例

5 10
6 3 5 4 6
2 2 6 5 4

算法思想

我们将在总重量不超过Y的前提下，前j种物品的总价格所能达到的最高值定义为A(j, Y)。
A(j, Y)的递推关系为：

A(0, Y) = 0
A(j, 0) = 0
如果 wj > Y,超过背包容量舍弃， A(j, Y) = A(j - 1, Y)
如果 wj ≤ Y,两种情况，放第j个物品和不放第j个物品， A(j, Y) = max { A(j - 1, Y), pj + A(j - 1, Y - wj) }

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
/**
 * @author corlymeng.com
 * @date  2015年9月22日
 */
package dynamic.plan;

import java.util.Scanner;

public class Knapsack {
	
	private int[] weight;
	private int[] value;
	// 背包的容量
	private int pack;
	int[][] f;
	public void init() {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		pack = in.nextInt();
		weight = new int[n+1];
		value = new int[n+1];
		int i;
		for(i=1; i<n+1; i++)
			value[i] = in.nextInt();
		for(i=1; i<n+1; i++)
			weight[i] = in.nextInt();
	}
	//自顶向上递归实现
	private int _top01PackageAnswer(int n, int w) {
		if (n==0 || w==0) {
			return 0;
		}
		if (weight[n] > w) {
			return _top01PackageAnswer(n-1, w);
		}else {
			return Math.max(_top01PackageAnswer(n-1, w), _top01PackageAnswer(n-1, w-weight[n]) + value[n]);
		}
	}
	
	public void top01PackageAnswer() {
		System.out.println(_top01PackageAnswer(weight.length-1, pack));
	}
	
	// 自低向上
	public void buttom01PackageAnswer() {
		f = new int[weight.length][pack+1];
		int i,j;
		//枚举物品
		for(i=1; i<weight.length; i++){
			for(j=0; j<=pack; j++){
				if (weight[i] > j) {
					f[i][j] = f[i-1][j];
				} else {
					f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i]] + value[i]);
				}
			}
		}
		// 输出最大价值
		System.out.println(f[weight.length-1][pack]);
		// 输出选取物品的下标
		StringBuffer str = new StringBuffer();
		int x,y;
		x = weight.length-1;
		y = pack;
		while(x > 0 && y>0) {
			if (f[x-1][ y-weight[x] ] == f[x][y]-value[x]) {
				str.append(","+x);
				y -= weight[x];
			}
			x--;
		}
		System.out.println(str.reverse().toString());
		
	}
	
	public static void main(String[] args) {
		Knapsack k = new Knapsack();
		k.init();
//		k.top01PackageAnswer();
		k.buttom01PackageAnswer();
	}

}

在执行自低向上求解时，数组 f 的值如下：

[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6],
[0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9],
[0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14],
[0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14],
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
]

发表于 更新于 分类于

问题描述：

点集Q的凸包ch(Q)是一个最小的凸多边形P，它满足Q中的每个点或者在P的边界上，或者在P的内部。你的任务是对于给定的点集Q，求Q的凸包ch(Q)集。

输入：

输入测试数据。测试数据的第一行上有整数n，表示该组测试数据有n个点组成的集合Q。接下来有n行，其每一行上有二个正整数，之间用一个或几个空格隔开。

输出：

输出该凸包的顶点集合，要求先输出凸包的顶点中纵坐标最小且靠最左边的点，然后将凸包的其它顶点按逆时针方向列出。

输入样例：

6
1 1
2 2
1 3
2 3
3 1
3 3

输出样例：

(1,1)(3,1)(3,3)(1,3)

Graham 扫描法

在 《算法导论》上 Graham 扫描法的伪代码如下

Graham.jpg

过程 GRAHAM-SCAN 的输入为点集 Q ，其中 |Q|> 3。

第一行从点集 Q 中选取 y 值最小的，并且与其有相同 y 值的点都在它的右边，后面的点都已 p0 为参考点。（下面代码中的 setP0() 方法）

第二行根据相对于 p0 的极角对 Q 中剩余的点进行排序，采用插入排序的方法（参考：计算几何02-用叉积比较极角大小并对点集进行排序）。如果有两个或更多的点对 p0 的极角相同，那么除了与 p0 距离最远的点外，其余各点都是 p0 与该最远点的凸组合。因此，我们可以完全不考虑这些点。（下面代码中的 PolarAngleSort 类下的 sortPoints(int[][] points, int[] sorts) 方法。）

第五行–第十二行运用了栈 S，其中第68行对栈进行初始化，使其从底部到顶部依次包含前三个点 p0,p1,p2。第912行的 for 循环对序列（p3,p4,···,pm）中的每一个点进行一次迭代。算法的意图是在对 pi 进行处理后，在栈 S 中，由底部到顶部依次包含 ch(p0,p1,···,pi) 中按逆时针排列的各个顶点。第10~11行的 while 循环把所有发现的不是凸包中的顶点的点从栈中移去。当沿逆时针方向遍历凸包时，我们应该在每个顶点处向左转。因此，每当 while 循环发现一个顶点处没有向左转时，就把该顶点从栈中弹出来。

当程序运行结束时，栈 S 从底部到顶部包含了按逆时针方向排列在 ch（Q） 中的个顶点。

PolarAngleSort.java

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
/**
 * @author corlymeng.com
 * @date  2015年9月18日
 */
package geometry.convex;

import java.util.Scanner;

public class PolarAngleSort {

	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积。
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	public static int direction(int[] pi, int[] pk, int[] pj){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	// 计算点 p1 到点 p2 的距离
	public static double pointDistance(int[] p1, int[] p2) {
		return Math.hypot( p1[0]-p2[0], p1[1]-p2[1] );
	}
	
	/**
	 * ！核心代码
	 * 采用插入排序的思想对点集进行排序。
	 * 以点points[0] 为参考点
	 */
	public static void sortPoints(int[][] points, int[] sorts) {
		int i,j;
		int[] tmp;
		double d1,d2;
		for (i = 2; i < sorts.length; i++) {
			tmp = points[i];
			j = i-1;
			while( j>0 ){
				if (sorts[j]<0 || direction(points[0], points[sorts[j]], tmp) < 0) {
					sorts[j+1] = sorts[j];
					j--;
				} else {
					break;
				}
			}
			// 叉积为 0 的时候，要计算这两点到 p0 的距离，
			//将距离最远的点保留，距离近的点舍去，将点对应的sorts 数组的值设置为负数即表示忽略此点
			if (j != 0 && direction(points[0], points[sorts[j]], tmp) == 0) {
				d1 = pointDistance(points[0], points[sorts[j]]);
				d2 = pointDistance(points[0], tmp);
				if (d1 > d2) {
					sorts[j+1] = -i;
				} else {
					sorts[j] = -sorts[j];
					sorts[j+1] = i;
				}
			} else {
				sorts[j+1] = i;
			}
		}
	}
}

FindConvex.java

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
/**
 * @author corlymeng.com
 * @date  2015年9月19日
 */
package geometry.convex;

import java.util.Scanner;

/**
 * 找出给定点集的凸包
 */
public class FindConvex {
	//点的数量
	private int nums;
	// 存放输入的点集
	private int[][] points;
	/**
	 * 存放点的顺序，sorts[0] = 0，默认的相对点，后面的点1，2，3...都是以 0 为参考点
	 * sorts[1]=4,表示点集中相对于参考点极角最小的是点 4
	 */
	private int[] sorts;
	
	// 模拟栈的操作
	private int[] stack;
	// 栈顶指针
	private int top;

	private void setP0(){
		int tmp = 0;
		//找出 y 值最小的点
		for(int i=1; i<nums; i++){
			if (points[tmp][3] > points[i][4]) {
				tmp = i;
			} else if (points[tmp][5] == points[i][6]) {
				// y 值相同时，比较 x 值
				if (points[tmp][0] > points[i][0]) {
					tmp = i;
				}
			}
		}
		if (tmp == 0) {
			return;
		}else {
			int[] p = points[0];
			points[0] = points[tmp];
			points[tmp] = p;
		}
	}

	public void init(){
		Scanner in = new Scanner(System.in);
		nums = in.nextInt();
		points = new int[nums][2];
		sorts = new int[nums];
		stack = new int[nums];
		top = 0;
		for (int i = 0; i < nums; i++) {
			sorts[i] = i;
			points[i][0] = in.nextInt();
			points[i][7] = in.nextInt();
		}
	}
	
	/**
	 * !核心代码
	 * 获取凸包的顶点集，存放在 stack 变量中，按逆时针顺序存放。
	 */
	public void findConvexPoint() {
		// 初始化操作
		init();
		setP0();
		PolarAngleSort.sortPoints(points, sorts);
		
		//首先，将点集 p0,p1,p2 入栈
		int s = 0;
		stack[top] = sorts[0];
		while(top < 2){
			if (sorts[s]>0) {
				stack[++top] = sorts[s];
			}
			s++;
		}
		for ( ; s < nums; s++) {
			if (sorts[s] < 0) {
				continue;
			}
			while(PolarAngleSort.direction(points[stack[top]], points[stack[top-1]], points[sorts[s]]) >= 0 ) {
				top--;
			}
			stack[++top] = sorts[s];
		}
	}	
	
	public void print() {
		for(int i=0; i<=top; i++){
			System.out.print("("+ points[stack[i]][0] +","+ points[stack[i]][8] +")");
		}
	}
	
	public static void main(String[] args) {
		FindConvex fc = new FindConvex();
		fc.findConvexPoint();
		fc.print();
	}

}

发表于 更新于 分类于

一个点 p1 相对于原点 p0 的极角（polar angle）也就是向量 p1-p0 在常规坐标系中的角度。例如，点（3，5）相对于（2，4）的极角即为向量（1，1）的极角，即 45 度或 π/4 弧度。点（3，3）相对于（2，4）的极角即为向量（1，-1）的极角，即 315 度或 7π/4 弧度。请编写一段代码，根据相对于某个给定的原点 p0 的极角，对一个由 n 个点构成的序列（p1,p2,···,pn）进行排序。

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
/**
 * @author corlymeng.com
 * @date  2015年9月18日
 */
package geometry;

import java.util.Scanner;

public class PolarAngle {
	//点的数量
	private int nums;
	// 存放输入的点集
	private int[][] points;
	/**
	 * 存放点的顺序，sorts[0] = 0，默认的相对点，后面的点1，2，3...都是以 0 为参考点
	 * sorts[1]=4,表示点集中相对于参考点极角最小的是点 4
	 */
	private int[] sorts;
	
	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积。
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	private int direction(int[] pi, int[] pk, int[] pj){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	
	/**
	 * ！核心代码
	 * 采用插入排序的思想对点集进行排序。
	 */
	public void sortPoints() {
		init();
		int i,j;
		int[] tmp;
		for (i = 2; i < nums; i++) {
			tmp = points[i];
			j = i-1;
			while(j>0 && direction(points[0], points[sorts[j]], tmp) < 0){
				sorts[j+1] = sorts[j];
				j--;
			}
			sorts[j+1] = i;
		}
	}
	
	public void init(){
		Scanner in = new Scanner(System.in);
		nums = in.nextInt();
		points = new int[nums][2];
		sorts = new int[nums];
		for (int i = 0; i < nums; i++) {
			sorts[i] = i;
			points[i][0] = in.nextInt();
			points[i][1] = in.nextInt();
		}
	}
	
	public static void main(String[] args) {
		PolarAngle ch = new PolarAngle();
		ch.sortPoints();
	}

}

输入样例：

6
1 1
2 2
1 3
2 3
3 1
3 3

排序后的 sorts 数组：[0, 4, 1, 5, 3, 2]，即序列为 p4,p1,p5,p3,p2 。

发表于 更新于 分类于

两条线段相交当且仅当下面两个条件至少成立一个：

1.每条线段都跨越了包含另一条线段的直线。
2.一条线段的某个端点落在了另一条线段上。（这一情况来自于边界情况）

在判断线段的相交时我们可以利用向量的叉积。当两条向量在一条直线上时，向量的叉积等于 0 ，即上面的第二种情况，所以判断两条线段相交就分为两种情况讨论：1.向量的叉积不等于 0 ；2.向量的叉积等于 0 。

一.叉积不等于 0

首先：我们要判断点 p3，p4 分布在线段 p1 p2 两边。如下图所示：

segment_insect.jpg

① 根据向量的叉积，如果 p1p4 * p1p2 > 0 则表示向量 p1p2 在向量 p1p4 的逆时针方向，根据 p1p2 * p1p3 > 0，可以判断 p1p3 在 p1p2 的逆时针方向。这时就可以判断点p3，p4 在线段 p1p2 的两端。

② 同理，我们可以判断 p1,p2 分布在线段 p3 p4 的两端。

如果同时满足①，② 成立，则这两个线段就相交

二.叉积等于 0

当叉积等于 0 的时候，只需要判断这三个点是否在同一条直线上就可以了。

java 代码如下：

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
/**
 * @author corlymeng.com
 * @date  2015年9月16日
 */
package geometry;

import java.util.Scanner;

public class Segment {
	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	private int direction(int[] pi, int[] pj, int[] pk){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	/**
	 * 判断点pk是否在线段 pi,pj 上
	 * @return boolean
	 */
	private boolean onSegment(int[] pi, int[] pj, int[] pk) {
		if ( Math.min(pi[0], pj[0]) <= pk[0] && pk[0] <= Math.max(pi[0], pj[0]) && 
			 Math.min(pi[1], pj[1]) <= pk[1] && pk[1] <= Math.max(pi[1], pj[1]) ) {
			return true;
		}else {
			return false;
		}
	}
	// 判断线段 p1,p2 和线段 p3,p4 是否相交
	public boolean segmentInsert(int[] p1, int[] p2, int[] p3, int[] p4) {
		int d1 = direction(p3, p4, p1);
		int d2 = direction(p3, p4, p2);
		int d3 = direction(p1, p2, p3);
		int d4 = direction(p1, p2, p4);
		if ( ((d1>0 && d2<0) || (d1<0 && d2>0)) &&
			 ((d3>0 && d4<0) || (d3<0 && d4>0))) {
			return true;
		} else if ( d1==0 && onSegment(p3, p4, p1)) {
			return true;
		} else if ( d2==0 && onSegment(p3, p4, p2)) {
			return true;
		} else if ( d3==0 && onSegment(p1, p2, p3)) {
			return true;
		} else if ( d4==0 && onSegment(p1, p2, p4)) {
			return true;
		} else {
			return false;
		}
	}
	
	public static void main(String[] args){
		Segment segment = new Segment();
		Scanner in = new Scanner(System.in);
		int[] p1 = {in.nextInt(), in.nextInt()};
		int[] p2 = {in.nextInt(), in.nextInt()};
		int[] p3 = {in.nextInt(), in.nextInt()};
		int[] p4 = {in.nextInt(), in.nextInt()};
		if (segment.segmentInsert(p1, p2, p3, p4)) {
			System.out.println("相交");
		} else {
			System.out.println("不相交");
		}
	}
}

发表于 更新于 分类于

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

我们先看一个简单的例子：

例子：越多越好

问题描述

某公司要求它的一些员工从事若干个项目。因这些项目相当复杂，项目是分期进行的，但每个项目需要熟悉该项目的人数越多越好。当然对人员有一定的要求。

公司的员工很多，达10000人，编号从1到10000。员工们中如果有人熟悉这个项目，那么与其认识的人只要讨教一些技巧后也能知道项目如何进行，经过传帮带后所有与其直接或间接认识的人也掌握了从事项目的技巧。为便于交流与项目修改，要求从事项目的人都直接或间接认识。

现在给定直接认识的人员对，您应该做出正确的选择。

输入
有若干个项目。每个项目的数据中第一行是一个整数n (0 ≤ n ≤ 100000) ，即该项目中直接认识的人数对。接下来有n行，每行是一个用空格隔开的数对A和B，表示他们认识，(A ≠ B, 1 ≤ A, B ≤ 10000000) 。
输出
对每个项目输出从事项目的最大人数。

输入样例
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
输出样例
4
2

首先进行初始化，将每个元素看作一个树，他们的父节点指向自己。

然后将想认识的两个人看作一个集合，修改元素的根节点：{1,2}，{3,4}，{5,6}，{1,6}。

将每个集合构造一个树：
unionfind.jpg

当执行到{1,6} 是，查询 1 的根节点是 2，这时就将 6 根节点（即自己）和 1 的根节点连接，从中选择一个做根节点。
unionfind2.jpg

这是就可以看出最多的一组就是 2 为根节点的那一组，即输出 4。

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
/**
 * @author corlymeng.com
 * @date  2015年9月12日
 */
package union.find;
import java.util.Scanner;

/**
 * 并查集
 */
public class Exec1 {
	// 存放每个元素的父节点，默认指向自己。
	int[] father;
	// 每个元素的子孙节点个数，默认为  0
	int[] son;
	// 员工总数
	final int num = 1000;
	private void init(){
		father = new int[num+1];
		son = new int[num+1];
		for (int i = 0; i < father.length; i++) {
			father[i] = i;
			son[i] = 0;
		}
	}
	/**
	 * 找出 s 节点的父亲节点。
	 * 这个递归的查找会将所有的 s 的孙子以下节点的指向都修正为 s，对并查集进行优化。
	 * @param s
	 * @return
	 */
	private int findRoot(int s) {
		if (s != father[s]) {
			// 修正节点的指向
			father[s] = findRoot(father[s]);
		}
		return father[s];
	}
	/**
	 * 将 x 和 y 所在的集合合并。
	 * 默认将节点少的树合并到节点多的树上。
 	 * @param x
	 * @param y
	 */
	private void union(int x, int y) {
		x = findRoot(x);
		y = findRoot(y);
		if (x == y) {
			return;
		}
		//修改父节点和子节点
		if (son[x] > son[y]) {
			father[y] = x;
			son[x] = son[x] + son[y] + 1;
		} else {
			father[x] = y;
			son[y] = son[y] + son[x] +1;
		}
	}
	public void start(){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		init();
		for (int i = 1; i < n+1; i++) {
			int x = in.nextInt();
			int y = in.nextInt();
			union(x, y);
		}
	}
	public int max() {
		int max = 1;
		for(int i=2;i<=num;i++)  
	         if( son[max] < son[i])
	        	 max = i;
		return son[max]+1;
	}
	public static void main(String[] args) {
		Exec1 exec1 = new Exec1();
		exec1.start();
		System.out.println(exec1.max());
	}
}

并查集的精髓（即三个操作）

  1. init 把每一个元素初始化为一个集合，初始化后每一个元素的父亲节点是它本身。
  2. findRoot 查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！
    判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
  3. union(x,y) 合并x,y所在的两个集合。合并两个不相交集合操作很简单：
    利用 findRoot 找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。

发表于 更新于 分类于

大家常想到的方法就是构建一个布尔值的数组，索引 i 对应该字符串的第 i 个字符。若这个字符出现第二次，则立即返回 false 。

下面我们来介绍一种利用位向量（bit vector）来解决的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 判断字符串中的字符是否有重复（字符串只包含a-z）
 * @param str String
 * @return boolean
 */
public static boolean isUniqueChars(String str){
	if(str.length() > 26)
		return false;
	int checker = 0;
	for(int i=0; i < str.length(); i++){
		int val = str.charAt(i) - 'a';
		if( (checker & (1<<val)) > 0)
			return false;
		checker |= (1 << val );
	}
	return true;
}

checker 用二进制来表示，每一位就代表一个英文字母，最多26位。

发表于 更新于 分类于

tar [-j|-z] [cv] [-f 创建的档名] filename… <==打包与压缩
tar [-j|-z] [tv] [-f 创建的档名] <==察看档名
tar [-j|-z] [xv] [-f 创建的档名] [-C 目录] <==解压缩

-c  ：创建打包文件，可搭配 -v 来察看过程中被打包的档名(filename)
-t  ：察看打包文件的内容含有哪些档名，重点在察看『档名』就是了；
-x  ：解打包或解压缩的功能，可以搭配 -C (大写) 在特定目录解开
      特别留意的是， -c, -t, -x 不可同时出现在一串命令列中。
-j  ：透过 bzip2 的支持进行压缩/解压缩：此时档名最好为 *.tar.bz2
-z  ：透过 gzip  的支持进行压缩/解压缩：此时档名最好为 *.tar.gz
-v  ：在压缩/解压缩的过程中，详细地列出处理的文件
-f filename：-f 后面要立刻接要被处理的档名！建议 -f 单独写一个选项罗！
-C 目录    ：这个选项用在解压缩，若要在特定目录解压缩，可以使用这个选项。
-p  ：保留备份数据的原本权限与属性，常用於备份(-c)重要的配置档
-P  ：保留绝对路径，亦即允许备份数据中含有根目录存在之意；
--exclude=FILE：在压缩的过程中，不要将 FILE 打包！

其实最简单的使用 tar 就只要记忆底下的方式即可：

压　缩：tar -jcv -f filename.tar.bz2 要被压缩的文件或目录名称
查　询：tar -jtv -f filename.tar.bz2
解压缩：**tar -jxv -f filename.tar.bz2 [-C 欲解压缩的目录]**（默认在当前目录）

示例：用 tar 备份 /etc/ 目录

tar -jpcv -f /root/ect.tar.bz2 /etc

示例：查看 tar 文件的数据内容

tar -jtv -f ect.tar.bz2
☞ ：加上 -v 这个选项时，详细的文件权限/属性都会被列出来

仅解开单一文件

1.首先找到我们要的文件名，假设要解开 shadow 文件

[root@www ~]# tar -jtv -f /root/etc.tar.bz2 | grep ‘shadow’
-r——– root/root 1230 2008-09-29 02:21:20 etc/shadow-
-r——– root/root 622 2008-09-29 02:21:20 etc/gshadow-
-r——– root/root 636 2008-09-29 02:21:25 etc/gshadow
-r——– root/root 1257 2008-09-29 02:21:25 etc/shadow <==这是我们要的
☞ ：其中那个 grep 是“选取”关键字的功能。那个竖线 | 配合 grep 可以选取关键字

2.解开单个文件的语法：tar -jxv -f filename.tar.bz2 待解开文件名

[root@www ~]# tar -jxv -f /root/etc.tar.bz2 etc/shadow

打包某目录，但不含该目录下的

假设我要打包当前目录，但是我不想打包 bashrc 开头的文件，而且新打包的文件也放在当前目录中，当然这个文件自己不要打包自己，此时我们可以通过 exclude 来实现。

[root@www ~]# tar -jcv -f system.tar.bz2 –exclude=bashrc* –exclude=system.tar.bz2 .

发表于 更新于 分类于

概述

定义一个用于创建对象的接口，让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。

当系统准备为用户提供某个类的子类的实例，又不想让用户代码和该子类形成耦合时，就可以使用工厂方法来设计系统。工厂方法的关键是在一个接口或抽象类中定义一个抽象方法，该方法返回某个类的子类的实例，该抽象类或接口让让其子类或实现该接口的类通过重写这个抽象方法返回某个子类的实例。

结构与使用

工厂方法模式中包含四种角色：

  • 抽象产品（Product）：抽象类或接口，负责定义具体产品必须实现的方法。

  • 具体产品（ConcreteProduct）：具体产品是一个类，如果 Product 是一个抽象类，那么具体产品是 Product 的子类；如果 Product 是一个接口，那么具体产品是实现 Product 接口的类。

  • 构造者（Creator）：一个接口或抽象类。构造者负责定义一个称作工厂方法的抽象方法，该方法返回具体产品类的实例。

  • 具体构造者（ConcreteCreator）：具体构造者重写工厂方法，使该方法返回具体产品的实例。

UML 类图

factoryMethod.jpg

结构的描述

比如，有一个 PenCore 类（笔芯），该类是一个抽象类。假设 PenCore 有三个子类，分别是 RedPenCore 类（红笔芯）和 BluePenCore 类（蓝笔芯），而系统设计的目的是为用户提供的 BallPen 类（圆珠笔）的子类的实例，即含有笔芯的圆珠笔，也就是说系统想让用户使用 BallPen 类的子类的实例来得到 PenCore 类的子类的实例。

1.抽象产品

1
2
3
4
public abstract class PenCore {
	String color;
	public abstract void writeWord(String s);
}

2.具体产品

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// RedPenCore.java
public class RedPenCore extends PenCore {
	public RedPenCore() {
		color = "红色";
	}
	@Override
	public void writeWord(String s) {
		System.out.println("写出" + color + "的字：" + s);
	}
}

// BluePenCore.java
public class BluePenCore extends PenCore {
	public BluePenCore() {
		color = "绿色";
	}
	@Override
	public void writeWord(String s) {
		System.out.println("写出" + color + "的字：" + s);
	}
}

3.构造者

1
2
3
4
5
6
public abstract class BallPen {
	public BallPen() {
		System.out.println("生产一支装有" + getPenCore().color + "笔芯的圆珠笔");
	}
	public abstract PenCore getPenCore();
}

4.具体构造者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// RedBallPen.java
public class RedBallPen extends BallPen {
	@Override
	public PenCore getPenCore() {
		return new RedPenCore();
	}
}

// BlueBallPen.java
public class BlueBallPen extends BallPen {
	@Override
	public PenCore getPenCore() {
		return new BluePenCore();
	}
}

5.模式的使用

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
	PenCore penCore;
	BallPen ballPen = new BlueBallPen();
	penCore = ballPen.getPenCore();
	penCore.writeWord("hello, nice to meet you");
	ballPen = new RedBallPen();
	penCore = ballPen.getPenCore();
	penCore.writeWord("How are you ");
}

Java集合框架与工厂模式

Java 集合框架中有一个重要的接口 Collection ，该接口中的 iterator() 方法就是一个工厂方法。iterator() 方法返回一个实现 Iterator 接口类的实例。按照工厂模式的角色分类，Iterator 接口是抽象角色；Collection 接口是构造者；而实现Collection 接口的类，即集合，都是具体构造者，比如 LinkedList 链表类就是一个具体构造者。
集合框架中的工厂方法.jpg

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
	Collection<Integer> mylist = new LinkedList<Integer>();
	for (int i = 0; i < 10; i++) {
		mylist.add(new Integer(i));
	}
	Iterator<Integer> iter = mylist.iterator();
	while (iter.hasNext()) {
		System.out.println(iter.next());
	}
}

优点

  • 使用工厂方法可以使得用户的代码和某个特定类的子类的代码解耦。

  • 工厂方法使用户不需要知道他所使用的对象是如何被创建的，只需要知道该对象有哪些方法即可。

发表于 更新于 分类于

在 Linux 下通常 find 不很常用的，因为速度慢（find是直接查找硬盘），通常我们都是先使用 whereis 或者是 locate 来检查，如果真的找不到了，才以 find 来搜寻。 为什么呢？这是因为 Linux 系统会将系统内的所有文件都记录在一个数据库文件里面， 而当使用 whereis 或者是 locate 时，都会以此数据库文件的内容为准， 因此，有的时后你还会发现使用这两个运行档时，会找到已经被删除的文件，而且也找不到最新的刚刚创建的文件，这就是因为这两个命令是由数据库当中的结果去查找文件的所在，更多与这个数据库有关的说明，请参考 locate 命令。

whereis [-bmsu] 文件或目录名

-b    :只找 binary 格式的文件
-m    :只找在说明档 manual 路径下的文件
-s    :只找 source 来源文件
-u    :搜寻不在上述三个项目当中的其他特殊文件

locate [-ir] keyword

-i  ：忽略大小写的差异；
-r  ：后面可接正规表示法的显示方式

使用locate的时候可以直接在后面输入文件的部分名称就能够得到结果。但是，这个命令寻找的数据是由已创建的数据库 /var/lib/mlocate 里面的数据查找到的，而数据库默认每天执行一次（每个distribution不同），所以当你新建文件后查找该文件，那么 locate 会告诉你“找不到”，因为必须跟新数据库。

我们可以使用 updatedb 这个命令，它根据 /etc/updatedb.conf 的设置去查找文件系统盘内的文件名，并跟新 /var/lib/mlocate 内的数据库文件。

find [PATH] [option] [action]

1. 与时间有关的选项

共有 -atime, -ctime 与 -mtime ，以 -mtime 说明

   -mtime  n ：n 为数字，意义为在 n 天之前的“一天之内”被更动过内容的文件；
   -mtime +n ：列出在 n 天之前(不含 n 天本身)被更动过内容的文件档名；
   -mtime -n ：列出在 n 天之内(含 n 天本身)被更动过内容的文件档名。
   -newer file ：file 为一个存在的文件，列出比 file 还要新的文件档名

2. 与使用者或群组名称有关的参数

-uid n ：n 为数字，这个数字是使用者的帐号 ID，亦即 UID ，这个 UID 是记录在
        /etc/passwd 里面与帐号名称对应的数字。这方面我们会在第四篇介绍。
-gid n ：n 为数字，这个数字是群组名称的 ID，亦即 GID，这个 GID 记录在
        /etc/group，相关的介绍我们会第四篇说明～
-user name ：name 为使用者帐号名称喔！例如 dmtsai 
-group name：name 为群组名称喔，例如 users ；
-nouser    ：寻找文件的拥有者不存在 /etc/passwd 的人！
-nogroup   ：寻找文件的拥有群组不存在於 /etc/group 的文件！
            当你自行安装软件时，很可能该软件的属性当中并没有文件拥有者，
            这是可能的！在这个时候，就可以使用 -nouser 与 -nogroup 搜寻。

3. 与文件权限及名称有关的参数

-name filename：搜寻文件名称为 filename 的文件；
-size [+-]SIZE：搜寻比 SIZE 还要大(+)或小(-)的文件。这个 SIZE 的规格有：
               c: 代表 byte， k: 代表 1024bytes。所以，要找比 50KB
               还要大的文件，就是“ -size +50k ”
-type TYPE    ：搜寻文件的类型为 TYPE 的，类型主要有：一般正规文件 (f),
               装置文件 (b, c), 目录 (d), 连结档 (l), socket (s), 
               及 FIFO (p) 等属性。
-perm mode  ：搜寻文件权限“刚好等於” mode 的文件，这个 mode 为类似 chmod
             的属性值，举例来说， -rwsr-xr-x 的属性为 4755 ！
-perm -mode ：搜寻文件权限“必须要全部囊括 mode 的权限”的文件，举例来说，
             我们要搜寻 -rwxr--r-- ，亦即 0744 的文件，使用 -perm -0744，
             当一个文件的权限为 -rwsr-xr-x ，亦即 4755 时，也会被列出来，
             因为 -rwsr-xr-x 的属性已经囊括了 -rwxr--r-- 的属性了。
-perm +mode ：搜寻文件权限“包含任一 mode 的权限”的文件，举例来说，我们搜寻
             -rwxr-xr-x ，亦即 -perm +755 时，但一个文件属性为 -rw-------
             也会被列出来，因为他有 -rw.... 的属性存在！

###4. 额外可进行的动作

-exec command ：command 为其他命令，-exec 后面可再接额外的命令来处理搜寻到的结果。
-print        ：将结果列印到萤幕上，这个动作是默认动作！

将找到的文件使用 ls -l 列出来～

find / -perm +755 -exec ls -l {} ;
☞ 那个 -exec 后面的 ls -l 就是额外的命令，命令不支持命令别名， 所以仅能使用 ls -l 不可以使用 ll 。

  • {} 代表的是“由 find 找到的内容”，find 的结果会被放置到 {} 位置中；
  • -exec 一直到 ; 是关键字，代表 find 额外动作的开始 (-exec) 到结束 (;) ，在这中间的就是 find 命令内的额外动作。 在本例中就是“ ls -l {} ”；
  • 因为“ ; ”在 bash 环境下是有特殊意义的，因此利用反斜线来转义。

另外，find还可以使用通配符来查找文件。

find /etc -name ‘*httpd*‘