lcp362

8029. 与车相交的点

方法一：差分数组

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int n = nums.size(), cnt = 0;
        int[] diff = new int[103];
        for (List<Integer> list : nums) {
            diff[list.get(0)]++;
            diff[list.get(1) + 1]--;
        }
        int s = 0;
        for (int i = 0; i < diff.length; ++i) {
            s += diff[i];
            if (s > 0)
                ++cnt;
        }
        return cnt;
    }
}

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

方法一：数学

class Solution {
    public boolean isReachableAtTime(int x, int y, int fx, int fy, int t) {
        if (x == fx && y == fy && t == 1)
            return false;
        int a = Math.abs(fx - x), b = Math.abs(fy - y), min = Math.min(a, b);
        t -= min;
        a -= min;
        b -= min;
        t = t - a - b;
        return t >= 0;
    }
}

List<int[]> map0 = new ArrayList<>(), map2 = new ArrayList<>();
int n, m;

public int minimumMoves(int[][] grid) {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (grid[i][j] == 0)
                map0.add(new int[]{i, j, 0});
            else if (grid[i][j] > 1)
                map2.add(new int[]{i, j, grid[i][j]});
        }
    }
    if (map0.isEmpty())
        return 0;
    n = map2.size();
    m = map0.size();
    int res = 0;
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visited = new boolean[3][3];
    return dfs(0, 0, visited);

}

private int dfs(int i, int j, boolean[][] visited) {
    if (i == map2.size())
        return 0;
    if (j == map0.size())
        return map2.get(i)[2] == 1 ? 0 : Integer.MAX_VALUE / 2;
    int[] x = map2.get(i), y = map0.get(j);
    int pass = dfs(i, j + 1, visited), choose = Integer.MAX_VALUE / 2;
    if (x[2] > 1) {
        if (visited[y[0]][y[1]])
            choose = dfs(i, j + 1, visited);
        else {
            visited[y[0]][y[1]] = true;
            map2.get(i)[2]--;
            choose = dfs(i, j + 1, visited) + Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
            map2.get(i)[2]++;
            visited[y[0]][y[1]] = false;
        }
    }
    else if (x[2] == 1) {
        int xx = dfs(i + 1, 0, visited);
        choose += xx;
        pass += xx;
    }
    return Math.min(pass, choose);
}

private boolean isValid(int i, int j) {
    return i >= 0 && j >= 0 && i < 3 && j < 3;
}

int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};