leetcode-36双周赛 - 《leetcode》

1603. 设计停车系统——easy
1604. 警告一小时内使用相同员工卡大于等于三次的人——medium
1605. 给定行和列的和求可行矩阵——medium

1603. 设计停车系统——easy

你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类：
ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，三个参数分别对应每种停车位的数目。
bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。

示例 1：

输入：
[“ParkingSystem”, “addCar”, “addCar”, “addCar”, “addCar”]
[[1, 1, 0], [1], [2], [3], [1]]
输出：
[null, true, true, false, false]

解释：

ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-parking-system

思路：模拟

/**
 * @param {number} big
 * @param {number} medium
 * @param {number} small
 */
var ParkingSystem = function (big, medium, small) {
    this.car = [0,big, medium, small]
};

/**
 * @param {number} carType
 * @return {boolean}
 */
ParkingSystem.prototype.addCar = function (carType) {
    if (this.car[carType] > 0) {
        this.car[carType]--;
        return true;
    } else {
        return false
    }
};

1604. 警告一小时内使用相同员工卡大于等于三次的人——medium

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个警告。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在某一天内使用员工卡的时间。

使用时间的格式是 24小时制，形如 “HH:MM” ，比方说 “23:51” 和 “09:49” 。

请你返回去重后的收到系统警告的员工名字，将它们按字典序升序排序后返回。

请注意 “10:00” - “11:00” 视为一个小时时间范围内，而 “23:51” - “00:10” 不被视为一小时内，因为系统记录的是某一天内的使用情况。

示例 1：

输入：keyName = [“daniel”,”daniel”,”daniel”,”luis”,”luis”,”luis”,”luis”], keyTime = [“10:00”,”10:40”,”11:00”,”09:00”,”11:00”,”13:00”,”15:00”]
输出：[“daniel”]
解释：”daniel” 在一小时内使用了 3 次员工卡（”10:00”，”10:40”，”11:00”）。

示例 2：

输入：keyName = [“alice”,”alice”,”alice”,”bob”,”bob”,”bob”,”bob”], keyTime = [“12:01”,”12:00”,”18:00”,”21:00”,”21:20”,”21:30”,”23:00”]
输出：[“bob”]
解释：”bob” 在一小时内使用了 3 次员工卡（”21:00”，”21:20”，”21:30”）。

示例 3：

输入：keyName = [“john”,”john”,”john”], keyTime = [“23:58”,”23:59”,”00:01”]
输出：[]

示例 4：

输入：keyName = [“leslie”,”leslie”,”leslie”,”clare”,”clare”,”clare”,”clare”], keyTime = [“13:00”,”13:20”,”14:00”,”18:00”,”18:51”,”19:30”,”19:49”]
输出：[“clare”,”leslie”]

提示：

1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime 格式为 “HH:MM” 。
保证 [keyName[i], keyTime[i]] 形成的二元对互不相同。
1 <= keyName[i].length <= 10
keyName[i] 只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period

思路：
**
用map保存每个人的打卡时间，如果time[i+2] - time[i] <=60，说明一小时内打卡了3次，将名字录入答案，最后按字典序对名字进行排序。

复杂度分析:
时间复杂度O(nlogn)
空间复杂度O(n)

var alertNames = function (keyName, keyTime) {
    let ans = [];
    let map = new Map()
    let time = 0
    for (let i = 0; i < keyName.length; i++) {
         time =(Number(keyTime[i][0])*10+Number(keyTime[i][1]))*60+(Number(keyTime[i][3])*10+Number(keyTime[i][4]))
        if (map.has(keyName[i])) {
            map.get(keyName[i]).push(time)
        } else {
            map.set(keyName[i],[time])
        }
    }
    map.forEach((v,k)=>{
        v.sort((a,b)=>a-b)
          for (let i = 0; i < v.length - 2; i++) {
            if (v[i + 2] - v[i] <= 60) {
                ans.push(k);
                break;
            }
        }
    })
    return ans.sort()
};

1605. 给定行和列的和求可行矩阵——medium

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意非负整数矩阵，且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵，题目保证存在至少一个可行矩阵。

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
[1,7]]
解释：
第 0 行：3 + 0 = 0 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
[3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
[6,1,0],
[2,0,8]]

示例 3：

输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
[6,0,3]]

示例 4：

输入：rowSum = [1,0], colSum = [1]
输出：[[1],
[0]]

示例 5：

输入：rowSum = [0], colSum = [0]
输出：[[0]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-valid-matrix-given-row-and-column-sums

思路：
QQ图片20201011145148.png
作者：lucifer1004
链接：https://leetcode-cn.com/problems/find-valid-matrix-given-row-and-column-sums/solution/tan-xin-zheng-ming-by-lucifer1004/

var restoreMatrix = function (rowSum, colSum) {
    let n = rowSum.length;
    let m = colSum.length;
    let ans = new Array(n).fill(undefined).map(()=>{
        return new Array(m).fill(0);
    })
    let i=0,j=0;
    while(1){
        let min = Math.min(rowSum[i],colSum[j]);
        ans[i][j] += min;
        rowSum[i] -= min;
        colSum[j] -=min;
        if(rowSum[i] === 0) i++;
        if(colSum[j] === 0) j++;
        if(i>=n || j>=m) break;
    }
    return ans;
};