Skip to content

Commit 38f56f4

Browse files
author
zhuchen
committed
2021-3-25
1 parent 91b5ed7 commit 38f56f4

File tree

72 files changed

+2136
-154
lines changed

Some content is hidden

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

72 files changed

+2136
-154
lines changed

‎contest_3_20/QYH.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package contest_3_20;
2+
3+
public class QYH {
4+
private static final int COUNT_BITS = Integer.SIZE - 3;
5+
private static final int CAPACITY = (1 << COUNT_BITS) - 1;
6+
7+
// runState is stored in the high-order bits
8+
private static final int RUNNING = -1 << COUNT_BITS;
9+
10+
private static final int SHUTDOWN = 0 << COUNT_BITS;
11+
12+
private static final int STOP = 1 << COUNT_BITS;
13+
14+
private static final int TIDYING = 2 << COUNT_BITS;
15+
16+
private static final int TERMINATED = 3 << COUNT_BITS;
17+
18+
public static void main(String[] args) {
19+
System.out.println("COUNT_BITS = \t" + COUNT_BITS + "(" + Integer.toBinaryString(COUNT_BITS) + ")");
20+
System.out.println("CAPACITY = \t" + CAPACITY + "(" + Integer.toBinaryString(CAPACITY) + ")");
21+
System.out.println("RUNNING = \t" + RUNNING + "(" + Integer.toBinaryString(RUNNING) + ")");
22+
System.out.println("SHUTDOWN = \t" + SHUTDOWN + "(" + Integer.toBinaryString(SHUTDOWN) + ")");
23+
System.out.println("STOP = \t" + STOP + "(" + Integer.toBinaryString(STOP) + ")");
24+
System.out.println("TIDYING = \t" + TIDYING + "(" + Integer.toBinaryString(TIDYING) + ")");
25+
System.out.println("TERMINATED = \t" + TERMINATED + "(" + Integer.toBinaryString(TERMINATED) + ")");
26+
System.out.println(Integer.toBinaryString(~CAPACITY));
27+
}
28+
}

‎question0059_spiral_matrix_ii/Solution.java

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

33
/**
4-
* https://leetcode-cn.com/problems/spiral-matrix-ii/
5-
*
64
* 时间复杂度是O(n ^ 2)。空间复杂度是O(1)。
75
*
86
* 执行用时：1ms，击败45.11%。消耗内存：35.2MB，击败49.02%。
97
*/
108
public class Solution {
9+
1110
public int[][] generateMatrix(int n) {
1211
int[][] result = new int[n][n];
1312
int num = 1, left = 0, right = n - 1, top = 0, bottom = n - 1;
@@ -35,4 +34,5 @@ public int[][] generateMatrix(int n) {
3534
}
3635
return result;
3736
}
37+
3838
}

‎question0073_set_matrix_zeroes/Solution1.java

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

33
/**
4-
* https://leetcode-cn.com/problems/set-matrix-zeroes/
5-
*
64
* 用一个m * n的矩阵记录哪些位置是0。
75
*
86
* 时间复杂度和空间复杂度均是O(mn)，其中m是矩阵matrix的行数，n是矩阵matrix的列数。

‎question0073_set_matrix_zeroes/Solution2.java

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

33
/**
4-
* https://leetcode-cn.com/problems/set-matrix-zeroes/
5-
*
64
* 记录哪些行和列应该置为0。
75
*
86
* 时间复杂度为O(mn)，其中m是矩阵matrix的行数，n是矩阵matrix的列数。空间复杂度为O(m + n)。

‎question0073_set_matrix_zeroes/Solution3.java

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

33
/**
4-
* https://leetcode-cn.com/problems/set-matrix-zeroes/
5-
*
64
* 如果矩阵matrix的每一行都包含0，我们把整个矩阵都置为0。
75
*
86
* 如果并不是每一行都包含0，基于Solution2的思路，我们需要用一些标记来标识某一行或是某一列是否存在0。其实Solution2的思路可以进一步改进。

‎question0082/ListNode.java renamed to ‎question0082_remove_duplicates_from_sorted_list_ii/ListNode.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
1-
package question0082;
1+
package question0082_remove_duplicates_from_sorted_list_ii;
22

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

78
ListNode(int x) {
89
val = x;
910
}
11+
1012
}

‎question0082/Solution.java renamed to ‎question0082_remove_duplicates_from_sorted_list_ii/Solution.java

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,14 @@
1-
package question0082;
1+
package question0082_remove_duplicates_from_sorted_list_ii;
22

33
/**
44
* 链表相关的题，多画图一定能出来。
5-
* <p>
5+
*
66
* 时间复杂度是O(n)，其中n为链表中的节点个数。空间复杂度是O(1)。
7-
* <p>
7+
*
88
* 执行用时：2ms，击败91.09%。消耗内存：37.1MB，击败56.19%。
99
*/
1010
public class Solution {
11+
1112
public ListNode deleteDuplicates(ListNode head) {
1213
//对链表为空或链表中只有一个节点的情况进行特殊处理
1314
if (head == null || head.next == null) {
@@ -39,4 +40,5 @@ public ListNode deleteDuplicates(ListNode head) {
3940
}
4041
return dummyHead.next;
4142
}
43+
4244
}

‎question0092_reverse_linked_list_ii/ListNode.java

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

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

67
ListNode next;
78

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

‎question0092_reverse_linked_list_ii/Solution1.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
* 执行用时：0ms，击败100.00%。消耗内存：34.1MB，击败89.26%。
99
*/
1010
public class Solution1 {
11+
1112
public ListNode reverseBetween(ListNode head, int m, int n) {
1213
ListNode dummyHead = new ListNode(-1);
1314
dummyHead.next = head;
@@ -40,4 +41,5 @@ private ListNode movePoint(ListNode cur, int step) {
4041
}
4142
return cur;
4243
}
44+
4345
}

‎question0092_reverse_linked_list_ii/Solution2.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
* 执行用时：0ms，击败100.00%。消耗内存：34.1MB，击败89.26%。
99
*/
1010
public class Solution2 {
11+
1112
public ListNode reverseBetween(ListNode head, int m, int n) {
1213
ListNode dummyHead = new ListNode(-1);
1314
dummyHead.next = head;
@@ -46,4 +47,5 @@ private ListNode movePoint(ListNode cur, int step) {
4647
}
4748
return cur;
4849
}
50+
4951
}

‎question0115_distinct_subsequences/Solution.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package question0115_distinct_subsequences;
2+
3+
public class Solution {
4+
5+
public int numDistinct(String s, String t) {
6+
int[][] dp = new int[s.length() + 1][t.length() + 1];
7+
for (int i = 0; i < dp.length; i++) {
8+
dp[i][t.length()] = 1;
9+
}
10+
for (int i = s.length() - 1; i >= 0; i--) {
11+
for (int j = t.length() - 1; j >= 0; j--) {
12+
dp[i][j] = dp[i + 1][j];
13+
if (s.charAt(i) == t.charAt(j)) {
14+
dp[i][j] += dp[i + 1][j + 1];
15+
}
16+
}
17+
}
18+
return dp[0][0];
19+
}
20+
21+
}

‎question0150_evaluate_reverse_polish_notation/Solution.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package question0150_evaluate_reverse_polish_notation;
2+
3+
import java.util.LinkedList;
4+
5+
public class Solution {
6+
7+
public int evalRPN(String[] tokens) {
8+
LinkedList<Integer> stack = new LinkedList<>();
9+
for (String string : tokens) {
10+
switch (string) {
11+
case "+":
12+
stack.push(stack.pop() + stack.pop());
13+
break;
14+
case "-":
15+
stack.push(-stack.pop() + stack.pop());
16+
break;
17+
case "*":
18+
stack.push(stack.pop() * stack.pop());
19+
break;
20+
case "/":
21+
Integer num1 = stack.pop();
22+
Integer num2 = stack.pop();
23+
stack.push(num2 / num1);
24+
break;
25+
default:
26+
stack.push(Integer.parseInt(string));
27+
}
28+
}
29+
return stack.pop();
30+
}
31+
32+
}

‎question191/Solution1.java renamed to ‎question0191_number_of_1_bits/Solution1.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
1-
package question191;
1+
package question0191_number_of_1_bits;
22

33
public class Solution1 {
4+
45
public int hammingWeight(int n) {
56
int count = 0;
67
for (int i = 0; i < 32; i++) {
@@ -10,4 +11,5 @@ public int hammingWeight(int n) {
1011
}
1112
return count;
1213
}
14+
1315
}

‎question0191_number_of_1_bits/Solution2.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package question0191_number_of_1_bits;
2+
3+
public class Solution2 {
4+
5+
public int hammingWeight(int n) {
6+
int result = 0;
7+
while (n != 0) {
8+
n &= n - 1; // n & (n - 1) 的运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果
9+
result++;
10+
}
11+
return result;
12+
}
13+
14+
}

‎question0191_number_of_1_bits/Solution3.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package question0191_number_of_1_bits;
2+
3+
public class Solution3 {
4+
5+
public int hammingWeight(int n) {
6+
return Integer.bitCount(n);
7+
}
8+
9+
}

‎question0341_flatten_nested_list_iterator/NestedInteger.java

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package question0341_flatten_nested_list_iterator;
2+
3+
import java.util.List;
4+
5+
public interface NestedInteger {
6+
7+
// @return true if this NestedInteger holds a single integer, rather than a nested list.
8+
public boolean isInteger();
9+
10+
// @return the single integer that this NestedInteger holds, if it holds a single integer
11+
// Return null if this NestedInteger holds a nested list
12+
public Integer getInteger();
13+
14+
// @return the nested list that this NestedInteger holds, if it holds a nested list
15+
// Return null if this NestedInteger holds a single integer
16+
public List<NestedInteger> getList();
17+
18+
}

‎question0341_flatten_nested_list_iterator/NestedIterator.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package question0341_flatten_nested_list_iterator;
2+
3+
import java.util.Iterator;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
public class NestedIterator implements Iterator<Integer> {
8+
9+
private LinkedList<Integer> linkedList = new LinkedList<>();
10+
11+
public NestedIterator(List<NestedInteger> nestedList) {
12+
flatten(nestedList);
13+
}
14+
15+
private void flatten(List<NestedInteger> nestedList) {
16+
for (NestedInteger nestedInteger : nestedList) {
17+
if (nestedInteger.isInteger()) {
18+
linkedList.addLast(nestedInteger.getInteger());
19+
} else {
20+
flatten(nestedInteger.getList());
21+
}
22+
}
23+
}
24+
25+
@Override
26+
public Integer next() {
27+
return linkedList.pollFirst();
28+
}
29+
30+
@Override
31+
public boolean hasNext() {
32+
return !linkedList.isEmpty();
33+
}
34+
35+
}

‎question0456_132_pattern/132模式.md

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

‎question0456_132_pattern/Solution.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,14 @@
33
import java.util.Stack;
44

55
/**
6-
* 栈的应用。
6+
* 单调栈。
77
*
88
* 时间复杂度和空间复杂度均是O(n)，其中n为nums数组的长度。
99
*
1010
* 执行用时：8ms，击败95.87%。消耗内存：42.4MB，击败5.45%。
1111
*/
1212
public class Solution {
13+
1314
public boolean find132pattern(int[] nums) {
1415
int n;
1516
if (null == nums || (n = nums.length) < 3) {
@@ -37,4 +38,5 @@ public boolean find132pattern(int[] nums) {
3738
}
3839
return false;
3940
}
41+
4042
}

0 commit comments

Comments
 (0)