Skip to content

Commit e42c180

Browse files
GoflyingingGoflyinging
committed
first add
0 parents  commit e42c180

15 files changed

Lines changed: 1066 additions & 0 deletions

‎1/ExistTwo.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
import java.util.Scanner;
2+
import java.util.Random;
3+
public class ExistTwo {
4+
public static void mergesort(int[] a, int p, int r) {
5+
if (p < r) {
6+
int mid = (r+p) / 2;
7+
mergesort(a, p, mid);
8+
mergesort(a, mid + 1, r);
9+
merge(a, p, mid, r);
10+
}
11+
12+
}
13+
14+
public static void merge(int[] a, int p, int q, int r) {
15+
16+
int i = p;
17+
int j = q + 1;
18+
int k = p;
19+
20+
int[] temp1 = new int[q - p + 1 +1];
21+
int[] temp2 = new int[r - q +1];
22+
int l1 = temp1.length;
23+
int l2 = temp2.length;
24+
for (int n = 0; n < l1-1; n++) {
25+
temp1[n] = a[i];
26+
i++;
27+
}
28+
for (int n = 0; n < l2-1; n++) {
29+
temp2[n] = a[j];
30+
j++;
31+
}
32+
temp1[l1-1] = 8888888;
33+
temp2[l2-1] = 8888888;
34+
i = 0;
35+
j = 0;
36+
37+
for(; k<r+1;k++) {
38+
if (temp1[i] <= temp2[j]) {
39+
a[k] = temp1[i++];
40+
41+
}
42+
else{
43+
a[k] = temp2[j++] ;
44+
}
45+
}//for
46+
}//meger
47+
public static int[] arrRandom(int n,int min , int max ){
48+
int arr[] = new int[n];
49+
Random r = new Random();
50+
for(int i=0;i<n;i++){
51+
arr[i] =(r.nextInt(max-min + 1)+min);
52+
System.out.print(arr[i] + " ");
53+
}
54+
return arr;
55+
56+
}//arrRandom
57+
public static boolean binarySearch(int arr[],int x, int min,int max){
58+
while(min<=max){
59+
int mid = (max + min)/2;
60+
if(arr[mid] > x)
61+
{
62+
max = mid-1;
63+
}
64+
else if(arr[mid] < x)
65+
{
66+
min = mid + 1;
67+
}
68+
else{
69+
return true;
70+
}
71+
}
72+
73+
return false;
74+
}
75+
public static void main(String[] args) {
76+
int[] a = arrRandom(10, 0, 30);
77+
mergesort(a, 0, 9); //归并排序
78+
System.out.print("\n");
79+
for(int in:a){
80+
System.out.print(in+" ");
81+
}
82+
Scanner scanner = new Scanner(System.in);
83+
int i ;
84+
System.out.print("\n请输入你要查找的数：");
85+
int x = scanner.nextInt();
86+
for( i = 0 ;i<a.length;i++){
87+
if(binarySearch(a, x -a[i], i+1, a.length -1)) //二分查找
88+
{
89+
System.out.print("存在: "+x+"="+a[i]+"+"+(x-a[i]));
90+
break;
91+
}
92+
}
93+
if(i == a.length){
94+
System.out.print("不存在");
95+
}
96+
97+
98+
}
99+
100+
101+
}

‎1/KthLargest.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
import java.util.Arrays;
2+
3+
public class KthLargest {
4+
private int[] a;
5+
private int[] b;
6+
public int find(int aLeft, int aRight, int bLeft, int bRight, int k) {
7+
int aMid = (aLeft + aRight) / 2;
8+
int bMid = (bLeft + bRight) / 2;
9+
if (aLeft > aRight)
10+
return b[bLeft + k - 1];
11+
if (bLeft > bRight)
12+
return a[aLeft + k - 1];
13+
if (a[aMid] <= b[bMid]) {
14+
if (k <= (aMid - aLeft) + (bMid - bLeft) + 1)
15+
return find(aLeft, aRight, bLeft, bMid - 1, k);
16+
else
17+
return find(aMid + 1, aRight, bLeft, bRight, k - (aMid - aLeft + 1));
18+
} else {
19+
if (k <= (aMid - aLeft) + (bMid - bLeft) + 1)
20+
return find(aLeft, aMid - 1, bLeft, bRight, k);
21+
else
22+
return find(aLeft, aRight, bMid + 1, bRight, k - (bMid - bLeft + 1));
23+
}
24+
}
25+
26+
public static void main(String[] args) {
27+
KthLargest kthLargest = new KthLargest();
28+
kthLargest.a = new int[] { 1, 4, 6,7,10};
29+
kthLargest.b = new int[] { 5, 8, 9 };
30+
System.out.println("a数组："+Arrays.toString(kthLargest.a));
31+
System.out.println("b数组："+Arrays.toString(kthLargest.b));
32+
System.out.println("待查值：5");
33+
System.out.println("第5个数为："+kthLargest.find(0, 4, 0, 2, 5));
34+
}
35+
}

‎1/PriorityQueue.java‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
public class PriorityQueue {
2+
final static int BaseLen = 15;
3+
final static int IncreaseLen = 10;
4+
int size = BaseLen;
5+
int length = 0;
6+
int[] arr = new int[BaseLen];
7+
8+
public PriorityQueue() {
9+
10+
}
11+
12+
public void insert(int key) {
13+
if (length + 1 > arr.length) {
14+
int[] temp = new int[length];
15+
for(int i = 0; i < length; ++i )
16+
temp[i] = arr[i];
17+
arr = new int[size = length+IncreaseLen];
18+
for(int i = 0; i < length; ++i )
19+
arr[i] = temp[i];
20+
}
21+
arr[length] = Integer.MIN_VALUE;
22+
length = length + 1;
23+
increaseKey(length, key);
24+
25+
}
26+
27+
public void increaseKey(int i, int key) {
28+
i = i - 1;
29+
if (key < arr[i])
30+
System.out.println("插入的数小于原来的数");
31+
arr[i] = key;
32+
int p = (i + 1) / 2 - 1; // 父节点
33+
while (i > 0 && arr[p] < arr[i]) {
34+
int t = arr[i];
35+
arr[i] = arr[p];
36+
arr[p] = t;
37+
i = p;
38+
p = (i + 1) / 2 - 1;
39+
}
40+
}
41+
42+
public int maximum() {
43+
if (length == 0) {
44+
System.out.println("队列中没有加入元素");
45+
return 0;
46+
}
47+
return arr[0];
48+
}
49+
50+
public int extractMax() {
51+
52+
if (length == 0) {
53+
System.out.println("队列中没有加入元素");
54+
return 0;
55+
}
56+
int max = arr[0];
57+
length--;
58+
arr[0] = Integer.MIN_VALUE;
59+
maxHeapIfy(1);
60+
return max;
61+
62+
}
63+
64+
public void maxHeapIfy(int i) {
65+
int l = 2 * i - 1; // left左节点
66+
int r = 2 * i;// 右节点
67+
i = i - 1;
68+
int largest = 0;
69+
if (l < arr.length && arr[l] > arr[i])
70+
largest = l;
71+
else
72+
largest = i;
73+
if (r < arr.length && arr[r] > arr[largest])
74+
largest = r;
75+
if (largest != i) {
76+
int t = arr[i];
77+
arr[i] = arr[largest];
78+
arr[largest] = t;
79+
maxHeapIfy(largest + 1);
80+
}
81+
82+
}
83+
84+
public static void main(String[] args) {
85+
PriorityQueue q = new PriorityQueue();
86+
System.out.println("插入队列的数字:12,3,4,8,13,20,16,15,22,17");
87+
q.insert(12);
88+
q.insert(3);
89+
q.insert(4);
90+
q.insert(8);
91+
q.insert(13);
92+
q.insert(20);
93+
q.insert(16);
94+
q.insert(15);
95+
q.insert(22);
96+
q.insert(17);
97+
System.out.println("最大值："+q.maximum());
98+
q.increaseKey(3, 30);
99+
System.out.println("在第3个位置插入30后的最大值："+q.maximum());
100+
System.out.println("取出最大值："+q.extractMax());
101+
System.out.println("取出后的最大值："+q.maximum());
102+
103+
}
104+
105+
}

‎1/QuickSort.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
public class QuickSort{
2+
3+
public static void main(String[] args) {
4+
5+
int[] a = { 0, 1, 7, 3, 8, 4, 5,2,2,4 };
6+
System.out.println("原数组：");
7+
for(int i:a){
8+
System.out.print(i+" ");
9+
}
10+
System.out.println("\n用快排排序后的数组：");
11+
quickSort(a,0,9);
12+
for(int i:a){
13+
System.out.print(i+" ");
14+
}
15+
16+
17+
18+
}
19+
20+
public static void quickSort(int[] a, int p, int r) {
21+
if (p < r) {
22+
int q = partition(a, p, r);
23+
quickSort(a, p, q - 1);
24+
quickSort(a, q + 1, r);
25+
26+
}
27+
28+
}
29+
30+
public static int partition(int[] a, int p, int r) {
31+
int x = a[r];
32+
int t = 0;
33+
int i = p -1 ;
34+
for (int j = p; j <= r; j++) {
35+
if(a[j] <= x){
36+
t = a[j];
37+
a[j] = a[i+1];
38+
a[i+1] = t;
39+
i++;
40+
}
41+
}
42+
43+
return i ;
44+
45+
}
46+
47+
}

‎2/DPShortestpath.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
public class DPShortestpath {
2+
public static final int MAX= 999999;
3+
4+
/**
5+
* 次算法用于计算特定结构图的最短路径
6+
* @param args
7+
*/
8+
public static void main(String[] args) {
9+
int[][] path = new int[16][16];
10+
for (int i = 0; i < 16; ++i) // 初始化
11+
for (int j = 0; j < 16; ++j)
12+
path[i][j] = MAX;
13+
path[0][1] = 5;
14+
path[0][2] = 3;
15+
path[1][3] = 1;
16+
path[1][4] = 3;
17+
path[1][5] = 6;
18+
path[2][4] = 8;
19+
path[2][5] = 7;
20+
path[2][6] = 6;
21+
path[3][7] = 6;
22+
path[3][8] = 8;
23+
path[4][7] = 3;
24+
path[4][8] = 5;
25+
path[5][8] = 3;
26+
path[5][9] = 3;
27+
path[6][8] = 8;
28+
path[6][9] = 4;
29+
path[7][10] = 2;
30+
path[7][11] = 2;
31+
path[8][11] = 1;
32+
path[8][12] = 2;
33+
path[9][11] = 3;
34+
path[9][12] = 3;
35+
path[10][13] = 3;
36+
path[10][14] = 5;
37+
path[11][13] = 5;
38+
path[11][14] = 2;
39+
path[12][13] = 6;
40+
path[12][14] = 6;
41+
path[13][15] = 4;
42+
path[14][15] = 3;
43+
int[][] f = { { 0, 0 }, { 1, 2 }, { 3, 6 }, { 7, 9 }, { 10, 12 }, { 13, 14 }, { 15, 15 } }; // 分层情况
44+
int[] d = new int[16]; // 记录到源点最小路径
45+
int[] front = new int[16]; // 记录前驱
46+
d[0] = 0;
47+
48+
for (int i = 1; i < 16; ++i) { // 初始化俩点直接的路径为无穷
49+
d[i] =MAX;
50+
}
51+
for (int i = 0; i < 6; ++i)
52+
for (int j = f[i][0]; j <= f[i][1]; ++j)
53+
for (int k = f[i + 1][0]; k <= f[i + 1][1]; ++k) {
54+
if (d[k] > d[j] + path[j][k]) {
55+
d[k] = d[j] + path[j][k];
56+
front[k] = j; // 记录最短路径的前驱
57+
}
58+
}
59+
System.out.println("The shortest path from 0 to 15:" + d[15]);
60+
System.out.print("The paths is:");
61+
printPath(front, 15);
62+
}
63+
64+
public static void printPath(int[] front, int forward) {
65+
if (forward == 0)
66+
return;
67+
int i = front[forward];
68+
printPath(front, i);
69+
System.out.print(forward + " ");
70+
}
71+
72+
}

0 commit comments

Comments
 (0)