总是抽不出时间参加LeetCode周日上午的周赛，最近发现有周六晚上10点半的双周赛，就参加了两把。这次是第七场。
题意
一个只有一行的键盘，随机有26个字母，给定单词，先移动到对应的单词，然后输入第一个字母，再移动，再输入第二个字母，以此类推。问输入这个单词需要移动多长。
题解
题目难度easy，直接模拟就好：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public int calculateTime(String keyboard, String word) {
int res = 0;
int index = 0;
int[] map = new int[128];
for (int i = 0; i < keyboard.length(); i++) {
map[keyboard.charAt(i)] = i;
}
for (char ch : word.toCharArray()) {
int newIndex = map[ch];
res += Math.abs(newIndex - index);
index = newIndex;
}
return res;
}
}
|
题意
设计文件系统，有两种操作：create、get。
create(path, value)：创建一个新路径，将一个值关联到这个路径，并返回True。如果路径已经存在或其父路径不存在，则返回False。
get(path)：返回与路径关联的值，如果路径不存在，则返回-1。
路径以 / 分隔层级。
题解
基本上，把每一级目录当作一个目录项存到map中即可，剩下的就是照抄题目描述就好：
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
| import java.util.HashMap;
public class FileSystem {
private HashMap<String, Integer> map = new HashMap<>();
public FileSystem() {
map.put("/", -1);
}
public boolean create(String path, int value) {
StringBuilder sb = new StringBuilder();
String[] strs = path.split("/");
for (int i = 0; i < strs.length; i++) {
if (strs[i].isEmpty() || i + 1 == strs.length) {
continue;
}
sb.append("/");
sb.append(strs[i]);
if (!map.containsKey(sb.toString())) {
return false;
}
}
if (map.containsKey(path)) {
return false;
}
map.put(path, value);
return true;
}
public int get(String path) {
return map.getOrDefault(path, -1);
}
}
|
我刚刚试了一下，如果在path已经存在，直接覆盖原来的值（而不是按照题目要求返回-1），即没有上面高亮的三行，也是可以AC的。LeetCode这个失误很不应该呐(已经发邮件反馈了这个问题）。
题意
要把一大堆木棍合并成一个长木棍：把长度X的木棍和长度为Y的木棍接成一个需要花费X+Y。而且一次只能合并两个木棍。
问将所有木棍合成一个需要的最小花费。
题解
很简单，每次取剩下木棍中最短的两个，合成一个（这样花费最小），然后放回。直到最后剩下一个木棍：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.PriorityQueue;
public class Solution {
public int connectSticks(int[] sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int stick : sticks) {
pq.add(stick);
}
int res = 0;
while (pq.size() > 1) {
int stick = pq.poll();
stick += pq.poll();
res += stick;
pq.add(stick);
}
return res;
}
}
|
由于这个木棍是动态变化的，所以还是用堆来处理，不然每次排序很花时间。
题意
一个村子里有n座房子。我们想通过建井和铺设管道为所有的房子供水。
对于每栋房子i，我们要么直接用在里面建一口井，要么把水从另一口井引过来。
建井的花费由数组wells给出。在房子之间铺设管道的成本由数组pipes给出，其中每个pipe[i] = [house1, house2, cost]表示使用管道将房子1和房子2连接在一起的花费cost。
题解
这个还是比较难的，当时没有做出来，主要在于既要考虑连接成本最短，还要考虑有时是不是应该直接建井。
看了人家的做法：首先建立一个虚拟的村庄，比如叫水库，水库到每个村庄的费用就是打井的费用。这样，这个题目就变成了一个最小生成树问题了。
最小生成树问题的解法就很简单：
首先，所有的节点都是单独一个集合。从边中选择最短的边，如果这个边是连接了两个集合，那么这个边记入成本，并合并两个集合；否则，抛弃这条边。直到所有的边都连接起来了。
嗯，节点的集合关系处理，直接用并查集就行：
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
| import java.util.*;
public class Solution {
private HashMap<Integer, List<int[]>> map = new HashMap<>();
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes_o) {
int[][] pipes = new int[pipes_o.length + n][];
System.arraycopy(pipes_o, 0, pipes, 0, pipes_o.length);
for (int i = 0; i < n; i++) {
pipes[pipes_o.length + i] = new int[]{n + 1, i + 1, wells[i]};
}
Arrays.sort(pipes, (Comparator.comparingInt(o -> o[2])));
int[] parents = new int[n + 2];
int res = 0;
for (int[] pipe : pipes) {
if (pipe[0] > pipe[1]) {
int tmp = pipe[1];
pipe[1] = pipe[0];
pipe[0] = tmp;
}
int p1 = pipe[0];
while (parents[p1] != 0) {
p1 = parents[p1];
}
parents[pipe[0]] = pipe[0] == p1 ? 0 : p1;
int p2 = pipe[1];
while (parents[p2] != 0) {
p2 = parents[p2];
}
if (p1 != p2) {
parents[p2] = p1;
parents[pipe[1]] = pipe[1] == p1 ? 0 : p1;
res += pipe[2];
} else {
parents[pipe[1]] = pipe[1] == p2 ? 0 : p2;
}
}
return res;
}
}
|
- 为了防止并查集出现环，也为了优化性能。在此题中，规定父节点一定小于自己。
- 这道题目不像第三题，边的集合不会变化，所以只需要在开始的时候排序一次即可。
总结
第四题应该可以做出来的，可是太早放弃了，唉。
名次288 / 1901，马上就不是5积分参与奖了！加油！（200名之前有50积分的）