力扣第 103 场双周赛

比赛时间 2023-04-29。本场周赛国服共 262 人 AK。

半场开香槟：这场不 FST 的话，上 Guardian 啦！~

T1. K 个元素的最大和（3 分）

解题思路

贪心。等差数列求和。

时间复杂度：O(n)。

参考代码

class Solution {
    public int maximizeSum(int[] nums, int k) {
        int max = Arrays.stream(nums).max().orElseThrow();
        return (max + (max + k - 1)) * k / 2;
    }
}

T2. 找到两个数组的前缀公共数组（4 分）

解题思路

枚举。

时间复杂度：O(n)。

参考代码

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] cnt = new int[n + 1];
        int[] res = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int ai = A[i], bi = B[i];
            cnt[ai]++;
            cnt[bi]++;
            if (cnt[ai] == 2) {
                ans++;
            }
            if (cnt[bi] == 2 && ai != bi) {
                ans++;
            }
            res[i] = ans;
        }
        return res;
    }
}

T3. 网格图中鱼的最大数目（5 分）

解题思路

BFS。相似题目: 695. 岛屿的最大面积 https://leetcode.cn/problems/max-area-of-island/

时间复杂度：O(mn)。

参考代码

class Solution {
    public static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private int[][] grid;
    private int m, n;

    public int findMaxFish(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;

        boolean[][] visited = new boolean[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    int area = getArea(visited, i, j);
                    max = Math.max(max, area);
                }
            }
        }
        return max;
    }

    private int getArea(boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        int area = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] tuple = queue.remove();
                int cx = tuple[0], cy = tuple[1];
                area += grid[cx][cy];

                for (int[] dir : DIRECTIONS) {
                    int nx = cx + dir[0];
                    int ny = cy + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n
                            && grid[nx][ny] > 0 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return area;
    }
}

T4. 将数组清空（6 分）

解题思路

组合排序。

将数组值和下标组合排序。每轮扫过去，下标单调递增的归属同一轮。假设第 k 轮长度为 remain，则每轮答案加上 remain。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i, nums[i]);
        }
        Arrays.sort(nodes, Comparator.comparingInt(o -> o.val));

        // 第 k 轮剩余的元素个数
        int remain = n;
        long res = remain;
        for (int i = 1; i < n; i++) {
            remain--;
            // 开始新的一轮
            if (nodes[i - 1].id > nodes[i].id) {
                res += remain;
            }
        }
        return res;
    }

    private static class Node {
        int id;
        int val;

        public Node(int id, int val) {
            this.id = id;
            this.val = val;
        }
    }
}

（全文完）