- 191. 位1的个数 - 力扣（LeetCode）
class Solution {
public:
int hammingWeight(int n) {
int cnt = 0;
while (n > 0) {
cnt++;
n = n & (n - 1); // 将最低位1置零
}
return cnt;
}
};
- 231. 2 的幂 - 力扣（LeetCode）
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n; // 取最低位1
}
};
- 190. 颠倒二进制位 - 力扣（LeetCode）
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for (int i = 0; i < 32; i++)
ans = (ans << 1) | (n >> i & 1); // 循环取n的第i位补在ans后位
return ans;
}
};
- 338. 比特位计数 - 力扣（LeetCode）
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
for (int i = 1; i <= n; i++)
ans[i] = ans[i & (i - 1)] + 1; // 后i位1的个数等于去掉最低位1的数中1个数加一
return ans;
}
};
-
50. Pow(x, n) - 力扣（LeetCode）
快速幂
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
if (n == -(1ll << 31)) return 1.0 / (myPow(x, -(n + 1)) * x);
if (n < 0) return 1.0 / myPow(x, -n);
double temp = x;
double ans = 1;
while (n > 0) {
if (n & 1) ans = ans * temp;
temp = temp * temp;
n = n >> 1;
}
return ans;
}
};
-
37. 解数独 - 力扣（LeetCode）
用位运算优化掉bool数组
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) row[i] = col[i] = box[i] = ((1 << 9) - 1) << 1;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') continue;
int digit = board[i][j] - '0';
if (row[i] >> digit & 1) row[i] ^= (1 << digit);
if (col[j] >> digit & 1) col[j] ^= (1 << digit);
int k = boxIdx(i, j);
if (box[k] >> digit & 1) box[k] ^= (1 << digit);
}
dfs(board);
}
private:
bool dfs(vector<vector<char>>& board) {
pair<int, int> pos = findMinPro(board);
int x = pos.first, y = pos.second;
if (x == -1) return true;
vector<int> leftDigits = getLeftDigits(x, y);
for (int digit : leftDigits) {
board[x][y] = '0' + digit;
row[x] ^= (1 << digit);
col[y] ^= (1 << digit);
box[boxIdx(x, y)] ^= (1 << digit);
if (dfs(board)) return true;
box[boxIdx(x, y)] ^= (1 << digit);
col[y] ^= (1 << digit);
row[x] ^= (1 << digit);
board[x][y] = '.';
}
return false;
}
pair<int, int> findMinPro(vector<vector<char>>& board) {
int minVal = 10;
pair<int, int> pos = {-1, -1};
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
vector<int> leftDigits = getLeftDigits(i, j);
if (leftDigits.size() < minVal) {
minVal = leftDigits.size();
pos = {i, j};
}
}
return pos;
}
vector<int> getLeftDigits(int i, int j) {
vector<int> res;
int state = row[i] & col[j] & box[boxIdx(i, j)];
for (int digit = 1; digit <= 9; digit++)
if (state >> digit & 1)
res.push_back(digit);
return res;
}
int boxIdx(int i, int j) {
return i / 3 * 3 + j / 3;
}
int row[9];
int col[9];
int box[9];
};
- 218. 天际线问题 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<Event> events;
for (int i = 0; i < buildings.size(); i++) {
int left = buildings[i][0];
int right = buildings[i][1];
int height = buildings[i][2];
events.push_back({left, height, 1, i});
events.push_back({right, height, -1, i});
}
sort(events.begin(), events.end(),
[](const Event& a, const Event& b) {
return a.pos < b.pos;
});
vector<vector<int>> ans;
removed = vector<bool>(buildings.size());
for (int i = 0; i < events.size(); i++) {
if (events[i].type == 1) {
q.push({events[i].height, events[i].index});
}
else {
removed[events[i].index] = true;
}
if (i == events.size() - 1 || events[i].pos != events[i + 1].pos) {
while (!q.empty() && removed[q.top().second]) q.pop();
int height = q.empty() ? 0 : q.top().first;
if (ans.empty() || height != ans[ans.size() - 1][1])
ans.push_back({events[i].pos, height});
}
}
return ans;
}
private:
struct Event {
int pos, height, type, index;
};
// <height, index>
priority_queue<pair<int, int>> q;
// 删除标记
vector<bool> removed;
};
- 1851. 包含每个查询的最小区间 - 力扣（LeetCode）
class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
vector<Event> events;
for (int i = 0; i < intervals.size(); i++) {
int len = intervals[i][1] - intervals[i][0] + 1;
events.push_back({intervals[i][0], len, 1, i});
events.push_back({intervals[i][1], len, -1, i});
}
for (int i = 0; i < queries.size(); i++)
events.push_back({queries[i], i, 0, i});
sort(events.begin(), events.end(),
[](const Event& a, const Event& b) {
return a.pos < b.pos || (a.pos == b.pos && a.type > b.type);
});
vector<int> ans(queries.size());
removed = vector<bool>(intervals.size());
for (int i = 0; i < events.size(); i++) {
if (events[i].type == 1)
q.push({-events[i].len, events[i].index});
else if (events[i].type == -1)
removed[events[i].index] = true;
else {
while (!q.empty() && removed[q.top().second]) q.pop();
ans[events[i].index] = q.empty() ? -1 : -q.top().first;
}
}
return ans;
}
private:
struct Event {
int pos, len, type, index;
};
// <-len, index>
priority_queue<pair<int, int>> q;
vector<bool> removed;
};
