LeetCode双周赛-第七场

总是抽不出时间参加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积分的)

作者

Robert Lu

发布于

2019-08-25

许可协议

评论