Skip to content

Commit 14ca1d4

Browse files
gjgb2312-maxgjgb2312-max
committed
修改项目目录结构
1 parent d3da1d5 commit 14ca1d4

8 files changed

Lines changed: 279 additions & 33 deletions

File tree

‎algorithms/datastructure/src/main/java/cn/lastwhisper/stack/ArrayStackDemo.java‎

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -52,8 +52,7 @@ public int pop() {
5252
if (n > 0 && n == (arr.length / 4)) {
5353
resize(n / 2);
5454
}
55-
int data = arr[--n];
56-
return data;
55+
return arr[--n];
5756
}
5857
// 查看栈顶元素
5958
public int peek(){
@@ -69,9 +68,7 @@ public int size() {
6968
// resize
7069
public void resize(int maxSize) {
7170
int[] newArr = new int[maxSize];
72-
for (int i = 0; i < size(); i++) {
73-
newArr[i] = arr[i];
74-
}
71+
if (size() >= 0) System.arraycopy(arr, 0, newArr, 0, size());
7572
this.arr = newArr;
7673
}
7774
}

‎algorithms/datastructure/src/main/java/cn/lastwhisper/stack/InCalculator.java‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,11 +53,11 @@ public static void main(String[] args) {
5353
keepNum += ch - 48;
5454
// ch是否是最后一个字符
5555
if (index == expression.length() - 1) {
56-
numStack.push(Integer.valueOf(keepNum));
56+
numStack.push(Integer.parseInt(keepNum));
5757
} else {
5858
// 如果后一位是运算符，则将当前keepNum入栈
5959
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
60-
numStack.push(Integer.valueOf(keepNum));
60+
numStack.push(Integer.parseInt(keepNum));
6161
// 每次清空多位数
6262
keepNum = "";
6363
}
@@ -104,8 +104,7 @@ public int pop() {
104104
if (n > 0 && n == (arr.length / 4)) {
105105
resize(arr.length / 2);
106106
}
107-
int data = arr[--n];
108-
return data;
107+
return arr[--n];
109108
}
110109

111110
/**

‎algorithms/leetcode/linkedlist/src/main/java/cn/lastwhisper/leetcode/linkedlist/两两交换链表中的节点_24_中等/Solution1.java‎

Lines changed: 13 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -17,29 +17,22 @@ class Solution1 {
1717
* 空间复杂度：
1818
*/
1919
public ListNode swapPairs(ListNode head) {
20-
ListNode lastTail = head;
21-
ListNode rHead = head.next;
2220

23-
ListNode current = head;
24-
ListNode next ;
25-
ListNode afterNext ;
26-
27-
while (current != null) {
28-
// 后移
29-
next = current.next;
30-
afterNext = current.next.next;
31-
32-
// 反转
33-
next.next = current;
34-
if(afterNext!=null){
35-
lastTail.next = afterNext.next;
36-
}
37-
lastTail = afterNext;
38-
39-
current = afterNext;
21+
ListNode dummyHead = new ListNode(0);
22+
dummyHead.next = head;
23+
24+
ListNode p = dummyHead;
25+
while(p.next != null && p.next.next != null ){
26+
ListNode node1 = p.next;
27+
ListNode node2 = node1.next;
28+
ListNode next = node2.next;
29+
node2.next = node1;
30+
node1.next = next;
31+
p.next = node2;
32+
p = node1;
4033
}
4134

42-
return rHead;
35+
return dummyHead.next;
4336
}
4437

4538
public static void main(String[] args) {

‎algorithms/leetcode/readme.md‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -31,12 +31,12 @@
3131
| 5-1 链表，在节点间穿针引线 Reverse Linked List | ~~206~~ | ~~*92~~ |
3232
| 5-2 测试你的链表程序 | ~~206~~ | ~~83~~ ~~86~~ ~~328~~ ~~2 445~~ |
3333
| 5-3 设立链表的虚拟头结点 Remove Linked List Elements | ~~203~~ | ~~82~~ ~~*21(递归)~~ |
34-
| 5-4 复杂的穿针引线 Swap Nodes in Pairs | 24 | 25 147 148 |
34+
| 5-4 复杂的穿针引线 Swap Nodes in Pairs | ~~*24~~ | 25 147 148 |
3535
| 5-5 不仅仅是穿针引线 Delete Node in a Linked List | ~~237~~ | [无] |
36-
| 5-6 链表与双指针 Remove Nth Node Form End of List | ~~19~~ | 61 143 ~~234~~ |
37-
| 额外刷题 | ~~*160~~ | |
36+
| 5-6 链表与双指针 Remove Nth Node Form End of List | ~~19~~ | 61 ~~143 234~~ |
37+
| 额外刷题 | ~~*160~~ | ~~876~~ |
3838
| **第六章 栈、队列、优先队列** | | |
39-
| 6-1 栈的基础应用 Valid Parentheses | 20 | 150 71 |
39+
| 6-1 栈的基础应用 Valid Parentheses | ~~20~~ | ~~150 71~~ |
4040
| 6-2 栈和递归的紧密关系 Binary Tree Preorder, Inorder and Postorder Traversal | 144 94 145 | [无] |
4141
| 6-3 运用栈模拟递归 | 144 94 145 | 341 |
4242
| 6-4 队列的典型应用 Binary Tree Level Order Traversal | 102 | 107 103 199 346 |

‎algorithms/leetcode/stackqueue/src/main/java/cn/lastwhisper/leetcode/stackqueue/有效的括号_20_简单/Solution1.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package cn.lastwhisper.leetcode.stackqueue.有效的括号_20_简单;
2+
3+
import java.util.Stack;
4+
5+
class Solution1 {
6+
/**
7+
* 题目地址：https://leetcode-cn.com/problems/valid-parentheses/
8+
* -------------------------------------------------------------------
9+
* 思考：
10+
* 1.括号闭合长度肯定是偶数
11+
* 2.空字符串可被认为是有效字符串
12+
* 3.左括号必须用相同类型的右括号闭合
13+
* 4.左括号必须以正确的顺序闭合
14+
* 5.右括号可以出现在前面
15+
* -------------------------------------------------------------------
16+
* 思路：
17+
* -------------------------------------------------------------------
18+
* 时间复杂度：O(n)
19+
* 空间复杂度：O(1)
20+
*/
21+
public boolean isValid(String s) {
22+
//if ("".equals(s)) {
23+
// return true;
24+
//}
25+
if (s.length() % 2 != 0) {
26+
return false;
27+
}
28+
29+
Stack<Character> stack = new Stack<>();
30+
for (int i = 0; i < s.length(); i++) {
31+
char c = s.charAt(i);
32+
if (c == '(' || c == '{' || c == '[') {
33+
stack.push(c);
34+
} else {
35+
// "})"
36+
if (stack.empty()) {
37+
return false;
38+
}
39+
if (!match(stack.pop(), c)) {
40+
return false;
41+
}
42+
}
43+
}
44+
// 两种情况""、"(("
45+
return stack.empty();
46+
}
47+
48+
/**
49+
* 左右括号是否配对
50+
*/
51+
public boolean match(char left, char right) {
52+
if (left == '(') {
53+
return right == ')';
54+
} else if (left == '{') {
55+
return right == '}';
56+
} else if (left == '[') {
57+
return right == ']';
58+
}
59+
return false;
60+
}
61+
62+
public static void main(String[] args) {
63+
//String s = "{[]}";
64+
//String s = "()[]{}";
65+
//String s = "((";
66+
//String s = "}}";
67+
String s = "";
68+
System.out.println(new Solution1().isValid(s));
69+
}
70+
}

‎algorithms/leetcode/stackqueue/src/main/java/cn/lastwhisper/leetcode/stackqueue/简化路径_71_中等/Solution1.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package cn.lastwhisper.leetcode.stackqueue.简化路径_71_中等;
2+
3+
import java.util.Stack;
4+
5+
class Solution1 {
6+
/**
7+
* 题目地址：https://leetcode-cn.com/problems/simplify-path/
8+
* -------------------------------------------------------------------
9+
* 思考：
10+
* -------------------------------------------------------------------
11+
* 思路：
12+
* -------------------------------------------------------------------
13+
* 时间复杂度：O(n)
14+
* 空间复杂度：O(n)
15+
*/
16+
public String simplifyPath(String path) {
17+
// 按"/"分隔，进行处理
18+
String[] pathArr = path.split("/");
19+
Stack<String> stack = new Stack<>();
20+
for (String p : pathArr) {
21+
// 处理"."和""
22+
if (p.equals("") || p.equals(".")) {
23+
continue;
24+
}
25+
// ".."返回上一级
26+
if (p.equals("..")) {
27+
if (!stack.empty()) {
28+
stack.pop();
29+
}
30+
} else {
31+
// "path"正常路径
32+
stack.push(p);
33+
}
34+
}
35+
// 说明path是一个"/"或者"/../"等
36+
if (stack.empty()) {
37+
return "/";
38+
}
39+
// 拼接处理后的路径
40+
StringBuilder lastPath = new StringBuilder();
41+
for (String p : stack) {
42+
lastPath.append("/");
43+
lastPath.append(p);
44+
}
45+
return lastPath.toString();
46+
}
47+
48+
public static void main(String[] args) {
49+
//String path = "/a/../../b/../c//.//";
50+
//String path = "/a/./b/../../c/";
51+
//String path ="/";
52+
String path ="/../";
53+
System.out.println(new Solution1().simplifyPath(path));
54+
//System.out.println(Arrays.toString("/a/../../b/../c//.//".replaceAll("//", "/").split("/")));
55+
}
56+
}

‎algorithms/leetcode/stackqueue/src/main/java/cn/lastwhisper/leetcode/stackqueue/逆波兰表达式求值_150_中等/Solution1.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package cn.lastwhisper.leetcode.stackqueue.逆波兰表达式求值_150_中等;
2+
3+
import java.util.Stack;
4+
5+
class Solution1 {
6+
/**
7+
* 题目地址：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
8+
* -------------------------------------------------------------------
9+
* 思考：
10+
* -------------------------------------------------------------------
11+
* 思路：安装NPN规则即可
12+
* -------------------------------------------------------------------
13+
* 时间复杂度：O(n)
14+
* 空间复杂度：O(n)
15+
*/
16+
public int evalRPN(String[] tokens) {
17+
Stack<String> numStack = new Stack<>();
18+
for (String token : tokens) {
19+
if (isNum(token)) {
20+
numStack.push(token);
21+
} else {
22+
String num2 = numStack.pop();
23+
String num1 = numStack.pop();
24+
numStack.push(calculate(num1, num2, token));
25+
}
26+
}
27+
28+
return Integer.parseInt(numStack.pop());
29+
}
30+
31+
/**
32+
* 判断该字符串是不是数字
33+
*/
34+
public boolean isNum(String token) {
35+
java.util.regex.Pattern pattern = java.util.regex.Pattern.compile("^([-+])?\\d+(\\.\\d+)?$");
36+
return pattern.matcher(token).matches();
37+
}
38+
39+
/**
40+
* 计算
41+
*/
42+
public String calculate(String num1, String num2, String expressions) {
43+
switch (expressions) {
44+
case "+":
45+
return String.valueOf(Integer.parseInt(num1) + Integer.parseInt(num2));
46+
case "-":
47+
return String.valueOf(Integer.parseInt(num1) - Integer.parseInt(num2));
48+
case "*":
49+
return String.valueOf(Integer.parseInt(num1) * Integer.parseInt(num2));
50+
case "/":
51+
return String.valueOf(Integer.parseInt(num1) / Integer.parseInt(num2));
52+
default:
53+
return "";
54+
}
55+
}
56+
57+
public static void main(String[] args) {
58+
//String[] tokens = new String[]{"2", "1", "+", "3", "*"};
59+
String[] tokens = new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
60+
61+
System.out.println(new Solution1().evalRPN(tokens));
62+
}
63+
}

‎algorithms/leetcode/stackqueue/src/main/java/cn/lastwhisper/leetcode/stackqueue/逆波兰表达式求值_150_中等/Solution2.java‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package cn.lastwhisper.leetcode.stackqueue.逆波兰表达式求值_150_中等;
2+
3+
import java.util.Stack;
4+
5+
class Solution2 {
6+
/**
7+
* 题目地址：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
8+
* -------------------------------------------------------------------
9+
* 思考：
10+
* -------------------------------------------------------------------
11+
* 思路：安装NPN规则即可
12+
* -------------------------------------------------------------------
13+
* 时间复杂度：O(n)
14+
* 空间复杂度：O(n)
15+
*/
16+
public int evalRPN(String[] tokens) {
17+
Stack<Integer> numStack = new Stack<>();
18+
for (String token : tokens) {
19+
//if ("+".equals(token)) {
20+
// //第一个弹出来的数字，要做被+-*/数
21+
// Integer num = numStack.pop();
22+
// numStack.push(numStack.pop() + num);
23+
//} else if ("-".equals(token)) {
24+
// Integer num = numStack.pop();
25+
// numStack.push(numStack.pop() - num);
26+
//} else if ("*".equals(token)) {
27+
// Integer num = numStack.pop();
28+
// numStack.push(numStack.pop() * num);
29+
//} else if ("/".equals(token)) {
30+
// Integer num = numStack.pop();
31+
// numStack.push(numStack.pop() / num);
32+
//} else {
33+
// numStack.push(Integer.parseInt(token));
34+
//}
35+
Integer num;
36+
switch (token){
37+
case "+":
38+
num = numStack.pop();
39+
numStack.push(numStack.pop() +num);
40+
break;
41+
case "-":
42+
num = numStack.pop();
43+
numStack.push(numStack.pop() - num);
44+
break;
45+
case "*":
46+
num = numStack.pop();
47+
numStack.push(numStack.pop() * num);
48+
break;
49+
case "/":
50+
num = numStack.pop();
51+
numStack.push(numStack.pop() / num);
52+
break;
53+
default:
54+
numStack.push(Integer.parseInt(token));
55+
}
56+
57+
}
58+
return numStack.pop();
59+
}
60+
61+
62+
public static void main(String[] args) {
63+
//String[] tokens = new String[]{"2", "1", "+", "3", "*"};
64+
String[] tokens = new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
65+
66+
System.out.println(new Solution2().evalRPN(tokens));
67+
}
68+
}

0 commit comments

Comments
 (0)