方法一：暴力模拟
比赛直接暴力模拟。
1
2
3
4
5
6
7
8
9
10
| class Solution {
public String finalString(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c != 'i') sb.append(c);
else sb.reverse();
}
return sb.toString();
}
}
|
复杂度分析
- 时间复杂度：\(O(n^{2})\)。
- 空间复杂度：\(O(n)\)。
方法二：双端队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String finalString(String s) {
int n = s.length();
boolean reverse = false;
Deque<Character> q = new LinkedList<>();
for (char c : s.toCharArray()) {
if (c == 'i') reverse = !reverse;
else if (reverse) q.offerFirst(c);
else q.offerLast(c);
}
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
if (reverse) sb.append(q.pollLast());
else sb.append(q.pollFirst());
}
return sb.toString();
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\)。
- 空间复杂度：\(O(n)\)。
方法一：正难则反
题目要求将数组拆分为单个元素，因为从拆分角度不太好模拟，所以可以考虑怎么将单个元素合并为整个数组。如果数组长度小于等于 \(2\)，则必定满足要求。如果数组长度大于 \(2\)，要想将所有元素合并成完整的数组，则必须有一个大于等于 \(m\) 的合并。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean canSplitArray(List<Integer> nums, int m) {
int n = nums.size();
if (n <= 2) return true;
for (int i = 1; i < n; i++) {
if (nums.get(i) + nums.get(i - 1) >= m) {
return true;
}
}
return false;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\)。
- 空间复杂度：\(O(1)\)。
纯暴力做法是使用 \(O(n^{2})\) 的时间判断当前点的的安全系数是否大于等于指定的安全系数，总时间复杂度是 \(O(n^{4}\log n)\)。而我在比赛时预处理了一下小偷的位置，最坏情况其实也是 \(O(n^{4}\log n)\)，结果通过了，我想大概是因为如果小偷的数量很多，那么 BFS 的限制就多，如果小偷的数量很少，那么 BFS 的限制就少，所以复杂度也不会真的到达最坏情况吧。比较好的做法是多源 BFS + 二分，以每个小偷为起点进行多源 BFS，标记每个位置的最小安全系数，然后在二分的 BFS 时就可以花 \(O(1)\) 的时间判断当前点是否合法。
方法一：多源 BFS + 二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Solution {
int n;
int[][] dis;
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public int maximumSafenessFactor(List<List<Integer>> grid) {
n = grid.size();
dis = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dis[i], -1);
}
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 1) {
dis[i][j] = 0;
q.offer(new int[]{i, j});
}
}
}
while (!q.isEmpty()) {
int[] p = q.poll();
int x = p[0], y = p[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || dis[nx][ny] >= 0) continue;
dis[nx][ny] = dis[x][y] + 1;
q.offer(new int[]{nx, ny});
}
}
int lo = 0, hi = Math.min(dis[0][0], dis[n - 1][n - 1]);
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) lo = mid + 1;
else hi = mid - 1;
}
return hi;
}
private boolean check(int mid) {
boolean[][] vis = new boolean[n][n];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0});
vis[0][0] = true;
while (!q.isEmpty()) {
int[] p = q.poll();
int x = p[0], y = p[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || dis[nx][ny] < mid) continue;
vis[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
return vis[n - 1][n - 1];
}
}
|
复杂度分析
- 时间复杂度：\(O(n^{2}\log n)\)。
- 空间复杂度：\(O(n^{2})\)。
方法一：贪心
刚看见题目不知道怎么做，想了想动态规划好像不太行，一个是时间复杂度不行，一个是找不到递推关系（感觉）。然后就想这个数据量，可以排序试一下，然后不知怎么就想到正确答案了。首先贪心取利润最大的 \(k\) 个元素，然后每当遇到一个未选过的类别，则用其替换之前的重复类别中的利润最小的元素，每次计算都更新答案。具体分析如下：
- 如果第 \(k+1\) 个元素的类别是重复的，那么使用其替换之前的元素不会使优雅度变大，因为
distinct_categories 不变，并且数组元素按照利润降序排列，所以 total_profit 可能会变小或者不变。
- 反之，我们可以尝试使用当前元素替换之前的元素：① 如果替换之前不重复的元素，那么显然不会优雅度不会变大；② 如果替换之前重复的元素，那么肯定优先选择利润最小的重复元素，
distinct_categories 变大，total_profit 变小，优雅度有变大的可能。
反复执行上述操作，就一定可以遍历到最优的情况。比赛时代码很乱，赛后参考了灵神的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public long findMaximumElegance(int[][] items, int k) {
int n = items.length;
long ans = 0, sum = 0;
Arrays.sort(items, (a, b) -> b[0] - a[0]);
HashSet<Integer> set = new HashSet<>();
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int profit = items[i][0], category = items[i][1];
if (i < k) {
sum += profit;
if (!set.add(category)) q.push(profit);
} else if (!q.isEmpty() && set.add(category)) {
sum += profit - q.pop();
}
ans = Math.max(ans, sum + (long) set.size() * set.size());
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n\log n)\)。
- 空间复杂度：\(O(n)\)。