当前位置：首页 > backend >正文

leetcode 每日一题 1931. 用三种不同颜色为网格涂色

backend 2025/5/20 6:54:50

题目

1931. 用三种不同颜色为网格涂色

思路

先获取列表，上下左右的所有情况。解决一维的问题
然后所有一维的问题暴力循环。已知一个一维的解，可以对应其他一维解的列表（用于记忆化搜索）
然后使用递归，进行累加

代码

from collections import defaultdict# 用java的思维写的
class Solution(object):def colorTheGrid(self, m, n):mod = 10 ** 9 + 7# 初始化字典valid = dict()# 枚举一行中所有可能的值 3的m次方for mask in range(3 ** m):# 初始化一个list  list存放的是具体的color，用于前后值的比较# mask和list是相互对应的color = list()tmp = maskfor i in range(m):color.append(tmp % 3)tmp = tmp // 3  # 需要的是返回整数# 对color的各项进行校验flag = Falsefor i in range(m - 1):if color[i] == color[i + 1]:flag = Truebreakif not flag:valid[mask] = color# 需要预处理，上下两行的对应关系，key和list的结构# 遍历所有valid中的数值adjacent = dict()for key1, value1 in valid.items():adjacent_list = list()for key2, value2 in valid.items():# 需要遍历上下是否会冲突flag = Falsefor x, y in zip(value1, value2):if x == y:flag = Trueif not flag:adjacent_list.append(key2)adjacent[key1] = adjacent_listf = dict()g = dict()for key1, _ in valid.items():f[key1] = 1for i in range(1, n):g = dict()  # 这里需要清空数据for mask1 in valid.keys():for mask2 in adjacent[mask1]:# g[mask1] 如果取不到会报错if mask1 in g:g[mask1] += f[mask2]else:g[mask1] = f[mask2]if g[mask1] >= mod:g[mask1] -= modf = gsum = 0for v1, v2 in f.items():sum += v2return sum % mod# 用python的语法糖写
def colorTheGrid2(self, m, n):mod = 10 ** 9 + 7# 初始化字典valid = dict()# 枚举一行中所有可能的值 3的m次方for mask in range(3 ** m):# 初始化一个list  list存放的是具体的color，用于前后值的比较# mask和list是相互对应的color = list()tmp = maskfor i in range(m):color.append(tmp % 3)tmp = tmp // 3  # 需要的是返回整数if any(color[i] == color[i + 1] for i in range(m - 1)):continuevalid[mask] = color# 需要预处理，上下两行的对应关系，key和list的结构# 遍历所有valid中的数值adjacent = defaultdict(list)for key1, value1 in valid.items():for key2, value2 in valid.items():if not any(x == y for x, y in zip(value1, value2)):adjacent[key1].append(key2)f = defaultdict(int)for key1, _ in valid.items():f[key1] += 1for i in range(1, n):g = defaultdict(int)for mask1 in valid.keys():for mask2 in adjacent[mask1]:g[mask1] += f[mask2]g[mask1] = g[mask1] % modf = greturn sum(f.values()) % modsolution = Solution()
ans = solution.colorTheGrid(1, 1)
print(ans)
ans = solution.colorTheGrid(1, 2)
print(ans)
ans = solution.colorTheGrid(5, 5)
print(ans)ans = colorTheGrid2(None, 5, 5)
print(ans)dic = defaultdict(list)
dic["a"].append("11")
print(dic)  # defaultdict(<class 'list'>, {'a': ['11']})dict2 = dict()
value = list()
value.append("11")
dict2["a"] = value
print(dict2)  # {'a': ['11']}my_list = [5, 8, 12, 3, 7]
my_list2 = [my_list[i] * 2 for i in range(len(my_list))]
print(my_list2)"""
None相当于null
if not flag: 相当于!flag
adjacent[key1] = adjacent_list  相当于adjacent.put(key1,adjacent_list)  hashmap用法if mask1 in g:g[mask1] += f[mask2]    这里取值之前还需要进行key不在map（dict）的判断my_list = [5, 8, 12, 3, 7]
长度 len(my_list)  如果是java my_list.length()或者是my_list.size()python有if any的写法
my_list = [5, 8, 12, 3, 7]
result = False
for num in my_list:if num > 10:result = Truebreakresult = any(num > 10 for num in my_list)python 还有all的语法糖
my_list = [6, 8, 7, 9]
result = True
for num in my_list:if num <= 5:result = Falsebreak
result = all(num > 5 for num in my_list)这里直接初始化值dic = defaultdict(list)
dic["a"].append("11")
print(dic)  # defaultdict(<class 'list'>, {'a': ['11']})dict2 = dict()
value = list()
value.append("11")
dict2["a"] = value
print(dict2)  # {'a': ['11']}my_list = [5, 8, 12, 3, 7]
my_list2 = [my_list[i] * 2 for i in range(len(my_list))]
print(my_list2)
这个就像是java的流式处理，只是处理的逻辑前置了f = dict()
可以有四种方法
f.keys()
f.values()
f.items()
"""