LeetCode双周赛-第七场

总是抽不出时间参加LeetCode周日上午的周赛，最近发现有周六晚上10点半的双周赛，就参加了两把。这次是第七场。

第一题：

题意

一个只有一行的键盘，随机有26个字母，给定单词，先移动到对应的单词，然后输入第一个字母，再移动，再输入第二个字母，以此类推。问输入这个单词需要移动多长。

题解

题目难度easy，直接模拟就好：

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中即可，剩下的就是照抄题目描述就好：

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。而且一次只能合并两个木棍。

问将所有木棍合成一个需要的最小花费。

题解

很简单，每次取剩下木棍中最短的两个，合成一个（这样花费最小），然后放回。直到最后剩下一个木棍：

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。

题解

这个还是比较难的，当时没有做出来，主要在于既要考虑连接成本最短，还要考虑有时是不是应该直接建井。

看了人家的做法：首先建立一个虚拟的村庄，比如叫水库，水库到每个村庄的费用就是打井的费用。这样，这个题目就变成了一个最小生成树问题了。

最小生成树问题的解法就很简单：

首先，所有的节点都是单独一个集合。从边中选择最短的边，如果这个边是连接了两个集合，那么这个边记入成本，并合并两个集合；否则，抛弃这条边。直到所有的边都连接起来了。

嗯，节点的集合关系处理，直接用并查集就行：

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积分的）