【LeetCode周赛】LeetCode第362场周赛

与车相交的点

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。
示例 1：

输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

示例 2：

输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为7 。

提示：
$1<=nums.length<=100$
$nums[i].length==2$
$1<=starti<=endi<=100$
分析:
这是一个简单的差分数组题，可以用差分数组求出每一个点被覆盖了多少次，答案就是覆盖次数大于0的点的个数。
代码:

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        int a[105];
        memset(a,0,sizeof(a));
        for(auto num:nums){
            a[num[0]]++;
            a[num[1]+1]--;
        }
        int ans=0;
        for(int i=1;i<=100;i++)a[i]+=a[i-1];
        for(int i=1;i<=100;i++){
            if(a[i]>0)ans++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

判断能否在给定时间到达单元格

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。
在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你 必须 移动到任一与之前所处单元格相邻的单元格中。
如果你能在 恰好 t 秒 后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。
单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。
示例 1：

输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6
输出：true
解释：从单元格 (2, 4)开始出发，穿过上图标注的单元格，可以在恰好 6 秒后到达单元格 (7, 7) 。

示例 2：

输入：sx = 3, sy = 1, fx = 7, fy = 3, t = 3
输出：false
解释：从单元格 (3, 1)开始出发，穿过上图标注的单元格，至少需要 4 秒后到达单元格 (7, 3) 。 因此，无法在 3 秒后到达单元格 (7, 3)。

提示：
$1<=sx,sy,fx,fy<=10^9$
$0<=t<=10^9$

分析:
这个题目有一点小坑点，首先，由于可以往八个方向走，因此，最少最少可以用$max(abs(sx-fx),abs(sy-fy))$步，可以到达指定位置，所以只要t大于等于这个最少步骤，即可满足条件(因为你可以在终点附近一直绕，当绕到相应要求是再去终点即可)。
但是有一个特殊情况，如果起点和终点重合，$t=1$时，是肯定到不了终点的，因为必须走出去一步，考虑到这一点即可。
代码:

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if(sx==fx&&sy==fy){
            return t!=1;
        }
        int minn=max(abs(sx-fx),abs(sy-fy));
        return t>=minn;
    }
};
1
2
3
4
5
6
7
8
9
10

将石头分散到网格图的最少移动次数

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。
示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 -将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子(1,2) 移动到 (0,2) 。 总共需要 3 次操作让每个格子都有一个石头。 让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 -将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子(2,2) 移动到 (1,2) 。 4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。 总共需要 4次操作让每个格子都有一个石头。 让每个格子都有一个石头的最少操作次数为 4 。

提示：
$grid.length==grid[i].length==3$
$0<=grid[i][j]<=9$
$grid中元素之和为9。$

分析:
因为数据范围很小，可以考虑全排列求解。根据题意，可以分析出，只要将所有位置多出来的石头移动到位置石头数为0的地方即可。那么我们可以先存储所有石头多的位置和0石头的位置，对0石头的位置进行全排列，然后依次计算从石头多的位置移动到0石头的位置需要多少步，维护一个最小值即可。
代码:

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int,int>>more;//存储多出来的点
        vector<pair<int,int>>less;//存储少的点，即0点
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]>1){
                    int k=grid[i][j];
                    while(k>1){
                        more.push_back({i,j});
                        k--;
                    }
                }else if(grid[i][j]==0)less.push_back({i,j});
            }
        }
        //对less全排列，然后计算more和less的距离
        int ans=1e9;
        do{
            int cnt=0;
            for(int i=0;i<less.size();i++){
                cnt+=abs(more[i].first-less[i].first)+abs(more[i].second-less[i].second);
            }
            ans=min(ans,cnt);
        }while(next_permutation(less.begin(),less.end()));
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28