10000 update · rchen102/Leetcode-Notes@77d8733 · GitHub
[go: up one dir, main page]
Skip to content

Commit 77d8733

Browse files
author
rchen102
committed
update
1 parent 78deb21 commit 77d8733

File tree

7 files changed

+85
-61
lines changed

7 files changed

+85
-61
lines changed

‎Java/leetcode 153.java

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,27 +4,30 @@
44
*/
55
class Solution {
66
public int findMin(int[] nums) {
7-
if (nums == null || nums.length == 0) return 0;
87
int lo = 0, hi = nums.length - 1;
9-
while (lo < hi) {
10-
if (nums[lo] < nums[hi]) return nums[lo];
8+
while (lo <= hi) {
9+
if (nums[lo] <= nums[hi]) return nums[lo];
1110
int mid = lo + ((hi - lo) >> 1);
12-
if (nums[mid] >= nums[lo]) lo = mid + 1;
13-
else if (nums[mid] < nums[lo]) hi = mid;
11+
if (nums[mid] > nums[hi]) lo = mid + 1;
12+
else if (nums[mid] < nums[hi]) hi = mid;
1413
}
1514
return nums[lo];
1615
}
1716
}
1817

18+
/**
19+
* Solution: Binary Search
20+
* T:O(logn) S: O(1)
21+
*/
1922
class Solution {
2023
public int findMin(int[] nums) {
2124
if (nums == null || nums.length == 0) return 0;
2225
int lo = 0, hi = nums.length - 1;
2326
while (lo < hi) {
2427
if (nums[lo] < nums[hi]) return nums[lo];
2528
int mid = lo + ((hi - lo) >> 1);
26-
if (nums[mid] < nums[hi]) hi = mid;
27-
else if (nums[mid] > nums[hi]) lo = mid + 1;
29+
if (nums[mid] >= nums[lo]) lo = mid + 1;
30+
else if (nums[mid] < nums[lo]) hi = mid;
2831
}
2932
return nums[lo];
3033
}

‎Java/leetcode 154.java

Lines changed: 6 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -2,60 +2,17 @@
22
// T: O(n)(worst) O(logn)(best) S: O(1)
33
class Solution {
44
public int findMin(int[] nums) {
5-
if (nums == null || nums.length == 0) return 0;
65
int lo = 0, hi = nums.length - 1;
7-
while (lo < hi) {
6+
while (lo <= hi) {
87
if (nums[lo] < nums[hi]) return nums[lo];
98
int mid = lo + ((hi - lo) >> 1);
10-
if (nums[mid] < nums[hi]) hi = mid;
11-
else if (nums[mid] > nums[hi]) lo = mid + 1;
12-
else {
13-
// nums[mid] == nums[hi]
14-
if (nums[hi-1] > nums[hi]) return nums[hi];
15-
hi--;
9+
if (nums[mid] > nums[hi]) lo = mid + 1;
10+
else if (nums[mid] < nums[hi]) hi = mid;
11+
else if (nums[mid] == nums[hi]) {
12+
if (hi != 0 && nums[hi-1] > nums[hi]) return nums[hi];
13+
hi = hi - 1;
1614
}
1715
}
1816
return nums[lo];
1917
}
20-
}
21-
22-
// Solution2: traverse T: O(n) S: O(1)
23-
class Solution {
24-
public int findMin(int[] nums) {
25-
for(int i = 1 ; i < nums.length; i++) {
26-
if(nums[i] < nums[i-1])
27-
return nums[i];
28-
}
29-
return nums[0];
30-
}
31-
}
32-
33-
34-
// Solution3: remove the duplicate elements T: O(n) S: O(n)
35-
class Solution {
36-
public int findMin(int[] nums) {
37-
Set<Integer> set = new HashSet<>();
38-
int[] filtered = new int[nums.length];
39-
int n = 0;
40-
41-
for(int num : nums) {
42-
if(set.add(num)) {
43-
filtered[n++] = num;
44-
}
45-
}
46-
return find(filtered, n);
47-
}
48-
49-
private int find(int[] nums, int n) {
50-
int left = 0;
51-
int right = n - 1;
52-
while(left < right) {
53-
int mid = (left + right)/2;
54-
if(nums[mid] < nums[right])
55-
right = mid;
56-
else
57-
left = mid + 1;
58-
}
59-
return nums[left];
60-
}
6118
}

‎Java/leetcode 219.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
// Solution1: HashSet + Sliding Window
2-
// T: O(n) S: O(k)
2+
// T: O(n) S: O(k) worst
33
class Solution {
44
public boolean containsNearbyDuplicate(int[] nums, int k) {
55
if (nums == null || nums.length == 0) return false;

‎Java/leetcode 23.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
4040

4141
/**
4242
* Solution2: Heap (PriorityQueue)
43-
*
43+
* O(N*logk) S: O(k)
4444
*/
4545
class Solution {
4646
public ListNode mergeKLists(ListNode[] lists) {

‎Java/leetcode 239.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ public int[] maxSlidingWindow(int[] nums, int k) {
2222
if (!queue.isEmpty() && queue.peekFirst() <= i - windowLen) queue.pollFirst();
2323
}
2424
// update
25-
if (i == k - 1 || i >= windowLen) {
25+
if (i >= windowLen - 1) {
2626
res[cur] = nums[queue.peekFirst()];
2727
cur++;
2828
}

‎Java/leetcode 25.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* public class ListNode {
4+
* int val;
5+
* ListNode next;
6+
* ListNode() {}
7+
* ListNode(int val) { this.val = val; }
8+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9+
* }
10+
*/
11+
// T: O(n) S: O(1)
12+
class Solution {
13+
public ListNode reverseKGroup(ListNode head, int k) {
14+
if (head == null) return head;
15+
16+
ListNode dummy = new ListNode();
17+
ListNode prev = dummy;
18+
while (head != null) {
19+
20+
ListNode start = head;
21+
22+
ListNode cur = start;
23+
int counter = 1;
24+
while (cur.next != null && counter < k) {
25+
cur = cur.next;
26+
counter++;
27+
}
28+
// 下一轮循环的头节点
29+
head = cur.next;
30+
31+
ListNode end = cur;
32+
end.next = null;
33+
34+
if (counter == k) {
35+
reverse(start, end);
36+
// 连接反转后的k个节点
37+
prev.next = end;
38+
prev = start;
39+
}
40+
else {
41+
prev.next = start;
42+
break;
43+
}
44+
}
45+
return dummy.next;
46+
}
47+
48+
private void reverse(ListNode start, ListNode end) {
49+
ListNode dummy = new ListNode();
50+
ListNode cur = start;
51+
while (cur != end) {
52+
// store next
53+
ListNode nextNode = cur.next;
54+
cur.next = null;
55+
56+
cur.next = dummy.next;
57+
dummy.next = cur;
58+
59+
// restore next
60+
cur = nextNode;
61+
}
62+
end.next = dummy.next;
63+
}
64+
}

‎Java/leetcode 74.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
/**
22
* Own solution: Binary Search
3-
* T: O(logmax(row, col)) S: O(1)
3+
* T: O(log(row) + log(col)) S: O(1)
44
*/
55
class Solution {
66
public boolean searchMatrix(int[][] matrix, int target) {
@@ -30,7 +30,7 @@ public boolean searchMatrix(int[][] matrix, int target) {
3030

3131
/**
3232
* Solution1: BST
33-
* T: O(log(row * col)) S: O(1)
33+
* T: O(m+n) S: O(1)
3434
*/
3535
class Solution {
3636
public boolean searchMatrix(int[][] matrix, int target) {

0 commit comments

Comments
 (0)
0