代码收藏家技术教程 2024-11-15

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

寻找独特数字卡片

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求：

设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。
尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1：

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2：

输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：数字 2 只出现一次，是独特的卡片。

样例3：

输入：cards = [7, 3, 3, 7, 10]
输出：10
解释：10 是班级中唯一一个不重复的数字卡片。

约束条件

1 ≤ cards.length ≤ 1001

0 ≤ cards[i] ≤ 1000

班级人数为奇数

除了一个数字卡片只出现一次外，其余每个数字卡片都恰好出现两次

def solution(cards):
    unique_card = 0
    for card in cards:
        unique_card ^= card
    return unique_card


if __name__ == "__main__":
    print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)  # 输出 4
    print(solution([0, 1, 0, 1, 2]) == 2)  # 输出 2
    print(solution([7, 3, 3, 7, 10]) == 10)  # 输出 10

找出整型数组中占比超过一半的数

问题描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

def solution(array):
    candidate = None
    count = 0
    
    for num in array:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate


if __name__ == "__main__":
    print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)  # 输出 3
    print(solution([5, 5, 5, 1, 2, 5, 5]) == 5)       # 输出 5
    print(solution([9, 9, 9, 9, 8, 9, 8, 8]) == 9)    # 输出 9

小U的数字插入问题

问题描述

小U手中有两个数字 a 和 b。第一个数字是一个任意的正整数，而第二个数字是一个非负整数。她的任务是将第二个数字 b 插入到第一个数字 a 的某个位置，以形成一个最大的可能数字。

你需要帮助小U找到这个插入位置，输出插入后的最大结果。

测试样例

样例1：

输入：a = 76543, b = 4
输出：765443

样例2：

输入：a = 1, b = 0
输出：10

样例3：

输入：a = 44, b = 5
输出：544

样例4：

输入：a = 666, b = 6
输出：6666

def solution(a: int, b: int) -> int:
    a_str = str(a)
    b_str = str(b)
    max_number = ""
    
    # 遍历所有可能的插入位置
    for i in range(len(a_str) + 1):
        # 在位置 i 插入 b_str
        new_number = a_str[:i] + b_str + a_str[i:]
        # 更新最大值
        if new_number > max_number:
            max_number = new_number
    
    return int(max_number)

if __name__ == '__main__':
    print(solution(76543, 4) == 765443)
    print(solution(1, 0) == 10)
    print(solution(44, 5) == 544)
    print(solution(666, 6) == 6666)

组成字符串ku的最大次数

问题描述

给定一个字符串 ss，该字符串中只包含英文大小写字母。你需要计算从字符串中最多能组成多少个字符串 "ku"。每次可以随机从字符串中选一个字符，并且选中的字符不能再使用。字符串中的字符大小写可以忽略，即大写和小写字母视为相同。

例如，输入 "AUBTMKAxfuu"，从中最多能组成 1 个 "ku"。

测试样例

样例1：

输入：s = "AUBTMKAxfuu"
输出：1

样例2：

输入：s = "KKuuUuUuKKKKkkkkKK"
输出：6

样例3：

输入：s = "abcdefgh"
输出：0

def solution(s: str) -> int:
    # 将字符串转换为小写以忽略大小写
    s = s.lower()
    
    # 统计 'k' 和 'u' 的出现次数
    count_k = s.count('k')
    count_u = s.count('u')
    
    # 返回可以组成的 'ku' 的最大次数
    return min(count_k, count_u)

if __name__ == '__main__':
    print(solution("AUBTMKAxfuu") == 1)  # True
    print(solution("KKuuUuUuKKKKkkkkKK") == 6)  # True
    print(solution("abcdefgh") == 0)  # True

游戏排名第三大的分数

问题描述

小M想要通过查看往届游戏比赛的排名来确定自己比赛的目标分数。他希望找到往届比赛中排名第三的分数，作为自己的目标。具体规则如下：

如果分数中有三个或以上不同的分数，返回其中第三大的分数。
如果不同的分数只有两个或更少，那么小M将选择最大的分数作为他的目标。

请你帮小M根据给定的分数数组计算目标分数。

测试样例

样例1：

输入：n = 3,nums = [3, 2, 1]
输出：1

样例2：

输入：n = 2,nums = [1, 2]
输出：2

样例3：

输入：n = 4,nums = [2, 2, 3, 1]
输出：1

def solution(n: int, nums: list) -> int:
    # 去重并排序
    unique_scores = sorted(set(nums))
    
    # 判断不同分数的数量
    if len(unique_scores) >= 3:
        return unique_scores[-3]  # 返回第三大的分数
    else:
        return unique_scores[-1]  # 返回最大的分数

if __name__ == '__main__':
    print(solution(3, [3, 2, 1]) == 1)  # 输出: 1
    print(solution(2, [1, 2]) == 2)      # 输出: 2
    print(solution(4, [2, 2, 3, 1]) == 1)  # 输出: 1

环状 DNA 序列的最小表示法

问题描述

小C正在研究一种环状的 DNA 结构，它由四种碱基A、C、G、T构成。这种环状结构的特点是可以从任何位置开始读取序列，因此一个长度为 n 的碱基序列可以有 n 种不同的表示方式。小C的任务是从这些表示中找到字典序最小的序列，即该序列的“最小表示”。

例如：碱基序列 ATCA 从不同位置读取可能的表示有 ATCA, TCAA, CAAT, AATC，其中 AATC 是字典序最小的表示。

测试样例

样例1：

输入：dna_sequence = "ATCA"
输出：'AATC'

样例2：

输入：dna_sequence = "CGAGTC"
输出：'AGTCCG'

样例3：

输入：dna_sequence = "TTGAC"
输出：'ACTTG'

def solution(dna_sequence: str) -> str:
    # 将dna_sequence连接到自身，得到所有旋转形式
    s = dna_sequence + dna_sequence
    n = len(dna_sequence)
    
    # 最小表示法初始为第一个旋转
    min_rotation = dna_sequence
    
    # 检查所有可能的旋转
    for i in range(1, n):
        current_rotation = s[i:i + n]
        if current_rotation < min_rotation:
            min_rotation = current_rotation
            
    return min_rotation

if __name__ == "__main__":
    print(solution("ATCA") == "AATC")
    print(solution("CGAGTC") == "AGTCCG")
    print(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG") == "AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG")

完美偶数计数

问题描述

小C定义了一个“完美偶数”。一个正整数 xx 被认为是完美偶数需要满足以下两个条件：

xx 是偶数；
xx 的值在区间 [l,r][l,r] 之间。

现在，小C有一个长度为 nn 的数组 aa，她想知道在这个数组中有多少个完美偶数。

测试样例

样例1：

输入：n = 5,l = 3,r = 8,a = [1, 2, 6, 8, 7]
输出：2

样例2：

输入：n = 4,l = 10,r = 20,a = [12, 15, 18, 9]
输出：2

样例3：

输入：n = 3,l = 1,r = 10,a = [2, 4, 6]
输出：3

def solution(n: int, l: int, r: int, a: list) -> int:
    count = 0
    for x in a:
        if x % 2 == 0 and l <= x <= r:
            count += 1
    return count

if __name__ == '__main__':
    print(solution(5, 3, 8, [1, 2, 6, 8, 7]) == 2)
    print(solution(4, 10, 20, [12, 15, 18, 9]) == 2)
    print(solution(3, 1, 10, [2, 4, 6]) == 3)

二进制之和

问题描述

小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过O(n^2)的前提下，返回两个二进制字符串的十进制求和结果。

测试样例

样例1：

输入：binary1 = "101" ,binary2 = "110"
输出：'11'

样例2：

输入：binary1 = "111111" ,binary2 = "10100"
输出：'83'

样例3：

输入：binary1 = "111010101001001011" ,binary2 = "100010101001"
输出：'242420'

样例4：

输入：binary1 = "111010101001011" ,binary2 = "10010101001"
输出：'31220'

样例5：

输入：binary1 = "11" ,binary2 = "1"
输出：'4'

def solution(binary1: str, binary2: str) -> str:
    # 将二进制字符串转换为十进制整数
    decimal1 = int(binary1, 2)
    decimal2 = int(binary2, 2)

    # 计算总和
    total = decimal1 + decimal2

    return str(total)

if __name__ == "__main__":
    print(solution("101", "110") == "11")  # True
    print(solution("111111", "10100") == "83")  # True
    print(solution("111010101001001011", "100010101001") == "242420")  # True
    print(solution("111010101001011", "10010101001") == "31220")  # True
    print(solution("11", "1") == "4")  # True

查找热点数据问题

问题描述

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。请按升序排列。

1 <= nums.length <= 10^5

k 的取值范围是 [1, 数组中不相同的元素的个数]

题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

你所设计算法的时间复杂度必须优于 O(n log n)，其中 n 是数组大小。

测试样例

样例1：

输入：nums = [1, 1, 1, 2, 2, 3], k = 2
输出：[1,2]

样例2：

输入：nums = [1], k = 1
输出：[1]

样例3：

输入：nums = [4, 4, 4, 2, 2, 2, 3, 3, 1], k = 2
输出：[2,4]

import heapq
from collections import Counter

def solution(nums, k):
    # 统计每个元素的频率
    freq_map = Counter(nums)
    
    # 使用最小堆存储前 k 个高频元素
    min_heap = []
    
    for num, freq in freq_map.items():
        heapq.heappush(min_heap, (freq, num))
        # 保持堆的大小为 k
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    # 提取结果并按升序排序
    top_k_elements = [num for freq, num in min_heap]
    return sorted(top_k_elements)

if __name__ == "__main__":
    print(solution([1, 1, 1, 2, 2, 3], 2) == [1, 2])  
    print(solution([1], 1) == [1])                      
    print(solution([4, 4, 4, 2, 2, 2, 3, 3, 1], 2) == [2, 4])

叠盘子排序

问题描述

小M有一个独特的方式来收拾家中的盘子。每次用餐后，他会将盘子按照他们的序号顺序叠放。盘子的序号都是唯一的整数，并且在收拾前就是递增的。小M的叠放规则是，每一堆盘子的序号都是连续递增的，并且至少包含3个盘子。需要编写程序帮助小M确定盘子的叠放方式。

例如，输入的盘子序号是 [-3, -2, -1, 2, 10, 15, 16, 18, 19, 20]，按照小M的规则，连续递增序列 -3, -2, -1 可以叠在一起表示为 -3--1，而 18, 19, 20 可以叠在一起表示为 18-20。不满足连续递增至少3个的，如 2, 10, 15, 16 都应单独列出。

输入参数

plates: 一个整数数组，表示盘子的序号

n: 盘子总数

测试样例

样例1：

输入：plates = [-3, -2, -1, 2, 10, 15, 16, 18, 19, 20], n = 10
输出："-3--1,2,10,15,16,18-20"

样例2：

输入：plates = [-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20], n = 20
输出："-6,-3-1,3-5,7-11,14,15,17-20"

样例3：

输入：plates = [1, 2, 7, 8, 9, 10, 11, 19], n = 8
输出："1,2,7-11,19"

def solution(plates: list[int], n: int) -> str:
    if n == 0:
        return ""
    
    result = []
    i = 0
    
    while i < n:
        start = plates[i]
        end = start
        
        # 寻找连续的递增序列
        while i + 1 < n and plates[i + 1] == plates[i] + 1:
            end = plates[i + 1]
            i += 1
        
        # 检查当前找到的序列的长度
        length = end - start + 1
        
        # 如果长度大于等于3，则将其格式化为范围
        if length >= 3:
            result.append(f"{start}-{end}")
        else:
            # 否则，将每个数字单独添加到结果
            for j in range(length):
                result.append(str(start + j))
        
        # 移动到下一个盘子
        i += 1
    
    return ",".join(result)

if __name__ == "__main__":
    print(solution([-3, -2, -1, 2, 10, 15, 16, 18, 19, 20], 10) == "-3--1,2,10,15,16,18-20")
    print(solution([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20], 20) == "-6,-3-1,3-5,7-11,14,15,17-20")
    print(solution([1, 2, 7, 8, 9, 10, 11, 19], 8) == "1,2,7-11,19")

连续子串和的整除问题

问题描述

小M是一个五年级的小学生，今天他学习了整除的知识，想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1}，然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这个问题吗？

测试样例

样例1：

输入：n = 3,b = 3,sequence = [1, 2, 3]
输出：3

样例2：

输入：n = 4,b = 5,sequence = [5, 10, 15, 20]
输出：10

样例3：

输入：n = 5,b = 2,sequence = [1, 2, 3, 4, 5]
输出：6

def solution(n, b, sequence):
    # 用于存储前缀和模 b 的频率
    mod_count = {0: 1}  # 初始化模为0的前缀和的频率为1（即空序列）
    current_sum = 0
    count = 0

    for num in sequence:
        current_sum += num
        mod_value = current_sum % b

        # 如果这个模值已经存在，说明有连续子序列的和能够被 b 整除
        if mod_value in mod_count:
            count += mod_count[mod_value]

        # 更新模值的出现次数
        if mod_value in mod_count:
            mod_count[mod_value] += 1
        else:
            mod_count[mod_value] = 1

    return count

if __name__ == "__main__":
    print(solution(3, 3, [1, 2, 3]) == 3)
    print(solution(4, 5, [5, 10, 15, 20]) == 10)
    print(solution(5, 2, [1, 2, 3, 4, 5]) == 6)

最大乘积区间问题

问题描述

小R手上有一个长度为 n 的数组 (n > 0)，数组中的元素分别来自集合 [0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]。小R想从这个数组中选取一段连续的区间，得到可能的最大乘积。

你需要帮助小R找到最大乘积的区间，并输出这个区间的起始位置 x 和结束位置 y (x ≤ y)。如果存在多个区间乘积相同的情况，优先选择 x 更小的区间；如果 x 相同，选择 y 更小的区间。

注意：数组的起始位置为 1，结束位置为 n。

测试样例

样例1：

输入：n = 5, arr = [1, 2, 4, 0, 8]
输出：[1, 3]

样例2：

输入：n = 7, arr = [1, 2, 4, 8, 0, 256, 0]
输出：[6, 6]

样例3：

输入：n = 8, arr = [1, 2, 4, 8, 0, 256, 512, 0]
输出：[6, 7]

def solution(n: int, arr: list[int]) -> list[int]:
    max_product = float('-inf')
    start = end = -1  # 存储最大乘积区间的起始和结束索引
    for i in range(n):
        if arr[i] == 0:
            continue  # 如果遇到0，直接跳过
        
        product = 1
        for j in range(i, n):
            if arr[j] == 0:
                break  # 如果遇到0，停止计算当前区间的乘积
            
            product *= arr[j]
            if product > max_product:
                max_product = product
                start = i
                end = j
            elif product == max_product:
                if i < start or (i == start and j < end):
                    start = i
                    end = j
    
    # 如果未找到有效区间，返回[-1, -1]
    if start == -1 or end == -1:
        return [-1, -1]
    
    # 返回区间的1-based索引
    return [start + 1, end + 1]

if __name__ == "__main__":
    print(solution(5, [1, 2, 4, 0, 8]) == [1, 3])
    print(solution(7, [1, 2, 4, 8, 0, 256, 0]) == [6, 6])
    print(solution(8, [1, 2, 4, 8, 0, 256, 512, 0]) == [6, 7])

完美整数

问题描述

一个整数如果由相同的数字构成，则称为完美整数。例如：

1、11、333 是完美整数。

12、19、101 是不完美整数。

现在，你需要计算给定区间 [x, y] 中有多少个整数是完美整数。

测试样例

样例1：

输入：x = 1 ,y = 10
输出：9

样例2：

输入：x = 2 ,y = 22
输出：10

def is_perfect_integer(n):
    # 将数字转换为字符串
    s = str(n)
    # 检查所有字符是否相同
    return all(digit == s[0] for digit in s)

def solution(x, y):
    count = 0
    # 在区间 [x, y] 中循环
    for num in range(x, y + 1):
        if is_perfect_integer(num):
            count += 1
    return count

if __name__ == "__main__":
    print(solution(1, 10) == 9)  # 输出: True
    print(solution(2, 22) == 10)  # 输出: True

线上报警问题分类

问题描述

AB 实验作为推荐策略迭代的有力工具，经常会有新的实验上线，以及一些无效策略的下线。在这些迭代过程中，难免会遇到意料之外的情况，导致部分服务崩溃而不可用。为了避免系统的全面崩溃，工程师们会添加监控报警，确保第一时间通知到值班同学进行处理。

小M同学刚刚开始负责线上报警的值班工作。很快，她就收到了第一条报警日志。在报警的时间范围内，小M同学收到了 NN 名用户的反馈，每位用户编号为 11 到 NN。小M同学查询线上实验后，统计了用户命中实验的列表，其中第 ii 位用户命中了 kiki 个实验，第 jj 个实验的编号为 ai,jai,j。

这些用户的反馈并不完全是由于一个问题造成的，因此小M同学需要对这些问题进行分类。根据先前的经验，小M同学会进行 QQ 次询问尝试对问题进行分类，第 ii 次询问会给出一个序列 bi,1,bi,2,…,bi,cibi,1,bi,2,…,bi,ci，cici 表示第 ii 次查询的实验数量。当 bi,j>0bi,j>0 时表示命中实验 ∣bi,j∣∣bi,j∣，否则表示未命中实验 ∣bi,j∣∣bi,j∣。小M同学需要得到符合这些条件的用户数。例如，序列 1, -2, 3 表示命中实验 1, 3 且未命中实验 2 的用户数量。

小M同学初来乍到，希望你能帮她解决这个问题。

测试样例

样例1：

输入：n = 3, m = 3, q = 3, arrayN = [[2, 1, 2], [2, 2, 3], [2, 1, 3]], arrayQ = [[2, 1, -2], [2, 2, -3], [2, 3, -1]]
输出：[1, 1, 1]

样例2：

输入：n = 5, m = 4, q = 2, arrayN = [[3, 1, 2, 3], [1, 2], [2, 1, 4], [3, 2, 3, 4], [2, 1, 3]], arrayQ = [[3, 1, -4, 2], [2, -1, -3]]
输出：[1, 1]

样例3：

输入：n = 4, m = 3, q = 2, arrayN = [[1, 1], [2, 2, 3], [1, 3], [2, 1, 2]], arrayQ = [[1, -3], [2, 2, 3]]
输出：[2, 1]

def solution(n, m, q, arrayN, arrayQ):
    # 存储每个用户命中的实验
    user_experiments = [set(arr[1:]) for arr in arrayN]

    results = []
    
    for query in arrayQ:
        count = 0
        c_i = query[0]
        required_hits = set()
        required_misses = set()

        # 根据查询条件分类出命中和未命中的实验
        for j in range(1, c_i + 1):
            if query[j] > 0:
                required_hits.add(query[j])
            else:
                required_misses.add(-query[j])

        # 检查每个用户是否符合查询条件
        for user in range(n):
            hits = user_experiments[user]
            if required_hits.issubset(hits) and required_misses.isdisjoint(hits):
                count += 1

        results.append(count)

    return results


if __name__ == "__main__":
    print(
        solution(
            3,
            3,
            3,
            [[2, 1, 2], [2, 2, 3], [2, 1, 3]],
            [[2, 1, -2], [2, 2, -3], [2, 3, -1]],
        )
        == [1, 1, 1]
    )
    
    print(
        solution(
            5,
            4,
            2,
            [[3, 1, 2, 3], [1, 2], [2, 1, 4], [3, 2, 3, 4], [2, 1, 3]],
            [[3, 1, -4, 2], [2, -1, -3]]
        )
        == [1, 1]
    )
    
    print(
        solution(
            4,
            3,
            2,
            [[1, 1], [2, 2, 3], [1, 3], [2, 1, 2]],
            [[1, -3], [2, 2, 3]]
        )
        == [2, 1]
    )

游戏队友搜索

问题描述

在一款多人游戏中，每局比赛需要多个玩家参与。如果发现两名玩家至少一起玩过两局比赛，则可以认为这两名玩家互为队友。现在你有一份玩家（通过玩家ID标识）和比赛局次（通过比赛ID标识）的历史记录表，目标是帮助某位指定玩家找到所有符合条件的队友。

例如，已知以下比赛历史记录：

| 玩家ID | 游戏ID |

测试样例

样例1：

输入：id = 1, num = 10, array = [[1,1], [1,2], [1,3], [2,1], [2,4], [3,2], [4,1], [4,2], [5,2], [5,3]]
输出：[4, 5]

样例2：

输入：id = 2, num = 6, array = [[2,1], [2,3], [1,1], [1,2], [3,1], [4,3]]
输出：[]

样例3：

输入：id = 3, num = 8, array = [[3,1], [3,2], [3,3], [4,1], [5,2], [6,3], [7,1], [7,2]]
输出：[7]

def solution(id, num, array):
    from collections import defaultdict

    # 字典记录每个玩家参与的比赛
    player_games = defaultdict(set)
    
    # 填充字典
    for player_id, game_id in array:
        player_games[player_id].add(game_id)
    
    # 寻找指定玩家的队友
    teammates = set()  # 用于存放找到的队友
    target_games = player_games[id]  # 获取目标玩家的比赛ID集合
    
    # 遍历所有玩家，寻找符合条件的队友
    for player in player_games:
        if player != id:
            # 计算目标玩家和当前玩家的共同比赛数量
            common_games = target_games.intersection(player_games[player])
            if len(common_games) >= 2:  # 至少共同参与2场比赛
                teammates.add(player)

    return sorted(teammates)  # 返回队友的有序列表

if __name__ == "__main__":
    # 添加测试用例
    print(
        solution(
            1,
            10,
            [
                [1, 1],
                [1, 2],
                [1, 3],
                [2, 1],
                [2, 4],
                [3, 2],
                [4, 1],
                [4, 2],
                [5, 2],
                [5, 3],
            ],
        )
        == [4, 5]
    )
    
    print(solution(2, 6, [[2, 1], [2, 3], [1, 1], [1, 2], [3, 1], [4, 3]]) == [])
    print(solution(3, 8, [[3, 1], [3, 2], [3, 3], [4, 1], [5, 2], [6, 3], [7, 1], [7, 2]]) == [7])