Skip to content

Commit 212a929

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#417 from plm1025624185/master
431-week-02
2 parents 1aaf20f + 4ca3484 commit 212a929

32 files changed

+1211
-3
lines changed

‎Week 01/id_431/LeetCode_115_431.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package simple;
2+
3+
/**
4+
* @author 潘磊明
5+
* @date 2019/10/22
6+
*/
7+
public class MinStack {
8+
Node head; //头结点
9+
int min;
10+
/** initialize your data structure here. */
11+
public MinStack() {
12+
head = new Node(Integer.MAX_VALUE);
13+
min = head.val;
14+
}
15+
16+
public void push(int x) {
17+
Node tmp = new Node(x);
18+
if (x <= min) {
19+
Node minNode = new Node(min);
20+
minNode.next = head.next;
21+
head.next = minNode;
22+
min = x;
23+
}
24+
tmp.next = head.next;
25+
head.next = tmp;
26+
}
27+
28+
public void pop() {
29+
if (head.next != null) {
30+
if (head.next.val == min) {
31+
min = head.next.next.val;
32+
head.next = head.next.next.next;
33+
}else {
34+
head.next = head.next.next;
35+
}
36+
}
37+
}
38+
39+
public int top() {
40+
return head.next.val;
41+
}
42+
43+
public int getMin() {
44+
return min;
45+
}
46+
47+
class Node {
48+
int val;
49+
Node next;
50+
51+
Node (int val) {
52+
this.val = val;
53+
}
54+
}
55+
}

‎Week 01/id_431/LeetCode_141_431.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package simple;
2+
3+
import java.util.List;
4+
5+
/**
6+
* @author 潘磊明
7+
* @date 2019/10/21
8+
*/
9+
public class LinkedListCycle {
10+
11+
public boolean hasCycle(ListNode head) {
12+
if (head == null) return false;
13+
//快慢节点求解
14+
ListNode fast = head;
15+
ListNode slow = head;
16+
while (fast.next != null && fast.next.next != null && slow.next != null) {
17+
if (fast.next.next == slow.next) {
18+
return true;
19+
}
20+
fast = fast.next.next;
21+
slow = slow.next;
22+
}
23+
return false;
24+
}
25+
26+
class ListNode {
27+
int val;
28+
ListNode next;
29+
ListNode(int x) {
30+
val = x;
31+
next = null;
32+
}
33+
}
34+
}

‎Week 01/id_431/LeetCode_142_431.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package medium;
2+
3+
import simple.LinkedListCycle;
4+
5+
/**
6+
* @author 潘磊明
7+
* @date 2019/10/21
8+
*/
9+
public class LinkedListCycleII {
10+
11+
/**
12+
* 解题思路：
13+
* 快慢指针，快指针每次走两步，慢指针每次走一步，
14+
* 当两个指针相遇时，说明快指针走过的长度为慢指针走过的2倍。
15+
* 又由于除了第一次相遇之后，以后的相遇就是在环里面走了，
16+
* 所以可以得出，慢指针第一次相遇后，离初始环节点的长度就是头结点到初始环节点的长度
17+
* @param head
18+
* @return
19+
*/
20+
public ListNode detectCycle(ListNode head) {
21+
if (head == null ) return null;
22+
//快慢指针
23+
ListNode fast = head;
24+
ListNode slow = head;
25+
boolean isCircle = false;
26+
while (fast.next != null && fast.next.next != null && slow.next != null) {
27+
fast = fast.next.next;
28+
slow = slow.next;
29+
if (fast == slow) {
30+
isCircle = true;
31+
break;
32+
}
33+
34+
}
35+
if (!isCircle) return null;
36+
fast = head;
37+
while (fast != slow) {
38+
fast = fast.next;
39+
slow = slow.next;
40+
}
41+
return fast;
42+
}
43+
44+
class ListNode {
45+
int val;
46+
ListNode next;
47+
ListNode(int x) {
48+
val = x;
49+
next = null;
50+
}
51+
}
52+
}

‎Week 01/id_431/LeetCode_189_431.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package simple;
2+
3+
/**
4+
* @author 潘磊明
5+
* @date 2019/10/20
6+
*/
7+
public class RotateArray {
8+
/**
9+
* 暴力求解
10+
* @param nums
11+
* @param k
12+
*/
13+
// public void rotate(int[] nums, int k) {
14+
// for (int i = 0; i < k; i++) {
15+
// int tmp = nums[nums.length - 1];
16+
// for(int j = nums.length - 2; j > -1; j--) {
17+
// nums[j + 1] = nums[j];
18+
// }
19+
// nums[0] = tmp;
20+
// }
21+
// }
22+
23+
/**
24+
* 使用一个长度为k的数组进行临时存放
25+
* @param nums
26+
* @param k
27+
*/
28+
public void rotate(int[] nums, int k) {
29+
if (nums.length < k) {
30+
k = k - nums.length;
31+
}
32+
int[] tmp = new int[k];
33+
for (int j = 0; j < k; j++){
34+
tmp[k - j - 1] = nums[nums.length - 1 - j];
35+
}
36+
for (int i = 0; i < nums.length - k; i++) {
37+
nums[nums.length - 1 - i] = nums[nums.length -1 - i - k];
38+
}
39+
for (int i = 0; i < k; i++) {
40+
nums[i] = tmp[i];
41+
}
42+
}
43+
44+
public static void main(String[] args) {
45+
RotateArray rotateArray = new RotateArray();
46+
rotateArray.rotate(new int[]{
47+
1,2,3,4,5,6,7
48+
}, 3);
49+
}
50+
}

‎Week 01/id_431/LeetCode_206_431.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package simple;
2+
3+
4+
import java.util.List;
5+
6+
/**
7+
* @author 潘磊明
8+
* @date 2019/10/21
9+
*/
10+
public class ReverseLinkedList {
11+
/**
12+
* 对链表进行迭代
13+
* @param head
14+
* @return
15+
*/
16+
// public ListNode reverseList(ListNode head) {
17+
// ListNode newHead = null;
18+
// while (head != null) {
19+
// ListNode tmp = head;
20+
// head = head.next;
21+
// tmp.next = newHead;
22+
// newHead = tmp;
23+
// }
24+
// return newHead;
25+
// }
26+
27+
/**
28+
* 递归
29+
* @param head
30+
* @return
31+
*/
32+
public ListNode reverseList(ListNode head) {
33+
return head ==null ? head : reverseNode(head, null);
34+
}
35+
36+
public ListNode reverseNode(ListNode src, ListNode dest){
37+
ListNode tmp = null;
38+
tmp = src;
39+
src = src.next;
40+
tmp.next = dest;
41+
if (src != null) {
42+
return reverseNode(src, tmp);
43+
}else{
44+
return tmp;
45+
}
46+
}
47+
48+
public class ListNode {
49+
int val;
50+
ListNode next;
51+
52+
public ListNode(int x) {
53+
val = x;
54+
}
55+
}
56+
57+
}

‎Week 01/id_431/LeetCode_20_431.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package simple;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* @author 潘磊明
7+
* @date 2019/10/22
8+
*/
9+
public class ValidParentheses {
10+
/**
11+
* 使用栈
12+
* @param s
13+
* @return
14+
*/
15+
public boolean isValid(String s) {
16+
Stack<String> stack = new Stack<>();
17+
for (int i = 0; i < s.length(); i++) {
18+
String tmp = s.substring(i, i + 1);
19+
if (stack.empty()) {
20+
stack.push(tmp);
21+
}else {
22+
if (isValid(stack.peek(), tmp)){
23+
stack.pop();
24+
}else {
25+
stack.push(tmp);
26+
}
27+
}
28+
}
29+
return stack.empty();
30+
}
31+
32+
boolean isValid(String left, String right){
33+
if("(".equals(left) && ")".equals(right)){
34+
return true;
35+
}else if ("[".equals(left) && "]".equals(right)) {
36+
return true;
37+
}else if ("{".equals(left) && "}".equals(right)) {
38+
return true;
39+
}
40+
return false;
41+
}
42+
}

‎Week 01/id_431/LeetCode_21_431.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package simple;
2+
3+
/**
4+
* @author 潘磊明
5+
* @date 2019/10/22
6+
*/
7+
public class MergeTwoSortedLists {
8+
9+
/**
10+
* 使用循环
11+
* @param l1
12+
* @param l2
13+
* @return
14+
*/
15+
// public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
16+
// ListNode newHead = null;
17+
// ListNode cur = null;
18+
// while (l1 != null || l2 != null) {
19+
// int v1 = l1 == null ? Integer.MAX_VALUE : l1.val;
20+
// int v2 = l2 == null ? Integer.MAX_VALUE : l2.val;
21+
// if (newHead == null) {
22+
// newHead = new ListNode(Math.min(v1, v2));
23+
// cur = newHead;
24+
// }else {
25+
// cur.next = new ListNode(Math.min(v1, v2));
26+
// cur = cur.next;
27+
// }
28+
// if (v1 < v2) {
29+
// l1 = l1.next;
30+
// }else {
31+
// l2 = l2.next;
32+
// }
33+
// }
34+
// return newHead;
35+
// }
36+
37+
/**
38+
* 使用递归
39+
* @param l1
40+
* @param l2
41+
* @return
42+
*/
43+
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
44+
if (l1 == null) return l2;
45+
if (l2 == null) return l1;
46+
if (l1.val < l2.val) {
47+
l1.next = mergeTwoLists(l1.next, l2);
48+
return l1;
49+
}else {
50+
l2.next = mergeTwoLists(l1, l2.next);
51+
return l2;
52+
}
53+
}
54+
55+
public class ListNode {
56+
int val;
57+
ListNode next;
58+
ListNode(int x) { val = x; }
59+
}
60+
}

‎Week 01/id_431/LeetCode_24_431.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package medium;
2+
3+
import java.util.List;
4+
5+
/**
6+
* @author 潘磊明
7+
* @date 2019/10/21
8+
*/
9+
public class SwapNodesInPairs {
10+
11+
public ListNode swapPairs(ListNode head) {
12+
if (head == null) return head;
13+
ListNode newHead = new ListNode(0); //哨兵节点用于占位
14+
swapNode(newHead, head);
15+
return newHead.next;
16+
}
17+
18+
public void swapNode(ListNode head, ListNode swapNode){
19+
if (swapNode != null && swapNode.next != null) {
20+
ListNode tmp = swapNode.next.next;
21+
head.next = swapNode.next;
22+
head.next.next = swapNode;
23+
swapNode = tmp;
24+
swapNode(head.next.next, swapNode);
25+
}else{
26+
head.next = swapNode;
27+
}
28+
}
29+
30+
public class ListNode {
31+
int val;
32+
ListNode next;
33+
ListNode(int x) { val = x; }
34+
}
35+
}

0 commit comments

Comments
 (0)