且听疯吟

leetcode weekly contes 356

2023-07-31

leetcode weekly contes 356

$T4$ 还算质量比较高的数位 $dp$, 其余的题目没有太大难度。

6917. 满足目标工作时长的员工数目

公司里共有 n 名员工，按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。

公司要求每位员工工作 至少 target 小时。

给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。

请你用整数表示并返回工作至少 target 小时的员工数。

示例 1：

输入：hours = [0,1,2,3,4], target = 2
输出：3
解释：公司要求每位员工工作至少 2 小时。
- 员工 0 工作 0 小时，不满足要求。
- 员工 1 工作 1 小时，不满足要求。
- 员工 2 工作 2 小时，满足要求。
- 员工 3 工作 3 小时，满足要求。
- 员工 4 工作 4 小时，满足要求。
共有 3 位满足要求的员工。

示例 2：

输入：hours = [5,1,4,2,2], target = 6
输出：0
解释：公司要求每位员工工作至少 6 小时。
共有 0 位满足要求的员工。

提示：

  • 1 <= n == hours.length <= 50
  • 0 <= hours[i], target <= 105

地址

https://leetcode.cn/contest/weekly-contest-356/problems/number-of-employees-who-met-the-target/

题意

直接模拟

思路

  1. 直接遍历即可，找到数组中大于 $target$ 的元素个数即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

[sol1-C++]
class Solution {
public:
    int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) {
        int ans = 0;
        for (auto v : hours) {
            if (v >= target) ans++;
        }
        return ans;
    }
};

6900. 统计完全子数组的数目

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

  • 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2000

地址

https://leetcode.cn/contest/weekly-contest-356/problems/count-complete-subarrays-in-an-array/

题意

枚举或者滑动窗口

思路

  1. 题目本身给的数量级较小，我们直接枚举所有的 $i,j$ ，统计当前的子数组中含有的不同元素的个数即可。该算法比较简单时间复杂度为 $O(n^2)$, 另一种解法就是经典的双指针解法，该题目应该在力扣平台中出现过很多次了，每次固定 $i$，然后移动 $j$，直到 $nums[j, \cdots, i]$ 构成的构成的子数组中的不同的元素的数目小于整个数组中不同元素的数目，此时以 $i$ 为结尾可以构成的符合要求的连续子数组的数目即为 $j$ 个，我们依次枚举即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n^2)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(U)$，其中 $U$ 为数组的最大元素。

代码

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_set<int> cnt(nums.begin(), nums.end());
        int tot = cnt.size();
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            vector<int> arr(2001);
            int now = 0;
            for (int j = i; j < nums.size(); j++) {
                if (arr[nums[j]] == 0) {
                    arr[nums[j]] = 1;
                    now++;
                }
                if (now >= tot) {
                    ans++;
                }
            }
        }
        return ans;
    }
};


class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> cnt(nums.begin(), nums.end());
        int maxV = *max_element(nums.begin(), nums.end());
         vector<int> count(maxV + 1);
        int tot = cnt.size();
        int ans = 0, curr = 0;
        for (int i = 0, j = 0; i < nums.size(); i++) {
            count[nums[i]]++;
            if (count[nums[i]] == 1) {
                curr++;
            }
            while (j < n && curr >= tot) {
                count[nums[j]]--;
                if (count[nums[j]] == 0) {
                    curr--;
                }
                j++;
            }
            ans += j;
        }
        return ans;
    }
};

6918. 包含三个字符串的最短字符串

给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。

如果有多个这样的字符串，请你返回 字典序最小 的一个。

请你返回满足题目要求的字符串。

注意：

  • 两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
  • 子字符串 是一个字符串中一段连续的字符序列。

示例 1：

输入：a = "abc", b = "bca", c = "aaa"
输出："aaabca"
解释：字符串 "aaabca" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。

示例 2：

输入：a = "ab", b = "ba", c = "aba"
输出："aba"
解释：字符串 "aba" 包含所有三个字符串：a = ans[0..1] ，b = ans[1..2] ，c = ans[0..2] 。由于 c 的长度为 3 ，结果字符串的长度至少为 3 。"aba" 是字典序最小的一个。

提示：

  • 1 <= a.length, b.length, c.length <= 100
  • a ，b ，c 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-356/problems/shortest-string-that-contains-three-strings/

题意

暴力

思路

  1. 最短子字符串一定在下面几种之一，设 $a,b,c$ 为三个字符串：

    • $a,b$ 均为 $c$ 的子串，即其中两个字符串一定是另一个字符串的子串，此时最短的字符串一定是 $c$;
    • $a$ 是 $b$ 的子串，则此时 $a$ 与 $b$ 合并的最短长度子串一定是 $b$, 否则则是 $a$ 的后缀或者前缀与 $b$ 的前缀或者后缀重合，从而通过合并得到最短的合并子串；
    • $a$ 与 $b$ 合并的字符串为 $d$，$d$ 与 $c$ 合并后的字符串为 $e$；
    • $a,b,c$ 三种字符串不同的顺序组合一共有 $6$ 种不同的顺序组合，期望通过顺序组合计算得到最佳答案即可；

  2. 复杂度分析：

  • 时间复杂度：$O(2^n \times m)$，其中 $n$ 表示给定字符串的数目。
  • 空间复杂度：$O(m)$，其中 $m$ 表示给定字符串的总长度。

代码

class Solution {
public:
    string merge(const string &a, const string &b) {
        if (a.find(b) != std::string::npos) {
            return a;
        }
        if (b.find(a) != std::string::npos) {
            return b;
        }
        for (int i = min(a.size(), b.size()); i >= 0; i--) {
            if (b.substr(0, i) == a.substr(a.size() - i)) {
                return a + b.substr(i);
            }
        }
        return a + b;
    }
    
    string minimumString(string a, string b, string c) {        
        vector<string> arr = {a, b, c};
        string res = a + b + c;
        sort(arr.begin(), arr.end());
        do {
            string s = merge(merge(arr[0], arr[1]), arr[2]);
            if (s.size() < res.size() || (s.size() == res.size() && s < res)) {
                res = s;
            }
        } while(next_permutation(arr.begin(), arr.end()));
        return res;
    }
};

6957. 统计范围内的步进数字数目

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。

如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

注意：步进数字不能有前导 0 。

示例 1：

输入：low = "1", high = "11"
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。

示例 2：

输入：low = "90", high = "101"
输出：2
解释：区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。

提示：

  • 1 <= int(low) <= int(high) < 10100
  • 1 <= low.length, high.length <= 100
  • low 和 high 只包含数字。
  • low 和 high 都不含前导 0 。

地址

https://leetcode.cn/contest/weekly-contest-356/problems/count-stepping-numbers-in-range/

题意

数位DP

思路

  1. 典型的数位 $dp$，求区间问题可以分为两个子问题来解决，求区间 $[l,r]$ 满足题目要求的数目可以变为求小于等于 $r$ 与 $l$ 的数目，设 $f(high)$ 表示小于等于 $high$ 构成的数目，$f(low)$ 表示小于等于 $low$ 构成的数目，此时题目的结果即为 $f(high) - f(low)$，最后还需要检测 $low$ 是否为进步数字。重点来介绍如何计算 $f(x)$，即计算小于等于 $x$ 的步进数字：
    • 需要设置状态设 $dp[prev][i]$ 表示前一位为 $prev$ ,当前为 $i$ 位的步进数字的个数，即此时还可以填充 $n-i$ 个位置的数字，该状态下的数字数目一定是固定的，我们可以利用动态规划快速计算出来，假设当前构成长度 $n$ 位且不含前导 $0$ 的步进数的数目也是确定的，这也可以通过动态规划计算出来。
    • 假设当前的数字为 $x$, 上一位填充的数字为 $prev$，则此时：
      • 当前位置可以填充的数字为 $prev - 1, prev + 1$,；
      • 还需要检测当前位置是由已经沿着边界构造，因此需要判断 $prev - 1 \le x , prev + 1 \le x$，如果当前沿着边界构造，则所有构成的数都应该小于等于 $x$;
      • 假设当前位没有填充数字，则剩余的位可以随意填充，此时可以根据上述计算出来的数据直接填充即可。
      • 数位 $dp$ 还是挺复杂的，容易写错，比赛的时候写错了一个判断条件导致数据没过。
  2. 复杂度分析：
  • 时间复杂度：$O(|\Sigma|m)$，其中 $m$ 表示字符串的长度，$|\Sigma|$ 表示字符串集，在这里字符集的为 $10$。
  • 空间复杂度：$O(|\Sigma|m)$，其中 $m$ 表示字符串的长度，$|\Sigma|$ 表示字符串集，在这里字符集的为 $10$。

代码

class Solution {
public:
    long long mod = 1e9 + 7;
    long long dfs(int pos, int prev, string &s, bool isNum, bool isLimit, vector<vector<long long>> &memo) {
        if (pos == s.size()) {
            return isNum;
        }
        if (!isLimit && isNum && memo[prev][pos] != -1) {
            return memo[prev][pos];
        }
        
        long long res = 0;
        int x = s[pos] - '0';
        if (!isNum) {
            res = (res + dfs(pos + 1, -1, s, false, false, memo)) % mod;
            if (pos == 0) {
                for (int i = 1; i < x; i++) {
                    res = (res + dfs(pos + 1, i, s, true, false, memo)) % mod;
                }
                res = (res + dfs(pos + 1, x, s, true, true, memo)) % mod;
            } else {
                for (int i = 1; i <= 9; i++) {
                    res = (res + dfs(pos + 1, i, s, true, false, memo)) % mod;
                }
            }
        } else {
            if (!isLimit) {
                if (prev + 1 < 10) {
                    res = (res + dfs(pos + 1, prev + 1, s, true, isLimit, memo)) % mod;
                }
                if (prev - 1 >= 0) {
                    res = (res + dfs(pos + 1, prev - 1, s, true, isLimit, memo)) % mod;
                }
                memo[prev][pos] = res;
            } else {
                if (prev + 1 < x) {
                    res = (res + dfs(pos + 1, prev + 1, s, true, !isLimit, memo)) % mod;
                    if (prev - 1 >= 0) {
                        res = (res + dfs(pos + 1, prev - 1, s, true, !isLimit, memo)) % mod;
                    }
                } else if (prev + 1 == x) {
                    res = (res + dfs(pos + 1, prev + 1, s, true, isLimit, memo)) % mod;
                    if (prev - 1 >= 0) {
                        res = (res + dfs(pos + 1, prev - 1, s, true, !isLimit, memo)) % mod;
                    }
                } else {
                    if (prev - 1 < x && prev - 1 >= 0) {
                        res = (res + dfs(pos + 1, prev - 1, s, true, !isLimit, memo)) % mod;
                    } else if (prev - 1 == x) {
                        res = (res + dfs(pos + 1, prev - 1, s, true, isLimit, memo)) % mod;
                    }
                }

            }
        }
        return res;
    }
    
    bool check(string s) {
        for (int i = 1; i < s.size(); i++) {
            if (abs(s[i] - s[i - 1]) != 1) {
                return false;
            }
        }
        return true;
    }
    
    int countSteppingNumbers(string low, string high) {
        int n = max(low.size(), high.size()) + 10;
        vector<vector<long long>> memo1(10, vector<long long>(n + 10, -1));
        vector<vector<long long>> memo2(10, vector<long long>(n + 10, -1));
        long long ret1 = dfs(0, -1, high, false, true, memo1);
        long long ret2 = dfs(0, -1, low, false, true, memo2);
        return ((ret1 - ret2 + mod) % mod + (check(low) ? 1 : 0)) % mod;
    }
};

class Solution {
    const int MOD = 1e9 + 7;

    int calc(string &s, vector<vector<int>> &dp) {
        int m = s.length();
        function<int(int, int, bool, bool)> f = [&](int i, int pre, bool is_limit, bool is_num) -> int {
            if (i == m)
                return is_num; // is_num 为 true 表示得到了一个合法数字
            if (!is_limit && is_num)
                return dp[m - i][pre];
            int res = 0;
            if (!is_num) // 可以跳过当前数位
                res = f(i + 1, pre, false, false);
            int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
            for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
                if (!is_num || abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1
                    res = (res + f(i + 1, d, is_limit && d == up, true)) % MOD;
            return res;
        };
        return f(0, 0, true, false);
    }

    bool valid(string &s) {
        for (int i = 1; i < s.length(); i++)
            if (abs(int(s[i]) - int(s[i - 1])) != 1)
                return false;
        return true;
    }

public:
    int countSteppingNumbers(string low, string high) {
        int n = max(low.size(), high.size()) + 1;
        vector<vector<int>> dp(n, vector<int>(10));
        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    if (abs(j - k) == 1) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        return (calc(high, dp) - calc(low, dp) + MOD + valid(low)) % MOD; // +MOD 防止算出负数
    }
};

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode weekly contes 354 leetcode biweekly contes 109 →

扫描二维码，分享此文章