稀土掘金——AI刷题4（python版）

判断回旋镖的存在

问题描述

小M正在玩一个几何游戏，给定一个二维平面上的三个点

points

，其中每个点用坐标

points[i] = [xi, yi]

表示。如果三点构成一个回旋镖，则返回

true

。回旋镖的定义是三点不在一条直线上，并且这三个点互不相同。

请你帮助小M判断这些点是否构成一个回旋镖。

---

测试样例

样例1：

输入：

points = [[1, 1], [2, 3], [3, 2]]

输出：

True

样例2：

输入：

points = [[1, 1], [2, 2], [3, 3]]

输出：

False

样例3：

输入：

points = [[0, 0], [1, 1], [1, 0]]

输出：

True

def solution(points: list) -> bool:
    # 检查三点是否相同
    if points[0] == points[1] or points[0] == points[2] or points[1] == points[2]:
        return False
    
    # 提取点的坐标
    x1, y1 = points[0]
    x2, y2 = points[1]
    x3, y3 = points[2]
    
    # 判断三点是否共线
    return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1)

if __name__ == '__main__':
    print(solution(points=[[1, 1], [2, 3], [3, 2]]) == True)  # True
    print(solution(points=[[1, 1], [2, 2], [3, 3]]) == False) # False
    print(solution(points=[[0, 0], [1, 1], [1, 0]]) == True)  # True

小F的永久代币卡回本计划

问题描述

小F最近迷上了玩一款游戏，她面前有一个永久代币卡的购买机会。该卡片的价格为

a

勾玉，每天登录游戏可以返还

b

勾玉。小F想知道她至少需要登录多少天，才能让购买的永久代币卡回本。

---

测试样例

样例1：

输入：

a = 10, b = 1

输出：

10

样例2：

输入：

a = 10, b = 2

输出：

5

样例3：

输入：

a = 10, b = 3

输出：

4

def solution(a: int, b: int) -> int:
    # 如果整除，直接返回 a // b，否则加 1 天
    return (a + b - 1) // b

# 测试用例
if __name__ == '__main__':
    print(solution(10, 1) == 10)  # 输出 10
    print(solution(10, 2) == 5)   # 输出 5
    print(solution(10, 3) == 4)   # 输出 4

比赛配对问题

问题描述

小R正在组织一个比赛，比赛中有

n

支队伍参赛。比赛遵循以下独特的赛制：

• 如果当前队伍数为 偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
• 如果当前队伍数为 奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

小R想知道在比赛中进行的配对次数，直到决出唯一的获胜队伍为止。

---

测试样例

样例1：

输入：

n = 7

输出：

6

样例2：

输入：

n = 14

输出：

13

样例3：

输入：

n = 1

输出：

0

def solution(n: int) -> int:
    matches = 0
    while n > 1:
        if n % 2 == 0:
            matches += n // 2
            n = n // 2
        else:
            matches += (n - 1) // 2
            n = (n - 1) // 2 + 1
    return matches

# 测试用例
if __name__ == '__main__':
    print(solution(7) == 6)    # 输出：6
    print(solution(14) == 13)  # 输出：13
    print(solution(1) == 0)    # 输出：0

不同整数的计数问题

问题描述

小R有一个字符串

word

，该字符串由数字和小写英文字母组成。小R想用空格替换每一个不是数字的字符。然后，他希望统计在替换后剩下的整数中，不同整数的数目。

例如，给定字符串

"a123bc34d8ef34"

，替换后形成的字符串是

" 123 34 8 34"

，剩下的整数是

"123"

、

"34"

、

"8"

和

"34"

。不同的整数有三个，即

"123"

、

"34"

和

"8"

。

注意，只有当两个整数的不含前导零的十进制表示不同，才认为它们是不同的整数。

---

测试样例

样例1：

输入：

word = "a123bc34d8ef34"

输出：

3

样例2：

输入：

word = "t1234c23456"

输出：

2

样例3：

输入：

word = "a1b01c001d4"

输出：

2

def solution(word: str) -> int:
    # 将非数字字符替换为空格
    modified_word = ''.join(char if char.isdigit() else ' ' for char in word)
    # 分割字符串，提取出数字部分
    numbers = modified_word.split()
    
    # 使用集合去重，处理前导零
    unique_numbers = set(int(num) for num in numbers)  # 转换为整数以去掉前导零

    return len(unique_numbers)

if __name__ == '__main__':
    # 测试用例
    print(solution("a123bc34d8ef34") == 3)  # True
    print(solution("t1234c23456") == 2)    # True
    print(solution("a1b01c001d4") == 2)     # True

判断子数组能否被5整除的问题

问题描述

小R有一个二进制数组

nums

，其中的下标从 0 开始。我们定义

xi

为从最高有效位到最低有效位的子数组

nums[0..i]

所表示的二进制数。例如，如果

nums = [1, 0, 1]

，那么

x0 = 1

，

x1 = 2

，

x2 = 5

。

小R想知道，对于每个

xi

，它能否被 5 整除。你需要返回一个布尔值列表

answer

，当

xi

能够被 5 整除时，

answer[i]

为

true

，否则为

false

。

---

测试样例

样例1：

输入：

nums = [0, 1, 1]

输出：

[True, False, False]

样例2：

输入：

nums = [1, 0, 1, 1, 0]

输出：

[False, False, True, False, False]

样例3：

输入：

nums = [1, 1, 1]

输出：

[False, False, False]

def solution(nums: list) -> list:
    answer = []
    current_value = 0  # 初始化当前值

    for num in nums:
        # 更新当前值，采用模运算避免溢出
        current_value = (current_value * 2 + num) % 5
        # 判断当前值是否能被 5 整除
        answer.append(current_value == 0)

    return answer

# 测试
if __name__ == '__main__':
    print(solution(nums=[0, 1, 1]) == [True, False, False])  # 应该返回 True
    print(solution(nums=[1, 0, 1, 1, 0]) == [False, False, True, False, False])  # 应该返回 True
    print(solution(nums=[1, 1, 1]) == [False, False, False])  # 应该返回 True

字符串解码问题

问题描述

小R正在处理一个包含小写字母的字符串解码问题。给定一个长度为

N

的字符串

S

，其中包含小写英文字母。字符串的解码规则如下：

1. 字符 'x' 应解码为 'y'，字符 'y' 应解码为 'x'。
2. 字符 'a' 应解码为 'b'，字符 'b' 应解码为 'a'。
3. 所有其他字符保持不变。

你的任务是返回解码后的字符串。

---

测试样例

样例1：

输入：

N = 5, S = "xaytq"

输出：

'ybxtq'

样例2：

输入：

N = 6, S = "abcxyz"

输出：

'bacyxz'

样例3：

输入：

N = 3, S = "zzz"

输出：

'zzz'

def solution(N: int, S: str) -> str:
    decoded_chars = []
    
    for char in S:
        if char == 'x':
            decoded_chars.append('y')
        elif char == 'y':
            decoded_chars.append('x')
        elif char == 'a':
            decoded_chars.append('b')
        elif char == 'b':
            decoded_chars.append('a')
        else:
            decoded_chars.append(char)
    
    return ''.join(decoded_chars)

if __name__ == '__main__':
    print(solution(N = 5, S = "xaytq") == 'ybxtq')  # True
    print(solution(N = 6, S = "abcxyz") == 'bacyxz')  # True
    print(solution(N = 3, S = "zzz") == 'zzz')        # True

小Q的奇偶操作数组

问题描述

小Q有一个长度为 nn 的数组，他可以进行 kk 次操作，每次操作可以对数组中的任意一个数字执行以下操作：

1. 如果选择的数字 xx 是奇数，则将 xx 乘以 2，即 x=x×2x=x×2。
2. 如果选择的数字 xx 是偶数，则将 xx 乘以 2 再加 1，即 x=x×2+1x=x×2+1。

小Q想知道，经过 kk 次操作后，数组的元素之和最小可以是多少。

---

测试样例

样例1：

输入：

n = 5 ,k = 3 ,a = [1, 2, 3, 5, 2]

输出：

20

样例2：

输入：

n = 3 ,k = 2 ,a = [7, 8, 9]

输出：

40

样例3：

输入：

n = 4 ,k = 4 ,a = [2, 3, 5, 7]

输出：

33

import heapq

def solution(n: int, k: int, a: list) -> int:
    # 将数组转换为最小堆
    min_heap = a[:]
    heapq.heapify(min_heap)
    
    # 执行 k 次操作
    for _ in range(k):
        # 取出堆顶最小的元素
        min_value = heapq.heappop(min_heap)
        
        # 根据奇偶性进行操作
        if min_value % 2 == 0:  # 偶数
            new_value = min_value * 2 + 1
        else:  # 奇数
            new_value = min_value * 2
            
        # 将新值重新放入堆中
        heapq.heappush(min_heap, new_value)

    # 计算最终的数组和
    return sum(min_heap)

if __name__ == '__main__':
    print(solution(5, 3, [1, 2, 3, 5, 2]) == 20)  # 应该返回 True
    print(solution(3, 2, [7, 8, 9]) == 40)  # 应该返回 True
    print(solution(4, 4, [2, 3, 5, 7]) == 33)  # 应该返回 True

括号补全问题

问题描述

小R有一个括号字符串

s

，他想知道这个字符串是否是有效的。一个括号字符串如果满足以下条件之一，则是有效的：

1. 它是一个空字符串；
2. 它可以写成两个有效字符串的连接形式，即 AB；
3. 它可以写成 (A) 的形式，其中 A 是有效字符串。

在每次操作中，小R可以在字符串的任意位置插入一个括号。你需要帮小R计算出，最少需要插入多少个括号才能使括号字符串

s

有效。

例如：当

s = "())"

时，小R需要插入一个左括号使字符串有效，结果为

1

。

---

测试样例

样例1：

输入：

s = "())"

输出：

1

样例2：

输入：

s = "((("

输出：

3

样例3：

输入：

s = "()"

输出：

0

样例4：

输入：

s = "()))(("

输出：

4

def solution(s: str) -> int:
    left_needed = 0  # 需要的左括号数
    right_needed = 0  # 需要的右括号数

    for char in s:
        if char == '(':
            left_needed += 1  # 遇到左括号，增加需要的左括号数
        elif char == ')':
            if left_needed > 0:
                left_needed -= 1  # 有左括号可以匹配，减少需要的左括号数
            else:
                right_needed += 1  # 没有左括号可匹配，增加需要的右括号数

    return left_needed + right_needed  # 返回需要插入的总括号数

# 测试
if __name__ == '__main__':
    print(solution("())") == 1)       # 应该返回 True
    print(solution("(((") == 3)        # 应该返回 True
    print(solution("()") == 0)         # 应该返回 True
    print(solution("()))((") == 4)     # 应该返回 True

数字字符串中圆圈的数量计算

问题描述

小I拿到了一串数字字符，她想知道这串数字中一共有多少个圆圈。具体规则如下：

• 数字0、6、9各含有一个圆圈。
• 数字8含有两个圆圈。
• 其他数字不含有任何圆圈。

---

测试样例

样例1：

输入：

s = "1234567890"

输出：

5

样例2：

输入：

s = "8690"

输出：

5

样例3：

输入：

s = "1111"

输出：

0

def solution(s: str) -> int:
    # 定义每个数字对应的圆圈数量
    circles = {
        '0': 1,
        '1': 0,
        '2': 0,
        '3': 0,
        '4': 0,
        '5': 0,
        '6': 1,
        '7': 0,
        '8': 2,
        '9': 1
    }
    
    # 计算圆圈的总数
    total_circles = sum(circles[digit] for digit in s)
    
    return total_circles

if __name__ == '__main__':
    print(solution(s = "1234567890") == 5)  # True
    print(solution(s = "8690") == 5)          # True
    print(solution(s = "1111") == 0)          # True

等和子数组问题

问题描述

小F最近在研究数组中子数组的总和问题。现在给定一个长度为

N

的数组

A

，数组按非递减顺序排序。你需要判断是否存在两个不同的长度相同的子数组，它们的元素总和相等。如果存在这样的子数组，返回

1

；否则，返回

0

。

请注意，只要两个子数组的起始和结束索引不同，即便它们包含相同的元素，也被认为是不同的子数组。

---

测试样例

样例1：

输入：

N = 5, A = [2, 5, 5, 5, 9]

输出：

True

样例2：

输入：

N = 4, A = [1, 2, 3, 4]

输出：

False

样例3：

输入：

N = 6, A = [1, 1, 2, 3, 3, 6]

输出：

True

def solution(N: int, A: list) -> int:
    prefix_sum = [0] * (N + 1)
    
    # 计算前缀和
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
    
    # 用于存储已经出现的和和长度组合
    seen = {}
    
    # 遍历所有可能的子数组长度
    for length in range(1, N + 1):
        for start in range(N - length + 1):
            # 计算当前子数组的和
            end = start + length
            current_sum = prefix_sum[end] - prefix_sum[start]
            
            # 检查当前和及其长度是否已经存在
            if (current_sum, length) in seen:
                return 1  # 找到相同的和和长度的子数组
            seen[(current_sum, length)] = True
    
    return 0  # 没有找到这样的子数组

if __name__ == '__main__':
    print(solution(N = 5, A = [2, 5, 5, 5, 9]) == 1)  # True
    print(solution(N = 4, A = [1, 2, 3, 4]) == 0)  # False
    print(solution(N = 6, A = [1, 1, 2, 3, 3, 6]) == 1)  # True

构造特定数组的逆序拼接

问题描述

小U得到了一个数字n，他的任务是构造一个特定数组。这个数组的构造规则是：对于每个i从1到n，将数字n到i逆序拼接，直到i等于n为止。最终，输出这个拼接后的数组。

例如，当n等于3时，拼接后的数组是

[3, 2, 1, 3, 2, 3]

。

---

测试样例

样例1：

输入：

n = 3

输出：

[3, 2, 1, 3, 2, 3]

样例2：

输入：

n = 4

输出：

[4, 3, 2, 1, 4, 3, 2, 4, 3, 4]

样例3：

输入：

n = 5

输出：

[5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5]

def solution(n: int) -> list:
    result = []
    for i in range(1, n + 1):
        result.extend(range(n, i - 1, -1))
    return result

# 测试用例
if __name__ == '__main__':
    print(solution(3) == [3, 2, 1, 3, 2, 3])
    print(solution(4) == [4, 3, 2, 1, 4, 3, 2, 4, 3, 4])
    print(solution(5) == [5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5])

小R的随机播放顺序

问题描述

小R有一个特殊的随机播放规则。他首先播放歌单中的第一首歌，播放后将其从歌单中移除。如果歌单中还有歌曲，则会将当前第一首歌移到最后一首。这个过程会一直重复，直到歌单中没有任何歌曲。

例如，给定歌单

[5, 3, 2, 1, 4]

，真实的播放顺序是

[5, 2, 4, 1, 3]

。

保证歌曲中的

id

两两不同。

---

测试样例

样例1：

输入：

n = 5 ,a = [5, 3, 2, 1, 4]

输出：

[5, 2, 4, 1, 3]

样例2：

输入：

n = 4 ,a = [4, 1, 3, 2]

输出：

[4, 3, 1, 2]

样例3：

输入：

n = 6 ,a = [1, 2, 3, 4, 5, 6]

输出：

[1, 3, 5, 2, 6, 4]

from collections import deque

def solution(n: int, a: list) -> list:
    playlist = deque(a)  # 将输入列表转换为双端队列
    result = []          # 存储播放顺序的结果

    while playlist:
        # 播放当前第一首歌
        result.append(playlist.popleft())
        if playlist:
            # 将新的第一首歌移动到最后
            playlist.append(playlist.popleft())
    
    return result

if __name__ == '__main__':
    print(solution(n = 5, a = [5, 3, 2, 1, 4]) == [5, 2, 4, 1, 3])
    print(solution(n = 4, a = [4, 1, 3, 2]) == [4, 3, 1, 2])
    print(solution(n = 6, a = [1, 2, 3, 4, 5, 6]) == [1, 3, 5, 2, 6, 4])

饭馆菜品选择问题

问题描述

小C来到了一家饭馆，这里共有 nn 道菜，第 ii 道菜的价格为

a_i

。其中一些菜中含有蘑菇，

s_i

代表第 ii 道菜是否含有蘑菇。如果

s_i = '1'

，那么第 ii 道菜含有蘑菇，否则没有。

小C希望点 kk 道菜，且希望总价格尽可能低。由于她不喜欢蘑菇，她希望所点的菜中最多只有 mm 道菜含有蘑菇。小C想知道在满足条件的情况下能选出的最小总价格是多少。如果无法按照要求选择菜品，则输出

-1

。

---

测试样例

样例1：

输入：

s = "001", a = [10, 20, 30], m = 1, k = 2

输出：

30

样例2：

输入：

s = "111", a = [10, 20, 30], m = 1, k = 2

输出：

-1

样例3：

输入：

s = "0101", a = [5, 15, 10, 20], m = 2, k = 3

输出：

30

def solution(s: str, a: list, m: int, k: int) -> int:
    mushroom_dishes = []
    non_mushroom_dishes = []

    # 分类菜品
    for i in range(len(s)):
        if s[i] == '1':
            mushroom_dishes.append(a[i])
        else:
            non_mushroom_dishes.append(a[i])
    
    # 排序
    mushroom_dishes.sort()
    non_mushroom_dishes.sort()
    
    min_price = float('inf')
    num_mushrooms = len(mushroom_dishes)
    num_non_mushrooms = len(non_mushroom_dishes)

    # 遍历含蘑菇的菜品数量
    for mushrooms_count in range(min(m, num_mushrooms) + 1):
        if mushrooms_count > k:  # 如果含蘑菇的数量超过要求的总数，跳过
            continue
        non_mushrooms_count = k - mushrooms_count  # 剩余需要的不含蘑菇的菜品数量
        
        if non_mushrooms_count > num_non_mushrooms:  # 不含蘑菇的菜品不足
            continue
        
        # 计算当前组合的总价格
        current_price = sum(mushroom_dishes[:mushrooms_count]) + sum(non_mushroom_dishes[:non_mushrooms_count])
        min_price = min(min_price, current_price)

    return min_price if min_price != float('inf') else -1

if __name__ == '__main__':
    print(solution("001", [10, 20, 30], 1, 2) == 30)
    print(solution("111", [10, 20, 30], 1, 2) == -1)
    print(solution("0101", [5, 15, 10, 20], 2, 3) == 30)

判断数组是否单调

问题描述

小S最近在研究一些数组的性质，她发现有一种非常有趣的数组被称为 单调数组。如果一个数组是单调递增或单调递减的，那么它就是单调的。

• 当对于所有索引i <= j时，nums[i] <= nums[j]，数组nums是单调递增的。
• 当对于所有索引i <= j时，nums[i] >= nums[j]，数组nums是单调递减的。

你需要编写一个程序来判断给定的数组

nums

是否为单调数组。如果是，返回

true

，否则返回

false

。

---

测试样例

样例1：

输入：

nums = [1, 2, 2, 3]

输出：

True

样例2：

输入：

nums = [6, 5, 4, 4]

输出：

True

样例3：

输入：

nums = [1, 3, 2, 4, 5]

输出：

False

def solution(nums: list) -> bool:
    is_increasing = True
    is_decreasing = True
    
    for i in range(len(nums) - 1):
        if nums[i] < nums[i + 1]:
            is_decreasing = False
        elif nums[i] > nums[i + 1]:
            is_increasing = False

    return is_increasing or is_decreasing

if __name__ == '__main__':
    print(solution(nums=[1, 2, 2, 3]) == True)  # True
    print(solution(nums=[6, 5, 4, 4]) == True)  # True
    print(solution(nums=[1, 3, 2, 4, 5]) == False)  # False

小F的矩阵值调整

问题描述

小F得到了一个矩阵。如果矩阵中某一个格子的值是偶数，则该值变为它的三倍；如果是奇数，则保持不变。小F想知道调整后的矩阵是什么样子的。

---

测试样例

样例1：

输入：

a = [[1, 2, 3], [4, 5, 6]]

输出：

[[1, 6, 3], [12, 5, 18]]

样例2：

输入：

a = [[7, 8, 9], [10, 11, 12]]

输出：

[[7, 24, 9], [30, 11, 36]]

样例3：

输入：

a = [[2, 4], [6, 8]]

输出：

[[6, 12], [18, 24]]

def solution(a: list) -> list:
    # 使用列表推导式遍历矩阵
    return [[(x * 3 if x % 2 == 0 else x) for x in row] for row in a]

if __name__ == '__main__':
    print(solution([[1, 2, 3], [4, 5, 6]]) == [[1, 6, 3], [12, 5, 18]])  # True
    print(solution([[7, 8, 9], [10, 11, 12]]) == [[7, 24, 9], [30, 11, 36]])  # True
    print(solution([[2, 4], [6, 8]]) == [[6, 12], [18, 24]])  # True

小Q的非素数和排列问题

问题描述

小C对排列很感兴趣，她想知道有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。排列定义为一个长度为n的数组，其中包含从1到n的所有整数，每个数字恰好出现一次。

---

测试样例

样例1：

输入：

n = 5

输出：

4

样例2：

输入：

n = 3

输出：

0

样例3：

输入：

n = 6

输出：

24

from itertools import permutations

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def solution(n: int) -> int:
    count = 0
    # Generate all permutations of numbers from 1 to n
    for perm in permutations(range(1, n + 1)):
        valid = True
        # Check adjacent elements
        for i in range(n - 1):
            if is_prime(perm[i] + perm[i + 1]):
                valid = False
                break
        if valid:
            count += 1
    return count

if __name__ == '__main__':
    print(solution(n = 5) == 4)  # True
    print(solution(n = 3) == 0)  # True
    print(solution(n = 6) == 24)  # True

按位与三元组问题

问题描述

小R正在研究位运算中的按位与操作。给定一个整数数组

nums

，你需要找到数组中所有满足条件的 按位与三元组 的数目。按位与三元组是由下标

(i, j, k)

组成的三元组，满足以下条件：

1. 0 <= i < nums.length
2. 0 <= j < nums.length
3. 0 <= k < nums.length
4. nums[i] & nums[j] & nums[k] == 0，其中 & 表示按位与运算符。

请你返回所有这样的三元组的数目。

---

测试样例

样例1：

输入：

nums = [2,1,3]

输出：

12

样例2：

输入：

nums = [0,2,5]

输出：

25

样例3：

输入：

nums = [1,2,4]

输出：

24

def solution(nums: list) -> int:
    count = 0
    n = len(nums)
    
    # 遍历所有可能的三元组 (i, j, k)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (nums[i] & nums[j] & nums[k]) == 0:
                    count += 1
    
    return count

# 测试
if __name__ == '__main__':
    print(solution(nums=[2, 1, 3]) == 12)  # 应该返回 True
    print(solution(nums=[0, 2, 5]) == 25)  # 应该返回 True
    print(solution(nums=[1, 2, 4]) == 24)  # 应该返回 True

相邻重复字母删除问题

问题描述

小M拿到了一个由小写字母组成的字符串

s

。她发现可以进行一种操作：选择两个相邻且相同的字母并删除它们。她可以在

s

上反复进行此操作，直到无法再删除任何字母。

请返回最终处理完所有重复项删除操作后的字符串。可以保证返回的答案是唯一的。

---

测试样例

样例1：

输入：

s = "abbaca"

输出：

'ca'

样例2：

输入：

s = "azxxzy"

输出：

'ay'

样例3：

输入：

s = "a"

输出：

'a'

def solution(s: str) -> str:
    stack = []
    
    for char in s:
        if stack and stack[-1] == char:  # 检查栈顶元素是否与当前字符相同
            stack.pop()  # 删除栈顶元素
        else:
            stack.append(char)  # 压入当前字符
    
    return ''.join(stack)  # 将栈中元素合并成字符串返回

# 测试
if __name__ == '__main__':
    print(solution(s="abbaca") == 'ca')  # 应该返回 True
    print(solution(s="azxxzy") == 'ay')   # 应该返回 True
    print(solution(s="a") == 'a')         # 应该返回 True

给定字符串的字符去重问题

问题描述

给定一个字符串 ss，你需要通过删除一些字符，使得每个字符在字符串中出现的次数均不相同。你需要找出最少需要删除的字符数量以达到这个目标。

例如，对于字符串

"aab"

，字符

"a"

出现2次，字符

"b"

出现1次，这些出现次数已经不同，因此不需要删除任何字符，输出为0。

---

测试样例

样例1：

输入：

s = "aab"

输出：

0

样例2：

输入：

s = "aaabbbcc"

输出：

2

样例3：

输入：

s = "abcdef"

输出：

5

def solution(s: str) -> int:
    from collections import Counter
    
    # 计算每个字符的频率
    freq = Counter(s)
    
    # 存储已使用的频率
    used_freq = set()
    deletions = 0
    
    # 遍历每个字符及其频率
    for count in freq.values():
        while count > 0 and count in used_freq:
            count -= 1  # 减少频率
            deletions += 1  # 记录删除次数
        used_freq.add(count)  # 添加当前频率到已使用的集合中
    
    return deletions

if __name__ == '__main__':
    print(solution("aab") == 0)           # 0
    print(solution("aaabbbcc") == 2)      # 2
    print(solution("abcdef") == 5)         # 5