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

☆ 异或和|倒数第二步

news 2026/6/12 23:18:03

lc2505
遍历数组累加前缀和，不断将当前数和前缀和与结果做或运算
最终得到所有子序列和的或值
算所有子序列和的或值，只需看每个二进制位是否能被“激活”：子序列和的任意二进制位为1，必然对应
1.“单个元素”
2.或“某个前缀和”的该位为1（前缀和覆盖了所有长于1的子序列和的位贡献可能）

class Solution {

public:
long long subsequenceSumOr(vector<int>& nums) {
long long sumOr = 0, prefixSum = 0;
for (int num : nums) {
prefixSum += num;
sumOr |= num;
sumOr |= prefixSum;
}
return sumOr;
}
};

lc2083

class Solution {
typedef long long ll;
public:
long long numberOfSubstrings(string s) {
ll ret=0;
unordered_map<char,int> hash;
for(auto& c:s)
hash[c]++;
for(auto& [a,b]:hash)
{
ret+=b*(ll)(b+1)/2;
}
return ret;
}
};

lc1072
hash
把每行转化为“与首元素(基准）的异或模式串”
统计出现次数最多的模式，其次数就是可得到的最多相等行数

class Solution {

public:
int maxEqualRowsAfterFlips(vector<vector<int>> &matrix) {
int ans = 0, n = matrix[0].size();
unordered_map<string, int> cnt;
for (auto &row: matrix) {
string r(n, 0);
for (int j = 0; j < n; ++j)
r[j] = row[j] ^ row[0]; // 翻转第一个数为 1 的行
ans = max(ans, ++cnt[r]);
}
return ans;
}
};

喵喵优化
vector<bool> 替代字符串存模式（更省内存，因为 vector<bool> 是比特级存储）
加 move(t) 避免vector拷贝（直接转移内存所有权）
逻辑上通过“首元素为1时翻转整行”统一模式，统计重复最多的模式数——本质是把“可通过列翻转变成相同的行”归为同一类，次数最多的类就是答案。

class Solution {
public:
int maxEqualRowsAfterFlips(const vector<vector<int>>& matrix) {
unordered_map<vector<bool>, int> cnt;
int ans = 0;
for (const auto& e : matrix) {
vector<bool> t(e.begin(), e.end());
if (e[0]) t.flip();
ans = max(ans, ++cnt[move(t)]);
}
return ans;
}
};