第430场周赛

tobegold574 Lv5
  2024-12-30 16:16:08 2024-12-30 16:16:08 Created   2024-12-31 10:12:19 2024-12-31 10:12:19 Updated    

🚀竞赛

使每一列严格递增的最少操作次数

做题过程

一次提交失败，因为之前只考虑了升序的情况。

算法概述

本题要求为将给出二维矩阵中的每一列变为升序，每次操作可对某一列中元素自增一次，计算最少操作次数。直接模拟即可。

  • 时间复杂度为
  • 空间复杂度为

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumOperations(int[][] grid) {
        int ans = 0;
        for (int i = 0; i != grid[0].length; ++i) {
            // 对每列维护一个最大值
            int max=grid[0][i];
            for (int j = 1; j != grid.length; ++j) {
                // 如果不是升序，则取下一个值，即当前最大值
                if(max<grid[j][i]) max=grid[j][i];
                else{
                    // 通过最大值计算下一个操作数
                    ans+=max-grid[j][i]+1;
                    // 最少操作即后一个数只比前一个数大1，所以最大数要自增
                    max++;
                }
            }
        }
        return ans;
    }
}

总结

没有考虑好不同顺序的情况，想当然的直接提交了，喜提一次wa

从盒子中找出字典序最大的字符串 I

做题过程

三次wa，没把情况考虑全，反反复复的追求过当前测试用例。但是完成时间在35分钟，还行。

算法概述

本题要求为按照给定个数划分字符串，全部可能划分完之后，找出字典序最大的字符串（即各个位上的字母顺序比较，完全相同则比较长度）。

  • 时间复杂度为
  • 空间复杂度为

JAVA

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
class Solution {
    public String answerString(String word, int numFriends) {
        if(numFriends==1) return word;
        // 计算最长索引
        int longest=word.length()-numFriends+1;
        // 先找到字典序最大的字母
        char max=word.charAt(0);
        for(int i=1;i!=word.length();++i){
            if(max<word.charAt(i)){
                max=word.charAt(i);
            }
        }
        // 再找该字母所有出现的位置
        List<Integer> subs=new ArrayList<>();
        for(int i=0;i!=word.length();++i){
            if(word.charAt(i)==max) subs.add(i);
        }
        // 再将该字母为首字母把所有划分下来最长的结果放入列表
        List<String> strs=new ArrayList<>();
        for(int i=0;i!=subs.size();++i){
            int seq=subs.get(i);
            if(seq+longest<=word.length()) strs.add(word.substring(seq,seq+longest));
            else strs.add(word.substring(seq));
        }
        // 排序
        strs.sort((a,b)->{
            // 根据最小长度来排
            for(int i=0;i!=Math.min(a.length(),b.length());++i){
                // 如果不同看谁的顺序在前
                if(a.charAt(i)!=b.charAt(i)) return b.charAt(i)-a.charAt(i);
            }
            // 不然比较长度
            return b.length()-a.length();
        });

        return strs.get(0);
        
    }
}


// 灵神的简单暴力写法
class Solution {
    public String answerString(String s, int k) {
        if (k == 1) {
            return s;
        }
        int n = s.length();
        String ans = "";
        for (int i = 0; i < n; i++) {
            String sub = s.substring(i, Math.min(i + n - k + 1, n));
            if (sub.compareTo(ans) > 0) {
                ans = sub;
            }
        }
        return ans;
    }
}

重要实例方法及属性(JAVA)

compareTo()：对字符串来讲，这个就是直接比较字典顺序

总结

还有一种后缀计算的方法，是源于一道困难题的，还没做到，就写不看了。

统计特殊子序列的数目

做题过程

大部分时间都花在这里了，也没做出来，最无语的是不知道哪里错了，难绷。

算法概述

本题要求为找到特殊子序列，该特殊子序列[p, q, r, s]中满足：且需要注意的是目标为 子序列 。以下解法均参考灵神（灵茶山艾府）。

解法一：

  • 时间复杂度为
  • 空间复杂度为

解法二：

  • 时间复杂度为
  • 空间复杂度为

JAVA

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
75
76
77
78
79
80
81
82
83
84
// 解法一
class Solution {
    public long numberOfSubsequences(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> suf = new HashMap<>();
        // 枚举 c
        for (int i = 4; i < n - 2; i++) {
            int c = nums[i];
            // 枚举 d
            for (int j = i + 2; j < n; j++) {
                int d = nums[j];
                int g = gcd(c, d);
                // 把分子和分母（两个 short）压缩成一个 int
                suf.merge((d / g) << 16 | (c / g), 1, Integer::sum);
            }
        }

        long ans = 0;
        // 枚举 b
        for (int i = 2; i < n - 4; i++) {
            int b = nums[i];
            // 枚举 a
            for (int j = 0; j < i - 1; j++) {
                int a = nums[j];
                int g = gcd(a, b);
                ans += suf.getOrDefault((a / g) << 16 | (b / g), 0);
            }
            // 撤销之前统计的 d'/c'
            int c = nums[i + 2];
            for (int j = i + 4; j < n; j++) {
                int d = nums[j];
                int g = gcd(c, d);
                // 减少哈希表中相应d/c组合的计数
                suf.merge((d / g) << 16 | (c / g), -1, Integer::sum);
            }
        }
        return ans;
    }
    // 计算最大公约数（欧几里得算法）
    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-special-subsequences/solutions/3033284/shi-zi-bian-xing-qian-hou-zhui-fen-jie-p-ts6n/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 解法二
class Solution {
    public long numberOfSubsequences(int[] nums) {
        int n = nums.length;
        long ans = 0;
        Map<Float, Integer> cnt = new HashMap<>();
        // 枚举 b 和 c
        for (int i = 4; i < n - 2; i++) {
            // 增量式更新，本轮循环只需枚举 b=nums[i-2] 这一个数
            // 至于更前面的 b，已经在前面的循环中添加到 cnt 中了，不能重复添加
            float b = nums[i - 2];
            // 枚举 a
            for (int j = 0; j < i - 3; j++) {
                cnt.merge(nums[j] / b, 1, Integer::sum);
            }

            float c = nums[i];
            // 枚举 d
            for (int j = i + 2; j < n; j++) {
                ans += cnt.getOrDefault(nums[j] / c, 0);
            }
        }
        return ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-special-subsequences/solutions/3033284/shi-zi-bian-xing-qian-hou-zhui-fen-jie-p-ts6n/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

重要实例方法及属性(JAVA)

  • Map.merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)：先查找key，不存在则插入key和value的键值对，如存在，则使用remappingFunction合并key查找的结果和value的值

总结

总而言之，思路如下：

  • 解法一：

    1. 先枚举c和d，通过 除以最大公约数 的方法使它们的分数最简，存入哈希表
    2. 再枚举a和b，在哈希表中通过查找相同的最简分数进行匹配，更新ans
    3. 同时还需要减少之前统计当前a和b组合能匹配到的的c和d计数，因为已经被用于匹配过了，注意c是从i+2开始，正好和b的位置是匹配的，所以这个撤销操作是必须的

  • 解法二：

    1. 以c为枚举的核心
    2. 枚举之前的b，再通过b来枚举之前的a，这里的b是和c一起动的，只有a会出现重复遍历的情况
    3. d遍历方式和a相同

suf.merge((d / g) << 16 | (c / g), 1, Integer::sum);还有这种存储最简分数的方式更为高效且精度更高（虽然说下面的解法说明了浮点数也是可以用的）

统计恰好有K个相邻元素的数组数目

算法概述

本题要求为给出n, m, k，要求数组长度为n，有k个下标满足arr[i - 1] == arr[i]，且每个元素都在[1, m]内。就是把n-1-k个不同的数看作切割线，那么就把这个问题变成排列组合了。

大概就是这个公式

  • 时间复杂度为
  • 空间复杂度为

PYTHON

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countGoodArrays(self, n: int, m: int, k: int) -> int:
        MOD = 1_000_000_007
        # python直接提供组合数的计算
        # 以及pow横幂算法提供了内部的快速幂实现
        return comb(n - 1, k) % MOD * m * pow(m - 1, n - k - 1, MOD) % MOD

作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

碰到数学的，要是推出来，就用python吧😊。

  • Title: 第430场周赛
  • Author: tobegold574
  • Created at : 2024-12-30 16:16:08
  • Updated at : 2024-12-31 10:12:19
  • Link: https://tobegold574.me/2024/12/30/第430场周赛/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
第430场周赛
  1. 使每一列严格递增的最少操作次数
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  2. 从盒子中找出字典序最大的字符串 I
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  3. 统计特殊子序列的数目
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  4. 统计恰好有K个相邻元素的数组数目
    1. 算法概述
    2. PYTHON
    3. 总结