LeetCode双周赛-第七场

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

第一题:Single-Row Keyboard

题意

一个只有一行的键盘,随机有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;
    }
}

第二题:Design File System

题意

设计文件系统,有两种操作: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这个失误很不应该呐(已经发邮件反馈了这个问题)。

第三题:Minimum Cost to Connect Sticks

题意

要把一大堆木棍合并成一个长木棍:把长度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;
    }
}

由于这个木棍是动态变化的,所以还是用堆来处理,不然每次排序很花时间。

第四题:Optimize Water Distribution in a Village

题意

一个村子里有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积分的)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.