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

第 374 场力扣周赛

需要添加的硬币的最小数量

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出需要向数组插入多少个数，使得数组的子序列能够表示 \([1,k]\) 范围内的所有整数。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq k\leq 10^{5}\)。

思路

从小到大遍历数组，假设当前能够表示的区间为 \([0,s]\)，此时遍历到数组中的数 \(a_{i}\)，我们可以表示区间 \([a_{i},s+a_{i}]\)。

  • 如果 \(a_{i}\leq s+1\)，那么就可以合并两个区间，得到 \([0,s+a_{i}]\)，然后继续遍历 \(a_{i+1}\)。
  • 否则，需要向数组插入数 \(s+1\) 来保证区间连续，得到 \([0,2s+1]\)，然后再次遍历 \(a_{i}\)。
  • 不断重复上述过程直到能够表示区间 \([1,k]\)。

排序数组的时间复杂度为 \(O(n\log{n})\)，插入操作最多执行 \(O(\log{k})\) 次。

统计完全子字符串

题目

输入长度为 \(n\) 的由小写英文字母组成的字符串 \(s\) 和整数 \(k\)，输出满足以下两个条件的子字符串的个数。

  • 每个字符恰好出现 \(k\) 次。
  • 相邻字符在字母表中的距离小于等于 \(2\)。

数据范围：\(1\leq k\leq n\leq 10^{5}\)。

思路

距离大于 \(2\) 的相邻字符可以将字符串分割成若干子串，对于每个子串 \(t\) 考虑满足条件一的子串 \(t_{i}\) 个数即可。我们可以枚举 \(t_{i}\) 包含多少个不同的字符（设为 \(x\)），对于每个 \(x\) 使用滑动窗口可以得到 \(t\) 中满足条件一的长度为 \(kx\) 的子串个数。时间复杂度为 \(O(|\Sigma| n)\)，外层循环执行 \(O(|\Sigma|)\) 次，内层循环滑窗执行 \(O(n)\) 次，滑窗的同时使用计数数组统计有多少个字符恰好出现 \(k\) 次，判断的时间复杂度为 \(O(1)\)。

统计感冒序列的数目

题目

输入整数 \(n\) 和长度为 \(m\) 的按照升序排列的数组 \(a\)，数组 \(a\) 存储下标 \([0,n-1]\) 的子序列，输出所有不在数组 \(a\) 中的下标被选择的方案数，答案对 \(10^{9}+7\) 取余。下标 \(i\) 可以被选择，当且仅当下标 \(i-1\) 或者 \(i+1\) 被选择，数组 \(a\) 中的下标可以看作是被选择的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq n-1\)，\(0\leq a_{i}\leq n-1\)。

思路

数组 \(a\) 中的下标将 \([0,n-1]\) 划分为多个子数组，首先考虑每个子数组内部的方案数：最左和最右的子数组只存在一种选择方案，其他子数组存在 \(2^{x_{i}-1}\) 种选择方案，\(x_{i}\) 为该子数组的长度。然后考虑子数组之间的方案数，最初我们有 \(n-m\) 个位置可以放置下标，假设各个子数组的长度分别为 \(x_{0},x_{1},\dots,x_{k}\)，那么总共有 \(\prod_{i=0}^{k}{C(n-m-\sum_{j=0}^{i-1}{x_{j}},x_{i})}=\frac{(n-m)!}{\prod_{i=0}^{k}{x_{i}!}}\) 种放置方案。将两者相乘即可得到答案，计算过程需要使用逆元和快速幂。

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

Codeforces Round 911 (Div. 2)

Cover in Water

只要存在三个连续的空格，就可以执行两次操作一，再多次执行操作二，来装满所有空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    String[] arr = s.split("#");
    int ans = 0;
    for (String t : arr) {
        int m = t.length();
        if (m >= 3) {
            io.println(2);
            return;
        }
        ans += m;
    }
    io.println(ans);
}

Laura and Operations

注意题目说的是剩下一种类型的数字，而不是一个数字。如果剩下数字 \(1\)，那么首先将 \(2\) 和 \(3\) 抵消，如果 \(2\) 多于 \(3\)，那么多出的数量如果是偶数，就可以将该数量的一半执行操作，再做一次抵消，最后就只剩下 \(1\)；反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
    if (Math.abs(b - c) % 2 == 0) io.print(1);
    else io.print(0);
    io.print(" ");
    if (Math.abs(a - c) % 2 == 0) io.print(1);
    else io.print(0);
    io.print(" ");
    if (Math.abs(a - b) % 2 == 0) io.print(1);
    else io.print(0);
    io.println();
}

Anji’s Binary Tree

做一次后序遍历即可。题目说的是选择任意字母替换，而不是选择其他节点上的字母替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    int[][] g = new int[n][];
    for (int i = 0; i < n; i++) {
        int l = io.nextInt() - 1, r = io.nextInt() - 1;
        g[i] = new int[]{l, r};
    }
    io.println(dfs(0, g, s));
}

private static int dfs(int x, int[][] g, String s) {
    if (g[x][0] == -1 && g[x][1] == -1) {
        return 0;
    }
    int res = Integer.MAX_VALUE;
    if (g[x][0] != -1) {
        res = Math.min(res, dfs(g[x][0],g, s) + (s.charAt(x) != 'L' ? 1 : 0));
    }
    if (g[x][1] != -1) {
        res = Math.min(res, dfs(g[x][1],g, s) + (s.charAt(x) != 'R' ? 1 : 0));
    }
    return res;
}

Small GCD

\(f(a,b,c)\) 表示 \(a,b,c\) 中最小的两个数的 \(\gcd\)，而我们要求出给定数组的所有不同下标构成的三元组的 \(f\) 之和。暴力的想法是枚举中间值，然后计算以该值为中心构成的三元组的 \(\gcd\) 之和，时间复杂度为 \(O(n^{2})\)。正确的做法：由于数据范围比较小，我们可以首先计算出 \([1,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
private static final int N = 100000;
private static final List<Integer>[] aux;

static {
    aux = new List[N + 1];
    Arrays.setAll(aux, k -> new ArrayList<>());
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            aux[j].add(i);
        }
    }
}

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);

    int[] c = new int[N + 1];
    long[] f = new long[N + 1];
    for (int i = 0; i < n; i++) {
        for (int x : aux[a[i]]) {
            f[x] += (long) c[x] * (n - i - 1);
            c[x]++;
        }
    }

    long ans = 0L;
    for (int i = N; i >= 1; i--) {
        for (int j = i + i; j <= N; j += i) {
            f[i] -= f[j];
        }
        ans += f[i] * i;
    }
    io.println(ans);
}

Transitive Graph

似乎是和强连通分量相关的题目，有空可以补一下。

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

第 373 场力扣周赛

循环移位后的矩阵相似检查

模拟。有个性质，如果左移 \(k\) 位之后相等，则右移 \(k\) 位也必定相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] != mat[i][((j + (i % 2 == 0 ? 1 : -1) * k) % n + n) % n]) {
                    return false;
                }
            }
        }
        return true;
    }
}

统计美丽子字符串 I

将元音字母看作 \(1\)，非元音字母看作 \(-1\)，使用前缀和 + 哈希表的技巧，可以得到若干个分组，每组中任意两个下标构成的子数组都满足条件一。然后我们可以暴力判断所有满足条件一的子数组的长度是否满足条件二，时间复杂度为 \(O(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
class Solution {
    public int beautifulSubstrings(String s, int k) {
        int n = s.length(), sum = 0;
        Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
        Map<Integer, List<Integer>> map = new HashMap<>();
        map.computeIfAbsent(0, t -> new ArrayList<>()).add(-1);
        for (int i = 0; i < n; i++) {
            sum += set.contains(s.charAt(i)) ? 1 : -1;
            map.computeIfAbsent(sum, t -> new ArrayList<>()).add(i);
        }
        int ans = 0;
        for (var list : map.values()) {
            for (int j = 0; j < list.size() ; j++) {
                for (int i = 0; i < j; i++) {
                    int len = (list.get(j) - list.get(i)) / 2;
                    if (len * len % k == 0) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
}

交换得到字典序最小的数组

如果 \(|nums[i]-nums[j]|<=limit\)，那么就可以交换 \(nums[i]\) 和 \(nums[j]\)，该交换的性质具有传递性，所以我们可以对原数组进行排序，只要相邻元素的差值小于等于 \(limit\)，它们就在同一个可交换集合中。这样可以将原数组划分为若干可交换集合，然后对每个集合排序，从小到大排列即可。

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
class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        var aux = new Integer[n];
        for (int i = 0; i < n; i++) {
            aux[i] = i;
        }
        Arrays.sort(aux, (i, j) -> nums[i] - nums[j]);
        
        int pre = -limit;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i : aux) {
            if (nums[i] - pre > limit) {
                buckets.add(new ArrayList<>());
            }
            buckets.get(buckets.size() - 1).add(i);
            pre = nums[i];
        }
        
        int[] ans = new int[n];
        for (var bucket : buckets) {
            List<Integer> pos = new ArrayList<>();
            pos.addAll(bucket);
            Collections.sort(pos);
            for (int i = 0; i < pos.size(); i++) {
                ans[pos.get(i)] = nums[bucket.get(i)];
            }
        }
        return ans;
    }
}

统计美丽子字符串 II

朴素做法的瓶颈在 \((\frac{L}{2})^{2}\bmod{k}=0\) 的判断上，可以通过将条件二变换为 \(L\bmod{k^{\prime}}=0\)，然后使用前缀和以及下标模 \(k^{\prime}\) 的值来分组，这样同组内的下标两两组合得到的必定是满足两个条件的子数组。灵神题解，时间复杂度 \(O(n+\sqrt{k})\)。还有另一种枚举的做法，题解。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×