Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbb3eb2b

Browse files
committed
Arrange the code.
1 parent7c9819f commitbb3eb2b

15 files changed

+170
-101
lines changed

‎Flatten.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
packageAlgorithms;
22
importjava.util.Stack;
33

4+
importAlgorithms.tree.TreeNode;
5+
46

57

68
publicclassFlatten {

‎InOrderTraversal.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22
importjava.util.ArrayList;
33
importjava.util.Stack;
44

5+
importAlgorithms.tree.TreeNode;
6+
57

68
publicclassInOrderTraversal {
79
publicArrayList<Integer>inorderTraversal(TreeNoderoot) {

‎IsSymmetric.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
importjava.util.ArrayDeque;
44

5+
importAlgorithms.tree.TreeNode;
6+
57
publicclassIsSymmetric {
68
publicbooleanisSymmetric(TreeNoderoot) {
79
if (root ==null) {

‎Max_path_BinaryTree.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
packageAlgorithms;
22
importjava.util.ArrayList;
33

4+
importAlgorithms.tree.TreeNode;
5+
46

57
publicclassMax_path_BinaryTree {
68
publicstaticvoidmain(Stringargs[]){

‎Populate2.java

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,7 @@
11
packageAlgorithms;
2+
3+
importAlgorithms.tree.TreeLinkNode;
4+
25
publicclassPopulate2 {
36
publicstaticvoidmain(String[]args) {
47
TreeLinkNoderoot =newTreeLinkNode(2);

‎Recover.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
packageAlgorithms;
22

3+
importAlgorithms.tree.TreeNode;
4+
35
publicclassRecover {
46
privateTreeNodebig =null;
57
privateTreeNodesmall =null;

‎ZigzagLevelOrder.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44
importjava.util.Queue;
55
importjava.util.Stack;
66

7+
importAlgorithms.tree.TreeNode;
8+
79

810
publicclassZigzagLevelOrder {
911
publicArrayList<ArrayList<Integer>>zigzagLevelOrder(TreeNoderoot) {

‎string/MinCut.javarenamed to‎dp/MinCut.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
packageAlgorithms.string;
1+
packageAlgorithms.dp;
22

33
publicclassMinCut {
44
publicintminCut(Strings) {

‎sort/QuickSort.java

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,149 @@
1+
packageAlgorithms.sort;
2+
3+
/*********************************************************
4+
*
5+
* 08-722 Data Structures for Application Programmers
6+
* Lab 5 Comparing MergeSort with QuickSort
7+
*
8+
* A simple QuickSort implementation
9+
*
10+
*********************************************************/
11+
12+
importjava.util.*;
13+
14+
publicclassQuickSort {
15+
//private static final int SIZE = 100000;
16+
privatestaticfinalintSIZE =100000;
17+
privatestaticRandomrand =newRandom();
18+
19+
publicstaticvoidmain(Stringargs[]) {
20+
int[]array =newint[SIZE];
21+
22+
for (inti =0;i <SIZE;i++)
23+
array[i] =rand.nextInt();
24+
25+
// reversely ordered
26+
/*
27+
for(int i=0;i<SIZE; i++) array[i] = SIZE - i;
28+
*/
29+
30+
quickSort(array);
31+
32+
// to make sure sorting works.
33+
// add "-ea" vm argument
34+
assertisSorted(array);
35+
36+
System.out.println(isSorted(array));
37+
//printArray(array);
38+
}
39+
40+
publicstaticvoidprintArray(int[]arr) {
41+
System.out.println();
42+
for(inti:arr) {
43+
System.out.println(i +" ");
44+
}
45+
}
46+
47+
publicstaticvoidquickSort(int[]arr) {
48+
recQuickSort(arr,0,arr.length -1);
49+
}
50+
51+
privatestaticvoidrecQuickSort(int[]arr,intleft,intright) {
52+
// Just the input parameter.
53+
if (arr ==null ||left >=right) {
54+
return;
55+
}
56+
57+
// we just set the right node to be pivot.
58+
intpivPosition =partition(arr,left,right,arr[right]);
59+
60+
recQuickSort(arr,left,pivPosition -1);
61+
recQuickSort(arr,pivPosition +1,right);
62+
}
63+
64+
// partition the array and return the new pivot position.
65+
privatestaticintpartition(int[]arr,intleft,intright,intpivot) {
66+
intlen =arr.length;
67+
68+
// set the pivot.
69+
intl =left ;
70+
intr =right -1;
71+
72+
/*
73+
example:
74+
let 4 to be the pivot.
75+
76+
(1) At the beginning:
77+
2 8 7 1 3 5 6 4
78+
i j
79+
80+
81+
(2) After the first while loop:
82+
2 8 7 1 3 5 6 4
83+
i j
84+
85+
(3) swap them, then continue to move i and j:
86+
2 3 7 1 8 5 6 4
87+
i j
88+
89+
(3) swap them, then continue to move i and j:
90+
2 3 1 7 8 5 6 4
91+
j i pivo
92+
93+
(4) swap the left and the pivo.
94+
2 3 1 7 8 5 6 4
95+
j i pivo
96+
97+
*/
98+
99+
while (true) {
100+
// Find the first element which does not fullfill the rule
101+
// When l move to the pivot, it will not move again because arr[l] == pivot.
102+
while (arr[l] <pivot) {
103+
l++;
104+
}
105+
106+
// Find the first element which does not fullfill the rule
107+
while (r >0 &&arr[r] >pivot) {
108+
r--;
109+
}
110+
111+
// If r <= l, means that all the elements is in the right place.
112+
if (r <=l) {
113+
break;
114+
}
115+
116+
// Swap the first two elements that does not fit the rule.
117+
swap(arr,r,l);
118+
}
119+
120+
// The l pointer point to the first element which is bigger than the pvio.
121+
// So we can put the pvio just here. Because put a big one in the last will not change the rule that:
122+
// all the smaller one is in the left and the right one is in the right.
123+
swap(arr,l,right);
124+
125+
returnl;
126+
}
127+
128+
// private helper method to swap two values in an array
129+
privatestaticvoidswap(int[]arr,intdex1,intdex2) {
130+
inttmp =arr[dex1];
131+
arr[dex1] =arr[dex2];
132+
arr[dex2] =tmp;
133+
}
134+
135+
/**********************************************************
136+
* Check if array is sorted. A simple debugging tool
137+
**********************************************************/
138+
privatestaticbooleanisSorted(int[]array) {
139+
returnisSorted(array,0,array.length -1);
140+
}
141+
142+
privatestaticbooleanisSorted(int[]array,intlo,inthi) {
143+
for (inti =lo +1;i <=hi;i++)
144+
if (array[i] <array[i -1])
145+
returnfalse;
146+
returntrue;
147+
}
148+
149+
}

‎tree/LCA.java

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
packageAlgorithms.tree;
22

3-
importAlgorithms.TreeNode;
43

54

65
/**

‎tree/Level_Order.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,6 @@
33
importjava.util.ArrayList;
44
importjava.util.Queue;
55

6-
importAlgorithms.TreeNode;
7-
86
publicclassLevel_Order {
97

108

‎tree/PostOrder.java

Lines changed: 0 additions & 93 deletions
This file was deleted.

‎TreeDemo.javarenamed to‎tree/TreeDemo.java

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
packageAlgorithms;
1+
@@ -1,1260 +0,0@@
2+
packageAlgorithms.tree;
23

34
importjava.util.ArrayList;
45
importjava.util.Iterator;
@@ -1257,4 +1258,4 @@ static int[] findLongest2Help(TreeNode root, int[] maxVal) {
12571258

12581259
returnret;
12591260
}
1260-
}
1261+
}

‎TreeLinkNode.javarenamed to‎tree/TreeLinkNode.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
packageAlgorithms;
1+
packageAlgorithms.tree;
22
publicclassTreeLinkNode {
33
intval;
44
TreeLinkNodeleft,right,next;

‎TreeNode.javarenamed to‎tree/TreeNode.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
packageAlgorithms;
1+
packageAlgorithms.tree;
22

33
publicclassTreeNode {
44
publicintval;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp