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

第 361 场力扣周赛

统计对称整数的数目

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int i = low; i <= high; i++) {
            int x = i, n = 0;
            int[] aux = new int[10];
            for (; x != 0; x /= 10) {
                aux[n++] = x % 10;
            }
            if (n % 2 == 0) {
                int sum = 0;
                for (int j = 0; j < n / 2; j++) {
                    sum += aux[j] - aux[j + n / 2];
                }
                if (sum == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

生成特殊数字的最少操作

比较简洁的暴力写法，当然从个位开始找 \(25,75,50,00,0\) 更快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumOperations(String num) {
        int n = num.length(), ans = n;
        for (int i = 0; i < n; i++) {
            if (num.charAt(i) == '0') {
                ans = Math.min(ans, n - 1);
            }
            for (int j = i + 1; j < n; j++) {
                int x = (num.charAt(i) - '0') * 10 + num.charAt(j) - '0';
                if (x % 25 == 0) {
                    ans = Math.min(ans, n - i - 2);
                }
            }
        }
        return ans;
    }
}

统计趣味子数组的数目

最开始的思路是，找到所有满足 \(nums[i]\bmod modulo=k\) 的下标放入新的列表，然后在新列表中枚举左端点 \(i\)，此时满足条件的右端点就是 \(i+k-1+j\times modulo\)。暴力解决的时间复杂度 \(O(n^{2})\)，所以可以倒序枚举左端点，顺便记录间隔为 \(modulo\) 的后缀和。但是，这样解决还需要特判 \(k=0\) 的情况，总之很麻烦。

更好的做法是利用同余的性质。将所有 \(nums[i]\bmod modulo=k\) 的数字看作 \(1\)，其他数字看作 \(0\)，这样我们要求的就是满足 \((sum[r+1]-sum[l])\bmod modulo=k\) 的所有子数组的数目。我们可以枚举右端点，找到满足 \((sum[r+1]-k)\equiv sum[l]\pmod{modulo}\) 的左端点的个数，使用前缀和 + 哈希表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0L;
        int n = nums.size(), sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int x : nums) {
            if (x % modulo == k) {
                sum = (sum + 1) % modulo;
            }
            ans += map.getOrDefault((sum - k + modulo) % modulo, 0);
            map.merge(sum, 1, Integer::sum);
        }
        return ans;
    }
}

边权重均等查询

树上倍增求最近公共祖先，同时维护边权的计数。详细见灵神题解。（发现汪佬的写法更简单，在 DFS 的同时进行倍增，以及通过拷贝数组来维护边权的计数信息。）

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    private static final int M = 14;

    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2] - 1;
            g[u].add(new int[]{v, w});
            g[v].add(new int[]{u, w});
        }
        int[] depth = new int[n];
        int[][] cnt = new int[n][26];
        int[][] parent = new int[M][n];
        dfs(0, -1, g, depth, parent, cnt);
        // 查询
        int k = queries.length;
        int[] ans = new int[k];
        while (k-- != 0) {
            int x = queries[k][0], y = queries[k][1];
            int z = lca(x, y, depth, parent), max = 0;
            for (int i = 0; i < 26; i++) {
                max = Math.max(max, cnt[x][i] + cnt[y][i] - 2 * cnt[z][i]);
            }
            ans[k] = depth[x] + depth[y] - 2 * depth[z] - max;
        }
        return ans;
    }

    // DFS 的同时进行倍增，以及维护边权的计数
    private void dfs(int x, int fa, List<int[]>[] g, int[] depth, int[][] parent, int[][] cnt) {
        for (int i = 1; 1 << i <= depth[x]; i++) {
            parent[i][x] = parent[i - 1][parent[i - 1][x]];
        }
        for (int[] t : g[x]) {
            int y = t[0], w = t[1];
            if (y != fa) {
                parent[0][y] = x;
                System.arraycopy(cnt[x], 0, cnt[y], 0, 26);
                cnt[y][w]++;
                depth[y] = depth[x] + 1;
                dfs(y, x, g, depth, parent, cnt);
            }
        }
    }

    // 求最近公共祖先
    private int lca(int x, int y, int[] depth, int[][] parent) {
        if (depth[x] > depth[y]) {
            int t = x;
            x = y;
            y = t;
        }
        // 先向上跳到相同深度
        int step = depth[y] - depth[x];
        for (int i = 0; i < 32; i++) {
            if ((step >> i & 1) != 0) {
                y = parent[i][y];
            }
        }
        // 尽量向上跳
        if (x != y) {
            for (int i = M - 1; i >= 0; i--) {
                int px = parent[i][x], py = parent[i][y];
                if (px != py) {
                    x = px;
                    y = py;
                }
            }
            x = parent[0][x];
        }
        return x;
    }
}
发表更新算法 / LeetCode3 分钟读完 (大约447个字)

第 112 场力扣夜喵双周赛

判断通过操作能否让字符串相等 I

同下。

判断通过操作能否让字符串相等 II

模拟。也可以手动比较，就是适用性不好。（PS：想出一个写法，结果被自己 Hack 掉了~）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[][] c1 = new int[2][26], c2 = new int[2][26];
        for (int i = 0; i < n; i++) {
            c1[i & 1][s1.charAt(i) - 'a']++;
            c2[i & 1][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(c1, c2);
    }
}

几乎唯一子数组的最大和

滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        long sum = 0L, ans = 0L;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.merge(nums.get(i), 1, Integer::sum);
            sum += nums.get(i);
            if (i >= k - 1) {
                if (map.size() >= m) ans = Math.max(ans, sum);
                if (map.merge(nums.get(i - k + 1), -1, Integer::sum) == 0) {
                    map.remove(nums.get(i - k + 1));
                }
                sum -= nums.get(i - k + 1);
            }
        }
        return ans;
    }
}

统计一个字符串的 k 子序列美丽值最大的数目

因为和选择的顺序没有关系，所以贪心的选择出现次数最大的字母就行。

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
class Solution {
    private static final long MOD = (long) 1e9 + 7;

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        char[] ss = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : ss) {
            cnt[c - 'a']++;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int i = 0; i < 26; i++) {
            map.merge(cnt[i], 1, Integer::sum);
        }
        long ans = 1L;
        for (var e : map.entrySet()) {
            int key = e.getKey(), val = e.getValue();
            if (val >= k) {
                return (int) (ans * comb(val, k) % MOD * pow(key, k) % MOD);
            }
            k -= val;
            ans = (ans * pow(key, val)) % MOD;
        }
        return 0;
    }
    
    private long pow(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if ((n & 1) == 1) res = (res * x) % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++) {
            res = res * --n / i;
        }
        return res % MOD;
    }
}
发表更新算法 / AtCoder5 分钟读完 (大约810个字)

AtCoder Beginner Contest 318

Full Moon

模拟。

1
2
3
4
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    io.println(n < m ? 0 : (n - m) / p + 1);
}

Overlapping sheets

比赛时没什么思路，想到扫描线，就用扫描线 + 区间合并来做了。结果一看题解，暴力标记每个点，没想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), ans = 0;
    int[][] g = new int[100][100];
    for (int i = 0; i < n; i++) {
        int a = io.nextInt(), b = io.nextInt();
        int c = io.nextInt(), d = io.nextInt();
        for (int x = a; x < b; x++) {
            for (int y = c; y < d; y++) {
                if (g[x][y]++ == 0) ans++;
            }
        }
    }
    io.println(ans);
}

Blue Spring

看到大佬的解法后，感觉我模拟的方式好蠢啊。当时我是枚举是否要买 \(d\) 张票，有点麻烦，原来枚举买当日的票更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), d = io.nextInt(), p = io.nextInt();
    int[] f = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        f[i] = io.nextInt();
    }
    Arrays.sort(f);
    long ans = Long.MAX_VALUE, sum = 0L;
    for (int i = 0; i <= n; i++) {
        sum += f[i];
        ans = Math.min(ans, sum + (long) (n - i + d - 1) / d * p);
    }
    io.println(ans);
}

General Weighted Max Matching

动态规划有点不太会，赛时瞎搞 AC 的。记忆化搜索会很好写，然后 DP 的话，我是用三层循环解决的，下面的解法优化掉一层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = io.nextInt();
        }
    }
    long[] dp = new long[1 << n];
    for (int k = 2; k < 1 << n; k++) {
        int i = Integer.numberOfTrailingZeros(k & -k);
        dp[k] = dp[k ^ (1 << i)];
        for (int j = i + 1; j < n; j++) {
            if ((k >> j & 1) == 1) {
                dp[k] = Math.max(dp[k], dp[k ^ (1 << i) ^ (1 << j)] + d[i][j]);
            }
        }
    }
    io.println(dp[(1 << n) - 1]);
}

Sandwiches

比较显然的做法是把相同的数分为一组，然后组内枚举中间的数。对于每个中间的数，让答案加上 \(L\times R\)，其中 \(L\) 和 \(R\) 分别是左右两边相等的数的个数，枚举时可以一次性枚举间隔内所有数。

第二个解法是参考大佬的代码得到的，相当于枚举右端点吧。对于每个右端点，它的贡献可以根据下面代码中的公式得出，感觉比较巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[n];
    long[] sum = new long[n];
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        ans += (long) i * cnt[a] - sum[a] - (long) (1 + cnt[a]) * cnt[a] / 2;
        cnt[a]++;
        sum[a] += i;
    }
    io.println(ans);
}

Octopus

有点抽象，不是很懂。大概是枚举了 \(N^{2}\) 个极限位置，然后分别对每个位置判断可行性。

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
public static void solve() {
    int N = io.nextInt();
    long[] X = new long[N];
    long[] L = new long[N];
    for (int i = 0; i < N; i++) {
        X[i] = io.nextLong();
    }
    for (int i = 0; i < N; i++) {
        L[i] = io.nextLong();
    }

    List<Long> pos = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pos.add(X[i] - L[j]);
            pos.add(X[i] + L[j] + 1);
        }
    }
    Collections.sort(pos);

    long ans = 0L;
    for (int i = 0; i < pos.size() - 1; i++) {
        long[] dis = new long[N];
        for (int j = 0; j < N; j++) {
            dis[j] = Math.abs(pos.get(i) - X[j]);
        }
        Arrays.sort(dis);
        boolean ok = true;
        for (int j = 0; j < N; j++) {
            if (dis[j] > L[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans += pos.get(i + 1) - pos.get(i);
        }
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×