Skip to content

Commit bfa8b9a

Browse files
author
zhuchen
committed
2020-10-27
1 parent b4d2d50 commit bfa8b9a

File tree

52 files changed

+1149
-216
lines changed

Some content is hidden

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

52 files changed

+1149
-216
lines changed

‎lcof52_liang_ge_lian_biao_de_di_yi_ge_gong_gong_jie_dian/ListNode.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package lcof52_liang_ge_lian_biao_de_di_yi_ge_gong_gong_jie_dian;
2+
3+
public class ListNode {
4+
5+
int val;
6+
7+
ListNode next;
8+
9+
ListNode(int x) {
10+
val = x;
11+
next = null;
12+
}
13+
14+
}

‎lcof52_liang_ge_lian_biao_de_di_yi_ge_gong_gong_jie_dian/Solution.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package lcof52_liang_ge_lian_biao_de_di_yi_ge_gong_gong_jie_dian;
2+
3+
/**
4+
* 双指针。
5+
*
6+
* 时间复杂度是 O(m + n)，其中 m 为链表 headA 的长度，n 为链表 headB 的长度。空间复杂度是 O(1)。
7+
*
8+
* 执行用时：1ms，击败100.00%。消耗内存：40.9MB，击败98.98%。
9+
*/
10+
public class Solution {
11+
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
12+
ListNode cur1 = headA, cur2 = headB;
13+
while (cur1 != cur2) {
14+
if (cur1 == null) {
15+
cur1 = headB;
16+
} else {
17+
cur1 = cur1.next;
18+
}
19+
if (cur2 == null) {
20+
cur2 = headA;
21+
} else {
22+
cur2 = cur2.next;
23+
}
24+
}
25+
return cur1;
26+
}
27+
}

‎question0019_remove_nth_node_from_end_of_list/ListNode.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,13 @@
11
package question0019_remove_nth_node_from_end_of_list;
22

33
public class ListNode {
4+
45
public int val;
56

67
public ListNode next;
78

89
public ListNode(int x) {
910
val = x;
1011
}
12+
1113
}

‎question0019_remove_nth_node_from_end_of_list/Solution1.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,6 @@
11
package question0019_remove_nth_node_from_end_of_list;
22

33
/**
4-
* https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
5-
*
64
* 两次扫描。第一趟扫描目的是得到链表的总节点个数。第二趟扫描的目的是找到待删除节点的前一个节点。
75
*
86
* 时间复杂度是O(m)，其中m为链表的长度。空间复杂度是O(1)。

‎question0019_remove_nth_node_from_end_of_list/Solution2.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,6 @@
11
package question0019_remove_nth_node_from_end_of_list;
22

33
/**
4-
* https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
5-
*
64
* 一趟扫描，双指针，让一个指针先走n步。
75
*
86
* 时间复杂度是O(m)，其中m为链表的长度。空间复杂度是O(1)。

‎question143/ListNode.java renamed to ‎question0143_reorder_list/ListNode.java

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,14 @@
1-
package question143;
1+
package question0143_reorder_list;
22

33
public class ListNode {
4+
45
int val;
6+
57
ListNode next;
68

79
ListNode(int x) {
810
val = x;
911
next = null;
1012
}
11-
}
13+
14+
}

‎question0143_reorder_list/Solution.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package question0143_reorder_list;
2+
3+
public class Solution {
4+
5+
public void reorderList(ListNode head) {
6+
ListNode dummyHead = new ListNode(-1);
7+
dummyHead.next = head;
8+
ListNode cur1 = head, cur2 = dummyHead, cur3 = dummyHead;
9+
while (cur3 != null && cur3.next != null) {
10+
cur2 = cur2.next;
11+
cur3 = cur3.next.next;
12+
}
13+
ListNode middle = cur2.next;
14+
cur2.next = null;
15+
ListNode newHead = reverseLinkedList(middle), newCur1 = newHead;
16+
while (cur1 != null && newCur1 != null) {
17+
ListNode nextCur1 = cur1.next, nextNewCur1 = newCur1.next;
18+
cur1.next = newCur1;
19+
newCur1.next = nextCur1;
20+
newCur1 = nextNewCur1;
21+
cur1 = nextCur1;
22+
}
23+
}
24+
25+
private ListNode reverseLinkedList(ListNode head) {
26+
if (head == null || head.next == null) {
27+
return head;
28+
}
29+
ListNode pre = null, cur = head, next = cur.next;
30+
while (cur != null) {
31+
cur.next = pre;
32+
pre = cur;
33+
cur = next;
34+
if (cur != null) {
35+
next = cur.next;
36+
}
37+
}
38+
return pre;
39+
}
40+
41+
}

‎question234/ListNode.java renamed to ‎question0234_palindrome_linked_list/ListNode.java

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,13 @@
1-
package question234;
1+
package question0234_palindrome_linked_list;
22

33
public class ListNode {
4+
45
int val;
6+
57
ListNode next;
68

79
ListNode(int x) {
810
val = x;
911
}
10-
}
12+
13+
}

‎question234/Solution.java renamed to ‎question0234_palindrome_linked_list/Solution.java

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,29 @@
1-
package question234;
1+
package question0234_palindrome_linked_list;
22

3+
/**
4+
* 快慢双指针 + 反转链表
5+
*
6+
* 时间复杂度是 O(n)，其中 n 为链表中的节点个数。空间复杂度是 O(1)。
7+
*
8+
* 执行用时：1ms，击败99.86%。消耗内存：41.1MB，击败93.28%。
9+
*/
310
public class Solution {
11+
412
public boolean isPalindrome(ListNode head) {
513
if (head == null || head.next == null) {
614
return true;
715
}
816
ListNode dummyHead = new ListNode(-1);
917
dummyHead.next = head;
10-
ListNode cur2 = dummyHead;
11-
ListNode cur3 = dummyHead;
18+
ListNode cur2 = dummyHead, cur3 = dummyHead;
1219
while (cur3 != null && cur3.next != null) {
1320
cur2 = cur2.next;
1421
cur3 = cur3.next.next;
1522
}
16-
cur2 = cur2.next;
17-
ListNode preCur2 = dummyHead;
18-
while (preCur2.next != cur2) {
19-
preCur2 = preCur2.next;
20-
}
21-
preCur2.next = null;
22-
ListNode newHead = reverseLinkedList(cur2);
23-
ListNode cur = head;
24-
ListNode newCur = newHead;
23+
ListNode tmp = cur2.next;
24+
cur2.next = null;
25+
ListNode newHead = reverseLinkedList(tmp);
26+
ListNode cur = head, newCur = newHead;
2527
while (cur != null && newCur != null) {
2628
if (cur.val != newCur.val) {
2729
return false;
@@ -36,9 +38,7 @@ private ListNode reverseLinkedList(ListNode head) {
3638
if (head == null || head.next == null) {
3739
return head;
3840
}
39-
ListNode pre = null;
40-
ListNode cur = head;
41-
ListNode next = cur.next;
41+
ListNode pre = null, cur = head, next = cur.next;
4242
while (cur != null) {
4343
cur.next = pre;
4444
pre = cur;
@@ -49,4 +49,5 @@ private ListNode reverseLinkedList(ListNode head) {
4949
}
5050
return pre;
5151
}
52-
}
52+
53+
}

‎question0270/Solution2.java

Lines changed: 0 additions & 35 deletions
This file was deleted.

‎question0270/Solution1.java renamed to ‎question0270_closest_binary_search_tree_value/Solution1.java

Lines changed: 8 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,19 @@
1-
package question0270;
1+
package question0270_closest_binary_search_tree_value;
22

33
/**
4-
* @author qianyihui
5-
* @date 2019-08-01
6-
*
74
* 中序遍历。
85
*
96
* 时间复杂度是O(n)，其中n为树中的节点个数。空间复杂度是O(h)，其中h为树的高度。
107
*
118
* 执行用时：1ms，击败100.00%。消耗内存：38.2MB，击败100.00%。
129
*/
1310
public class Solution1 {
11+
1412
private int result;
1513

16-
private Integer pre = null;
14+
private Integer pre = Integer.MIN_VALUE;
1715

18-
private Double gap = null;
16+
private Double gap = Double.MAX_VALUE;
1917

2018
public int closestValue(TreeNode root, double target) {
2119
inOrder(root, target);
@@ -26,18 +24,16 @@ private void inOrder(TreeNode root, double target) {
2624
if (null == root) {
2725
return;
2826
}
29-
if (null != pre && pre > target) {
27+
if (pre > target) {
3028
return;
3129
}
3230
inOrder(root.left, target);
33-
if (gap == null) {
34-
gap = Math.abs(target - root.val);
35-
result = root.val;
36-
} else if (Math.abs(target - root.val) < gap) {
31+
if (Math.abs(target - root.val) < gap) {
3732
gap = Math.abs(target - root.val);
3833
result = root.val;
3934
}
4035
pre = root.val;
4136
inOrder(root.right, target);
4237
}
43-
}
38+
39+
}

‎question0270_closest_binary_search_tree_value/Solution2.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package question0270_closest_binary_search_tree_value;
2+
3+
/**
4+
* 二分查找。
5+
*
6+
* 时间复杂度是O(n)，其中n为树中的节点个数。空间复杂度是O(h)，其中h为树的高度。
7+
*
8+
* 执行用时：1ms，击败100.00%。消耗内存：38.1MB，击败100.00%。
9+
*/
10+
public class Solution2 {
11+
12+
public int closestValue(TreeNode root, double target) {
13+
if (target > root.val) {
14+
if (root.right == null) {
15+
return root.val;
16+
}
17+
int rightResult = closestValue(root.right, target);
18+
return Math.abs(root.val - target) < Math.abs(rightResult - target) ? root.val : rightResult;
19+
}
20+
if (root.left == null) {
21+
return root.val;
22+
}
23+
int leftResult = closestValue(root.left, target);
24+
return Math.abs(root.val - target) < Math.abs(leftResult - target) ? root.val : leftResult;
25+
}
26+
27+
}

‎question0449/TreeNode.java renamed to ‎question0270_closest_binary_search_tree_value/TreeNode.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package question0449;
1+
package question0270_closest_binary_search_tree_value;
22

33
public class TreeNode {
44
int val;

‎question0272_closest_binary_search_tree_value_ii/Solution.java

Lines changed: 0 additions & 18 deletions
This file was deleted.

‎question0272_closest_binary_search_tree_value_ii/Solution1.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package question0272_closest_binary_search_tree_value_ii;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 中序遍历。
8+
*
9+
* 时间复杂度是 O(nlogn)，其中 n 为树中的节点个数。空间复杂度是 O(n)。
10+
*
11+
* 执行用时：3ms，击败52.82%。消耗内存：38.4MB，击败100.00%。
12+
*/
13+
public class Solution1 {
14+
15+
private List<Integer> inOrder = new ArrayList<>();
16+
17+
public List<Integer> closestKValues(TreeNode root, double target, int k) {
18+
inOrderTraversal(root);
19+
inOrder.sort((num1, num2) -> {
20+
if (Math.abs(num1 - target) - Math.abs(num2 - target) < 0) {
21+
return -1;
22+
}
23+
return 1;
24+
});
25+
return inOrder.subList(0, k);
26+
}
27+
28+
private void inOrderTraversal(TreeNode treeNode) {
29+
if (null == treeNode) {
30+
return;
31+
}
32+
inOrderTraversal(treeNode.left);
33+
inOrder.add(treeNode.val);
34+
inOrderTraversal(treeNode.right);
35+
}
36+
37+
}

0 commit comments

Comments
 (0)