Skip to content

Commit 54dc1a0

Browse files
617076674617076674
committed
2020-5-8
1 parent 0956fab commit 54dc1a0

File tree

14 files changed

+200
-175
lines changed

14 files changed

+200
-175
lines changed

‎contest/kmp/KMP.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package contest.kmp;
2+
3+
public class KMP {
4+
private int[][] dp;
5+
private String pat;
6+
7+
public KMP(String pat) {
8+
this.pat = pat;
9+
int M = pat.length();
10+
// dp[状态][字符] = 下个状态
11+
dp = new int[M][256];
12+
// base case
13+
dp[0][pat.charAt(0)] = 1;
14+
// 影子状态 X 初始为 0
15+
int X = 0;
16+
// 当前状态 j 从 1 开始
17+
for (int j = 1; j < M; j++) {
18+
for (int c = 0; c < 256; c++) {
19+
if (pat.charAt(j) == c)
20+
dp[j][c] = j + 1;
21+
else
22+
dp[j][c] = dp[X][c];
23+
}
24+
// 更新影子状态
25+
X = dp[X][pat.charAt(j)];
26+
System.out.println(X);
27+
}
28+
}
29+
30+
public static void main(String[] args) {
31+
KMP kmp = new KMP("ABABC");
32+
}
33+
34+
// public int search(String txt) {...}
35+
}

‎question0221_maximal_square/Solution.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package question0221_maximal_square;
2+
3+
/**
4+
* 动态规划。
5+
*
6+
* 状态定义：
7+
* dp[i][j]表示以matrix[i][j]为右下角的最大正方形边长。
8+
*
9+
* 初始化条件：
10+
* （1）当i == 0时，dp[0][j] = matrix[0][j] - '0'
11+
* （2）当j == 0时，dp[i][0] = matrix[i][0] - '0'
12+
*
13+
* 状态转移方程：
14+
* （1）当matrix[i][j] == '1`时，dp[i][j] = min(dp[i - 1][j - 1], max1, max2)，
15+
* 其中 max1 为第 j 列中从 i - 1 行往前的连续的 1 的个数， max2 为第 i 行中从 j - 1 列往前的连续的 1 的个数。
16+
* （2）当matrix[i][j] == '0'时，dp[i][j] = 0。
17+
*
18+
* 时间复杂度和空间复杂度均是O(m * n)，其中m为矩阵matrix的行数，n为矩阵matrix的列数。
19+
*
20+
* 执行用时：5ms，击败94.15%。消耗内存：42.7MB，击败62.50%。
21+
*/
22+
public class Solution {
23+
public int maximalSquare(char[][] matrix) {
24+
int m;
25+
if (null == matrix || (m = matrix.length) == 0) {
26+
return 0;
27+
}
28+
int n;
29+
if (null == matrix[0] || (n = matrix[0].length) == 0) {
30+
return 0;
31+
}
32+
int[][] dp = new int[m][n];
33+
int result = 0;
34+
for (int i = 0; i < n; i++) {
35+
if (matrix[0][i] == '1') {
36+
dp[0][i] = 1;
37+
result = 1;
38+
}
39+
}
40+
for (int i = 0; i < m; i++) {
41+
if (matrix[i][0] == '1') {
42+
dp[i][0] = 1;
43+
result = 1;
44+
}
45+
}
46+
for (int i = 1; i < m; i++) {
47+
for (int j = 1; j < n; j++) {
48+
if (matrix[i][j] == '1') {
49+
int max1 = 0, max2 = 0;
50+
for (int k = i - 1; k >= 0 && matrix[k][j] == '1'; k--) {
51+
max1++;
52+
}
53+
for (int k = j - 1; k >= 0 && matrix[i][k] == '1'; k--) {
54+
max2++;
55+
}
56+
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(max1, max2)) + 1;
57+
result = Math.max(result, dp[i][j] * dp[i][j]);
58+
}
59+
}
60+
}
61+
return result;
62+
}
63+
}

‎question0319/Solution1.java

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

‎question0319/Solution2.java renamed to ‎question0319_bulb_switcher/Solution.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package question0319;
1+
package question0319_bulb_switcher;
22

33
/**
44
* 第1个灯泡会在第1轮反转。
@@ -27,8 +27,8 @@
2727
*
2828
* 执行用时：0ms，击败100.00%。消耗内存：34.1MB，击败11.38%。
2929
*/
30-
public class Solution2 {
30+
public class Solution {
3131
public int bulbSwitch(int n) {
3232
return (int) Math.sqrt(n);
3333
}
34-
}
34+
}

‎question0435/Solution1.java renamed to ‎question0435_non_overlapping_intervals/Solution1.java

Lines changed: 10 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,22 @@
1-
package question0435;
1+
package question0435_non_overlapping_intervals;
22

33
import java.util.Arrays;
44
import java.util.Comparator;
55

66
/**
7-
* @author qianyihui
8-
* @date 2019-08-19
9-
*
107
* 首先对区间按左值由小到大进行排序。
118
*
129
* 动态规划。
1310
*
1411
* 状态定义：
15-
* dp[i]:考虑第[0, i]个区间，所能保留的最大区间数目。
12+
* dp[i]表示考虑第[0, i]个区间，所能保留的最大区间数目。
1613
*
17-
* 状态转移：
18-
* 当i == 0时，dp[0] = 1。
14+
* 初始化条件：
15+
* 当 i == 0 时， dp[0] = 1。
1916
*
20-
* 当i > 0时，我们可以不考虑第i个区间，那么dp[i] = dp[i - 1]。
21-
* 我们也可以考虑第i个区间，那么dp[i] = max(dp[k] + 1, dp[i])，其中k∈[0, i - 1]，且第k个区间与第i个区间不重合
17+
* 状态转移：
18+
* （1）我们可以不考虑第i个区间，那么dp[i] = dp[i - 1]。
19+
* （2）我们也可以考虑第i个区间，那么dp[i] = max(dp[k] + 1, dp[i])，其中k∈[0, i - 1]，且第k个区间与第i个区间不重合
2220
*
2321
* 时间复杂度是O(n ^ 2)，其中n为区间个数。空间复杂度是O(n)。
2422
*
@@ -33,16 +31,16 @@ public int eraseOverlapIntervals(int[][] intervals) {
3331
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
3432
int[] dp = new int[n];
3533
dp[0] = 1;
36-
int max = 1;
34+
int result = 1;
3735
for (int i = 1; i < n; i++) {
3836
dp[i] = dp[i - 1]; //不考虑第i个区间
3937
for (int k = 0; k < i; k++) { //考虑第i个区间
4038
if (intervals[k][1] <= intervals[i][0]) {
4139
dp[i] = Math.max(dp[k] + 1, dp[i]);
4240
}
4341
}
44-
max = Math.max(dp[i], max);
42+
result = Math.max(dp[i], result);
4543
}
46-
return n - max;
44+
return n - result;
4745
}
4846
}

‎question0435/Solution2.java renamed to ‎question0435_non_overlapping_intervals/Solution2.java

Lines changed: 4 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,9 @@
1-
package question0435;
1+
package question0435_non_overlapping_intervals;
22

33
import java.util.Arrays;
44
import java.util.Comparator;
55

66
/**
7-
* @author qianyihui
8-
* @date 2019-08-19
9-
*
107
* 首先对区间按左值由小到大进行排序。
118
*
129
* 贪心算法。
@@ -27,15 +24,15 @@
2724
*
2825
* 时间复杂度是O(nlogn)，其中n为区间个数。空间复杂度是O(1)。
2926
*
30-
* 执行用时：79ms，击败20.94%。消耗内存：39.2MB，击败48.17%。
27+
* 执行用时：2ms，击败93.10%。消耗内存：39.8MB，击败8.33%。
3128
*/
3229
public class Solution2 {
3330
public int eraseOverlapIntervals(int[][] intervals) {
3431
int n;
3532
if (null == intervals || (n = intervals.length) == 0) {
3633
return 0;
3734
}
38-
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
35+
Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
3936
int result = 0, pre = 0;
4037
for (int i = 1; i < n; i++) {
4138
if (intervals[pre][1] > intervals[i][0]) {
@@ -49,4 +46,4 @@ public int eraseOverlapIntervals(int[][] intervals) {
4946
}
5047
return result;
5148
}
52-
}
49+
}

‎question0435_non_overlapping_intervals/Solution3.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package question0435_non_overlapping_intervals;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
6+
/**
7+
* 计算最多有多少个区间不相交。
8+
*
9+
* 算法如下：
10+
* （1）将区间按结束时间从小到大排序。
11+
* （2）从区间集合 intervals 中选择一个区间 interval，这个 interval 是在当前所有区间中结束最早的。
12+
* （3）把所有与 interval 相交的区间从区间集合 intervals 中删除。
13+
* （4）重复步骤 （2） 和 （3），直到 intervals 为空为止。之前选出的 interval 就是最大不相交子集。
14+
*
15+
* 时间复杂度是O(nlogn)，其中n为区间个数。空间复杂度是O(1)。
16+
*
17+
* 执行用时：5ms，击败48.37%。消耗内存：39.6MB，击败8.33%。
18+
*/
19+
public class Solution3 {
20+
public int eraseOverlapIntervals(int[][] intervals) {
21+
if (null == intervals || intervals.length == 0) {
22+
return 0;
23+
}
24+
Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[1]));
25+
int count = 1, end = intervals[0][1];
26+
for (int[] interval : intervals) {
27+
if (interval[0] >= end) {
28+
count++;
29+
end = interval[1];
30+
}
31+
}
32+
return intervals.length - count;
33+
}
34+
}

‎question0452_minimum_number_of_arrows_to_burst_balloons/Solution.java

Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -6,18 +6,28 @@
66
/**
77
* 贪心算法。
88
*
9+
* 如果最多有 n 个不重叠的区间，那么就至少需要 n 个箭头穿透所有区间。
10+
*
11+
* 算法如下：
12+
* （1）将区间按结束时间从小到大排序。
13+
* （2）从区间集合 points 中选择一个区间 point，这个 point 是在当前所有区间中结束最早的。
14+
* （3）把所有与 point 相交的区间从区间集合 points 中删除。
15+
* （4）重复步骤 （2） 和 （3），直到 points 为空为止。之前选出的 point 就是最大不相交子集。
16+
*
917
* 时间复杂度是O(nlogn)，其中n为points数组的长度。空间复杂度是O(1)。
1018
*
1119
* 执行用时：25ms，击败80.31%。消耗内存：46.4MB，击败79.63%。
1220
*/
1321
public class Solution {
1422
public int findMinArrowShots(int[][] points) {
23+
if (null == points || points.length == 0) {
24+
return 0;
25+
}
1526
Arrays.sort(points, Comparator.comparingInt(point -> point[1])); //按右端点从小到大排序
16-
int result = 0;
17-
long last = Long.MIN_VALUE; //记录上一箭射出的位置
27+
int result = 1, end = points[0][1];
1828
for (int[] point : points) {
19-
if (point[0] > last) {
20-
last = point[1];
29+
if (point[0] > end) {
30+
end = point[1];
2131
result++;
2232
}
2333
}

‎question0877/Solution4.java

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

‎question0877/Solution1.java renamed to ‎question0877_stone_game/Solution1.java

Lines changed: 4 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,6 @@
1-
package question0877;
1+
package question0877_stone_game;
22

33
/**
4-
* @author qianyihui
5-
* @date 2019-08-19
6-
*
74
* 记忆化搜索。
85
*
96
* 时间复杂度和空间复杂度均是O(n ^ 2)，其中n为piles数组的长度。
@@ -23,12 +20,8 @@ public boolean stoneGame(int[] piles) {
2320
for (int i = 1; i < n; i++) {
2421
sum[i] = sum[i - 1] + piles[i];
2522
}
26-
int first = stoneGame(piles, 0, n - 1);
27-
int second = sum[n - 1] - first;
28-
if (first > second) {
29-
return true;
30-
}
31-
return false;
23+
int score = stoneGame(piles, 0, n - 1);
24+
return score > sum[n - 1] - score;
3225
}
3326

3427
/**
@@ -49,4 +42,4 @@ private int stoneGame(int[] piles, int left, int right) {
4942
}
5043
return Math.max(total - dp[left + 1][right], total - dp[left][right - 1]);
5144
}
52-
}
45+
}

0 commit comments

Comments
 (0)