下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例1:
输入：num = 2（或者0b10） 输出：[4, 1] 或者（[0b100, 0b1]） 示例2:
输入：num = 1 输出：[2, -1] 提示:
num的范围在[1, 2147483647]之间； 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
itoa和atoi都是直接百度复制的，nextGreaterElement函数是从我另外一个题目代码复制过来略改的
https://blog.csdn.net/nameofcsdn/article/details/106915634
只需要改2个地方，一个是整数转化为二进制字符串，一个是二进制字符串转化为整数。
nextLesserElement函数是nextGreaterElement函数直接修改得到，代码逻辑是一样的。
char* itoa(int num,char* str,int radix) //copy from 百度百科 {/*索引表*/ char index[]="0123456789ABCDEF"; unsigned unum;/*中间变量*/ int i=0,j,k; /*确定unum的值*/ if(radix==10&&num<0)/*十进制负数*/ { unum=(unsigned)-num; str[i++]='-'; } else unum=(unsigned)num;/*其他情况*/ /*转换*/ do{ str[i++]=index[unum%(unsigned)radix]; unum/=radix; }while(unum); str[i]='\0'; /*逆序*/ if(str[0]=='-') k=1;/*十进制负数*/ else k=0; for(j=k;j<=(i-1)/2;j++) { char temp; temp=str[j]; str[j]=str[i-1+k-j]; str[i-1+k-j]=temp; } return str; } int atoi2(const char *nptr) { int c; /* current char */ int total; /* current total */ int sign; /* if '-', then negative, otherwise positive */ /* skip whitespace */ while ( isspace((int)(unsigned char)*nptr) ) ++nptr; c = (int)(unsigned char)*nptr++; sign = c; /* save sign indication */ if (c == '-' || c == '+') c = (int)(unsigned char)*nptr++; /* skip sign */ total = 0; while (isdigit(c)) { total = 2 * total + (c - '0'); /* accumulate digit */ c = (int)(unsigned char)*nptr++; /* get next char */ } if (sign == '-') return -total; else return total; /* return result, negated if necessary */ } int nextGreaterElement(int n) { char sn[40]; for(int i=0;i<32;i++)sn[i]=((n&(1<<31-i))?'1':'0'); sn[32]='\0'; int len=strlen(sn); for(int i=len-2;i>=0;i--) { if(sn[i]>=sn[i+1])continue; for(int j=len-1;j>i;j--) { if(sn[i]>=sn[j])continue; sn[j]^=sn[i]^=sn[j]^=sn[i]; sort(sn+i+1,sn+len); long long res = atoi2(sn); if(res==int(res))return res; return -1; } } return -1; } int nextLesserElement(int n) { char sn[40]; for(int i=0;i<32;i++)sn[i]=((n&(1<<31-i))?'1':'0'); sn[32]='\0'; int len=strlen(sn); for(int i=len-2;i>=0;i--) { if(sn[i]<=sn[i+1])continue; for(int j=len-1;j>i;j--) { if(sn[i]<=sn[j])continue; sn[j]^=sn[i]^=sn[j]^=sn[i]; sort(sn+i+1,sn+len,greater<char>()); long long res = atoi2(sn); if(res==int(res))return res; return -1; } } return -1; } class Solution { public: vector<int> findClosedNumbers(int num) { vector<int> ans(2); ans[1]=nextLesserElement(num); ans[0]=nextGreaterElement(num); return ans; } };
后来发现可以用c++的库函数获取上一个下一个全排列，就更简单了
//把整数转化为字符串 char* itoa(int num,char* str,int radix) //copy from 百度百科 {/*索引表*/ char index[]="0123456789ABCDEF"; unsigned unum;/*中间变量*/ int i=0,j,k; /*确定unum的值*/ if(radix==10&&num<0)/*十进制负数*/ { unum=(unsigned)-num; str[i++]='-'; } else unum=(unsigned)num;/*其他情况*/ /*转换*/ do{ str[i++]=index[unum%(unsigned)radix]; unum/=radix; }while(unum); str[i]='\0'; /*逆序*/ if(str[0]=='-') k=1;/*十进制负数*/ else k=0; for(j=k;j<=(i-1)/2;j++) { char temp; temp=str[j]; str[j]=str[i-1+k-j]; str[i-1+k-j]=temp; } return str; } //把字符串转化为整数 long long atoi(const char *nptr,int radix) //copy from somebody { while ( isspace((int)(unsigned char)*nptr) ) ++nptr;/* skip whitespace */ int c = (int)(unsigned char)*nptr++; int sign = c; /* save sign indication */ if (c == '-' || c == '+') c = (int)(unsigned char)*nptr++; /* skip sign */ long long total = 0; while (isdigit(c)) { total = radix * total + (c - '0'); /* accumulate digit */ c = (int)(unsigned char)*nptr++; /* get next char */ } if (sign == '-') return -total; else return total; /* return result, negated if necessary */ } int nextGreaterElement(int n) { char sn[40]; for(int i=0;i<32;i++)sn[i]=((n&(1<<31-i))?'1':'0'); sn[32]='\0'; next_permutation(sn,sn+32); long long res = atoi(sn,2); if(res==int(res))return res; return -1; } int nextLesserElement(int n) { char sn[40]; for(int i=0;i<32;i++)sn[i]=((n&(1<<31-i))?'1':'0'); sn[32]='\0'; prev_permutation(sn,sn+32); long long res = atoi(sn,2); if(res==int(res))return res; return -1; } class Solution { public: vector<int> findClosedNumbers(int num) { vector<int> ans(2); ans[1]=nextLesserElement(num); ans[0]=nextGreaterElement(num); return ans; } };
