8000 update · rchen102/Leetcode-Notes@03f7279 · GitHub
[go: up one dir, main page]
Skip to content

Commit 03f7279

Browse files
author
rchen102
committed
update
1 parent 2811d3e commit 03f7279

14 files changed

+299
-88
lines changed

‎Java/leetcode 1249.java

Lines changed: 17 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,29 @@
11
// Solution1: stack + placeholder T: O(n) S: O(n)
22
class Solution {
33
public String minRemoveToMakeValid(String s) {
4+
if (s == null || s.length() == 0) return s;
5+
char[] seq = s.toCharArray();
46
Stack<Integer> stack = new Stack<>();
5-
StringBuilder res = new StringBuilder(s);
6-
for (int i = 0; i < s.length(); i++) {
7-
char ch = s.charAt(i);
7+
for (int i = 0; i < seq.length; i++) {
8+
char ch = seq[i];
89
if (ch == '(') stack.push(i);
910
if (ch == ')') {
10-
if (!stack.isEmpty()) stack.pop();
11-
else res.setCharAt(i, '$');
11+
if (stack.isEmpty()) {
12+
seq[i] = '$'; // 占位符
13+
}
14+
else {
15+
stack.pop();
16+
}
1217
}
13-
}
18+
}
1419
while (!stack.isEmpty()) {
1520
int idx = stack.pop();
16-
res.setCharAt(idx, '$');
21+
seq[idx] = '$';
22+
}
23+
StringBuilder res = new StringBuilder();
24+
for (char ch : seq) {
25+
if (ch != '$') res.append(ch);
1726
}
18-
return res.toString().replaceAll("\\$", "");
27+
return res.toString();
1928
}
2029
}

‎Java/leetcode 15.java

Lines changed: 19 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -5,29 +5,31 @@ public List<List<Integer>> threeSum(int[] nums) {
55
if (nums == null || nums.length == 0) return res;
66
Arrays.sort(nums);
77
for (int i = 0; i < nums.length; i++) {
8-
if (i != 0 && nums[i] == nums[i-1]) continue;
9-
List<List<Integer>> tmpRes = twoSum(nums, i);
10-
if (tmpRes.size() != 0) res.addAll(tmpRes);
8+
if (i > 0 && nums[i] == nums[i-1]) continue;
9+
List<List<Integer>> tmp = twoSum(nums, i);
10+
if (tmp.size() > 0) {
11+
res.addAll(tmp);
12+
}
1113
}
1214
return res;
1315
}
14-
15-
private List<List<Integer>> twoSum(int[] nums, int idx) {
16+
17+
public List<List<Integer>> twoSum(int[] nums, int idx) {
1618
int target = -nums[idx];
17-
int left = idx + 1, right = nums.length - 1;
18-
List<List<Integer>> tmpRes = new ArrayList<>();
19-
while (left < right) {
20-
int sum = nums[left] + nums[right];
21-
if (sum > target) right--;
22-
else if (sum < target) left++;
19+
int lo = idx + 1, hi = nums.length - 1;
20+
List<List<Integer>> res = new ArrayList<>(3);
21+
while (lo < hi) {
22+
int sum = nums[lo] + nums[hi];
23+
if (sum < target) lo++;
24+
else if (sum > target) hi--;
2325
else {
24-
tmpRes.add(Arrays.asList(nums[idx], nums[left], nums[right]));
25-
while (left < right && nums[left] == nums[left+1]) left++;
26-
while (left < right && nums[right-1] == nums[right]) right--;
27-
left++;
28-
right--;
26+
res.add(Arrays.asList(nums[idx], nums[lo], nums[hi]));
27+
while (lo < hi && nums[lo] == nums[lo+1]) lo++;
28+
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
29+
lo++;
30+
hi--;
2931
}
3032
}
31-
return tmpRes;
33+
return res;
3234
}
3335
}

‎Java/leetcode 1541.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution {
2+
public int minInsertions(String s) {
3+
if (s == null || s.length() == 0) return 0;
4+
int need = 0; // 对右括号的需要数量
5+
int res = 0;
6+
for (char ch : s.toCharArray()) {
7+
if (ch == '(') {
8+
need += 2;
9+
if (need % 2 == 1) {
10+
res++;
11+
need--;
12+
}
13+
}
14+
else if (ch == ')') {
15+
need--;
16+
if (need < 0) {
17+
need = 1;
18+
res++; // 插入一个左括号，这样只需要 1 个右括号即可匹配
19+
}
20+
}
21+
}
22+
return res + need;
23+
}
24+
}

‎Java/leetcode 207.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
// DFS 拓扑排序
2+
class Solution {
3+
4+
List<List<Integer>> edges;
5+
int[] visited; // 0 未搜索，1 正在搜索，2 搜索完成
6+
boolean valid;
7+
8+
public boolean canFinish(int numCourses, int[][] prerequisites) {
9+
edges = new ArrayList<>(numCourses);
10+
visited = new int[numCourses];
11+
valid = true;
12+
13+
// 创建邻接表
14+
for (int i = 0; i < numCourses; i++) {
15+
edges.add(new LinkedList<>());
16+
}
17+
// 初始化
18+
for (int[] prereq : prerequisites) {
19+
int from = prereq[1];
20+
int to = prereq[0];
21+
edges.get(from).add(to);
22+
}
23+
24+
// dfs
25+
for (int i = 0 ; i < numCourses; i++) {
26+
if (!valid) return false;
27+
if (visited[i] == 0) {
28+
dfs(i);
29+
}
30+
}
31+
return valid;
32+
}
33+
34+
void dfs(int course) {
35+
visited[course] = 1;
36+
for (int to : edges.get(course)) {
37+
if (visited[to] == 1) {
38+
// 有环，提前终止搜索
39+
valid = false;
40+
return;
41+
}
42+
if (visited[to] == 0) {
43+
dfs(to);
44+
if (!valid) return;
45+
}
46+
// 如果节点已经搜索完成，代表这是一个至少 2 个入边的节点，并且已经搜索完成，没有环
47+
// if (visited[to] == 2)
48+
}
49+
visited[course] = 2;
50+
}
51+
}

‎Java/leetcode 22.java

Lines changed: 19 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,27 @@
11
//Solution1: T: O(2^(2n)) S: O(n)
22
class Solution {
33
public List<String> generateParenthesis(int n) {
4-
List<String> list = new ArrayList<String>();
5-
addParenthesis(list, "", 0, 0, n);
6-
return list;
4+
List<String> res = new ArrayList<>();
5+
if (n <= 0) return res;
6+
backtrack(n, n, new StringBuilder(2*n), res);
7+
return res;
78
}
8-
public void addParenthesis(List<String> list, String str, int open, int close, int max) {
9-
if(close == max) {
10-
list.add(str);
9+
10+
void backtrack(int left, int right, StringBuilder path, List<String> res) {
11+
if (left < 0 || right < 0) return; // 剩余为负数，不合法
12+
if (left > right) return; // 剩下的左括号多，不合法
13+
if (left == 0 && right == 0) {
14+
res.add(path.toString());
1115
return;
1216
}
13-
14-
if(open < max)
15-
addParenthesis(list, str + '(', open + 1, close, max);
16-
if(close < open)
17-
addParenthesis(list, str + ')', open, close + 1, max);
17+
// 尝试左括号
18+
path.append('(');
19+
backtrack(left - 1, right, path, res);
20+
path.deleteCharAt(path.length() - 1);
21+
22+
// 尝试右括号
23+
path.append(')');
24+
backtrack(left, right - 1, path, res);
25+
path.deleteCharAt(path.length() - 1);
1826
}
1927
}

‎Java/leetcode 239.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,27 @@
11
// Solution1: sliding window + Deque
22
// T: O(n) S: O(k)
3+
class Solution {
4+
public int[] maxSlidingWindow(int[] nums, int k) {
5+
if (nums == null || nums.length == 0) return new int[0];
6+
List<Integer> res = new ArrayList<>();
7+
Deque<Integer> queue = new LinkedList<>();
8+
for (int i = 0; i < nums.length; i++) {
9+
int cur = nums[i];
10+
while (!queue.isEmpty() && cur >= nums[queue.peekLast()]) {
11+
queue.pollLast();
12+
}
13+
queue.offerLast(i);
14+
if (i >= k && queue.peekFirst() == i - k) queue.pollFirst();
15+
if (i >= k - 1) res.add(nums[queue.peekFirst()]);
16+
}
17+
int[] arr = new int[res.size()];
18+
for (int i = 0; i < arr.length; i++) {
19+
arr[i] = res.get(i);
20+
}
21+
return arr;
22+
}
23+
}
24+
325
class Solution {
426
public int[] maxSlidingWindow(int[] nums, int k) {
527
if (nums == null || nums.length == 0) return null;

‎Java/leetcode 24.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,31 @@ public ListNode swapPairs(ListNode head) {
1919
}
2020

2121
// Solution2: iterative T: O(n) S: O(1)
22+
class Solution {
23+
public ListNode swapPairs(ListNode head) {
24+
if (head == null || head.next == null) return head;
25+
ListNode dummy = new ListNode();
26+
dummy.next = head;
27+
ListNode prev = dummy;
28+
while (prev.next != null) {
29+
ListNode left = prev.next;
30+
// 检查是否不足 2 个节点
31+
if (left.next == null) {
32+
prev = left;
33+
}
34+
else {
35+
ListNode right = left.next;
36+
prev.next = right;
37+
left.next = right.next;
38+
right.next = left;
39+
prev = left;
40+
}
41+
}
42+
return dummy.next;
43+
}
44+
}
45+
46+
2247
class Solution {
2348
public ListNode swapPairs(ListNode head) {
2449
ListNode dummy = new ListNode(-1);

‎Java/leetcode 274.java

Lines changed: 24 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,38 @@
1-
// Solution1: Sort
2-
// T: O(nlogn) S: O(1) (no count sort)
1+
// Solution1: Array(Hash)
2+
// T: O(n) S: O(n)
33
class Solution {
44
public int hIndex(int[] citations) {
55
if (citations == null || citations.length == 0) return 0;
6-
Arrays.sort(citations);
7-
for (int i = 0; i < citations.length; i++) {
8-
int possibleH = citations.length - i;
9-
if (citations[i] >= possibleH) return possibleH;
6+
int len = citations.length;
7+
// ref[j] record the number of papers that have j citations
8+
int[] ref = new int[len + 1];
9+
for (int paper : citations) {
10+
if (paper > len) ref[len]++;
11+
else ref[paper]++;
12+
}
13+
14+
int sum = 0;
15+
for (int i = len; i >= 0; i--) {
16+
sum += ref[i];
17+
if (sum >= i) return i;
1018
}
1119
return 0;
1220
}
1321
}
1422

1523

16-
// Solution2: Array(Hash)
17-
// T: O(n) S: O(n)
24+
// Solution2: Sort
25+
// T: O(nlogn) S: O(1) (no count sort)
1826
class Solution {
1927
public int hIndex(int[] citations) {
20-
int len = citations.length;
21-
//num[j] record the number of papers that have more than j citations
22-
int[] num = new int[len + 1];
23-
24-
for(int i = 0; i < len; i++) {
25-
if(citations[i] > len) num[len]++;
26-
else num[citations[i]]++;
27-
}
28-
29-
int sum = 0;
30-
for(int i = len; i >= 0; i--) {
31-
sum += num[i];
32-
if(sum >= i) return i;
28+
if (citations == null || citations.length == 0) return 0;
29+
Arrays.sort(citations);
30+
for (int i = 0; i < citations.length; i++) {
31+
int possibleH = citations.length - i;
32+
if (citations[i] >= possibleH) return possibleH;
3333
}
3434
return 0;
3535
}
36-
}
36+
}
37+
38+

‎Java/leetcode 309.java

Lines changed: 11 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -3,20 +3,18 @@ class Solution {
33
public int maxProfit(int[] prices) {
44
if (prices == null || prices.length <= 1) return 0;
55
int n = prices.length;
6-
int[][] dp = new int[n][2];
7-
// base
6+
7+
int[][] dp = new int[n+1][2];
8+
// Base cases: 第 0 天，不允许交易
89
dp[0][0] = 0;
9-
dp[0][1] = -prices[0];
10-
11-
for (int i = 1; i < n; i++) {
12-
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
13-
if (i >= 2) {
14-
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
15-
} else {
16-
// dp[-1][] = 0，交易还未开始，该状态不可能存在
17-
dp[i][1] = Math.max(dp[i-1][1], 0 - prices[i]);
18-
}
10+
dp[0][1] = Integer.MIN_VALUE;
11+
// dp 推导
12+
for (int i = 1; i <= n; i++) {
13+
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
14+
if (i-2 < 0) dp[i][1] = Math.max(dp[i-1][1], 0 - prices[i-1]);
15+
else dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i-1]);
16+
1917
}
20-
return dp[n-1][0];
18+
return dp[n][0];
2119
}
2220
}

‎Java/leetcode 337.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,4 +18,27 @@ public int[] dp(TreeNode root) {
1818
dp[1] = root.val + left[0] + right[0];
1919
return dp;
2020
}
21+
}
22+
23+
// O(n)
24+
class Solution {
25+
26+
HashMap<TreeNode, Integer> memo;
27+
28+
public int rob(TreeNode root) {
29+
memo = new HashMap<>();
30+
return rob_dp(root);
31+
}
32+
33+
public int rob_dp(TreeNode root) {
34+
if (root == null) return 0;
35+
if (memo.containsKey(root)) return memo.get(root);
36+
int do_it = root.val +
37+
(root.left == null ? 0 : rob_dp(root.left.left) + rob_dp(root.left.right)) +
38+
(root.right == null ? 0 : rob_dp(root.right.left) + rob_dp(root.right.right));
39+
int not_do = rob_dp(root.left) + rob_dp(root.right);
40+
int res = Math.max(do_it, not_do);
41+
memo.put(root, res);
42+
return res;
43+
}
2144
}

0 commit comments

Comments
 (0)
0