u

python学习——哈希表法

哈希表与数组不同，不再使用索引，而是使用键值对来表示

python中的字典就是哈希表的体现

那么为什么还要学习哈希表法呢？

哈希表可以解决诸多问题。

下面是最简单的一种用法：

题目：两数之和，求出相加符合目标值的数,并返回对应下表

nums=[2,7,11,5]
target=9
hashset={}
for i in range(len(nums)):
    if hashset.get(target-nums[i]) is not None:
        print(hashset.get(target-nums[i]),i)
    hashset[nums[i]]=i

由题目可知求两数之和，那我们先建立一个字典（即哈希表）方便后续运算

进入循环，将无法与字典中所含数字相加为目标结果的数作为键存入字典（即哈希表）再将其在nums的索引作为值存入

接着我们再来看一种用法：

题目：整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

符号

值

I

1

V

5

X

10

L

50

C

100

D

500

M

1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

  • 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。

  • 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。

  • 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

在完成解题前我们要学习一个函数divmod

divmod 函数是 Python 中的内置函数，用于同时获取两个数相除的商和余数。当你使用 divmod 函数时，它会返回一个包含商和余数的元组

# 示例：使用 divmod 获取 7 和 2 相除的商和余数
result = divmod(7, 2)
print(result) # 输出：(3, 1)

因为罗马数字以1，5为界

所以在10进制中注意5这个点

num=3749
hashnet={1:"I",5:"V",10:"X",50:"L",100:"C",500:"D",1000:"M"}
ans=""
tip=1
while num>0:
    num,count=divmod(num,10)
    if count==4:
        ans=hashnet[tip]+hashnet[tip*5]+ans
    elif count==9:
        ans=hashnet[tip]+hashnet[tip*10]+ans
    else:
        if count<5:
            ans=count*hashnet[tip]+ans
        else:
            ans=hashnet[tip*5]+(count-5)*hashnet[tip]+ans
    tip=tip*10
print(ans)

tip为计数器,通过tip*5或10来应对罗马数中的情况，最后得到该程序

这种用法可以推广为密码的加密

我们再来看下一种应用：解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。

  2. 数字 1-9 在每一列只能出现一次。

  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

需要用到回溯法，不会

    def solveSudoku(self, board: List[List[str]]) -> None:
        row = [set(range(1, 10)) for _ in range(9)]  # 行剩余可用数字
        col = [set(range(1, 10)) for _ in range(9)]  # 列剩余可用数字
        block = [set(range(1, 10)) for _ in range(9)]  # 块剩余可用数字

        empty = []  # 收集需填数位置
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':  # 更新可用数字
                    val = int(board[i][j])
                    row[i].remove(val)
                    col[j].remove(val)
                    block[(i // 3)*3 + j // 3].remove(val)
                else:
                    empty.append((i, j))

        def backtrack(iter=0):
            if iter == len(empty):  # 处理完empty代表找到了答案
                return True
            i, j = empty[iter]
            b = (i // 3)*3 + j // 3
            for val in row[i] & col[j] & block[b]:
                row[i].remove(val)
                col[j].remove(val)
                block[b].remove(val)
                board[i][j] = str(val)
                if backtrack(iter+1):
                    return True
                row[i].add(val)  # 回溯
                col[j].add(val)
                block[b].add(val)
            return False
        backtrack()

作者：麦麦麦麦子。
链接：https://leetcode.cn/problems/sudoku-solver/solutions/27164/pythonsethui-su-chao-guo-95-by-mai-mai-mai-mai-zi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

观赏一下大哥的写法

主播正在努力消化q-q


site logo

Hi,Friend

© 2025 u