Skip to content

Commit 0530dc0

Browse files
dingjikerbodingjikerbo
committed
fd
1 parent 0108a40 commit 0530dc0

3 files changed

Lines changed: 88 additions & 19 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -387,6 +387,7 @@
387387
|654|[Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/description/)|[Java](leetcode/solution/src/MaximumBinaryTree.java)|100||
388388
|669|[Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/)|[Java](leetcode/solution/src/TrimABinarySearchTree.java)|100||
389389
|681|[Next Closest Time](https://leetcode.com/problems/next-closest-time/)|[Java](leetcode/solution/src/NextClosestTime.java)|80|这题多做几遍|
390+
|683|[K Empty Slots](https://leetcode.com/problems/k-empty-slots/)|[Java](leetcode/solution/src/KEmptySlots.java)|80||
390391
|684|[Redundant Connection](https://leetcode.com/problems/redundant-connection/)| [Java](leetcode/solution/src/RedundantConnection.java)|||
391392
|695|[Max Area of Island](https://leetcode.com/problems/max-area-of-island/)|[Java](leetcode/solution/src/MaxAreaOfIsland.java)|100||
392393
|703|[Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/)|[Java](leetcode/solution/src/KthLargestElementInAStream.java)|100||

‎leetcode/solution/src/KEmptySlots.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
import java.util.TreeSet;
2+
3+
/**
4+
* 这题意思是第i盆花第flowers[i]天开，问第几天的时候存在这么一种情况：有两盆已经开的花中间恰好隔着k盆没开的花
5+
*/
6+
public class KEmptySlots {
7+
8+
public int kEmptySlots(int[] flowers, int k) {
9+
TreeSet<Integer> map = new TreeSet<>();
10+
for (int i = 0; i < flowers.length; i++) {
11+
int flower = flowers[i] - 1;
12+
map.add(flower);
13+
14+
Integer key = map.ceiling(flower + 1);
15+
if (key != null && key - flower == k + 1) {
16+
return i + 1;
17+
}
18+
key = map.floor(flower - 1);
19+
if (key != null && flower - key == k + 1) {
20+
return i + 1;
21+
}
22+
}
23+
24+
return -1;
25+
}
26+
27+
/**
28+
* 时间复杂度O(n)
29+
* days表示第i盆花第几天开
30+
* 天数越大，表示花开的越晚
31+
* 对于(left, right)这个区间，(这个区间刚好相隔k)，如果days值都比left和right大，说明(left,right)区间的花都开的比left和right晚
32+
* 换言之，在left和right开的时候，中间的花都没开，而left和right刚好相隔k，符合条件。
33+
* 我们选择left和right之中较大的那个值作为备选结果之一，选取较大是因为表示发生的较晚，刚好触发条件
34+
* 但是题目要返回最早的那一天，所以我们要继续遍历下去
35+
*
36+
* 此外还要注意，当发现(left,right)区间存在不符合条件的情况，则sliding window要从i开始，因为如果从(left,i)区间的任何一个数开始，都不会符合条件
37+
* 另外当找到一组符合条件的情况后，sliding window也要从i开始，也就是从right开始，假如从left+1开始，则当前的right就不符合大于sliding window两端的条件了
38+
*/
39+
public int kEmptySlots2(int[] flowers, int k) {
40+
int[] days = new int[flowers.length];
41+
for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
42+
int left = 0, right = k + 1, res = Integer.MAX_VALUE;
43+
for (int i = left + 1; i <= right && right < days.length; i++) {
44+
if (i == right) {
45+
res = Math.min(res, Math.max(days[left], days[right]));
46+
left = i;
47+
right = k + 1 + i;
48+
continue;
49+
}
50+
51+
if (days[i] < days[left] || days[i] < days[right]) {
52+
left = i;
53+
right = k + 1 + i;
54+
}
55+
}
56+
return (res == Integer.MAX_VALUE) ? -1 : res;
57+
}
58+
}

‎leetcode/src/Main.java‎

Lines changed: 29 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,46 @@
1+
import com.sun.org.apache.xpath.internal.operations.Bool;
2+
13
import java.util.*;
24

35
public class Main {
46

57
public static class Solution {
68

7-
public String nearestPalindromic(String n) {
8-
long val = Long.parseLong(n);
9-
for (int i = 0; ; i++) {
10-
long k1 = val - i, k2 = val + i;
11-
if (isPalindrome(k1)) {
12-
return String.valueOf(k1);
13-
}
14-
if (isPalindrome(k2)) {
15-
return String.valueOf(k2);
9+
public int kEmptySlots(int[] flowers, int k) {
10+
int[] days = new int[flowers.length];
11+
for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
12+
int left = 0, right = k + 1, res = Integer.MAX_VALUE;
13+
for (int i = left + 1; i <= right && right < days.length; i++) {
14+
if (i == right) {
15+
res = Math.min(res, Math.max(days[left], days[right]));
1616
}
17-
}
18-
}
1917

20-
private boolean isPalindrome(long k) {
21-
long x = k, rev = 0;
22-
for ( ; k > 0; ) {
23-
rev = rev * 10 + k % 10;
24-
k /= 10;
18+
if (days[i] < days[left] || days[i] < days[right]) {
19+
left = i;
20+
right = k + 1 + i;
21+
}
2522
}
26-
return rev == x;
23+
return (res == Integer.MAX_VALUE) ? -1 : res;
2724
}
2825

2926
}
3027

3128
public static void main(String[] args) {
3229
Solution solution = new Solution();
33-
String s = solution.nearestPalindromic("807045053224792883");
34-
System.out.println(s);
30+
31+
TreeMap<Integer, Boolean> map = new TreeMap<>();
32+
int[] nums = {4, 1, 7, 5, 2, 8, 10, 0};
33+
for (int n : nums) {
34+
map.put(n, true);
35+
}
36+
for (int k : map.keySet()) {
37+
System.out.print(k + " ");
38+
}
39+
40+
int n = solution.kEmptySlots(new int[]{
41+
1, 2, 3
42+
}, 1);
43+
System.out.println(n);
44+
3545
}
3646
}

0 commit comments

Comments
 (0)