Skip to content

Commit 96dd311

Browse files
heyucoolheyucool
authored
Merge pull request onlyliuxin#6 from runMark/master
第一次作业
2 parents 26df313 + 37595ce commit 96dd311

File tree

17 files changed

+902
-0
lines changed

17 files changed

+902
-0
lines changed

‎group14/676615845/algo/pom.xml

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>com.mark</groupId>
8+
<artifactId>algo</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
11+
<dependencies>
12+
<dependency>
13+
<groupId>junit</groupId>
14+
<artifactId>junit</artifactId>
15+
<version>4.12</version>
16+
</dependency>
17+
</dependencies>
18+
</project>

‎group14/676615845/algo/src/main/java/algo/BinarySearch.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package algo;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
/**
8+
* Created by mark on 17/2/23.
9+
*/
10+
public class BinarySearch {
11+
12+
public static int rank(int key, int[] a) {
13+
List list = new ArrayList();
14+
list = new LinkedList();
15+
return -1;
16+
}
17+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/Array.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Created by mark on 17/2/24.
7+
*/
8+
public class Array {
9+
10+
public static Object[] grow(Object[] src, int size) {
11+
return Arrays.copyOf(src, src.length + size);
12+
// Object[] target = new Object[src.length + size];
13+
// System.arraycopy(src, 0, target, 0, src.length);
14+
15+
}
16+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.coding.basic;
2+
3+
public class ArrayList implements List {
4+
5+
private int size; // ArrayList 中的实际元素个数
6+
private Object[] elementData;
7+
8+
public ArrayList() {
9+
size = 0;
10+
elementData = new Object[100];
11+
}
12+
13+
public void add(Object o){
14+
if (size >= elementData.length) {
15+
elementData = Array.grow(elementData, 100);
16+
}
17+
elementData[size++] = o;
18+
}
19+
20+
public void add(int index, Object o){
21+
if (size >= elementData.length) {
22+
elementData = Array.grow(elementData, 100);
23+
}
24+
25+
if (index > size || index < 0) throw new ArrayIndexOutOfBoundsException();
26+
27+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
28+
elementData[index] = o;
29+
size++;
30+
}
31+
32+
public Object get(int index){
33+
if (index > size) throw new ArrayIndexOutOfBoundsException();
34+
return elementData[index];
35+
}
36+
37+
public Object remove(int index){
38+
39+
if (index >= size || index < 0) throw new ArrayIndexOutOfBoundsException();
40+
41+
Object result = elementData[index];
42+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
43+
elementData[--size] = null;
44+
return result;
45+
}
46+
47+
public int size() {
48+
return size;
49+
}
50+
51+
public Iterator iterator(){
52+
53+
return new Iterator() {
54+
55+
private int next = 0; // 下一个返回元素所在的位置
56+
57+
public boolean hasNext() {
58+
return next < size;
59+
}
60+
61+
public Object next() {
62+
if (!hasNext()) throw new ArrayIndexOutOfBoundsException();
63+
return elementData[next++];
64+
}
65+
66+
public Object remove() {
67+
if (next <= 0) throw new IllegalStateException();
68+
return ArrayList.this.remove(--next);
69+
}
70+
};
71+
}
72+
73+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/BinaryTreeNode.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode implements Comparable {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
13+
public void setData(Object data) {
14+
this.data = data;
15+
}
16+
17+
public BinaryTreeNode getLeft() {
18+
return left;
19+
}
20+
21+
public void setLeft(BinaryTreeNode left) {
22+
this.left = left;
23+
}
24+
25+
public BinaryTreeNode getRight() {
26+
return right;
27+
}
28+
29+
public void setRight(BinaryTreeNode right) {
30+
this.right = right;
31+
}
32+
33+
public BinaryTreeNode insert(Object o){
34+
return null;
35+
}
36+
37+
public int compareTo(Object obj) {
38+
if (obj == null || obj.getClass() != Integer.class) throw new IllegalArgumentException();
39+
return Integer.compare(((Integer) data).intValue(), ((Integer) obj).intValue());
40+
}
41+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package com.coding.basic;
2+
3+
public interface Iterator {
4+
boolean hasNext();
5+
Object next();
6+
Object remove();
7+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/LinkedList.java

Lines changed: 164 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,164 @@
1+
package com.coding.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node first = null;
6+
private Node last = null;
7+
private int size = 0;
8+
9+
public void add(Object o){
10+
Node node = new Node(o);
11+
if (first == null) {
12+
first = node;
13+
} else {
14+
last.next = node;
15+
node.prev = last;
16+
}
17+
last = node;
18+
size++;
19+
}
20+
21+
public void add(int index , Object o) {
22+
if (index < 0 || index > size) throw new ArrayIndexOutOfBoundsException();
23+
24+
Node node = new Node(o);
25+
26+
if (first == null) {
27+
first = node;
28+
last = node;
29+
} else {
30+
if (index == 0) {
31+
node.next = first;
32+
first.prev = node;
33+
first = node;
34+
} else if (index == size) {
35+
last.next = node;
36+
node.prev = last;
37+
last = node;
38+
} else {
39+
Node temp = first;
40+
while (--index > 0) {
41+
temp = temp.next;
42+
}
43+
node.next = temp.next;
44+
temp.next.prev = node;
45+
temp.next = node;
46+
node.prev = temp;
47+
}
48+
}
49+
size++;
50+
}
51+
public Object get(int index){
52+
if (index < 0 || index > size - 1) throw new ArrayIndexOutOfBoundsException();
53+
Node node = first;
54+
while (index-- > 0) {
55+
node = node.next;
56+
}
57+
return node.data;
58+
}
59+
60+
public Object remove(int index){
61+
if (index < 0 || index >= size) throw new ArrayIndexOutOfBoundsException();
62+
63+
Node node = null;
64+
if (index == 0) {
65+
node = first;
66+
if (size == 1) {
67+
first = null;
68+
last = null;
69+
} else {
70+
first = first.next;
71+
first.prev = null;
72+
}
73+
} else if (index == size - 1) {
74+
node = last;
75+
last = last.prev;
76+
last.next = null;
77+
} else {
78+
node = first;
79+
Node temp = null;
80+
while (index-- > 0) {
81+
node = node.next;
82+
}
83+
temp = node.prev;
84+
temp.next = node.next;
85+
node.next.prev = temp;
86+
}
87+
size--;
88+
return node.data;
89+
}
90+
91+
public int size(){
92+
return size;
93+
}
94+
95+
public void addFirst(Object obj){
96+
add(0, obj);
97+
}
98+
99+
public void addLast(Object obj){
100+
add(size, obj);
101+
}
102+
103+
public Object removeFirst(){
104+
return remove(0);
105+
}
106+
107+
public Object removeLast(){
108+
return remove(size - 1);
109+
}
110+
111+
public Iterator iterator(){
112+
113+
if (first == null || last == null) throw new IllegalStateException();
114+
115+
return new InnerIterator();
116+
}
117+
118+
private class InnerIterator implements Iterator {
119+
120+
private Node nextNode = first;
121+
122+
public boolean hasNext() {
123+
return nextNode != null;
124+
}
125+
126+
public Object next() {
127+
if (!hasNext()) throw new ArrayIndexOutOfBoundsException();
128+
Node node = nextNode;
129+
nextNode = nextNode.next;
130+
return node.data;
131+
}
132+
133+
public Object remove() {
134+
if (nextNode == first) throw new IllegalStateException();
135+
136+
Node node = nextNode.prev;
137+
if (nextNode == first.next) {
138+
first = nextNode;
139+
first.prev = null;
140+
} else if (nextNode == null) {
141+
node = last;
142+
last = last.prev;
143+
last.next = null;
144+
} else {
145+
node.prev = node.next;
146+
node.next.prev = node.prev;
147+
}
148+
return node.data;
149+
}
150+
}
151+
152+
private static class Node{
153+
154+
Object data;
155+
Node next;
156+
Node prev;
157+
158+
public Node(Object data) {
159+
this.data = data;
160+
next = null;
161+
prev = null;
162+
}
163+
}
164+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.basic;
2+
3+
public interface List {
4+
void add(Object o);
5+
void add(int index, Object o);
6+
Object get(int index);
7+
Object remove(int index);
8+
int size();
9+
}

‎group14/676615845/algo/src/main/java/com/coding/basic/Queue.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.coding.basic;
2+
3+
public class Queue {
4+
5+
private LinkedList linkedList = new LinkedList();
6+
7+
public void enQueue(Object o){
8+
linkedList.add(o);
9+
}
10+
11+
public Object deQueue(){
12+
return linkedList.removeFirst();
13+
}
14+
15+
public boolean isEmpty(){
16+
return linkedList.size() == 0;
17+
}
18+
19+
public int size(){
20+
return linkedList.size();
21+
}
22+
}

0 commit comments

Comments
 (0)