Skip to content

Commit e86db91

Browse files
znn0301znn0301
committed
其他解法+备注
1 parent cb0260c commit e86db91

File tree

16 files changed

+290
-5
lines changed

16 files changed

+290
-5
lines changed

‎src/main/java/com/chen/algorithm/study/test1/Solution4.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.chen.algorithm.study.test1;
2+
3+
import com.alibaba.fastjson.JSON;
4+
import org.junit.Test;
5+
6+
import java.util.HashMap;
7+
import java.util.Map;
8+
9+
/**
10+
* @Auther: zhunn
11+
* @Date: 2020/10/22 19:00
12+
* @Description: 两数之和
13+
*/
14+
public class Solution4 {
15+
16+
public int[] twoSum1(int[] nums, int target) {
17+
int n = nums.length;
18+
for (int i = 0; i < n; ++i) {
19+
for (int j = i + 1; j < n; ++j) {
20+
if (nums[i] + nums[j] == target) {
21+
return new int[]{i, j};
22+
}
23+
}
24+
}
25+
return new int[0];
26+
}
27+
28+
public int[] twoSum2(int[] nums, int target) {
29+
Map<Integer, Integer> hashtable = new HashMap<>();
30+
for (int i = 0; i < nums.length; ++i) {
31+
if (hashtable.containsKey(target - nums[i])) {
32+
return new int[]{hashtable.get(target - nums[i]), i};
33+
}
34+
hashtable.put(nums[i], i);
35+
}
36+
return new int[0];
37+
}
38+
39+
@Test
40+
public void testCase() {
41+
int[] array = {4, 5, 6, 7, 2};
42+
43+
int[] result = twoSum1(array, 9);
44+
System.out.println(JSON.toJSONString(result));
45+
46+
}
47+
}

‎src/main/java/com/chen/algorithm/study/test141/Solution1.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
*
66
* @author : chen weijie
77
* @Date: 2019-11-02 15:58
8+
* @Description: zhunn 判断链表是否有环
89
*/
910
public class Solution1 {
1011

‎src/main/java/com/chen/algorithm/study/test19/Solution4.java

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
package com.chen.algorithm.study.test19;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Deque;
6+
import java.util.LinkedList;
7+
8+
/**
9+
* @Auther: zhunn
10+
* @Date: 2020/10/22 14:51
11+
* @Description: 1、遍历length-n+1；2、栈、3、双指针法
12+
*/
13+
public class Solution4 {
14+
15+
class ListNode {
16+
int val;
17+
ListNode next;
18+
19+
public ListNode() {
20+
}
21+
22+
public ListNode(int val) {
23+
this.val = val;
24+
}
25+
26+
public ListNode(int val, ListNode next) {
27+
this.val = val;
28+
this.next = next;
29+
}
30+
}
31+
32+
/**
33+
* 计算链表长度并遍历
34+
*
35+
* @param head 头结点
36+
* @param n 删除倒数第几个
37+
* @return
38+
*/
39+
public ListNode removeNthFromEnd1(ListNode head, int n) {
40+
if (head == null) {
41+
return head;
42+
}
43+
44+
ListNode dummy = new ListNode(-1, head);
45+
ListNode curr = dummy;
46+
int len = getLength(head);
47+
for (int i = 1; i < len - n + 1; i++) {
48+
curr = curr.next;
49+
}
50+
curr.next = curr.next.next;
51+
52+
return dummy.next;
53+
}
54+
55+
/**
56+
* 用stack
57+
*
58+
* @param head 头结点
59+
* @param n 删除倒数第几个
60+
* @return
61+
*/
62+
public ListNode removeNthFromEnd2(ListNode head, int n) {
63+
if (head == null) {
64+
return head;
65+
}
66+
ListNode dummy = new ListNode(-1, head);
67+
Deque<ListNode> stack = new LinkedList<>();
68+
ListNode curr = dummy;
69+
while (curr != null) {
70+
stack.push(curr);
71+
curr = curr.next;
72+
}
73+
74+
for (int i = 0; i < n; i++) {
75+
stack.pop();
76+
}
77+
ListNode pre = stack.peek();
78+
pre.next = pre.next.next;
79+
return dummy.next;
80+
}
81+
82+
/**
83+
* 双指针法
84+
*
85+
* @param head 头结点
86+
* @param n 删除倒数第几个
87+
* @return
88+
*/
89+
public ListNode removeNthFromEnd3(ListNode head, int n) {
90+
if (head == null) {
91+
return head;
92+
}
93+
94+
ListNode dummy = new ListNode(-1, head);
95+
ListNode fast = dummy;
96+
ListNode slow = dummy;
97+
98+
for (int i = 0; i < n; i++) {
99+
fast = fast.next;
100+
}
101+
102+
while (fast.next != null) {
103+
fast = fast.next;
104+
slow = slow.next;
105+
}
106+
107+
slow.next = slow.next.next;
108+
109+
return dummy.next;
110+
}
111+
112+
private int getLength(ListNode head) {
113+
if (head == null) {
114+
return 0;
115+
}
116+
ListNode lenNode = head;
117+
int len = 0;
118+
while (lenNode != null) {
119+
len++;
120+
lenNode = lenNode.next;
121+
}
122+
return len;
123+
}
124+
125+
@Test
126+
public void test() {
127+
ListNode five = new ListNode(5);
128+
ListNode four = new ListNode(4, five);
129+
ListNode three = new ListNode(3, four);
130+
ListNode two = new ListNode(2, three);
131+
ListNode head = new ListNode(1, two);
132+
133+
ListNode result = removeNthFromEnd3(head, 2);
134+
135+
ListNode a = result;
136+
while (a != null) {
137+
System.out.println(a.val);
138+
a = a.next;
139+
}
140+
//System.out.println(result);
141+
}
142+
}

‎src/main/java/com/chen/algorithm/study/test2/ListNode.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,16 +3,24 @@
33
/**
44
* @author : chen weijie
55
* @Date: 2019-09-02 23:06
6+
* 参考 Solution3
67
*/
78
public class ListNode {
89

910
int val;
1011

1112
ListNode next;
1213

14+
ListNode() {
15+
}
16+
1317
ListNode(int val) {
1418
this.val = val;
1519
}
1620

21+
ListNode(int val, ListNode next) {
22+
this.val = val;
23+
this.next = next;
24+
}
1725

1826
}

‎src/main/java/com/chen/algorithm/study/test2/Solution3.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
/**
66
* @author : chen weijie
77
* @Date: 2020-07-30 17:43
8+
* @Description: zhunn 两数相加
89
*/
910
public class Solution3 {
1011

‎src/main/java/com/chen/algorithm/study/test206/Solution5.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.chen.algorithm.study.test206;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @Auther: zhunn
7+
* @Date: 2020/10/22 17:23
8+
* @Description: 反转链表：1-迭代法，2-递归
9+
*/
10+
public class Solution5 {
11+
12+
class ListNode {
13+
int val;
14+
ListNode next;
15+
16+
public ListNode() {
17+
}
18+
19+
public ListNode(int val) {
20+
this.val = val;
21+
}
22+
23+
public ListNode(int val, ListNode next) {
24+
this.val = val;
25+
this.next = next;
26+
}
27+
28+
}
29+
30+
public ListNode reverseList1(ListNode head) {
31+
if (head == null || head.next == null) {
32+
return head;
33+
}
34+
35+
ListNode pre = null;
36+
ListNode curr = head;
37+
while (curr != null) {
38+
ListNode nextTemp = curr.next;
39+
curr.next = pre;
40+
pre = curr;
41+
curr = nextTemp;
42+
}
43+
44+
return pre;
45+
}
46+
47+
public ListNode reverseList2(ListNode head){
48+
if(head == null || head.next == null){
49+
return head;
50+
}
51+
ListNode p = reverseList2(head.next);
52+
head.next.next = head;
53+
head.next = null;
54+
return p;
55+
}
56+
57+
@Test
58+
public void test() {
59+
ListNode l1_4 = new ListNode(18);
60+
ListNode l1_3 = new ListNode(9, l1_4);
61+
ListNode l1_2 = new ListNode(6, l1_3);
62+
ListNode l1_1 = new ListNode(7, l1_2);
63+
64+
ListNode result = reverseList2(l1_1);
65+
System.out.println(result.val);
66+
System.out.println(result.next.val);
67+
System.out.println(result.next.next.val);
68+
System.out.println(result.next.next.next.val);
69+
}
70+
71+
72+
}

‎src/main/java/com/chen/algorithm/study/test21/ListNode.java

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,15 +3,24 @@
33
/**
44
* @author : chen weijie
55
* @Date: 2019-09-06 00:35
6+
* 参考 Solution3
67
*/
78
public class ListNode {
89

910
int val;
1011

1112
ListNode next;
1213

13-
public ListNode(int val) {
14+
ListNode() {
15+
}
16+
17+
ListNode(int val) {
18+
this.val = val;
19+
}
20+
21+
ListNode(int val, ListNode next) {
1422
this.val = val;
23+
this.next = next;
1524
}
1625

1726

‎src/main/java/com/chen/algorithm/study/test21/Solution3.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
/**
66
* @author : chen weijie
77
* @Date: 2019-09-06 01:43
8+
* @Description: zhunn 合并两个有序链表
89
*/
910
public class Solution3 {
1011

‎src/main/java/com/chen/algorithm/study/test240/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
*
66
* @author : chen weijie
77
* @Date: 2019-12-22 14:26
8-
* @Description: 搜索二维矩阵
8+
* @Description: zhunn 搜索二维矩阵
99
*/
1010
public class Solution {
1111

‎src/main/java/com/chen/algorithm/study/test283/Solution2.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
* 移动0
99
* @author : chen weijie
1010
* @Date: 2019-11-03 18:44
11+
* @Description: zhunn 移动0至末尾
1112
*/
1213
public class Solution2 {
1314

‎src/main/java/com/chen/algorithm/study/test448/Solution.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
*
1313
* @author : chen weijie
1414
* @Date: 2019-11-04 00:06
15+
* @@Description: zhunn 找到所有数组中消失的数字
1516
*/
1617
public class Solution {
1718

‎src/main/java/com/chen/algorithm/study/test48/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
/**
77
* @author : chen weijie
88
* @Date: 2019-11-12 00:04
9-
* @Description: 顺时针旋转图像90°
9+
* @Description: zhunn 顺时针旋转图像90°
1010
*/
1111
public class Solution {
1212

‎src/main/java/com/chen/algorithm/study/test56/Solution.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
*
1313
* @author : chen weijie
1414
* @Date: 2019-11-14 00:22
15+
* @Description: zhunn 合并区间
1516
*/
1617
public class Solution {
1718

‎src/main/java/com/chen/algorithm/study/test581/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
*
1111
* @author : chen weijie
1212
* @Date: 2019-11-07 23:34
13-
* @Description: 最短无序连续子数组
13+
* @Description: zhunn 最短无序连续子数组
1414
*/
1515
public class Solution {
1616

‎src/main/java/com/chen/algorithm/study/test69/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
/**
66
* @author : chen weijie
77
* @Date: 2020-05-03 09:39
8-
* @Description: x的平方根，舍弃小数
8+
* @Description: zhunn x的平方根，舍弃小数
99
*/
1010
public class Solution {
1111

0 commit comments

Comments
 (0)