lcpBi103

K 个元素的最大和

方法二：等差数列

class Solution {
    public int maximizeSum(int[] nums, int k) {
        int max = 0;
        for (int x : nums)
            max = Math.max(max, x);
        // max + (max + 1) + ... + (max + k - 1)
        return (max * 2 + k - 1) * k / 2;
    }
}

时间复杂度：\(O(n)\)

方法一：模拟

class Solution {
    public int maximizeSum(int[] nums, int k) {
        Arrays.sort(nums);
        int  n = nums.length, res = 0, cur = nums[n - 1];
        for (int i = 0; i < k; ++i) {
            res += cur;
            ++cur;
        }
        return res;
    }
}

时间复杂度：\(O(nlogn)\)

找到两个数组的前缀公共数组

方法二：位运算

左移的时候是1L!!!,1是整型

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        long a = 0, b = 0;
        int n = A.length;
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            a |= 1L << A[i];
            b |= 1L << B[i];
            res[i] = Long.bitCount(a & b);
        }
        return res;
    }
}

方法一：HashMap

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] res = new int[n];
        Map<Integer, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int temp = 0;
            if (A[i] == B[i]) {
                if (i == 0)
                    res[i] = 1;
                else {
                    res[i] = res[i - 1] + 1;
                }
            }
            else {
                if (map2.containsKey(A[i])) {
                    ++temp;
                    map2.remove(A[i]);
                }
                else
                    map1.put(A[i], i);
                if (map1.containsKey(B[i])) {
                    ++temp;
                    map1.remove(B[i]);
                }
                else
                    map2.put(B[i], i);
                if (i == 0)
                    res[0] = 0;
                else {
                    res[i] = res[i - 1] + temp;
                }
            }
        }
        return res;
    }
}

网格图中鱼的最大数目

方法一：DFS

class Solution {
    public int findMaxFish(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    res = Math.max(res, dfs(i, j));
                }
            }
        }
        return res;
    }

    private int dfs(int i, int j) {
        visited[i][j] = true;
        int count = grid[i][j];
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] > 0 && !visited[row][col]) {
                count += dfs(row, col);
            }
        }
        return count;
    }

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

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

}

方法二：并查集

class Solution {
    public int findMaxFish(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        init(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    int index = i * n + j;
                    fish[index] = grid[i][j];
                    if (i > 0 && grid[i - 1][j] > 0) {
                        union(index, index - n);
                    }
                    if (j > 0 && grid[i][j - 1] > 0) {
                        union(index, index - 1);
                    }
                }
            }
        }
        for (int x : fish)
            res = Math.max(res, x);
        return res;
    }


    int m, n, res = 0;
    int[][] grid;
    int[] parent, fish;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootJ] = rootI;
            fish[rootI] += fish[rootJ];
            fish[rootJ] = 0;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
        fish = new int[n];
    }

}

image-20230729200112196