lcp334

左右元素和的差值

方法一：模拟

class Solution {
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length;
        int[] res = new int[n], leftSum = new int[n], rightSum = new int[n];
        for (int i = 1; i < n; ++i) 
            leftSum[i] = leftSum[i - 1] + nums[i - 1];
        for (int i = n - 2; i >= 0; --i)
            rightSum[i] = rightSum[i + 1] + nums[i + 1];
        for (int i = 0; i < n; ++i)
            res[i] = Math.abs(leftSum[i] - rightSum[i]);
        return res;
    }
}

找出字符串的可整除数组

方法一：

class Solution {
    public int[] divisibilityArray(String s, int m) {
        int n = s.length();
        int[] res = new int[n];
        long pre = 0;
        for (int i = 0; i < n; ++i) {
            long cur = pre * 10 + s.charAt(i) - '0';
            pre = cur % m;
            res[i] = pre == 0 ? 1 : 0;
        }
        return res;
    }
}

求出最多标记下标

方法一：贪心 + TreeMap

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        int res = 0, n = nums.length;
        Arrays.sort(nums);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = (n + 1) / 2; i < n; ++i) {
            int x = nums[i];
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        for (int i = 0; i < n; ++i) {
            int left = nums[i];
            Integer floor = map.ceilingKey(2 * left);
            if (floor == null)
                break;
            else {
                res += 2;
                map.put(floor, map.get(floor) - 1);
                if (map.get(floor) == 0)
                    map.remove(floor);
            }
        }
        return res;
    }
}

在网格图中访问一个格子的最少时间

二刷 dijkstra

无需visited数组

class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[1][0] > 1 && grid[0][1] > 1)
            return -1;
        int[][] dist = new int[m][n];
        for (int[] arr : dist)
            Arrays.fill(arr, Integer.MAX_VALUE >> 1);
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        q.offer(new int[]{0, 0, 0});
        while (true) {
            int[] node = q.poll();
            int i = node[0], j = node[1], d = node[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col, m, n)) {
                    int nd = Math.max(d, grid[row][col]);
                    nd += (nd + row + col) % 2;
                    if (nd < dist[row][col]) {
                        dist[row][col] = nd;
                        q.offer(new int[]{row, col, nd});
                    }
                }
            } 
        }
    }

    
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

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

方法一：堆优化的dijkstra

dist[i][j]与 i + j 同奇偶

class Solution {
    public int minimumTime(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        int[][] dist = new int[m][n];
        int inf = Integer.MAX_VALUE >> 1;
        for (int[] arr : dist)
            Arrays.fill(arr, inf);
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o1[0] - o2[0]));
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int d = arr[0], i = arr[1], j = arr[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col)) {
                    int nd = Math.max(d + 1, grid[row][col]);
                    nd += (nd - row - col) % 2;
                    if (nd < dist[row][col]) {
                        dist[row][col] = nd;
                        queue.offer(new int[]{nd, row, col});
                    }
                }
            }
        }
        return dist[m - 1][n - 1];
    }

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

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

方法二：二分+ BFS

双数组

class Solution {
    public int minimumTime(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        int left = Math.max(m + n - 2, grid[m - 1][n - 1]), right = (int) 1e5 + m + n;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left + (left + m + n) % 2; // 答案要与 m + n - 2同奇偶
    }

    private boolean check(int limit) {
        boolean[][] visited = new boolean[m][n];
        visited[m - 1][n - 1] = true;
        List<int[]> queue = new ArrayList<>();
        int t = limit - 1;
        queue.add(new int[]{m - 1, n - 1});
        while (!queue.isEmpty()) {
            List<int[]> temp = queue;
            queue = new ArrayList<>();
            for (int[] arr : temp) {
                int i = arr[0], j = arr[1];
                for (int[] dir : dirs) {
                    int row = i + dir[0], col = j + dir[1];
                    if (isValid(row, col) && !visited[row][col] && grid[row][col] <= t) {
                        if (row == 0 && col == 0)
                            return true;
                        visited[row][col] = true;
                        queue.add(new int[]{row, col});
                    }
                }
            }
            --t;
        }
        return false;
    }



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

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

Queue

q.offer(new int[]{m - 1, n - 1, limit - 1});表示终点在limit时访问过，邻居的grid值要小于limit - 1

从limit - 1开始

class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[1][0] > 1 && grid[0][1] > 1)
            return -1;
        int l = Math.max(m + n - 2, grid[m - 1][n - 1]), r = (int) 1e5;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, grid, m, n))
                r = mid - 1;
            else 
                l = mid + 1;
        }
        return l + (l + m + n - 2) % 2; // 答案需要和重点坐标[m - 1, n - 1]之和同奇偶
    }

    public boolean check(int limit, int[][] grid, int m, int n) {
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{m - 1, n - 1, limit - 1});
        visited[m - 1][n - 1] = true;
        while (!q.isEmpty()) {
            int[] node = q.poll();
            int i = node[0], j = node[1], t = node[2];
            if (i == 0 && j == 0)
                return true;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col, m, n) && !visited[row][col] && t >= grid[row][col]) {
                    q.offer(new int[]{row, col, t - 1});
                    visited[row][col] = true;
                }
            }
        }
        return false;
    }
    
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

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