找数字-算法

大家好，欢迎来到IT知识分享网。

解法一、数位模拟

比n大的最小数就是n+1，当n+1时，以下几种情况会导致n中1的个数发生变化（或者不变）

1.n的低位连续1的个数count>1，如1011，10111,1111等，加1后使得n中1的个数减少count-1个

解决办法也很简单，加1后，将这count-1个1补到低位即可。

2.n的低位连续1的个数count=1，如101，01，10101等，加1后n中1的个数不变，答案就是n+1；

3.n的低位连续1的个数count=0，如100，1010，10等，加1后使得n中1的个数增加1.

解决办法：找到最低位的1，再找到离它最近的高位0，两者互换，再把高位0位置后面的1全部放到低位。

代码：

import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); // 1.求n的低位连续1的个数 int count=get(n),ans=0; if(count==1){ ans=n+1; }else if(count==0){ int[] arr=toArray(n); int index=arr.length-1; while(index>=0&&arr[index]==0){// 1.找最低位1的位置index index--; } if(index==0){//只有一个1 ans=(n<<1); }else{// 2.找到index前面高位的第一个0位 int idx=index-1; while(idx>=0&&arr[idx]==1){ idx--; } if(idx<0){//前面没0，左移1位，除了最高位，全部取反 int base=0,len=arr.length; for(int i=0;i<len;i++){ arr[i]=(arr[i]==0?1:0); base=(base<<1)|arr[i]; } ans=((1<<len)|base); }else{//两处互换，idx后面的1全部放到低位 arr[index]=0; arr[idx]=1; int base=1,i=idx+1,j=arr.length-1; while(i<j){ if(arr[i]==1){ if(arr[j]==0){ arr[j]=1; arr[i]=0; i++; } j--; }else{ i++; } } for(i=1;i<arr.length;i++){ base=(base<<1)|arr[i]; } ans=base; } } }else{//加1，末尾补偿count-1个连续的1 int digit=1; for(int i=0;i<count-2;i++){ digit=(digit<<1)|1; } ans=((n+1)|digit); } System.out.println(ans); } // 求低位连续1的个数 public static int get(int n){ int count=0; while((n&1)==1){ n=(n>>1); count++; } return count; } //n转成bit数组 public static int[] toArray(int n){ int m=n,len=0; while(m!=0){ len++; m=(m>>1); } int[] ans=new int[len]; len--; while(n!=0){ ans[len--]=(n&1); n>>=1; } return ans; } }

解法二（博客原解）：寻找01数对

找到尾部第一对01，将其变成10即可。

特殊情况

1.没有数对01，如10，1000，111等值，在最高位补0即可。

2.按逻辑，10110->11010,而10011处理后的正确答案是：11001。将01变成10后，末尾的1应该全部放到低位，保证值最小。

代码1:比特数组

import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] arr=toArray(n); n=arr.length; int ans=0; //找到第一对“01”，将其变成“10” for(int i=n-2;i>=0;i--){ if(arr[i]==0&&arr[i+1]==1){ arr[i]=1; arr[i+1]=0; //i后面的1全部放到低位 int j=i+1,k=n-1; while(j<k){ if(arr[j]==1){ if(arr[k]==0){ arr[k]=1; arr[j]=0; j++; k--; }else{ k--; } }else{ j++; } } // 比特数组转成十进制：二进制转十进制 ans=arr[0]; for(int idx=1;idx<n;idx++){ ans=(ans<<1)|arr[idx]; } //处理结束，跳出循环 break; } } System.out.println(ans); } //n转成bit数组（高位补0，方便处理） public static int[] toArray(int n){ int m=n,len=0; while(m!=0){ len++; m=(m>>1); } int[] ans=new int[len+1]; while(n!=0){ ans[len--]=(n&1); n>>=1; } ans[len]=0; return ans; } }

代码2：充分利用java自带的api

import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); char[] arr=("0"+Integer.toBinaryString(n)).toCharArray(); int i=arr.length-2; while(i>=0&&!(arr[i]=='0'&&arr[i+1]=='1')){ i--; } arr[i]='1'; arr[i+1]='0'; //i后面的'1'全放到低位 int j=i+1,k=arr.length-1; while(j<k){ if(arr[j]=='1'){ if(arr[k]=='0'){ arr[k]='1'; arr[j]='0'; j++; k--; }else{ k--; } }else{ j++; } } int ans=arr[0]-'0'; for(i=1;i<arr.length;i++){ ans=(ans<<1)|(arr[i]-'0'); } System.out.println(ans); } }