2. 基础数据结构之哈希表

哈希表是由多个 key-value对来组成的，它有两个重要性质

• 性质1：哈希表中的key都是不重复的，因此可以用来进行去重操作
• 性质2：可以在 $o(1)$ 的时间内根据 key 得到 value 的值，因此也可以使用哈希表来记录元素的出现次数。

哈希表还可以去帮助实现离散化：差分专题中的离散化差分就是借助有序的哈希表来实现的，有序哈希表指的是key有序，而不是value有序，key是按照从小到大递增存储的，因此遍历有序哈希表的key是递增的。

1 果冻收藏家

题目链接

n = int(input())
a = list(map(int, input().split()))
cnt = {}
for i in range(n):
    cnt[a[i]] = cnt.get(a[i], 0) + 1
res = 0
for k, v in cnt.items():
    if v > 1:
        res += v - 1
print(res)

2 数组的最大权值

题目链接

import sys
input = lambda:sys.stdin.readline().strip()

n,k=map(int,input().split())
a=list(map(int,input().split()))

size=len(set(a))
print(min(k,size))

有些oj平台，不加前两行语句可能会报错
“traceback (most recent call last):
file “/w/foo.py”, line 1, in
eoferror: eof when reading a line”
这种错误通常是由于输入的方式或者输入数据的格式不符合预期引起的。常见的情况包括：

• 输入结束符不正确：

在一些在线评测系统中，特别是多行输入的情况下，如果输入结束时没有空行或者换行符，可能会导致这种错误。

• 输入数据不足：

如果程序期望接收多行输入，但实际上只提供了部分或没有提供任何输入，就会导致这个错误。

• 输入的方式不兼容：

某些平台或系统可能对输入有特定的要求或限制，例如需要使用 sys.stdin.readline() 来读取输入而不是简单的 input()。

3 you子串

题目链接

# 方法一
s = input()
cnts = {}  # 创建一个字典来存储每个字符的计数
for ch in s:
    cnts[ch] = cnts.get(ch, 0) + 1  # 计算每个字符的出现次数
num = min(cnts.get('y', 0), cnts.get('o', 0), cnts.get('u', 0))  # 计算'you'的最小出现次数
cnts['y'] = cnts.get('y', 0) - num
cnts['o'] = cnts.get('o', 0) - num
cnts['u'] = cnts.get('u', 0) - num
res = ''
# 先将'you'添加到结果字符串中
# for _ in range(num):  
#     res += 'you'
res = num * 'you'
for ch, count in cnts.items():
    res += ch * count  # 将剩余的字符添加到结果字符串中
print(res)

# 方法二
# from collections import counter

# s = input()

# cnt = min(s.count('y'), s.count('o'), s.count('u'))
# dic = counter(s)
# dic["y"] -= cnt
# dic["o"] -= cnt
# dic["u"] -= cnt

# res = cnt * "you"
# for k, v in dic.items():
#     if v > 0:
#         res += k * v
# print(res)

4 史莱姆大军

题目链接

n = int(input()) # 表示地图上的格子数量
a = [0] + list(map(int, input().split())) # 表示每只史莱姆的跳跃方向
pos = [i for i in range(n+1)]
for t in range(1, n+1): # 第1~n秒
    st = set()
    for i in range(1, n+1): # 编号1~n格子
        if a[i] == 1:  # 向右移动
            pos[i] += 1
        else:  # 向左移动
            pos[i] -= 1
        if 1 <= pos[i] <= n:
            st.add(pos[i])
    print(n - len(st), end=' ')

5 推荐算法

题目链接

n, q = map(int, input().split()) # 代表商品数量、用户搜索的关键词数量
k = list(map(str, input().split())) # 用户搜索过的关键词
name = [] # 商品名称
res = [] # 每一个元素又代表着（商品关键词命中个数，商品编号）
for i in range(n): # i表示商品编号
    name_m = input().split()
    name.append(name_m[0]) # 商品的名称
    m = int(name_m[1]) # 商品包含的关键词属性数量
    c = 0
    z = list(map(str, input().split())) # 该商品关键词
    for t in z:
        if t in k:
            c += 1
    res.append([c, i])
res.sort(key=lambda x: (-x[0], x[1]))
for i in range(n):
    print(name[res[i][1]]) # 通过商品编号获取商品名称

6 压缩数组

题目链接

s=input()
s=s[1:-1]  #去除首尾的括号
s = s.split(",")  #按照空格分隔,每一对数字用哈希表来记录
num,cnt=0,0
res=[]
for x in s:
    k = x.find('(')
    num1, cnt1 = int(x[:k]), int(x[k+1:-1])  #找到对应的数字以及出现的次数
    if num1 != num:  
        if cnt > 0:
            res.append((num, cnt))
        num, cnt = num1,cnt1
    else:
        cnt += cnt1
res.append((num, cnt))  #存最后一个数对
res = [f"{x}({y})" for x, y in res]
print("[" + ",".join(res) + "]")  #按照题目输出要求输出

7 手办爱好者

题目链接

在这里插入代码片

1 进球

题目链接

n = int(input())
dic = {}  # 统计每一支球队的进球次数
for _ in range(n):
    s = input()
    dic[s] = dic.get(s, 0) + 1  # 哈希表计数+1
print(dic)
# 根据最大值找到其对应的键
res = max(dic, key=dic.get)  # 遍历哈希表,查询出进球次数最大的球队
print(res)

3 滑动子数组的美丽值

题目链接

class solution:
    def getsubarraybeauty(self, nums, k, x):
        cnts = {}
        res = []
        n = len(nums)
        l = r = 0
        while r < n:
            cnts[nums[r]] = cnts.get(nums[r], 0) + 1
            if r - l + 1 > k:  # 当前窗口大小>k 左指针右移
                cnts[nums[l]] -= 1
                l += 1
            if r - l + 1 == k:  # 找到一个长度为k的区间
                cnt = 0  # 统计区间内的负数数量
                for i in range(-50, 0):
                    if i in cnts:
                        cnt += cnts[i]
                    if cnt >= x:   # 如果当前的负数数量已经>=x,说明当前数字i就是第x小的数字
                        res.append(i)
                        break
                if cnt < x:
                    res.append(0)
            r += 1
        return res

4 选取石子

题目链接

本题其实可以抽象为：如何将石子按照条件分组，使得组内所有石子的价值总和最大。对于相邻两个石子需要满足$x-y=a_x-a_y$，我们把$x$和$y$移动到等式一端，则可以得到$a_x-x=a_y-y$，我们不难看出，组内的石子按照从小到大排序可以得到一个递增的等差数列，也就是所有满足$a_x-x=t$（$t$为定值）均可以被分到一组，作为一种选择方案。因此，我们可以使用哈希表来存不同$t$值对应的石子价值总和，然后遍历哈希表来更新最大价值即可。

n = int(input())
a = [0] + list(map(int, input().split()))
mp = {}  # 记录每个分组的最大价值
for i in range(1, n + 1):
    mp[a[i] - i] = mp.get(a[i] - i, 0) + a[i]  # 当前分组加入价值a[i]的石头
res = 0  # 最大价值
for v in mp.values():  # 遍历哈希表
    res = max(res, v)
print(res)