第 36 场双周赛回顾

前言

前三题比较简单，第二题一开始没好好读题，稍微踩了点坑。最后一题暴力模拟，差几个点过，优化了半个小时也没什么进展。只对了3题居然也进前300了，整挺好。

第一题：设计停车系统

题解一：模拟

模拟，没啥好说的。

class ParkingSystem {
    private int big;
    private int medium;
    private int small;
    public ParkingSystem(int big, int medium, int small) {
        this.big = big;
        this.medium = medium;
        this.small = small;
    }
    public boolean addCar(int carType) {
        switch (carType) {
            case 1:
                if (big > 0) {
                    big--;
                    return true;
                }
                break;
            case 2:
                if (medium > 0) {
                    medium--;
                    return true;
                }
                break;
            case 3:
                if (small > 0) {
                    small--;
                    return true;
                }
                break;
        }
        return false;
    }
}
/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */

第二题：警告一小时内使用相同员工卡大于等于三次的人

题解一：哈希表+排序

用哈希表存储不同用户的打卡时间，将时间转换成 int 形式存储并排序，依次遍历判断是否有符合题目要求的情况，最后对结果再进行排序。

import java.util.*;
class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        final int n = keyName.length;
        Map<String, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int time = parse(keyTime[i]);
            if (map.containsKey(keyName[i])) {
                List list = map.get(keyName[i]);
                list.add(time);
                map.put(keyName[i], list);
            } else {
                List list = new ArrayList(100);
                list.add(time);
                map.put(keyName[i], list);
            }
        }
        Comparator<Integer> integerComparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };
        List<String> ans = new LinkedList<>();
        for (Map.Entry<String, List<Integer>> i : map.entrySet()) {
            List<Integer> list = i.getValue();
            list.sort(integerComparator);
            if (judge(list)) {
                ans.add(i.getKey());
            }
        }
        Comparator<String> stringComparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        };
        ans.sort(stringComparator);
        return ans;
    }
    private int parse(String keyTime) {
        String[] times = keyTime.split(":");
        int hour = Integer.parseInt(times[0]);
        int minute = Integer.parseInt(times[1]);
        return hour * 60 + minute;
    }
    private boolean judge(List<Integer> list) {
        final int len = list.size();
        for (int i = 0; i < len - 2; ++i) {
            int begin = list.get(i);
            if ((list.get(i + 1) - begin <= 60) && (list.get(i + 2) - begin <= 60)) {
                return true;
            }
        }
        return false;
    }
}

第三题：给定行和列的和求可行矩阵

题解一：数学

一开始还想着暴搜先试试，看了眼数据范围就放弃了。尝试寻找一种数学方法，保证能给出一种可行矩阵。其实很简单，每个格子填上其行列和的较小值，更新剩余所需的行列和就可以发现有一个已经为0了，那么这一行/列后续都填上0即可。这样同时可以保证和被用完。

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        final int row = rowSum.length;
        final int col = colSum.length;
        int[][] ans = new int[row][col];
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                ans[i][j] = Math.min(rowSum[i], colSum[j]);
                rowSum[i] -= ans[i][j];
                colSum[j] -= ans[i][j];
            }
        }
        return ans;
    }
}

第四题：找到处理最多请求的服务器

题解一：模拟（超时）

维护各个服务器的状态，并用集合存储忙碌的服务器，每次请求到来是更新剩余所需时间，依次遍历找到下一个可用服务器，最后统计处理请求最多的服务器。
数据最大的几个点超时了，我感觉可以从找下一个可用服务器上进行优化，但是一直到比赛结束都没成功。

import java.util.*;
class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        Server[] servers = new Server[k];
        Set<Server> busyServer = new HashSet<>();
        for (int i = 0; i < k; ++i) {
            servers[i] = new Server(i);
        }
        for (int i = 0; i < arrival.length; ++i) {
            for (Iterator<Server> it = busyServer.iterator(); it.hasNext(); ) {
                Server server = it.next();
                server.rest -= arrival[i] - arrival[i - 1];
                if (server.rest <= 0) {
                    server.isBusy = false;
                    it.remove();
                }
            }
            if (busyServer.size() == k) {
                continue;
            }
            int index = i % k;
            while (servers[index].isBusy) {
                index = (index + 1) % k;
            }
            servers[index].isBusy = true;
            servers[index].rest = load[i];
            servers[index].taskCnt++;
            busyServer.add(servers[index]);
        }
        int max = 0;
        List<Integer> ans = null;
        for (Server i : servers) {
            if (i.taskCnt > max) {
                max = i.taskCnt;
                ans = new LinkedList<>();
                ans.add(i.id);
            } else if (i.taskCnt == max) {
                ans.add(i.id);
            }
        }
        return ans;
    }
}
class Server {
    // 编号
    int id;
    // 当前是否在处理请求
    boolean isBusy;
    // 剩余处理时间
    int rest;
    // 总处理任务数
    int taskCnt;
    public Server(int id) {
        this.id = id;
        this.isBusy = false;
        this.rest = 0;
        this.taskCnt = 0;
    }
}