发表更新算法 / LeetCode6 分钟读完 (大约863个字)

第 365 场力扣周赛

有序三元组中的最大值 I

同下。

有序三元组中的最大值 II

方法一：枚举 j

比赛时第一想法是枚举 \(j\)，然后取左边和右边的最大值计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.max(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.max(suf[i + 1], nums[i]);
        }
        long ans = 0L;
        for (int j = 1; j < n - 1; j++) {
            ans = Math.max(ans, (long) (pre[j] - nums[j]) * suf[j + 1]);
        }
        return ans;
    }
}

方法二：枚举 k

参考灵神的题解，可以枚举 \(k\)，使空间复杂度降为 \(O(1)\)。主要想法就是枚举时，维护前缀最大差值。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = 0, preMax = 0;
        for (int x : nums) {
            ans = Math.max(ans, (long) maxDiff * x);
            maxDiff = Math.max(maxDiff, preMax - x);
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

无限数组的最短子数组

比赛时思路很快出来，但是实现的时候漏掉一些边界条件，导致 WA 多次，本来有机会进第一页的。比较直接的想法是枚举起始位置，然后利用前缀和二分结束的位置，如果满足条件就记入答案。也可以使用哈希表来优化，避免二分。这里贴一下灵神的滑动窗口解法，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long sum = 0L, pre = 0L;
        for (int x : nums) sum += x;
        int q = (int) (target / sum), r = (int) (target % sum);
        int lo = 0, hi = 0, ans = Integer.MAX_VALUE;
        while (hi < 2 * n) {
            pre += nums[hi++ % n];
            while (pre > r) {
                pre -= nums[lo++ % n];
            }
            if (pre == r) {
                ans = Math.min(ans, hi - lo);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans + q * n;
    }
}

有向图访问计数

看完题目就知道是内向基环树，直接修改上次的代码，轻松通过，本题是上次的简化版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        // 建立环外节点的反向边
        int[] in = new int[n];
        List<Integer>[] reverse = new List[n];
        Arrays.setAll(reverse, r -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            in[edges.get(i)]++;
            reverse[edges.get(i)].add(i);
        }
        // 拓扑序去除环外节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            if (--in[edges.get(x)] == 0) {
                q.offer(edges.get(x));
            }
        }
        // 记录每个节点在哪个环
        int[] cirNum = new int[n];
        boolean[] vis = new boolean[n];
        List<Integer> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && in[i] != 0) {
                int cnt = 0;
                for (int cur = i; !vis[cur]; cur = edges.get(cur)) {
                    vis[cur] = true;
                    cirNum[cur] = circles.size();
                    cnt++;
                }
                circles.add(cnt);
            }
        }
        // 对环内的每个节点向环外进行 dfs
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (in[i] != 0) dfs(i, reverse, in, circles.get(cirNum[i]), ans);
        }
        return ans;
    }
    
    private void dfs(int x, List<Integer>[] reverse, int[] in, int len, int[] ans) {
        ans[x] = len;
        for (int y : reverse[x]) {
            if (in[y] != 0) continue;
            dfs(y, reverse, in, len + 1, ans);
        }
    }
}

有个非常简单的写法，参考题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        int[] ans = new int[n];
        int[] vis = new int[n];
        for (int i = 0; i < n; i++) {
            if (ans[i] == 0) {
                int cnt = 0, cirLen = 0, totLen = 0, pos = i;
                while (vis[pos] == 0) {
                    vis[pos] = ++cnt;
                    pos = edges.get(pos);
                }
                if (ans[pos] == 0) {
                    cirLen = cnt - vis[pos] + 1;
                    totLen = cnt;
                } else {
                    totLen = cnt + ans[pos];
                }
                pos = i;
                while (ans[pos] == 0) {
                    ans[pos] = Math.max(totLen--, cirLen);
                    pos = edges.get(pos);
                }
            }
        }
        return ans;
    }
}
发表更新算法 / LeetCode3 分钟读完 (大约464个字)

第 364 场力扣周赛

最大二进制奇数

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int n = s.size(), cnt = 0;
        for (char c : s) {
            if (c == '1') cnt++;
        }
        string ans;
        for (int i = 0; i < n - 1; i++) {
            if (i < cnt - 1) ans.push_back('1');
            else ans.push_back('0');
        }
        ans.push_back('1');
        return ans;
    }
};

美丽塔 I

同下。

美丽塔 II

枚举以每个位置作为山顶，可以得到的最大高度和。通过使用单调栈 + 前后缀分解，可以 \(O(n)\) 的时间算出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        vector<long long> left(n + 1), right(n + 1);
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < n; i++) {
            while (stk.size() > 1 && maxHeights[stk.top()] > maxHeights[i]) stk.pop();
            left[i + 1] = left[stk.top() + 1] + 1LL * maxHeights[i] * (i - stk.top());
            stk.push(i);
        }
        stk = stack<int>();
        stk.push(n);
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() > 1 && maxHeights[stk.top()] > maxHeights[i]) stk.pop();
            right[i] = right[stk.top()] + 1LL * maxHeights[i] * (stk.top() - i);
            stk.push(i);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, left[i] + right[i]);
        }
        return ans;
    }
};

统计树中的合法路径数目

树型 DP，对于每个节点，计算以该节点为根的子树中，经过该节点的有效路径数，我们只需要维护子树中不包含质数的路径数和只包含一个质数的路径数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    private static final int N = (int) 1e5;
    private static final boolean[] np = new boolean[N + 1];

    static {
        np[0] = np[1] = true;
        for (int i = 2; i <= N / i; i++) {
            if (!np[i]) {
                for (int j = i; j <= N / i; j++) {
                    np[j * i] = true;
                }
            }
        }
    }

    long ans = 0L;

    public long countPaths(int n, int[][] edges) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        dfs(1, 0, g);
        return ans;
    }

    private int[] dfs(int x, int fa, List<Integer>[] g) {
        int zero = 0, one = 0;
        if (np[x]) zero = 1;
        else one = 1;

        for (int y : g[x]) {
            if (y == fa) continue;
            int[] t = dfs(y, x, g);
            ans += (long) zero * t[1] + (long) one * t[0];
            if (np[x]) {
                zero += t[0];
                one += t[1];
            } else {
                one += t[0];
            }
        }
        return new int[]{zero, one};
    }
}
发表更新算法 / LeetCode4 分钟读完 (大约561个字)

第 363 场力扣周赛

计算 K 置位下标对应元素的和

模拟。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            if (Integer.bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }
}

让所有学生保持开心的分组方法数

比赛时又写复杂了，当时是想到所有相同的数都必须同时选，所以加了一层循环来跳过相同的数。但是相同的数天然的不满足判断条件，所以不需要这样写。这题唯一需要注意的就是特判全都不选的情况，以及全都选的情况必定满足，可以直接加到答案里（以减少判断代码）。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int countWays(List<Integer> nums) {
        Collections.sort(nums);
        int n = nums.size(), ans = 1;
        if (nums.get(0) > 0) ans++;
        for (int i = 0; i < n - 1; i++) {
            if (i + 1 > nums.get(i) && i + 1 < nums.get(i + 1)) {
                ans++;
            }
        }
        return ans;
    }
}

最大合金数

比赛时又又写复杂了，当时是把所有的库存都清除了再二分的，其实可以直接二分！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int ans = 0;
        for (var cur : composition) {
            int lo = 0, hi = (int) 2e8;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                long cnt = 0L;
                for (int i = 0; i < n; i++) {
                    cnt += Math.max((long) cur.get(i) * mid - stock.get(i), 0L) * cost.get(i);
                }
                if (cnt <= budget) lo = mid + 1;
                else hi = mid - 1;
            }
            ans = Math.max(ans, hi);
        }
        return ans;
    }
}

完全子集的最大元素和

注意题目的描述是每对元素的乘积都是完全平方数。朴素的想法就是对下标进行质因数分解，将所有出现次数为奇数质因数相乘，其结果作为桶的下标，把所有同类的数放在同一个桶里面，然后对每个桶求和取最大值，这样的时间复杂度是 \(O(n\sqrt{n})\)。但是有 \(O(n)\) 的解法，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public long maximumSum(List<Integer> nums) {
        long ans = 0L;
        int n = nums.size();
        for (int i = 1; i <= n; i++) {
            long sum = 0L;
            for (int j = 1; i * j * j <= n; j++) {
                sum += nums.get(i * j * j - 1);
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×