lcpBi102

查询网格图中每一列的宽度

方法一：模拟

class Solution {
    public int[] findColumnWidth(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] res = new int[n];
        for (int j = 0; j < n; ++j) {
            int max = 0;
            for (int i = 0; i < m; ++i) {
                int num = grid[i][j], count = num > 0 ? 0 : 1;
                while (num != 0) {
                    num /= 10;
                    ++count;
                }
                max = Math.max(max, count);
                res[j] = max;
            }
        }
        return res;
    }
}

一个数组所有前缀的分数

方法一：前缀和

class Solution {
    public long[] findPrefixScore(int[] nums) {
        int n = nums.length;
        long[] conver = new long[n], res = new long[n];
        long max = 0;
        for (int i = 0; i < n; ++i) {
            max = Math.max(max, nums[i]);
            conver[i] = nums[i] + max;
            res[i] = (i > 0 ? res[i - 1] : 0)+ conver[i];
        }
        return res;
    }
}

二叉树的堂兄弟节点 II

方法一：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        Map<Integer, int[]> map = new HashMap<>();
        Map<Integer, Integer> sum = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        root.val = 0;
        if (root.left != null) {
            root.left.val = 0;
            queue.offer(root.left);
        }
        if (root.right != null) {
            root.right.val = 0;
            queue.offer(root.right);
        }
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int levelSum = 0;
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            if (level >= 2)
                sum.put(level, levelSum);
            ++level;
        }
        level = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int levelSum = 0;
            if (level >= 1) 
                levelSum = sum.getOrDefault(level + 1, 0);
            for (int i = 0; i < size; ++i) {
                int curSum = 0;
                TreeNode node = queue.poll();
                if (node.left != null) {
                    curSum += node.left.val;
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    curSum += node.right.val;
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    node.left.val = levelSum - curSum;
                }
                if (node.right != null) {
                    node.right.val = levelSum - curSum;
                }
            }
            
            ++level;
        }

        return root;
    }
}

设计可以求最短路径的图类

方法一：dijkstra

     class Graph {

        int n;
        int inf = Integer.MAX_VALUE >> 1;
        int[][] graph;

        public Graph(int n, int[][] edges) {
            this.n = n;
            graph = new int[n][n];
            for (int[] arr : graph)
                Arrays.fill(arr, inf);
            for (int[] edge : edges) {
                graph[edge[0]][edge[1]] = edge[2];
            }
        }

        public void addEdge(int[] edge) {
            graph[edge[0]][edge[1]] = edge[2];
        }

        public int shortestPath(int from, int to) {
            int[] dist = new int[n];
            Arrays.fill(dist, inf);
            boolean[] visited = new boolean[n];
            dist[from] = 0;
            for (int i = 0; i < n; ++i) {
                int minIndex = -1, minDist = inf;
                for (int j = 0; j < n; ++j) {
                    if (!visited[j] && dist[j] < minDist) {
                        minDist = dist[j];
                        minIndex = j;
                    }
                }
                if (minIndex == to)
                    return minDist;
                if (minIndex == -1) // not connected
                    return -1;
                visited[minIndex] = true;
                for (int j = 0; j < n; ++j) {
                    if (!visited[j] && dist[j] > minDist + graph[minIndex][j])
                        dist[j] = minDist + graph[minIndex][j];
                }
            }
            return -1;
        }
    }

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

方法二：floyd

     class Graph {

        int n;
        int inf = Integer.MAX_VALUE >> 2; // 只右移一位会溢出
        int[][] dp;

        public Graph(int n, int[][] edges) {
            this.n = n;
            dp = new int[n][n];
            for (int[] arr : dp)
                Arrays.fill(arr, inf);
            for (int i = 0; i < n; ++i)
                dp[i][i] = 0; // 为了增加边时更新
            for (int[] edge : edges) 
                dp[edge[0]][edge[1]] = edge[2];
            for (int k = 0; k < n; ++k)
                for (int i = 0; i < n; ++i)
                    for (int j = 0; j < n; ++j)
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
        }

        public void addEdge(int[] edge) {
            int x = edge[0], y = edge[1], w = edge[2];
            if (w >= dp[x][y]) // 如果权重比原来的还大，不更新(bu'neng'sheng)
                return;
            dp[x][y] = w;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dp[i][j] = Math.min(dp[i][j], dp[i][x] + dp[x][y] + dp[y][j]);
        }

        public int shortestPath(int from, int to) {
            return dp[from][to] < inf ? dp[from][to] : -1;
        }
    }

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */