回溯+位运算|前缀和优化背包

汉字写一遍代码思路 可以提升和人沟通 和加深理解

所以不可以只写完代码就去去丸了 还是要复习

lc756

class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
vector<int> groups[7][7];
for (auto& s : allowed) {
// A~F -> 1~6
groups[s[0] & 31][s[1] & 31].push_back(s[2] & 31);
}

int n = bottom.size();
vector<int> pyramid(n);
for (int i = 0; i < n; i++) {
pyramid[n - 1] |= (bottom[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = bottom[i]&31
}

vector<uint8_t> vis(1 << ((n - 1) * 3));

auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
if (i < 0) {
return true;
}

if (vis[pyramid[i]]) {
return false;
}

if (j == i + 1) {
vis[pyramid[i]] = true;
return dfs(i - 1, 0);
}

for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
if (dfs(i, j + 1)) {
return true;
}
}
return false;
};

return dfs(n - 2, 0);
}
};

lc3333

前缀和优化多重背包

class Solution {
public:
int possibleStringCount(string word, int k) {
int n = word.size();
if (n < k) { // 无法满足要求
return 0;
}

const int MOD = 1'000'000'007;
vector<int> cnts;
long long ans = 1;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 || word[i] != word[i + 1]) {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if (cnt > 1) {
if (k > 0) {
cnts.push_back(cnt - 1);
}
ans = ans * cnt % MOD;
}
k--; // 注意这里把 k 减小了
cnt = 0;
}
}

if (k <= 0) {
return ans;
}

int m = cnts.size();
vector f(m + 1, vector<int>(k));
ranges::fill(f[0], 1);
vector<int> s(k + 1);
for (int i = 0; i < m; i++) {
// 计算 f[i] 的前缀和数组 s
for (int j = 0; j < k; j++) {
s[j + 1] = (s[j] + f[i][j]) % MOD;
}
// 计算子数组和
for (int j = 0; j < k; j++) {
f[i + 1][j] = (s[j + 1] - s[max(j - cnts[i], 0)]) % MOD;
}
}

return (ans - f[m][k - 1] + MOD) % MOD; // 保证结果非负
}
};