Skip to content

Commit 1d96410

Browse files
author
zhuchen
committed
2022-1-25
1 parent 2a68506 commit 1d96410

File tree

20 files changed

+503
-260
lines changed

20 files changed

+503
-260
lines changed

‎lcp45/Solution.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package lcp45;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class Solution {
7+
8+
private int[][] terrain;
9+
10+
private int[][] obstacle;
11+
12+
private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
13+
14+
private int n, m;
15+
16+
private boolean[][][] visited;
17+
18+
public int[][] bicycleYard(int[] position, int[][] terrain, int[][] obstacle) {
19+
this.terrain = terrain;
20+
this.obstacle = obstacle;
21+
n = terrain.length;
22+
m = terrain[0].length;
23+
visited = new boolean[102][102][102];
24+
visited[position[0]][position[1]][1] = true;
25+
List<int[]> list = new ArrayList<>();
26+
bicycleYardHelper(position[0], position[1], 1);
27+
for (int i = 0; i < n; i++) {
28+
for (int j = 0; j < m; j++) {
29+
if (visited[i][j][1] && !(i == position[0] && j == position[1])) {
30+
list.add(new int[] {i, j});
31+
}
32+
}
33+
}
34+
int[][] result = new int[list.size()][2];
35+
for (int i = 0; i < result.length; i++) {
36+
result[i] = list.get(i);
37+
}
38+
return result;
39+
}
40+
41+
private void bicycleYardHelper(int x, int y, int speed) {
42+
for (int[] direction : DIRECTIONS) {
43+
int nextX = x + direction[0], nextY = y + direction[1];
44+
if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) {
45+
continue;
46+
}
47+
int nextSpeed = speed + (terrain[x][y] - terrain[nextX][nextY] - obstacle[nextX][nextY]);
48+
if (nextSpeed > 0 && !visited[nextX][nextY][nextSpeed]) {
49+
visited[nextX][nextY][nextSpeed] = true;
50+
bicycleYardHelper(nextX, nextY, nextSpeed);
51+
}
52+
}
53+
}
54+
55+
}

‎question0005_longest_palindromic_substring/Solution5.java

Lines changed: 14 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -3,86 +3,34 @@
33
public class Solution5 {
44

55
public String longestPalindrome(String s) {
6-
// 特判
7-
int len = s.length();
8-
if (len < 2) {
9-
return s;
6+
StringBuilder sb = new StringBuilder();
7+
for (int i = 0; i < s.length(); i++) {
8+
sb.append("#").append(s.charAt(i));
109
}
11-
12-
// 得到预处理字符串
13-
String str = addBoundaries(s, '#');
14-
// 新字符串的长度
15-
int sLen = 2 * len + 1;
16-
17-
// 数组 p 记录了扫描过的回文子串的信息
18-
int[] p = new int[sLen];
19-
20-
// 双指针，它们是一一对应的，须同时更新
21-
int maxRight = 0;
22-
int center = 0;
23-
24-
// 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
25-
int maxLen = 1;
26-
// 原始字符串的最长回文子串的起始位置，与 maxLen 必须同时更新
27-
int start = 0;
28-
29-
for (int i = 0; i < sLen; i++) {
10+
sb.append("#");
11+
int maxRight = 0, center = 0, maxLen = 1, startPos = 0;
12+
int[] p = new int[sb.length()];
13+
for (int i = 0; i < sb.length(); i++) {
3014
if (i < maxRight) {
3115
int mirror = 2 * center - i;
32-
// 这一行代码是 Manacher 算法的关键所在，要结合图形来理解
33-
p[i] = Math.min(maxRight - i, p[mirror]);
16+
p[i] = Math.min(p[mirror], maxRight - i);
3417
}
35-
36-
// 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中
37-
int left = i - (1 + p[i]);
38-
int right = i + (1 + p[i]);
39-
40-
// left >= 0 && right < sLen 保证不越界
41-
// str.charAt(left) == str.charAt(right) 表示可以扩散 1 次
42-
while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
43-
p[i]++;
18+
int left = i - (p[i] + 1), right = i + (p[i] + 1);
19+
while (left >= 0 && right < sb.length() && sb.charAt(left) == sb.charAt(right)) {
4420
left--;
4521
right++;
46-
22+
p[i]++;
4723
}
48-
// 根据 maxRight 的定义，它是遍历过的 i 的 i + p[i] 的最大者
49-
// 如果 maxRight 的值越大，进入上面 i < maxRight 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了
5024
if (i + p[i] > maxRight) {
51-
// maxRight 和 center 需要同时更新
5225
maxRight = i + p[i];
5326
center = i;
5427
}
5528
if (p[i] > maxLen) {
56-
// 记录最长回文子串的长度和相应它在原始字符串中的起点
5729
maxLen = p[i];
58-
start = (i - maxLen) / 2;
30+
startPos = (i - p[i]) / 2;
5931
}
6032
}
61-
return s.substring(start, start + maxLen);
62-
}
63-
64-
/**
65-
* 创建预处理字符串
66-
*
67-
* @param s 原始字符串
68-
* @param divide 分隔字符
69-
* @return 使用分隔字符处理以后得到的字符串
70-
*/
71-
private String addBoundaries(String s, char divide) {
72-
int len = s.length();
73-
if (len == 0) {
74-
return "";
75-
}
76-
if (s.indexOf(divide) != -1) {
77-
throw new IllegalArgumentException("参数错误，您传递的分割字符，在输入字符串中存在！");
78-
}
79-
StringBuilder stringBuilder = new StringBuilder();
80-
for (int i = 0; i < len; i++) {
81-
stringBuilder.append(divide);
82-
stringBuilder.append(s.charAt(i));
83-
}
84-
stringBuilder.append(divide);
85-
return stringBuilder.toString();
33+
return s.substring(startPos, startPos + maxLen);
8634
}
8735

88-
}
36+
}

‎question0219/Solution.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package question0219;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
public class Solution {
7+
8+
public boolean containsNearbyDuplicate(int[] nums, int k) {
9+
Map<Integer, Integer> window = new HashMap<>();
10+
int left = 0, right = -1;
11+
while (right + 1 < nums.length) {
12+
right++;
13+
window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);
14+
if (right - left > k) {
15+
window.put(nums[left], window.get(nums[left]) - 1);
16+
left++;
17+
}
18+
if (window.get(nums[right]) > 1) {
19+
return true;
20+
}
21+
}
22+
return false;
23+
}
24+
25+
}

‎question0373_find_k_pairs_with_smallest_sums/Solution3.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -30,11 +30,11 @@ public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
3030
return result;
3131
}
3232

33-
// flag 是 0，上一次移动的不是 num2，此次可以移动 num1 或 num2；flag 是 1，上一次移动的是 num2，此次只能移动 num2
34-
private static List<Integer> getList(int num1, int num2, int flag) {
33+
// flag 是 0，上一次移动的不是 index2，此次可以移动 index1 或 index2；flag 是 1，上一次移动的是 index2，此次只能移动 index2
34+
private static List<Integer> getList(int index1, int index2, int flag) {
3535
List<Integer> list = new ArrayList<>();
36-
list.add(num1);
37-
list.add(num2);
36+
list.add(index1);
37+
list.add(index2);
3838
list.add(flag);
3939
return list;
4040
}

‎question0382_linked_list_random_node/Solution.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -19,18 +19,17 @@
1919
* 时间复杂度是O(n)。空间复杂度是O(1)。
2020
*/
2121
public class Solution {
22+
2223
private ListNode head;
2324

24-
/** @param head The linked list's head.
25-
Note that the head is guaranteed to be not null, so it contains at least one node. */
2625
public Solution(ListNode head) {
2726
this.head = head;
2827
}
2928

3029
/** Returns a random node's value. */
3130
public int getRandom() {
32-
ListNode cur = head.next;
33-
int result = head.val, i = 2;
31+
ListNode cur = head;
32+
int result = 0, i = 1;
3433
Random random = new Random();
3534
while (null != cur) {
3635
if (random.nextInt(i) == 0) {
@@ -41,4 +40,5 @@ public int getRandom() {
4140
}
4241
return result;
4342
}
43+
4444
}

‎question0539_minimum_time_difference/Solution.java

Lines changed: 18 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -3,27 +3,25 @@
33
import java.util.Collections;
44
import java.util.List;
55

6-
/**
7-
* 排序后计算。
8-
*
9-
* 时间复杂度是O(nlogn)，其中n为timePoints集合的长度。空间复杂度是O(1)。
10-
*
11-
* 执行用时：15ms，击败69.70%。消耗内存：38.5MB，击败97.65%。
12-
*/
136
public class Solution {
14-
public int findMinDifference(List<String> timePoints) {
15-
Collections.sort(timePoints);
16-
int result = calculateGap(timePoints.get(0), timePoints.get(timePoints.size() - 1));
17-
for (int i = 0; i < timePoints.size() - 1; i++) {
18-
result = Math.min(result, calculateGap(timePoints.get(i), timePoints.get(i + 1)));
19-
}
20-
return result;
21-
}
227

23-
private int calculateGap(String s1, String s2) {
24-
int h1 = Integer.parseInt(s1.substring(0, 2)), m1 = Integer.parseInt(s1.substring(3, 5)),
25-
h2 = Integer.parseInt(s2.substring(0, 2)), m2 = Integer.parseInt(s2.substring(3, 5)),
26-
gap = Math.abs(h1 * 60 + m1 - h2 * 60 - m2);
27-
return Math.min(gap, 24 * 60 - gap);
8+
public int findMinDifference(List<String> timePoints) {
9+
if (timePoints.size() > 1440) {
10+
return 0;
11+
}
12+
Collections.sort(timePoints);
13+
int result = calculateGap(timePoints.get(0), timePoints.get(timePoints.size() - 1));
14+
for (int i = 0; i < timePoints.size() - 1; i++) {
15+
result = Math.min(result, calculateGap(timePoints.get(i), timePoints.get(i + 1)));
2816
}
17+
return result;
18+
}
19+
20+
private int calculateGap(String s1, String s2) {
21+
int h1 = Integer.parseInt(s1.substring(0, 2)), m1 = Integer.parseInt(s1.substring(3, 5)),
22+
h2 = Integer.parseInt(s2.substring(0, 2)), m2 = Integer.parseInt(s2.substring(3, 5)),
23+
gap = Math.abs(h1 * 60 + m1 - h2 * 60 - m2);
24+
return Math.min(gap, 24 * 60 - gap);
25+
}
26+
2927
}

‎question1044_longest_duplicate_substring/Solution4.java

Lines changed: 44 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -2,73 +2,84 @@
22

33
public class Solution4 {
44

5+
private int m, n;
6+
7+
private int[] x, y, t, sa;
8+
59
public String longestDupSubstring(String s) {
6-
int n = s.length() + 1;
7-
int i, j, p, m = 0;
10+
n = s.length() + 1;
811
int[] r = new int[n];
9-
for (i = 0; i < n - 1; i++) {
12+
for (int i = 0; i < n - 1; i++) {
1013
r[i] = s.charAt(i);
1114
m = Math.max(m, r[i]);
1215
}
1316
m++;
14-
int[] x = new int[n], y = new int[n], t, sa = new int[n], wv = new int[n], ws = new int[m];
15-
for (i = 0; i < n; i++) {
17+
x = new int[n];
18+
y = new int[n];
19+
sa = new int[n];
20+
for (int i = 0; i < n; i++) {
1621
x[i] = r[i];
17-
ws[x[i]]++;
18-
}
19-
for (i = 1; i < m; i++) {
20-
ws[i] += ws[i - 1];
22+
y[i] = i;
2123
}
22-
for (i = n - 1; i >= 0; i--) {
23-
sa[--ws[x[i]]] = i;
24-
}
25-
for (j = 1, p = 1; p < n; j *= 2, m = p) {
26-
for (p = 0, i = n - j; i < n; i++) {
24+
sort();
25+
for (int j = 1, p = 0; p < n; j *= 2, m = p) {
26+
p = 0;
27+
for (int i = n - j; i < n; i++) {
2728
y[p++] = i;
2829
}
29-
for (i = 0; i < n; i++) {
30+
for (int i = 0; i < n; i++) {
3031
if (sa[i] >= j) {
3132
y[p++] = sa[i] - j;
3233
}
3334
}
34-
for (i = 0; i < n; i++) {
35-
wv[i] = x[y[i]];
36-
}
37-
ws = new int[m];
38-
for (i = 0; i < n; i++) {
39-
ws[wv[i]]++;
40-
}
41-
for (i = 1; i < m; i++) {
42-
ws[i] += ws[i - 1];
43-
}
44-
for (i = n - 1; i >= 0; i--) {
45-
sa[--ws[wv[i]]] = y[i];
46-
}
47-
for (t = x, x = y, y = t, x[sa[0]] = 0, p = 1, i = 1; i < n; i++) {
48-
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
35+
sort();
36+
t = x;
37+
x = y;
38+
y = t;
39+
p = 1;
40+
x[sa[0]] = 0;
41+
for (int i = 1; i < n; i++) {
42+
x[sa[i]] = cmp(y, sa[i], sa[i - 1], j) ? p - 1 : p++;
4943
}
5044
}
5145
int[] height = getHeight(r, x, sa);
5246
int maxIndex = 0;
53-
for (i = 1; i < height.length; i++) {
47+
for (int i = 1; i < height.length; i++) {
5448
if (height[i] > height[maxIndex]) {
5549
maxIndex = i;
5650
}
5751
}
5852
return s.substring(sa[maxIndex], Math.min(s.length(), sa[maxIndex] + height[maxIndex]));
5953
}
6054

55+
private void sort() {
56+
int[] wv = new int[n];
57+
for (int i = 0; i < n; i++) {
58+
wv[i] = x[y[i]];
59+
}
60+
int[] ws = new int[m];
61+
for (int i = 0; i < n; i++) {
62+
ws[wv[i]]++;
63+
}
64+
for (int i = 1; i < m; i++) {
65+
ws[i] += ws[i - 1];
66+
}
67+
for (int i = n - 1; i >= 0; i--) {
68+
sa[--ws[wv[i]]] = y[i];
69+
}
70+
}
71+
6172
private static boolean cmp(int[] r, int a, int b, int l) {
6273
return r[a] == r[b] && r[a + l] == r[b + l];
6374
}
6475

6576
private static int[] getHeight(int[] r, int[] rankArray, int[] sufArray) {
6677
int[] height = new int[rankArray.length];
67-
for (int i = 0; i < height.length; i++) {
78+
for (int i = 0; i < rankArray.length; i++) {
6879
int rank = rankArray[i];
6980
if (rank > 0) {
7081
int index1 = sufArray[rank], index2 = sufArray[rank - 1];
71-
int j = i - 1 >= 0 ? Math.max(0, height[rankArray[i - 1]] - 1) : 0;
82+
int j = i > 0 ? Math.max(0, height[rankArray[i - 1]] - 1) : 0;
7283
while (index1 + j < r.length && index2 + j < r.length && r[index1 + j] == r[index2 + j]) {
7384
j++;
7485
}

0 commit comments

Comments
 (0)