Double-weekly-contest-36
排名不高,再接再厉
1/5515. 设计停车系统
- 简单题,没什么好说的
class ParkingSystem {
int[] carContainers;
public ParkingSystem(int big, int medium, int small) {
carContainers = new int[]{big,medium,small};
}
public boolean addCar(int carType) {
return carContainers[carType-1]-->0;
}
}
2/5516. 警告一小时内使用相同员工卡大于等于三次的人
- 这题难度其实不算太高,但是对给定输入没正确理解,一是keyName不会按照人名顺序排列,二是keyTime也不会按照顺序给出,如果对一个输入进行排序,则两个输入无法一一对应。
- 所以最后的想法是使用一个Map,员工名字对应他的出入时间的List,将时间转换为Integer储存。遍历完成所有输入以后对每个员工的时间List分别进行排序,然后进行时间差判断,如果 i 与 i-2 的差小于等于60则表示一个小时内使用了员工卡三次。
- 关于排序:Java类库中有数据结构能够对Map的Key进行排序,如TreeMap,若果要按照Value进行排序,则可以将Map中的键值对放到List中,使用Collections.sort()对List进行排序。当然这题既不是对Key排序也不是对Value排序,而是单个Value进行内部排序。
class Solution {
public List<String> alertNames(String[] keyName, String[] keyTime) {
List<String> result = new ArrayList<>();
Map<String, List<Integer>> map = new HashMap<>();
// 建立map, key-value:name-timeList
for(int i=0; i<keyName.length; i++){
if(!map.containsKey(keyName[i])){
map.put(keyName[i], new ArrayList<>());
}
String[] HM = keyTime[i].split(":");
int timeCur = Integer.parseInt(HM[0])* 60 + Integer.parseInt(HM[1]);
map.get(keyName[i]).add(timeCur);
}
// 遍历所有员工,判断时间差
for(String name:map.keySet()){
List<Integer> timeList = map.get(name);
if(timeList.size()>=3){
Collections.sort(timeList);
for(int j=2; j<timeList.size(); j++){
int cal = timeList.get(j) - timeList.get(j-2);
if(cal <=60 && cal>=0){
result.add(name);
break;
}
}
}
}
Collections.sort(result);
return result;
}
}
3/5518. 给定行和列的和求可行矩阵
- 题目到手的第一反应是回溯(dfs),但是数据规模很大,回溯是很有可能超时的,而且题目只需要求得一个解答,并不需要求全部解。
- 仔细阅读题目并思考后后发现,每次都先获取最大能获取的元素,就能得到一个解,这是贪心的思想,由于正确性无法判断,所以我在贪心的思想——先获取最大的元素,上再套了一层回溯,虽然时间复杂度很高,但是也算是AC了
class Solution {
// 回溯
int rows;
int cols;
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
rows = rowSum.length;
cols = colSum.length;
int[][] result = new int[rows][cols];
dfs(result,rowSum,colSum,0,0);
return result;
}
public boolean dfs(int[][] result, int[] rowSum, int[] colSum, int row, int col){
if(allZero(rowSum, colSum))return true;
if(col == cols){
return dfs(result,rowSum,colSum,row+1,0);
}
if(row == rows)return false;
//先选择最大可选的数字
int chooseNum = Math.min(rowSum[row], colSum[col]);
for(int i=chooseNum; i>=0; i--){
rowSum[row] -= i;
colSum[col] -= i;
if(dfs(result,rowSum,colSum,row,col+1)){
result[row][col] = i;
return true;
}
rowSum[row] += i;
colSum[col] += i;
}
return false;
}
public boolean allZero(int[] rowSum, int[] colSum){
int sum=0;
for(int n:rowSum)sum+=n;
for(int n:colSum)sum+=n;
return sum==0;
}
}
- 纯贪心
class Solution {
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int rows = rowSum.length;
int cols = colSum.length;
int[][] result = new int[rows][cols];
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
result[i][j] = Math.min(rowSum[i],colSum[j]);
rowSum[i]-=result[i][j];
colSum[j]-=result[i][j];
}
}
return result;
}
}
4/5517. 找到处理最多请求的服务器
- 解题思路不难,服务器状态有两种,空闲、忙碌,忙碌状态需要维护一个结束时间的值,到达结束时间之后从忙碌状态转回空闲状态。
- 我的做法是将服务器状态维护在一个int[]数组里,下标为服务器的标号,0的时候表示空闲,非0的时候值表示剩余结束时间。这样做的时间复杂度达到O(K*n),K为服务器数量,n为请求数量,对每个请求都要遍历所有的服务器,减去时间,判断是否空闲,这样的做法超时。
- 使用PriorityQueue和TreeSet分别储存忙碌服务器和空闲服务器,这两个数据结构查询和插入的时间复杂度都能达到LogN,这样整体的时间复杂度能减小到O(LogK*n)。
class Solution {
class BusinessServer{
int server;
int endTime;
public BusinessServer(int server, int endTime){
this.server = server;
this.endTime = endTime;
}
public int getServer(){
return server;
}
public int getEndTime(){
return endTime;
}
}
public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
List<Integer> result = new ArrayList<>();
int[] num = new int[k];
PriorityQueue<BusinessServer> bs = new PriorityQueue<>((o1,o2)->o1.getEndTime()-o2.getEndTime());
TreeSet<Integer> freeServer = new TreeSet();
//填充空闲服务器
for(int i=0; i<k; i++){
freeServer.add(i);
}
//遍历请求
for(int i=0; i<arrival.length; i++){
while(!bs.isEmpty() && bs.peek().getEndTime()<= arrival[i] ){
freeServer.add(bs.poll().getServer());
}
Integer nextServer = freeServer.ceiling(i%k);
if(nextServer==null){
nextServer = freeServer.ceiling(0);
}
if(nextServer!=null){
bs.add(new BusinessServer(nextServer, arrival[i]+load[i]));
freeServer.remove(nextServer);
num[nextServer]++;
}
}
int max = 0;
for(int i=0; i<k; i++){
max = Math.max(num[i],max);
}
for(int i=0; i<k; i++){
if(num[i]==max){
result.add(i);
}
}
return result;
}
}