Algorithm
lc1931_用三种不同颜色为网格涂色
思路:
这是N皇后的升级版本,需要状态dp。
需要枚举第一行,然后计算剩下n-1行的涂色方案数。
但是dp手法有点生疏了,和题解学一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
use std::collections::HashMap;
const MOD: i32 = 1_000_000_007;
impl Solution {
pub fn color_the_grid(m: i32, n: i32) -> i32 {
let m = m as usize;
let n = n as usize;
// 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
let mut valid = HashMap::new();
// 在 [0, 3^m) 范围内枚举满足要求的 mask
let mask_end = 3i32.pow(m as u32);
for mask in 0..mask_end {
let mut color = Vec::new();
let mut mm = mask;
for _ in 0..m {
color.push(mm % 3);
mm /= 3;
}
let mut check = true;
for i in 0..m - 1 {
if color[i] == color[i + 1] {
check = false;
break;
}
}
if check {
valid.insert(mask, color);
}
}
// 预处理所有的 (mask1, mask2) 二元组,满足 mask1 和 mask2 作为相邻行时,同一列上两个格子的颜色不同
let mut adjacent = HashMap::new();
for (&mask1, color1) in &valid {
for (&mask2, color2) in &valid {
let mut check = true;
for i in 0..m {
if color1[i] == color2[i] {
check = false;
break;
}
}
if check {
adjacent.entry(mask1).or_insert(Vec::new()).push(mask2);
}
}
}
let mut f = HashMap::new();
for &mask in valid.keys() {
f.insert(mask, 1);
}
// 滚动数组,f是上一行的状态,g是当前行的状态
for _ in 1..n {
let mut g = HashMap::new();
for &mask2 in valid.keys() {
let mut total = 0;
if let Some(list) = adjacent.get(&mask2) {
for &mask1 in list {
total = (total + f.get(&mask1).unwrap_or(&0)) % MOD;
}
}
g.insert(mask2, total);
}
f = g;
}
let mut ans = 0;
for &num in f.values() {
ans = (ans + num) % MOD;
}
ans
}
}
|
Review
魔术告诉你!你正掌控着自己做出的选择吗?【TED演讲】
实际上每个人的认知都是被生长环境和教育塑造的。
有多少是自己的选择呢?让自身舒服的选择就一定是对的嘛?不会是 DNA 的选择吗?
当然,这样追问下去可能没有结果,所以经过自己思考后,想干啥干啥吧,活在当下,开心就好。
Tip
推理加速新范式:火山引擎高性能分布式 KVCache (EIC)核心技术解读
Share
《货币未来:从金本位到区块链》有感 💰📚
“BTC就是最大的meme”?这话有点轻率了 🤔
读完此书,我才明白:BTC凭借四大核心特性 ⚙️
- 稀缺性(增量存量比)💎
- 工作证明(POW)⛏️
- 不可篡改性 🔒
- 点对点共识记账系统 🌐
这些特性共同构建了BTC的反脆弱生态与正向反馈循环 🔄
BTC与meme的发展路径恰恰相反:BTC先有价值后有狂热,而非从注意力转向价格 📈
体验过BTC转账的人都能感受:10分钟到账、仅收10U手续费 ⚡
与传统电汇动辄几天等待、高额手续费、繁琐审查相比,就是货币革命!🚀
书中指出,BTC将成为大型转账系统,而小额快捷支付则由其他系统承担 🔄
这与我的观点不谋而合:BTC负责储值(数字黄金🥇),Solana负责日常支付(快速、广泛应用🚀)
既见未来,何不梭啦(Sol @Solana_zh)! 🌞