第 83 场周赛：较大分组的位置、隐藏个人信息、连续整数求和、统计子串中的唯一字符

Q1、[简单] 较大分组的位置

1、题目描述

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

输入：s = "abbxxxxzzy"
输出：[[3,6]]
解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

提示：

• 1 <= s.length <= 1000
• s 仅含小写英文字母

2、解题思路

1. 遍历字符串：
   • 使用一个变量 num 记录当前连续相同字符的数量。
   • 遍历字符串，比较当前字符与下一个字符：
     • 如果相同，则 num 加 1。
     • 如果不同，则检查 num 是否大于或等于 3，如果是，则记录当前分组的区间 [i - num + 1, i]，并重置 num 为 1。
2. 记录较大分组：
   • 使用一个二维数组 ret 存储所有较大分组的区间。
3. 返回结果：
   • 返回 ret，其中区间按起始位置递增顺序排列。

3、代码实现

C++

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> ret; // 存储所有较大分组的区间
        int n = s.size();        // 字符串的长度
        int num = 1;             // 当前连续相同字符的数量，初始为 1
        // 遍历字符串
        for (int i = 0; i < n; ++i) {
            // 如果当前字符是最后一个字符，或者与下一个字符不同
            if (i == n - 1 || s[i] != s[i + 1]) {
                // 如果当前连续相同字符的数量大于或等于 3
                if (num >= 3) {
                    ret.push_back({i - num + 1, i}); // 记录当前分组的区间
                }
                num = 1; // 重置当前连续相同字符的数量
            }
            // 如果当前字符与下一个字符相同
            else {
                ++num; // 当前连续相同字符的数量加 1
            }
        }
        return ret; // 返回所有较大分组的区间
    }
};

Java

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> result = new ArrayList<>(); // 存储所有较大分组的区间
        int n = s.length(); // 字符串的长度
        int count = 1; // 当前连续相同字符的数量, 初始为 1

        // 遍历字符串
        for (int i = 0; i < n; ++i) {
            // 如果当前字符是最后一个字符，或者与下一个字符不同
            if (i == n - 1 || s.charAt(i) != s.charAt(i + 1)) {
                // 如果当前连续相同字符的数量大于或等于 3
                if (count >= 3) {
                    // 记录当前分组的区间
                    List<Integer> group = new ArrayList<>();
                    group.add(i - count + 1);
                    group.add(i);
                    result.add(group);
                }
                count = 1; // 重置当前连续相同字符的数量
            }
            // 如果当前字符与下一个字符相同
            else {
                count++; // 当前连续相同字符的数量加 1
            }
        }

        return result; // 返回所有较大分组的区间
    }
}

Python

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        ret = []  # 存储所有较大分组的区间
        n = len(s)  # 字符串的长度
        num = 1  # 当前连续相同字符的数量，初始为 1

        # 遍历字符串
        for i in range(n):
            # 如果当前字符是最后一个字符，或者与下一个字符不同
            if i == n - 1 or s[i] != s[i + 1]:
                # 如果当前连续相同字符的数量大于或等于 3
                if num >= 3:
                    ret.append([i - num + 1, i])  # 记录当前分组的区间
                num = 1  # 重置当前连续相同字符的数量
            # 如果当前字符与下一个字符相同
            else:
                num += 1  # 当前连续相同字符的数量加 1

        return ret  # 返回所有较大分组的区间

4、复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历一次该数组。

空间复杂度：O(1)。我们只需要常数的空间来保存若干变量，注意返回值不计入空间复杂度。

Q2、[中等] 隐藏个人信息

1、题目描述

给你一条个人信息字符串 s ，可能表示一个 邮箱地址 ，也可能表示一串 电话号码 。返回按如下规则 隐藏 个人信息后的结果：

电子邮件地址：

一个电子邮件地址由以下部分组成：

• 一个 名字 ，由大小写英文字母组成，后面跟着
• 一个 '@' 字符，后面跟着
• 一个 域名 ，由大小写英文字母和一个位于中间的 '.' 字符组成。'.' 不会是域名的第一个或者最后一个字符。

要想隐藏电子邮件地址中的个人信息：

• 名字 和 域名 部分的大写英文字母应当转换成小写英文字母。
• 名字 中间的字母（即，除第一个和最后一个字母外）必须用 5 个 "*****" 替换。

电话号码：

一个电话号码应当按下述格式组成：

• 电话号码可以由 10-13 位数字组成
• 后 10 位构成 本地号码
• 前面剩下的 0-3 位，构成 国家代码
• 利用 {'+', '-', '(', ')', ' '} 这些 分隔字符 按某种形式对上述数字进行分隔

要想隐藏电话号码中的个人信息：

• 移除所有 分隔字符
• 隐藏个人信息后的电话号码应该遵从这种格式：
  • "***-***-XXXX" 如果国家代码为 0 位数字
  • "+*-***-***-XXXX" 如果国家代码为 1 位数字
  • "+**-***-***-XXXX" 如果国家代码为 2 位数字
  • "+***-***-***-XXXX" 如果国家代码为 3 位数字
• "XXXX" 是最后 4 位 本地号码

示例 1：

输入：s = "LeetCode@LeetCode.com"
输出："l*****e@leetcode.com"
解释：s 是一个电子邮件地址。
名字和域名都转换为小写，名字的中间用 5 个 * 替换。

示例 2：

输入：s = "AB@qq.com"
输出："a*****b@qq.com"
解释：s 是一个电子邮件地址。
名字和域名都转换为小写，名字的中间用 5 个 * 替换。
注意，尽管 "ab" 只有两个字符，但中间仍然必须有 5 个 * 。

示例 3：

输入：s = "1(234)567-890"
输出："***-***-7890"
解释：s 是一个电话号码。
共计 10 位数字，所以本地号码为 10 位数字，国家代码为 0 位数字。
因此，隐藏后的电话号码应该是 "***-***-7890" 。

提示：

• s 是一个 有效 的电子邮件或者电话号码
• 如果 s 是一个电子邮件：
  • 8 <= s.length <= 40
  • s 是由大小写英文字母，恰好一个 '@' 字符，以及 '.' 字符组成
• 如果 s 是一个电话号码：
  • 10 <= s.length <= 20
  • s 是由数字、空格、字符 '('、')'、'-' 和 '+' 组成

2、解题思路

1. 判断输入类型：
   • 如果字符串包含 @，则认为是电子邮件地址。
   • 否则，认为是电话号码。
2. 处理电子邮件地址：
   • 将整个字符串转换为小写。
   • 提取名字的第一个字符和最后一个字符，中间用 "*****" 替换。
   • 域名部分保持不变。
3. 处理电话号码：
   • 移除所有非数字字符。
   • 根据电话号码的长度（10-13 位）确定国家代码的长度。
   • 按照规则格式化隐藏后的电话号码。

3、代码实现

C++

class Solution {
public:
    // 国家代码对应的前缀
    vector<string> country = {"", "+*-", "+**-", "+***-"};

    string maskPII(string s) {
        string res;           // 存储结果
        int at = s.find("@"); // 查找 '@' 的位置
        // 如果找到了 '@' 说明是电子邮箱
        if (at != string::npos) {
            // 将整个字符串转换为小写
            transform(s.begin(), s.end(), s.begin(), ::tolower);
            // 名字部分：第一个字符 + "*****" + 最后一个字符
            // 域名部分：保持不变
            return s.substr(0, 1) + "*****" + s.substr(at - 1);
        }
        // 如果是电话号码, 移除所有非数字字符
        s = regex_replace(s, regex("[^0-9]"), "");
        // 根据电话号码的长度确定国家代码的长度
        int countryCodeLength = s.size() - 10;
        // 格式化隐藏后的电话号码
        return country[countryCodeLength] + "***-***-" + s.substr(s.size() - 4);
    }
};

Java

class Solution {
    // 国家代码对应的前缀
    private static final String[] country = { "", "+*-", "+**-", "+***-" };

    public String maskPII(String s) {
        // 查找 '@' 的位置
        int at = s.indexOf('@');
        // 如果找到了 '@' 说明是电子邮箱
        if (at != -1) {
            // 将整个字符串转换为小写
            s = s.toLowerCase();
            // 名字部分：第一个字符 + "*****" + 最后一个字符
            // 域名部分：保持不变
            return s.charAt(0) + "*****" + s.substring(at - 1);
        }
        // 如果是电话号码, 移除所有非数字字符
        s = s.replaceAll("[^0-9]", "");
        // 根据电话号码的长度确定国家代码的长度
        int countryCodeLength = s.length() - 10;
        // 格式化隐藏后的电话号码
        return country[countryCodeLength] + "***-***-" + s.substring(s.length() - 4);
    }
}

Python

class Solution:
    def maskPII(self, s: str) -> str:
        # 国家代码对应的前缀
        country = ["", "+*-", "+**-", "+***-"]

        # 判断是否是电子邮件地址
        if '@' in s:
            # 将整个字符串转换为小写
            s = s.lower()
            # 找到 '@' 的位置
            at = s.find('@')
            # 名字部分：第一个字符 + "*****" + 最后一个字符
            # 域名部分：保持不变
            return s[0] + "*****" + s[at - 1:]
        else:
            # 移除所有非数字字符
            s = re.sub(r'[^0-9]', '', s)
            # 根据电话号码的长度确定国家代码的长度
            countryCodeLength = len(s) - 10
            # 格式化隐藏后的电话号码
            return country[countryCodeLength] + "***-***-" + s[-4:]

4、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串一次。
• 空间复杂度：O(n)，用于存储处理后的字符串。

Q3、[困难] 连续整数求和

1、题目描述

给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。

示****例 1:

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

示例 2:

输入: n = 9
输出: 3
解释: 9 = 4 + 5 = 2 + 3 + 4

示例 3:

输入: n = 15
输出: 4
解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示:

• 1 <= n <= 109

2、解题思路

1. 问题分析：

   • 我们需要找到所有连续的正整数序列，使得这些序列的和等于 n。

   • 设连续序列的长度为 k，序列的第一个数为 x，则序列的和可以表示为：

     $x+(x+1)+(x+2)+\cdots +(x+k-1)=kx+k(k-1)/2=n$

   • 整理得：$kx=n-k(k-1)/2$

   • 因为 x 是正整数，所以 $n-k(k-1)/2$ 必须为正整数，且能被 k 整除。

2. 算法设计：

   • 遍历可能的序列长度 k，从 1 到满足 $k(k+1)\le 2n$ 的最大值。
   • 对于每个 k，检查 $n-k(k-1)/2$ 是否能被 k 整除。
   • 如果满足条件，则存在一个长度为 k 的连续序列。

3. 优化：

   • 对于奇数 k，直接检查 n % k == 0。
   • 对于偶数 k，检查 n % k != 0 且 2n % k == 0。

3、代码实现

C++

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;       // 记录满足条件的组数
        int bound = 2 * n; // 确定 k 的上界
        // 遍历可能的 k
        for (int k = 1; k * (k + 1) <= bound; k++) {
            // 检查是否存在长度为 k 的连续序列, 如果存在，组数加 1
            if (isKConsecutive(n, k)) {
                ans++;
            }
        }
        return ans; // 返回结果
    }

    bool isKConsecutive(int n, int k) {
        if (k % 2 == 1) {                        // 如果 k 是奇数
            return n % k == 0;                   // 检查 n 是否能被 k 整除
        } else {                                 // 如果 k 是偶数
            return n % k != 0 && 2 * n % k == 0; // 检查 n 是否满足偶数条件
        }
    }
};

Java

class Solution {
    public int consecutiveNumbersSum(int n) {
        int ans = 0; // 记录满足条件的组数
        int bound = 2 * n; // 确定 k 的上界
        // 遍历可能的 k
        for (int k = 1; k * (k + 1) <= bound; k++) {
            // 检查是否存在长度为 k 的连续序列, 如果存在，组数加 1
            if (isKConsecutive(n, k)) {
                ans++;
            }
        }
        return ans; // 返回结果
    }

    private boolean isKConsecutive(int n, int k) {
        // 如果 k 是奇数
        if (k % 2 == 1) {
            return n % k == 0; // 检查 n 是否能被 k 整除
        }
        // 如果 k 是偶数
        else {
            return n % k != 0 && 2 * n % k == 0; // 检查 n 是否满足偶数条件
        }
    }
}

Python

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        ans = 0  # 记录满足条件的组数
        bound = 2 * n  # 确定 k 的上界
        k = 1
        while k * (k + 1) <= bound:  # 遍历可能的 k
            if self.is_k_consecutive(n, k):  # 检查是否存在长度为 k 的连续序列
                ans += 1  # 如果存在，组数加 1
            k += 1
        return ans  # 返回结果

    def is_k_consecutive(self, n: int, k: int) -> bool:
        if k % 2 == 1:  # 如果 k 是奇数
            return n % k == 0  # 检查 n 是否能被 k 整除
        else:  # 如果 k 是偶数
            return n % k != 0 and 2 * n % k == 0  # 检查 n 是否满足偶数条件

4、复杂度分析

1. 时间复杂度：
   • 遍历 k 的范围是 $1\le k\le sqr(2n)$，因此时间复杂度为 sqr(n)。
2. 空间复杂度：
   • 只使用了常数级别的额外空间，因此空间复杂度为 $O(1)$。

Q4、[困难] 统计子串中的唯一字符

1、题目描述

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

输入：s = "LEETCODE"
输出：92

提示：

• 1 <= s.length <= 105
• s 只包含大写英文字符

2、解题思路

1. 问题分析：
   • 我们需要统计所有子字符串中的唯一字符的总和。
   • 直接枚举所有子字符串并计算唯一字符的个数会超时，因为子字符串的数量是 O(n²)。
2. 优化思路：
   • 对于每个字符 c，计算它在多少个子字符串中是唯一的。
   • 对于字符 c ，假设它在字符串中的位置为 arr[0], arr[1], ..., arr[k-1] ，则：
     • 对于位置 arr[i]，它作为唯一字符的子字符串的左边界范围是 (arr[i-1], arr[i]]，右边界范围是 [arr[i], arr[i+1])。
     • 因此，位置 arr[i] 对结果的贡献是 (arr[i] - arr[i-1]) * (arr[i+1] - arr[i])。
3. 算法步骤：
   • 使用哈希表记录每个字符在字符串中的所有位置。
   • 对于每个字符，计算它在所有子字符串中作为唯一字符的贡献，并累加到结果中。

3、代码实现

C++

class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> index; // 记录每个字符串中的所有位置
        for (int i = 0; i < s.size(); ++i) {
            index[s[i]].emplace_back(i); // 将字符的位置加入哈希表
        }
        int ret = 0; // 记录结果
        // 遍历哈希表中的每个字符
        for (auto&& [_, arr] : index) {
            arr.insert(arr.begin(), -1); // 在数组开头插入 -1, 表示左边界
            arr.emplace_back(s.size());  // 在数组末尾插入 s.size(), 表示右边界
            for (int i = 1; i < arr.size() - 1; ++i) {
                // 计算当前位置作为唯一字符的贡献
                ret += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
            }
        }
        return ret;
    }
};

Java

class Solution {
    public int uniqueLetterString(String s) {
        Map<Character, List<Integer>> index = new HashMap<>(); // 记录每个字符在字符串中的所有位置
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            index.computeIfAbsent(c, k -> new ArrayList<>()).add(i); // 将字符的位置加入哈希表
        }
        int res = 0; // 记录结果
        for (List<Integer> arr : index.values()) { // 遍历哈希表中的每个字符
            arr.add(0, -1); // 在列表开头插入 -1，表示左边界
            arr.add(s.length()); // 在列表末尾插入 s.length()，表示右边界
            for (int i = 1; i < arr.size() - 1; i++) { // 遍历字符的每个位置
                // 计算当前位置作为唯一字符的贡献
                res += (arr.get(i) - arr.get(i - 1)) * (arr.get(i + 1) - arr.get(i));
            }
        }
        return res; // 返回结果
    }
}

Python

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        index = {}  # 记录每个字符在字符串中的所有位置
        for i, c in enumerate(s):
            if c not in index:
                index[c] = []
            index[c].append(i)  # 将字符的位置加入字典
        res = 0  # 记录结果
        for arr in index.values():  # 遍历字典中的每个字符
            arr = (
                [-1] + arr + [len(s)]
            )  # 在列表开头插入 -1，表示左边界；在列表末尾插入 len(s)，表示右边界
            for i in range(1, len(arr) - 1):  # 遍历字符的每个位置
                # 计算当前位置作为唯一字符的贡献
                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])
        return res  # 返回结果

4、复杂度分析

1. 时间复杂度：
   • 遍历字符串并记录字符位置：O(n)。
   • 遍历哈希表中的每个字符并计算贡献：每个字符的位置数量为 O(n)，总时间复杂度为 O(n)。
   • 总时间复杂度：O(n)。
2. 空间复杂度：
   • 哈希表存储字符的位置：O(n)。
   • 总空间复杂度：O(n)。