当前位置：网站首页>Leetcode第 79 场双周赛-完成所有题目

import java.util.HashMap;

public class Solution6083 {
    public static void main(String[] args) {
        new Solution6083().digitCount("1210");
    }

    public boolean digitCount(String num) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (char c: num.toCharArray()){
            map.put((int) c-48,map.getOrDefault(c-48,0)+1);
        }
        System.out.println(map);
        for (int i =0;i<num.length();i++){
            char c = num.charAt(i);
            if (map.getOrDefault(i,0) !=c-48){
                return false;
            }
        }
        return true;
    }
}

第二题

6084. 最多单词数的发件人

解题思路

依旧是两轮循环，第一轮将结果统计到HashMap中。第二轮，遍历HashMap统计最大值

解题代码


import java.util.HashMap;

public class Solution6084 {

    public String largestWordCount(String[] messages, String[] senders) {
        HashMap<String,Integer> map = new HashMap<>();
        for (int i =0;i< messages.length ;i ++){
            int msgLen = messages[i].split(" ").length;
            map.put(senders[i],map.getOrDefault(senders[i],0)+msgLen);
        }
        String maxName = senders[0];
        for (String k:map.keySet()){
            if (map.get(k)>map.get(maxName)){
                maxName= k;
            }else if (map.get(k).equals(map.get(maxName))){
                if (k.compareTo(maxName)>0) maxName = k;
            }
        }
        return maxName;
    }
}

第三题

6085. 道路的最大总重要性

解题思路

首先统计道路的起点终点出现次数，由于编号0到n-1，所以无需用Hashmap，直接用一个数组就可以了。

接下来就是按照出现次数排序，出现次数越多，分配的重要性就越大，这里面采用的是一个优先队列来做的。

先把数逐一加入优先队列，然帮再从优先队列中取数。每次取出的一定是最大值

解题思路

public long maximumImportance(int n, int[][] roads) {

        int[] p = new int[n];
        for (int[] l : roads) {
            p[l[0]]++;
            p[l[1]]++;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : p) {
            queue.add(i);
        }
        long index = 1;
        long res = 0;
        while (!queue.isEmpty()) {
            int num = queue.poll();
            System.out.println(num);
            res += index * num;
            index++;
        }
        return res;
    }

第四题

10011. 以组为单位订音乐会的门票

解题思路

构造函数和gather函数比较好写，其中构造函数主要为两个函数初始化变量。gather函数只需要去找一个满足的座位行即可。

重点在scatter，在解答题目的时候，我犯了几个错误。首先解题时候最初，只定义了一个数组，记录座位分配情况。但这样的话，每次分配就要从开头，遍历到结尾，导致超时。然后我定义了一个开始行start，在start之前的所有座位都分配完了，只需要从start往后数就可以了。然后，又超时了，我就定义了一个总剩余座位，一旦scatter要分配的座位超出剩余座位直接返回即可。

在解答的时候，我又犯了一个错，就是在分配的时候每分配一行就去修改了记录座位的s数组，这样加入最后分配的结果是失败的，就要进行回退，回退非常耗时，再次超时。

最后，我才找到了现在的办法，先按把给定的k拷一个出来叫k1，然后去分配座位，先不动座位数组s，先减少k1的值，看到最后能不能分配成功，如果能分配成功，就去修改s数组，修改start值，修改总剩余值。

解题代码


class BookMyShow {
    private final int n;
    private final int m;
    private final int[] s;//第i排分配的座位总数
    private int start;//当前还有座位的起始的行数
    private long allLeft;//当前总剩余座位数

    public BookMyShow(int n, int m) {
        this.start = 0;
        this.n = n;
        this.m = m;
        this.s = new int[n];
        this.allLeft = (long) m * (long) n;
    }

    public int[] gather(int k, int maxRow) {
        if (k > m) {
            return new int[]{};
        }
        for (int i = start; i < this.n; i++) {
            if (m - s[i] >= k && i <= maxRow) {
                //可以分配
                int rem = s[i];
                s[i] += k;
                return new int[]{i, rem};
            }
        }
        return new int[]{};
    }

    public boolean scatter(int k, int maxRow) {
        if (k > allLeft || maxRow > this.n) {
            return false;
        }
        int k1 = k;
        for (int i = start; i <= maxRow; i++) {
            if (m - s[i] >= k1) {
                //计算结果表明，可以分配k个座位，因此执行分配步骤
                // 总数减去k
                allLeft = allLeft - k;
                // 当前行之前的座位全部占满
                for (int j = start; j < i; j++) {
                    s[j] = m;
                }
                // 更新当前行的剩余座位
                s[i] += k1;
                // 下次再分配，就从当前行开始计算了。
                start = i;
                //返回
                return true;
            } else {
                // 把这一排分配光
                k1 -= m - s[i];
            }
        }
        return false;
    }
}