题目
思路
先获取列表，上下左右的所有情况。解决一维的问题
然后所有一维的问题暴力循环。已知一个一维的解，可以对应其他一维解的列表（用于记忆化搜索）
然后使用递归，进行累加
代码
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 = mask
for i in range(m):
color.append(tmp % 3)
tmp = tmp // 3 # 需要的是返回整数
# 对color的各项进行校验
flag = False
for i in range(m - 1):
if color[i] == color[i + 1]:
flag = True
break
if 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 = False
for x, y in zip(value1, value2):
if x == y:
flag = True
if not flag:
adjacent_list.append(key2)
adjacent[key1] = adjacent_list
f = dict()
g = dict()
for key1, _ in valid.items():
f[key1] = 1
for 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] -= mod
f = g
sum = 0
for v1, v2 in f.items():
sum += v2
return 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 = mask
for i in range(m):
color.append(tmp % 3)
tmp = tmp // 3 # 需要的是返回整数
if any(color[i] == color[i + 1] for i in range(m - 1)):
continue
valid[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] += 1
for 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] % mod
f = g
return sum(f.values()) % mod
solution = 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 = True
break
result = 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 = False
break
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()
"""
总结
这里对于数据的处理上比较考验细节