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