发表更新算法 / 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}!}}\) 种放置方案。将两者相乘即可得到答案，计算过程需要使用逆元和快速幂。

发表更新算法 / 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})\)。还有另一种枚举的做法，题解。

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

第 118 场力扣夜喵双周赛

查找包含给定字符的单词

模拟。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].contains(x + "")) {
                ans.add(i);
            }
        }
        return ans;
    }
}

最大化网格图中正方形空洞的面积

分别求出行和列的最长连续线段，然后最大正方形面积就是两者最小值加一的平方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int maxH = 0, maxV = 0;
        for (int i = 0, j = 0; j < hBars.length; j++) {
            if (hBars[j] - hBars[i] == j - i) {
                maxH = Math.max(maxH, j - i + 1);
            } else {
                i = j;
            }
        }
        for (int i = 0, j = 0; j < vBars.length; j++) {
            if (vBars[j] - vBars[i] == j - i) {
                maxV = Math.max(maxV, j - i + 1);
            } else {
                i = j;
            }
        }
        int len = Math.min(maxH, maxV) + 1;
        return len * len;
    }
}

购买水果需要的最少金币数

动态规划，\(dp[i]\) 表示获取 \([i,n]\) 范围内所有水果所需的最少金币数，有 \(dp[i]=prices[i]+\min_{j=i+1}^{2i+1}{dp[j]}\)，时间复杂度 \(O(n^{2})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        for (int i = (n + 1) / 2 - 1; i > 0; i--) {
            int min = Integer.MAX_VALUE;
            for (int j = i + 1; j <= 2 * i + 1; j++) {
                min = Math.min(min, prices[j - 1]);
            }
            prices[i - 1] += min;
        }
        return prices[0];
    }
}

单调队列优化，时间复杂度 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = n; i > 0; i--) {
            while (!q.isEmpty() && q.peekFirst() > 2 * i + 1) {
                q.pollFirst();
            }
            if (i <= (n + 1) / 2 - 1) {
                prices[i - 1] += prices[q.peekFirst() - 1];
            }
            while (!q.isEmpty() && prices[q.peekLast() - 1] >= prices[i - 1]) {
                q.pollLast();
            }
            q.offerLast(i);
        }
        return prices[q.peekLast() - 1];
    }
}

找到最大非递减数组的长度

单调队列优化 DP，随缘补题。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×