第一次认真周赛总结
T1:一个 整数的 二进制形式中 奇数位上bit==1 和 偶数 位上bit==1 分别计数
给你一个 正 整数 n
。
用 even
表示在 n
的二进制形式(下标从 0 开始)中值为 1
的偶数下标的个数。
用 odd
表示在 n
的二进制形式(下标从 0 开始)中值为 1
的奇数下标的个数。
返回整数数组 answer
,其中 answer = [even, odd]
。
解:
1.关键:
(1)利用 十进制 转 二进制 的思路 : 除2 取余 ,然后 分奇偶计数即可
2.代码:
class Solution {
public:
vector<int> evenOddBit(int n) {
//直接利用 除2取余的 十进制数 转2进制数
int i=0; // 从低位 0 下标开始用
int cnt_odd = 0;
int cnt_even = 0;
while(n!=0)
{
int num_mod = n%2;
if(i%2 ==1 && num_mod==1)
{
cnt_odd++;
}
else if(i%2 == 0 && num_mod==1)
{
cnt_even++;
}
i++;
n=n/2;
}
return {cnt_even,cnt_odd};
}
};
T2:检查 国际象棋(马)跳“日”字的 方式 是否可以遍历整个棋盘
骑士在一张 n x n
的棋盘上巡视。在有效的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n
的整数矩阵 grid
,由范围 [0, n * n - 1]
内的不同整数组成,其中 grid[row][col]
表示单元格 (row, col)
是骑士访问的第 grid[row][col]
个单元格。骑士的行动是从下标 0 开始的。
如果 grid
表示了骑士的有效巡视方案,返回 true
;否则返回 false
。
注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
解:
1.关键:
(1)有一个坑,出发点如果不在(0,0)直接返回false
(2)然后,time=1开始,利用之前大作业“贪吃蛇”的移动方向的那个2个方位数组,一个外层循环判断 移动的次数 ,内层分8个方向探索下一个位置是否 合理
2.代码:
class Solution {
public:
bool checkValidGrid(vector<vector<int>>& grid) {
if(grid[0][0]!=0)
{
return false;
}
// 只要 模拟 深搜 一下 即可
//利用 循环实现
int n = grid.size();
int time = 1 ;// 代表第time次访问
int x=0 , y= 0; //代表当前所处的 位置
while(time <=n*n-1)
{
int flag = 0;
//每次 可以 移动的8种可能的位置, 0<=x<=n-1 , 0<=y<=n-1
int index1[8] = {1,1,-1,-1,2,2,-2,-2};
int index2[8] = {2,-2,2,-2,1,-1,1,-1};
for(int i=0;i<=7;i++)
{
int next_x = x+index1[i];
int next_y = y+index2[i];
if(next_x >= 0 && next_x <=n-1 && next_y >=0 && next_y <=n-1)
{
//这个下标是合理 , 但是 需要 里面的val 等于 time+1
if(grid[next_x][next_y] == time)
{
time++;
x = next_x;
y = next_y;
flag = 1;
break;
}
}
}
if(flag == 0)
{
return false;
}
}
return true;
}
};
T3:美丽子集的个数:
母题:枚举出所有的子集(即列出 幂集)
法一: 设原集合的大小为n ,那么 正好对应2的n次方中bit串,其中对应bit==1说明这个位置的元素可以加入到这个子集, 所以一共有2的n次方的子集,
解:
1.关键:
(1)外层循环:枚举0 - 1<<n 之间的bit_str
(2)内层循环 , 2的0次方 ,2的1次方。。。一直到2的n-1次方, 然后和 bit_str 按位与& 如果不为0,说明 bit_str在这个位置的 bit==1 ,原数组中的这个元素可以 加入到新的子集中
2.代码:
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
//求出所有的 子集 , 也就是 枚举幂集
//这是 和 集合有关的问题中的 最基础 也是最本质的一个
//如果是你平时 , 会怎么枚举呢?
//手写的话,我会 0元,1元这样依次的来写
//如果 利用 1 和 0的思想的话,估计需要很多层循环 ,
//法一:借鉴答案的思想,虽然是0 和 1的序列 但是是0-2的n次方-1的所有二进制序列
//枚举这种序列, 并且 序列中的1 和 nums中取对应位置的元素
int n=nums.size();
vector<int> tmp;
vector<vector<int>> ans;
for(int bit_str = 0;bit_str < (1<<n) ; bit_str++)
{
tmp.clear();
for(int i=0;i<n;i++)
{
//判断对应位置的 bit是否为1,也就是是否需要加入到 vec中
if(bit_str & (1<<i))
{
tmp.push_back(nums[i]);
} //按位与的 结果不为0 ,必然有bit_str的某个1位置
}
ans.push_back(tmp);
}
return ans;
}
};
法二:利用递归的方式 进行 实现
解:
1.关键:
(1)我没有 想到的是,0-n-1层都是 在向2个方向递归,加入 or 不加入 一个元素,但是,一直到最深层 才真正枚举完 一种子集
(2)递归的 参数:cur考虑的数组中cur位置的元素,nums原数组,全局参数:tmp临时数组,ans最终结果数组
2.代码:
class Solution {
public:
vector<int> tmp;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
//法二:递归:
//其实 思想是对的,但是 我没有想到的是--需要一直递归到 最深层 才加入数组
//所以,前面的所有层中 都有 push当前cur元素与否 这2种选择
dfs(0,nums);
return ans;
}
void dfs(int cur,vector<int>& nums)
{
//(1)出口:
if(cur == nums.size())
{
//说明都 遍历完了
ans.push_back(tmp);
return ;
}
//(2)各种可能的 递归方向:
tmp.push_back(nums[cur]);
dfs(cur+1,nums); //加入cur位置的元素,并且向下一个 位置进发
tmp.pop_back();
dfs(cur+1,nums); //不加入cur位置的元素,并且向下一个 位置进发
}
};
回到 “周赛 ”这个题目:
给你一个由正整数组成的数组 nums
和一个 正 整数 k
。
如果 nums
的子集中,任意两个整数的绝对差均不等于 k
,则认为该子数组是一个 美丽 子集。
返回数组 nums
中 非空 且 美丽 的子集数目。
nums
的子集定义为:可以经由 nums
删除某些元素(也可能不删除)得到的一个数组。只有在删除元素时选择的索引不同的情况下,两个子集才会被视作是不同的子集。
解:
1.关键:
(1)依然 借鉴 “母题”的思想, 只不过 稍微添加一些东西即可
(2)递归的第一个方向一定成立,也就是 不加入这个元素一定可以继续下一层 ,
但是, 需要time[nums[i]-k] 和 time[nums[i]+k] 都为 0 才能保证 time[nums[i]]++ 可以 做到
(3)每次到达最深层的时候 cnt++ 即可:
2.代码:
class Solution {
public:
int cnt = 0;
//这里不适用 set,而是使用一个数组进行记录
int time[4001]={0};
int beautifulSubsets(vector<int>& nums, int k) {
//母题中 稍微 添加一个条件即可:
//如果 nums[i] 需要加入数组,必须保证nums[i]-k 和 nums[i]+k没有选过
//利用set进行判断即可
//unordered_set<int> Set;
dfs(0,nums,k);
return cnt-1; //不能是空集
}
void dfs(int cur , vector<int>& nums , int k)
{
//(1)出口:
if(cur == nums.size())
{
cnt++;
return ;
}
//(2)递归:
dfs(cur+1,nums,k);
//加入到Set中
// nums[i]-k 和 nums[i]+k
if((nums[cur]-k < 0 || time[nums[cur]-k]==0) && time[nums[cur]+k]==0)
{
time[nums[cur]]++;
dfs(cur+1,nums,k);
//递归回来的时候 需要 还原原来的 数组time,因为返回上一层时,这个元素没加
time[nums[cur]]--;
}
}
};
T4:执行任意次 操作之后的 MEX
给你一个下标从 0 开始的整数数组 nums
和一个整数 value
。
在一步操作中,你可以对 nums
中的任一元素加上或减去 value
。
- 例如,如果
nums = [1,2,3]
且value = 2
,你可以选择nums[0]
减去value
,得到nums = [-1,2,3]
。
数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。
- 例如,
[-1,2,3]
的 MEX 是0
,而[1,0,3]
的 MEX 是2
。
返回在执行上述操作 任意次 后,nums
的最大 MEX 。
解:
第一次 超时的 代码
class Solution {
public:
int findSmallestInteger(vector<int>& nums, int value) {
//我去 , 这个题目的 意思是 从0开始 缺失的最小非负整数
//先 从0 开始 从小到大的 顺序进行 填充 ,如果 后续 有重复的 , 就+value即可
//利用 一个set 进行存储即可
int size =nums.size();
unordered_set<int> Set;
for(int i=0 ;i <=size-1;i++)
{
int mod_x = 0;
if(nums[i] > 0)
{
mod_x = nums[i]%value;
}
else if(nums[i] <0 )
{
//先加到正数为止
int cnt = -(nums[i]/value) + 1;
nums[i]+= cnt*value;
mod_x = nums[i]%value;
}
//case1:
if(!Set.count(mod_x))
{
//没有存过
Set.insert(mod_x);
}
else
{
//存进去过
while(Set.count(mod_x) && mod_x<=size)
{
mod_x+=value;
}
if(mod_x <=size && !Set.count(mod_x))
Set.insert(mod_x);
}
}
//感觉 必然是 需要 遍历一次的 ,那么 可能就是 出现了死循环什么的
//开始检测
int i=0;
while(Set.count(i))
{
i++;
}
return i;
}
};
总算知道 哪里超时了, 就是那个while循环中while(Set.count(mod_X) && mod_x<=size),这个循环时不必要的, 因为最终那个while循环可以改为:
//反正 可以 利用 一个大小为 value的vector数组容器存储下所有的 mod_x出现的次数
修改后(借鉴了 某人)的代码如下:
class Solution {
public:
int findSmallestInteger(vector<int>& nums, int value) {
//我去 , 这个题目的 意思是 从0开始 缺失的最小非负整数
//先 从0 开始 从小到大的 顺序进行 填充 ,如果 后续 有重复的 , 就+value即可
//利用 一个set 进行存储即可
//直接利用个数组就可以了
vector<int> cnt(value,0);
int size= nums.size();
for(int i=0;i<=size-1;i++)
{
int it = nums[i];
cnt[(it%value+value)%value]++; //计算一个负数的 模数的 技巧
}
//遍历
for(int i=0; ; i++)
{
if(--cnt[i%value] < 0)
{
return i;
}
}
}
};
最后,总结一下:
(1)确实 没有AC,不过 思路都在形成
(2)第3题,关于 “幂集”的问题 ,“生成所有子集”这个“母题”需要 熟练掌握, 然后举一反三,“巧妇难为无米之炊”
(3)第4题:一个关于 “数论”中 余数的问题:<1>关于 负数的 除法取余,操作
<2>Map有的时候 可以 直接 用一个数组替代