霸州网站制作,北京王府井附近景点攻略,网站如何在国外推广,嘉兴做网站优化的公司LeetCode第362场周赛 与车相交的点判断能否在给定时间到达单元格将石头分散到网格图的最少移动次数 与车相交的点
给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i#xff0c;nums[i] [starti, endi] #xff0c;其中 starti 是第 i… LeetCode第362场周赛 与车相交的点判断能否在给定时间到达单元格将石头分散到网格图的最少移动次数 与车相交的点
给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 inums[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 n u m s . l e n g t h 100 1 nums.length 100 1nums.length100 n u m s [ i ] . l e n g t h 2 nums[i].length 2 nums[i].length2 1 s t a r t i e n d i 100 1 starti endi 100 1startiendi100 分析: 这是一个简单的差分数组题可以用差分数组求出每一个点被覆盖了多少次答案就是覆盖次数大于0的点的个数。 代码:
class Solution {
public:int numberOfPoints(vectorvectorint nums) {int a[105];memset(a,0,sizeof(a));for(auto num:nums){a[num[0]];a[num[1]1]--;}int ans0;for(int i1;i100;i)a[i]a[i-1];for(int i1;i100;i){if(a[i]0)ans;}return ans;}
};判断能否在给定时间到达单元格
给你四个整数 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 s x , s y , f x , f y 1 0 9 1 sx, sy, fx, fy 10^9 1sx,sy,fx,fy109 0 t 1 0 9 0 t 10^9 0t109
分析: 这个题目有一点小坑点首先由于可以往八个方向走因此最少最少可以用 m a x ( a b s ( s x − f x ) , a b s ( s y − f y ) ) max(abs(sx-fx),abs(sy-fy)) max(abs(sx−fx),abs(sy−fy))步可以到达指定位置所以只要t大于等于这个最少步骤即可满足条件(因为你可以在终点附近一直绕当绕到相应要求是再去终点即可)。 但是有一个特殊情况如果起点和终点重合 t 1 t1 t1时是肯定到不了终点的因为必须走出去一步考虑到这一点即可。 代码:
class Solution {
public:bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {if(sxfxsyfy){return t!1;}int minnmax(abs(sx-fx),abs(sy-fy));return tminn;}
};将石头分散到网格图的最少移动次数
给你一个大小为 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 。 提示 g r i d . l e n g t h g r i d [ i ] . l e n g t h 3 grid.length grid[i].length 3 grid.lengthgrid[i].length3 0 g r i d [ i ] [ j ] 9 0 grid[i][j] 9 0grid[i][j]9 g r i d 中元素之和为 9 。 grid 中元素之和为 9 。 grid中元素之和为9。
分析: 因为数据范围很小可以考虑全排列求解。根据题意可以分析出只要将所有位置多出来的石头移动到位置石头数为0的地方即可。那么我们可以先存储所有石头多的位置和0石头的位置对0石头的位置进行全排列然后依次计算从石头多的位置移动到0石头的位置需要多少步维护一个最小值即可。 代码:
class Solution {
public:int minimumMoves(vectorvectorint grid) {vectorpairint,intmore;//存储多出来的点vectorpairint,intless;//存储少的点即0点for(int i0;igrid.size();i){for(int j0;jgrid[i].size();j){if(grid[i][j]1){int kgrid[i][j];while(k1){more.push_back({i,j});k--;}}else if(grid[i][j]0)less.push_back({i,j});}}//对less全排列然后计算more和less的距离int ans1e9;do{int cnt0;for(int i0;iless.size();i){cntabs(more[i].first-less[i].first)abs(more[i].second-less[i].second);}ansmin(ans,cnt);}while(next_permutation(less.begin(),less.end()));return ans;}
};
