contest url :
https://leetcode.cn/contest/weekly-contest-362/

8029 与车相交的点

解法1 模拟

根据题意暴力解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        int ans = 0;
        vector<int>q(101);
        for(int i = 0 ; i < nums.size() ; i++){
            int a = nums[i][0],b = nums[i][1];
            for(int j = a ; j <= b ; j++){
                q[j] = 1;
            }
        }


        for(int i = 1 ; i <= 100 ; i++){
            ans += q[i];
        }

        return ans; 
    }
};

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

解法1 数学公式

常规思路 最短路问题 : BFS
但这题没有障碍物 且是无限边界的图 数据范围1e9 BFS就不适用了
考虑数学公式 两边之和 大于等于 第三边
由于向周围8格子走 那么理论最短肯定是斜线 由于是格子是整数 所以不会是直接斜线
那么最短距离就是先走完最短斜线 -> 起点x,y 终点x,y 任一相等后再走完 -> 即相当于最短 走了最长那条边的距离 

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        // 特殊情况 起点终点相同时 如果只能走一步的话 那就只能往外走 回不来了
        if(sx == fx && sy == fy && t == 1 ){
            return false;
        }
        return max(abs(sx - fx),abs(sy - fy)) <= t;
    }
};