$\large\color{orange}{比赛入口:}$$ \color{orange}{LeetCode337} $$ \large\color{orange}{周赛} $
$\large\color{green}{2595. 奇偶位数}$
模拟 + 位运算,时间复杂度:$O(C)$
class Solution {
public:
string get(int x){
string res = "";
while(x){
res += ((x % 2) + '0');
x >>= 1;
}
if(res == "") res = "";
return res;
}
vector<int> evenOddBit(int n) {
string s = get(n);
int even = 0, odd = 0;
int len = s.size();
for(int i = 0; i < len; i ++ ){
if(s[i] == '1' && i % 2 == 0) even ++ ;
if(s[i] == '1' && i % 2 == 1) odd ++ ;
}
return {even, odd};
}
};
$\large\color{orange}{2596. 检查骑士巡视方案}$
模拟,时间复杂度:$O(n^{2})$
class Solution {
public:
typedef pair<int, int> pii;
unordered_map<int, pii> mp;
bool checkValidGrid(vector<vector<int>>& grid) {
int n = grid.size();
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < n; j ++ ){
mp[grid[i][j]] = {i, j};
}
}
if(mp[0].first != 0 || mp[0].second != 0) return false;
for(int i = 0; i < n * n - 1; i ++ ){
bool flag = false;
pii cur = mp[i], nx = mp[i + 1];
if(abs(cur.first - nx.first) == 1 && abs(cur.second - nx.second) == 2) flag = true;
if(abs(cur.first - nx.first) == 2 && abs(cur.second - nx.second) == 1) flag = true;
if(!flag) return false;
}
return true;
}
}
$\large\color{orange}{2597. 美丽子集的数目}$
DFS
class Solution {
public:
int ans=0;
unordered_map<int, int> mp;
static const int N = 1010;
bool st[N];
int beautifulSubsets(vector<int>& nums, int k) {
for(auto & x : nums) mp[x] ++ ;
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
int n=nums.size();
dfs(0,0,n,nums,k);
return ans-1;
}
void dfs(int pre,int cur,int n,vector<int>& nums,int k){
if(cur==n) {
int t = 1;
for(int i = 0; i < n; i ++ ){
if(pre >> i & 1) t *= (pow(2, mp[nums[i]]) - 1);
}
ans += t;
return;
}
if(nums[cur]<k){
dfs(pre,cur+1,n,nums,k);
st[nums[cur]] = true;
dfs((pre|(1<<cur)),cur+1,n,nums,k);
st[nums[cur]] = false;
}
else{
dfs(pre,cur+1,n,nums,k);
bool judge=true;
if(st[nums[cur] - k]) judge = false;
st[nums[cur]] = true;
if(judge) dfs((pre|(1<<cur)),cur+1,n,nums,k);
st[nums[cur]] = false;
}
return;
}
};
$\large\color{orange}{2598. 执行操作后的最大 MEX}$
组合数学;时间复杂度:$O(n)$
class Solution {
public:
unordered_map<int, int> mp;
int findSmallestInteger(vector<int>& nums, int value) {
for(auto &x : nums) mp[(x % value + value) % value] ++ ;
int minv = nums.size() + 1, index;
for(int i = 0; i < value; i ++ ){
if(mp[i] == 0) return i;
if(minv > mp[i]) minv = mp[i], index = i;
}
return minv * value + index;
}
};