Skip to content

Commit 22e1be0

Browse files
wizardzhang2017wizardzhang2017
authored
Merge pull request onlyliuxin#53 from onlyliuxin/master
同步
2 parents 6121f13 + ccdb524 commit 22e1be0

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

54 files changed

+1701
-137
lines changed

‎liuxin/data-structure/answer/src/com/coding/basic/queue/CircleQueue.java

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,33 @@
11
package com.coding.basic.queue;
22

3-
public class CircleQueue {
3+
public class CircleQueue <E> {
4+
5+
private final static int DEFAULT_SIZE = 10;
6+
7+
//用数组来保存循环队列的元素
8+
private Object[] elementData = new Object[DEFAULT_SIZE] ;
9+
10+
//队头
11+
private int front = 0;
12+
//队尾
13+
private int rear = 0;
14+
15+
public boolean isEmpty() {
16+
return false;
17+
18+
}
419

20+
public int size() {
21+
return -1;
22+
}
23+
24+
25+
26+
public void enQueue(E data) {
27+
28+
}
29+
30+
public E deQueue() {
31+
return null;
32+
}
533
}

‎liuxin/data-structure/answer/src/com/coding/basic/queue/Josephus.java

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,15 +5,35 @@
55

66
/**
77
* 用Queue来实现Josephus问题
8-
* 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数： N个人围成一圈（位置记为0到N-1）， 并且从第一个人报数， 报到M的人会被杀死， 知道最后一个人留下来
8+
* 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数： N个人围成一圈（位置记为0到N-1）， 并且从第一个人报数， 报到M的人会被杀死， 直到最后一个人留下来
99
* @author liuxin
1010
*
1111
*/
1212
public class Josephus {
1313

1414
public static List<Integer> execute(int n, int m){
1515

16-
return null;
16+
Queue<Integer> queue = new Queue<Integer>();
17+
for (int i = 0; i < n; i++){
18+
queue.enQueue(i);
19+
}
20+
21+
List<Integer> result = new ArrayList<Integer>();
22+
int i = 0;
23+
24+
while (!queue.isEmpty()) {
25+
26+
int x = queue.deQueue();
27+
28+
if (++i % m == 0){
29+
result.add(x);
30+
} else{
31+
queue.enQueue(x);
32+
}
33+
}
34+
35+
36+
return result;
1737
}
1838

1939
}

‎liuxin/data-structure/answer/src/com/coding/basic/queue/QueueWithTwoStacks.java

Lines changed: 20 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
package com.coding.basic.queue;
22

3+
import java.util.NoSuchElementException;
34
import java.util.Stack;
45

56
public class QueueWithTwoStacks<E> {
6-
private Stack<E> stack1;
7+
private Stack<E> stack1;
78
private Stack<E> stack2;
89

910

@@ -13,29 +14,42 @@ public QueueWithTwoStacks() {
1314
}
1415

1516

16-
17+
private void moveStack1ToStack2() {
18+
while (!stack1.isEmpty()){
19+
stack2.push(stack1.pop());
20+
}
21+
22+
}
1723

1824

1925
public boolean isEmpty() {
20-
return false;
26+
return stack1.isEmpty() && stack2.isEmpty();
2127
}
2228

2329

2430

2531
public int size() {
26-
return -1;
32+
return stack1.size() + stack2.size();
2733
}
2834

2935

3036

3137
public void enQueue(E item) {
32-
38+
stack1.push(item);
3339
}
3440

3541
public E deQueue() {
36-
return null;
42+
if (isEmpty()) {
43+
throw new NoSuchElementException("Queue is empty");
44+
}
45+
if (stack2.isEmpty()) {
46+
moveStack1ToStack2();
47+
}
48+
49+
return stack2.pop();
3750
}
3851

3952

53+
4054
}
4155

‎liuxin/data-structure/answer/src/com/coding/basic/stack/Tail.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package com.coding.basic.stack;
2+
3+
public class Tail {
4+
5+
}

‎liuxin/data-structure/answer/src/com/coding/basic/stack/expr/InfixExpr.java

Lines changed: 8 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -25,22 +25,16 @@ public float evaluate() {
2525

2626
if (token.isOperator()){
2727

28-
if(opStack.isEmpty()){
28+
while(!opStack.isEmpty()
29+
&& !token.hasHigherPriority(opStack.peek())){
30+
Token prevOperator = opStack.pop();
31+
Float f2 = numStack.pop();
32+
Float f1 = numStack.pop();
33+
Float result = calculate(prevOperator.toString(), f1,f2);
34+
numStack.push(result);
2935

30-
opStack.push(token);
31-
} else{
32-
33-
while(!opStack.isEmpty()
34-
&& !token.hasHigherPriority(opStack.peek())){
35-
Token prevOperator = opStack.pop();
36-
Float f2 = numStack.pop();
37-
Float f1 = numStack.pop();
38-
Float result = calculate(prevOperator.toString(), f1,f2);
39-
numStack.push(result);
40-
41-
}
42-
opStack.push(token);
4336
}
37+
opStack.push(token);
4438
}
4539
if(token.isNumber()){
4640
numStack.push(new Float(token.getIntValue()));

‎liuxin/data-structure/answer/src/com/coding/basic/stack/expr/InfixToPostfix.java

Lines changed: 33 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,43 @@
11
package com.coding.basic.stack.expr;
22

3+
import java.util.ArrayList;
34
import java.util.List;
5+
import java.util.Stack;
46

57
public class InfixToPostfix {
6-
8+
79
public static List<Token> convert(String expr) {
8-
return null;
10+
List<Token> inFixTokens = new TokenParser().parse(expr);
11+
12+
List<Token> postFixTokens = new ArrayList<>();
13+
14+
Stack<Token> opStack = new Stack<Token>();
15+
for(Token token : inFixTokens){
16+
17+
if(token.isOperator()){
18+
19+
while(!opStack.isEmpty()
20+
&& !token.hasHigherPriority(opStack.peek())){
21+
postFixTokens.add(opStack.pop());
22+
23+
}
24+
opStack.push(token);
25+
26+
}
27+
if(token.isNumber()){
28+
29+
postFixTokens.add(token);
30+
31+
}
32+
}
33+
34+
while(!opStack.isEmpty()){
35+
postFixTokens.add(opStack.pop());
36+
}
37+
38+
return postFixTokens;
939
}
10-
40+
1141

1242

1343
}

‎liuxin/data-structure/answer/src/com/coding/basic/stack/expr/InfixToPostfixTest.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.coding.basic.stack.expr;
2+
3+
import java.util.List;
4+
5+
import org.junit.After;
6+
import org.junit.Assert;
7+
import org.junit.Before;
8+
import org.junit.Test;
9+
10+
11+
12+
public class InfixToPostfixTest {
13+
14+
@Before
15+
public void setUp() throws Exception {
16+
}
17+
18+
@After
19+
public void tearDown() throws Exception {
20+
}
21+
22+
@Test
23+
public void testConvert() {
24+
{
25+
List<Token> tokens = InfixToPostfix.convert("2+3");
26+
Assert.assertEquals("[2, 3, +]", tokens.toString());
27+
}
28+
{
29+
30+
List<Token> tokens = InfixToPostfix.convert("2+3*4");
31+
Assert.assertEquals("[2, 3, 4, *, +]", tokens.toString());
32+
}
33+
34+
{
35+
36+
List<Token> tokens = InfixToPostfix.convert("2-3*4+5");
37+
Assert.assertEquals("[2, 3, 4, *, -, 5, +]", tokens.toString());
38+
}
39+
}
40+
41+
}

‎liuxin/data-structure/assignment/src/com/coding/basic/queue/CircleQueue.java

Lines changed: 35 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,39 @@
11
package com.coding.basic.queue;
22

3-
public class CircleQueue {
3+
/**
4+
* 用数组实现循环队列
5+
* @author liuxin
6+
*
7+
* @param <E>
8+
*/
9+
public class CircleQueue <E> {
10+
11+
private final static int DEFAULT_SIZE = 10;
12+
13+
//用数组来保存循环队列的元素
14+
private Object[] elementData = new Object[DEFAULT_SIZE] ;
15+
16+
//队头
17+
private int front = 0;
18+
//队尾
19+
private int rear = 0;
20+
21+
public boolean isEmpty() {
22+
return false;
23+
24+
}
425

26+
public int size() {
27+
return -1;
28+
}
29+
30+
31+
32+
public void enQueue(E data) {
33+
34+
}
35+
36+
public E deQueue() {
37+
return null;
38+
}
539
}

‎liuxin/data-structure/assignment/src/com/coding/basic/queue/Josephus.java

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,17 @@
11
package com.coding.basic.queue;
22

3-
import java.util.ArrayList;
43
import java.util.List;
54

65
/**
76
* 用Queue来实现Josephus问题
8-
* 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数： N个人围成一圈（位置记为0到N-1）， 并且从第一个人报数， 报到M的人会被杀死， 知道最后一个人留下来
7+
* 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数： N个人围成一圈（位置记为0到N-1）， 并且从第一个人报数， 报到M的人会被杀死， 直到最后一个人留下来
8+
* 该方法返回一个List， 包含了被杀死人的次序
99
* @author liuxin
1010
*
1111
*/
1212
public class Josephus {
1313

14-
public static List<Integer> execute(int n, int m){
15-
14+
public static List<Integer> execute(int n, int m){
1615
return null;
1716
}
1817

‎liuxin/data-structure/assignment/src/com/coding/basic/queue/QueueWithTwoStacks.java

Lines changed: 11 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,14 @@
22

33
import java.util.Stack;
44

5+
/**
6+
* 用两个栈来实现一个队列
7+
* @author liuxin
8+
*
9+
* @param <E>
10+
*/
511
public class QueueWithTwoStacks<E> {
6-
private Stack<E> stack1;
12+
private Stack<E> stack1;
713
private Stack<E> stack2;
814

915

@@ -13,16 +19,16 @@ public QueueWithTwoStacks() {
1319
}
1420

1521

16-
22+
1723

1824
public boolean isEmpty() {
19-
return false;
25+
return false;
2026
}
2127

2228

2329

2430
public int size() {
25-
return -1;
31+
return -1;
2632
}
2733

2834

@@ -36,5 +42,6 @@ public E deQueue() {
3642
}
3743

3844

45+
3946
}
4047

‎liuxin/mini-jvm/answer/src/com/coderising/jvm/attr/CodeAttr.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -102,7 +102,7 @@ public String toString(ConstantPool pool){
102102
StringBuilder buffer = new StringBuilder();
103103
//buffer.append("Code:").append(code).append("\n");
104104
for(int i=0;i<cmds.length;i++){
105-
buffer.append(cmds[i].toString(pool)).append("\n");
105+
buffer.append(cmds[i].toString()).append("\n");
106106
}
107107
buffer.append("\n");
108108
buffer.append(this.lineNumTable.toString());

‎liuxin/mini-jvm/answer/src/com/coderising/jvm/clz/ClassFile.java

Lines changed: 1 addition & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -106,15 +106,6 @@ public Method getMethod(String methodName, String paramAndReturnType){
106106
return null;
107107
}
108108
public Method getMainMethod(){
109-
for(Method m :methods){
110-
int nameIndex = m.getNameIndex();
111-
int descIndex = m.getDescriptorIndex();
112-
String name = this.getConstantPool().getUTF8String(nameIndex);
113-
String desc = this.getConstantPool().getUTF8String(descIndex);
114-
if(name.equals("main") && desc.equals("([Ljava/lang/String;)V")){
115-
return m;
116-
}
117-
}
118-
return null;
109+
return getMethod("main","([Ljava/lang/String;)V");
119110
}
120111
}

0 commit comments

Comments
 (0)