第93场周赛
868. 二进制间距
题解：根据描述，只需要找到两个1之间的距离即可。但又问题的是，如果某数的二进制表达只有一个1，不存在满足题目要求，这是，需要设计一个标记
int binaryGap(int N) {
int tmp = 0,ret = 0,flag=0;
while(N>0){
if(N&1&&flag==0)
{//第一次找到1，表示可以开始计算两个之间距离
flag=1;
tmp=1;
}
else if(N&1&&flag>0){
ret = max(ret,tmp);
flag++;
tmp = 1;
}
else{
tmp++;
};
N = N>>1;
}
return flag<2?0:ret;
}869. 重新排序得到 2 的幂
题解：根据描述以及题目所给的2的幂范围，只要以有序字符串形式枚举出来，之后对数字N字符串化以后，进行匹配即可。
bool reorderedPowerOf2(int N) {
vector<string>tmp = {"1","2","4","8","16","23","46","128","256","125",
"0124","0248","0469","1289","13468","23678","35566","011237","122446",
"224588","0145678","0122579","0134449","0368888","11266777","23334455",
"01466788","112234778","234455668","012356789","0112344778"};
string n = to_string(N);
sort(n.begin(),n.end());
for(auto i:tmp)
{
if(n==i) return true;
}
return false;
}870. 优势洗牌
题解：每次在A中寻找大于B[i]的最小值，若没有，则使用A中的最小值即可。
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
vector<int> ret;
sort(A.begin(),A.end());
for(auto i:B){
int flag=0;
for(vector<int>::iterator j=A.begin();j!=A.end();j++){
//如果能找到一个数比i大一点
if(*j>i){
flag=1;
ret.push_back(*j);
A.erase(j);
break;
}
}
//如果不能，加入最小的
if(flag==0){
ret.push_back(A[0]);
A.erase(A.begin());
}
}
return ret;
}上面这代码超时，原因在于，在A中寻找大于B[i]的最小值使用的是线性查找，整个程序时间复杂度达到了O(n^2)，因此只需要把这个查找过程使用二分查找代替，转化为给B[i]在有序的A中找到一个合适的插入位置的问题。
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
vector<int> ret;
sort(A.begin(),A.end());
for(auto i:B){
int index = nextGreatertNum(A,i);//二分查找出大于i的最小值，
if(index==A.size())
{//当查找的结果在数组末尾，说明没有大于i的最小值，那么使用最小的A[0]
ret.push_back(A[0]);
A.erase(A.begin());
}
else
{
ret.push_back(A[index]);
A.erase(A.begin()+index);
}
}
return ret;
}
int nextGreatertNum(vector<int>& A, int target) {
int len = A.size();
int l = 0;
int r = len - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (target < A[mid])
r = mid - 1;
else
l = mid + 1;
}
return l;
}871. 最低加油次数
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-152，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录