题解:根据描述,只需要找到两个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;
}
题解:根据描述以及题目所给的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;
}
题解:每次在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;
}