最接近的数_

C/C++

但求八月九月好运！

//这就比较尴尬了，简单的加减搞定！
class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        vector<int>res;
        int temp=x;
        int num1=get1(x);
        while(temp>0)
        {
            --temp;
            if(get1(temp)==num1) {res.push_back(temp);break;}
        }
        temp=x;
        while(temp!=0)
        {
            ++temp;
            if(get1(temp)==num1) {res.push_back(temp);break;}
        }
        return res;
    }
private:
    int get1(int n)
    {
        int cnt=0;
        while(n>0)
        {
            if(n&1) ++cnt;
            n=n>>1;
        }
        return cnt;
    }
};

发表于 2019-05-14 20:43:57 回复(0)

打爆面试官

根据《程序员面试金典》上的位算数解法写的。
c01是拖尾0的个数，c01是拖尾0左方全为1的位的个数。p位除了拖尾0之外最最右边的0的位，p=c01+c11。x后一个数求取：
1.将位p置1；
2.将位0到p位清零；
3.将位0到c11-1位置1.

c1为拖尾1的个数，c0位拖尾1右方全为0的位的个数，p=c0+c1.则x前面一个数的求取步骤：
1.将p位清零。
2.将位p右边所有的位置1.
3.将位0到位c0-1清零。
具体到位上怎么操作，可以翻来数或下电子版来看看。我只是提供途径，公式不好打出来。

#include <vector>
classCloseNumber {
public:
    vector<int> getCloseNumber(intx) {
        // write code here
     vector <int> result;
     int c01=0;//拖尾0的个数
     int c11=0;//拖尾0左方全为1的个数
     
     int c1=0;//拖尾1的个数
     int c0=0;//拖尾1左方全为0的位个数
     int c = x,d=x;//临时变量
//分别求取
     while(((c & 1) == 0) && (c!=0)){
         c01 ++;
         c >>= 1;
     }
     while((c & 1)==1){
         c11 ++;
         c >>= 1;
     }
     while((d & 1)==1){
         c1 ++;
         d >>= 1;
     }
     while(((d & 1) == 0) && (d!=0)){
         c0 ++;
         d >>= 1;
     }
   
 
     result.push_back((x - (1<<(c1))-(1<<(c0-1)) +1));
     result.push_back((x + (1<<(c11-1)) + (1<<c01) -1));
     return result;
            }
};

编辑于 2015-08-20 23:12:12 回复(5)

绿色的小妖

import java.util.*;
/*
* 思路：1、getNum得到一个数中1的个数
*       2、向后搜索略小的一个arr[0]
*       3、向前搜索略大的一个arr[1]
*/
public class CloseNumber {
    public int getNum(int n){
        int count = 0;
        while(n != 0){
            if((n&1) == 1){
                count++;
            }
            n = n>>1;
        }
        return count;
    }
    public int[] getCloseNumber(int x) {
        // write code here
        int[] arr = new int[2];
        int num = getNum(x);
        int i;
        for(i = x-1; getNum(i) != num; i--);
        arr[0] = i;
        for(i = x+1; getNum(i) != num; i++);
        arr[1] = i;
        return arr;
    }
}

发表于 2018-09-03 11:01:34 回复(4)

jason1990

class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        
        vector<int> res;
        if(x<=0) return res;
        
        int prev=x+1,next=x-1,num=getonenum(x);
        
        while(getonenum(next)!=num){
            --next;
        }
        res.push_back(next);
        while(getonenum(prev)!=num){
            ++prev;
        }
        res.push_back(prev);
        
        return res;
    }
    
private:
    int getonenum(int data){
        int n=0;
        while(data){
            ++n;
            data=data&(data-1);
        }
        return n;
    }
};

我还是****法，通过位操作未必真能节省指令，待有空做实验比较。

发表于 2015-08-30 19:06:48 回复(3)

InGodWeTrust

import java.util.*;

public class CloseNumber {
    public int[] getCloseNumber(int x) {
        int min=x-1,max=x+1;
		while(Integer.bitCount(x)!=Integer.bitCount(min)&&min>=0){
			min--;
		}
		
		while(Integer.bitCount(x)!=Integer.bitCount(max)){
			max++;
		}
		int arr[]={min,max};
		return arr;
    }
}
程序员面试金典java http://blog.csdn.net/sinat_22797429/article/details/75451808

编辑于 2017-07-25 22:17:50 回复(0)

木然猫猫

有点绕，还是直接暴力吧

# -*- coding:utf-8 -*-
class CloseNumber:
    def getCloseNumber(self, x):
        res = [0, 0]
        n = x
        while True:
            n -= 1
            if bin(x).count("1") == bin(n).count("1"):
                res[0] = n
                break
        n = x
        while True:
            n += 1
            if bin(x).count("1") == bin(n).count("1"):
                res[1] = n
                break
        return res

发表于 2018-12-26 15:56:08 回复(0)

Python

Yannyezixin

思路：

取得略大的数：

c0 是拖尾0的个数，c1是紧邻拖尾0左方位为1的个数， p为最右边但非拖尾的0 等于 c0 + c1
把位p置为1
将p右方所有位置为零
在右方插入c1 - 1 个1

取得略小的数：

c1是拖尾1的个数， c0是紧邻拖尾1的左方一连串0的个数，p为最右边但非拖尾的1 等于c0 + c1
把位p置为0
将p右方所以位置清零
在p的紧邻右方插入c1 + 1个1

# -*- coding:utf-8 -*-
class CloseNumber:
    def getCloseNumber(self, x):
        return self.getPrev(x), self.getNext(x)
    
    def getNext(self, n):
        c = n
        c0 = 0
        c1 = 0
        
        while c & 1 == 0 and c:
            c0 += 1
            c >>= 1
        while c & 1 == 1:
            c1 += 1
            c >>= 1
        if c0 + c1 >= 31 or c0 + c1 == 0:
            return False
        
        p = c0 + c1
        # 翻转最右边非拖尾0
        n |= (1 << p)
        # 将p右方的所有为清零
        n &= ~((1 << p) - 1)
        # 在右方插入(c1 - 1)个1
        n |= (1 << (c1 - 1)) - 1
        
        return n
    
    def getPrev(self, n):
        c = n
        c0 = 0
        c1 = 0
        while c & 1 == 1:
            c1 += 1
            c >>= 1
        if c == 0: return -1
        while c & 1 == 0 and c:
            c0 += 1
            c >>= 1
        
        p = c0 + c1
        # 位0到p位清零
        n &= (~0) << (p + 1)
        # 在p后面插入c1 + 1个1
        n |= ((1 << (c1 + 1)) - 1) << (c0 - 1)
        return n

发表于 2016-08-03 21:17:54 回复(1)

C/C++

j-217

略小的数：

1. 找到第一个10的位置，将其置换为01；

2. 统计10后1的个数，并将其整体放置10后的位置；

略大的数：

1. 找到第一个01的位置，将其置换为10；

2. 统计01后1的个数，并将其整体放置到最低位；

例：1110 0111

（小）=> 1101 1110

（大）=> 1110 1011

用到的位操作：

将n的后i位置零：n&(~0<<(i + 1))

取n的后i位： n&(1<<(i+1)) - 1

n的i位置零： n&~(1<<i)

n的i位置一： n|(1<<i)

代码如下：

class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        vector<int> res;
        int pos10 = find10(x);
        int pos01 = find01(x);
        // get small one
        int s = (x&(~0)<<pos10+1) + (1<<(pos10-1));
        int mask = (1<<(pos10-1)) - 1;
        int n = x&mask;
        int cnt_one = count_one(n);
        if (cnt_one > 0) {
            n = ((1<<cnt_one) - 1)<<(pos10-1-cnt_one);
            s += n;
        }
        res.emplace_back(s);
        // get larger one
        int l = (x&(~0)<<pos01+1) + (1<<pos01);
        mask = (1<<(pos01-1)) - 1;
        n = x&mask;
        cnt_one = count_one(n);
        if (cnt_one > 0) {
            n = (1<<cnt_one) - 1;
            l += n;
        }
        res.emplace_back(l);
        return res;
    }

    int count_one(int n) {
        int cnt = 0;
        while (n) {
            if ((n&1) == 1)
                ++cnt;
            n >>= 1;
        }
        return cnt;
    }

    int find01(int n) {
        int pos = 0;
        while (n && (n&1) == 0) {
            ++pos;
            n >>= 1;
        }
        while (n && (n&1) == 1) {
            ++pos;
            n >>= 1;
        }
        if (n == 0) return -1;
        return pos;
    }

    int find10(int n) {
        int pos = 0;
        while (n && (n&1) == 1) {
            ++pos;
            n >>= 1;
        }
        if (n == 0) return -1;
        while (n && (n&1) == 0) {
            ++pos;
            n >>= 1;
        }
        return pos;
    }
};

发表于 2020-03-19 01:06:16 回复(0)

杨领well

// 就是该数二进制相邻的两个排列
class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        
        string ans0, ans1, temp;
        while(x)
        {
            temp.push_back(x%2 + '0');
            x /= 2;
        }
        reverse(temp.begin(), temp.end());
        
        ans0 = temp;
        ans1 = temp;
        // 下一个排列
        next_permutation(ans1.begin(), ans1.end());
        // 上一个排列
        prev_permutation(ans0.begin(), ans0.end());
        
        int a[2] = {0};
        for(int i = 0; i < ans0.size(); ++i)
        {
            a[0] = a[0]*2 + ans0[i]-'0';
        }
        for(int i = 0; i < ans1.size(); ++i)
        {
            a[1] = a[1]*2 + ans1[i]-'0';
        }
        
        return {a[0], a[1]};
    }
};

发表于 2019-09-09 07:19:30 回复(0)

C/C++

wykxwyc

比较直观的一种做法：
大的数：找到右侧第一个‘01’对，然后互换，然后将右侧所有的0放在最左边，所有的1放在最右边
小的数：找到右侧第一个'10'对，然后互换，然后将右侧所有的1放在最左边，所有的0放在最右边

空间上来说，需要最多32字节长度的string。

class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        // write code here
        int small=x;
        string s;
        int left10=-1;  // "10"中0的位置
        int right01=-1; // "01"中1的位置
        int bitcnt=0;
        while(small!=0){
            if(small&1){
                s='1'+s;
            }else{
                s='0'+s;
            }
            small/=2;
            bitcnt++;
        }

        for(int i=s.size()-1;i>0;--i){
            if( right01==-1 && s[i]=='1' && s[i-1]=='0'){
                right01=s.size()-1-i;
            }
            if( left10==-1 && s[i]=='0' && s[i-1]=='1'){
                left10=s.size()-1-i;
            }
        }

        vector<int> ret(2,x);
        if(right01==-1){
            ret[1]=x<<1;
        }else{
            ret[1]=x+(1<<right01);
            for(int i=right01-1,j=0;j<i;++j,--i){
                while(i>0 && s[s.size()-1-i]=='0') --i;
                while(j<s.size() && s[s.size()-1-j]=='1') ++j;
                if(j<i){
                    ret[1]=ret[1]-(1<<i)+(1<<j);
                }
            }
        }

        ret[0]=x-(1<<left10);
        for(int i=left10-1,j=0;j<i;++j,--i){
            while(i>0 && s[s.size()-1-i]=='1') --i;
            while(j<s.size() && s[s.size()-1-j]=='0') ++j;
            if(j<i) {
                ret[0]=ret[0]+(1<<i)-(1<<j);
            }
        }
        return ret;
    }
};

编辑于 2019-08-09 15:26:44 回复(0)

C/C++

nbgao

class CloseNumber {
public:     int F(int n){         int s = 1;         while(n){             s += n&1;             n>>=1;         }         return s;     }
    vector<int> getCloseNumber(int x) {
        vector<int> r;
        int cnt = F(x),i;
        for(i=x-1;F(i)!=cnt && i>0;i--);
        r.push_back(i);
        for(i=x+1;F(i)!=cnt;i++);
        r.push_back(i);
        return r;
    }
};

发表于 2019-02-27 01:34:57 回复(0)

吾生有你

import java.util.*;

public class CloseNumber {
    public int[] getCloseNumber(int x) {
        // write code here
        int[] a=new int[2];
        int left=x-1;
        int right=x+1;
        int num=oneNum(x);
        while(left>0){
            if(num==oneNum(left))
                break;
            left--;
        }
        while(true){
            if(num==oneNum(right))
                break;
            right++;
        }
        a[0]=left;
        a[1]=right;
        return a;
    }
    public int oneNum(int x){
        int count=0;
        while(x!=0){
            if((x&1)==1)
                count++;
            x>>=1;
        }
        return count;
    }
}

发表于 2018-05-16 15:02:20 回复(0)

本命年的Offer！

public static int[] getCloseNumber(int x) { // write code here  String xBin = Integer.toBinaryString(x); int oneNumber = 0; for (int i = 0; i < xBin.length(); i++) { if (xBin.charAt(i) == '1') {
            oneNumber++;
        }
    } int[] result = new int[2]; for (int i = x-1; i > 0; i--) {
        String xxBin = Integer.toBinaryString(i); int onexNumber = 0; for (int k = 0; k < xxBin.length(); k++) { if (xxBin.charAt(k) == '1') {
                onexNumber++;
            }
        } if (onexNumber == oneNumber) {
            result[0] = i; break;
        }
    } for (int j = x+1; j < Integer.MAX_VALUE; j++) {
        String xxBin = Integer.toBinaryString(j); int onexNumber = 0; for (int k = 0; k < xxBin.length(); k++) { if (xxBin.charAt(k) == '1') {
                onexNumber++;
            }
        } if (onexNumber == oneNumber) {
            result[1] = j; break;
        }
    } return result;

} 笨笨的方法

发表于 2017-07-30 10:31:35 回复(0)

孙强Jimmy

使用书上的方法，具体的意义见书：

public class CloseNumber {
    public int[] getCloseNumber(int x) {
        int n, c0, c1;
        int[] result = new int[2];
        for (n = x, c1 = 0; (n & 1) == 1; n >>= 1, ++c1);
        for (c0 = 0; (n & 1) == 0; n >>= 1, ++c0);
        result[0] = x - (1 << c1) - (1 << (c0 - 1)) + 1;
        for (n = x, c0 = 0; (n & 1) == 0; n >>= 1, ++c0);
        for (c1 = 0; (n & 1) == 1; n >>= 1, ++c1);
        result[1] = x + (1 << c0) + (1 << (c1 - 1)) - 1;
        return result;
    }
}

发表于 2017-06-16 11:20:39 回复(0)

kestars

class CloseNumber {
public:
    int getNext(int n){
        //compute c0,c1
        int c=n;
        int c0=0;
        int c1=0;
        while(((c&1)==0)&&(c!=0)){
            c0++;
            c>>=1;
        }
        while((c&1)==1){
            c1++;
            c>>=1;
        }
        if(c1+c1==31||c0+c1==0){
            return -1;
        }
        int p=c1+c0;
        n|=(1<<p);
        n&=~((1<<p)-1);
        n|=(1<<(c1-1))-1;
        return n;
    }
    
    
    int getPrev(int n){
        int temp=n;
        int c0=0;
        int c1=0;
        while(temp&1==1){
            c1++;
            temp>>=1;
        }
        if(temp==0)
            return -1;
        while(((temp&1)==0)&&(temp!=0)){
            c0++;
            temp>>=1;
        }
        int p=c0+c1;
        n&=((~0)<<(p+1));
        
        int mask=(1<<(c1+1))-1;
        n|=mask<<(c0-1);
        return n;
    }
    
    vector<int> getCloseNumber(int x) {
        // write code here
        int next=getNext(x);
        int pre=getPrev(x);
        vector<int> result;
        result.push_back(pre);
        result.push_back(next);
        return result;
    }
};

发表于 2016-10-21 23:12:55 回复(0)

简单的快乐

import java.util.*;

public class CloseNumber {

public int[] getCloseNumber(int x) {

int[] result=new int[2];

result[1]=findNext(x);

result[0]=findPre(x);

return result;

}

public int findNext(int a){

//c0是尾部0的个数， c1是0左方全为1的个数

/*

1,将index位p置为1；

2,将index位从0到p-1清零

（1,2的快速做法就是将拖尾0变为1，然后加1）

3,将index位0到c1-2位置为1

*/

int c0=0,c1=0;

int temp=a;

while((temp&1)==0&&temp!=0){

c0++;

temp>>=1;

}

while((temp&1)==1){

c1++;

temp>>=1;

}

//判断是否没有更大的数

if(c0+c1==31||c0+c1==0){

return -1;

}

int p=c0+c1;//index为p的位置，此时p的位置肯定是0

//1,2的快速版

a+=Math.pow(2,c0);

//3,将0到c1-2位置为1

a+=Math.pow(2,c1-1)-1;

return a;

}

public int findPre(int b){

//c1是尾部1的个数，c0是尾部1左方全为0的个数

/*

1,将index位p清零

2,将p右边所有的位都置为1

(1,2的快速版本就是将拖尾1置为0，然后减1)

3,将位0到位c0-2清零

*/

int c1=0,c0=0;

int temp=b;

while((temp&1)==1){

c1++;

temp>>=1;

}

while((temp&1)==0&&temp!=0){

c0++;

temp>>=1;

}

int p=c0+c1; //p位肯定为1

//1,2

b-=Math.pow(2,c1)-1;

b-=1;

b-=Math.pow(2,c0-1)-1;

return b;

}

发表于 2016-06-25 16:27:16 回复(0)

Aurora1

    public int[] getCloseNumber(int x) {

		int[] a = new int[2];
		getNext(x, a);
		getPrev(x, a);
		return a;
	}

	void getPrev(int x, int[] a) {
		int k = x, p = 0, c0 = 0; // c0代表0的个数
		// 求拖尾1（1后面跟0）的位置p
		for (; k != 0; k >>= 1, p++) {
			if ((k & 1) == 0)
				c0++;
			else if (c0 > 0)
				break;
		}

		// 将p位置0
		k = 1 << p;
		x &= ~k;
		// 将p后所有位置0
		x &= ~(k - 1);
		// 补全c0-1个0放在最后，其它为1
		x |= (k - 1) & ~((1 << (c0 - 1)) - 1);
		a[0] = x;
	}

	void getNext(int x, int[] a) {
		int k = x, p = 0, c1 = 0; // c1代表1的个数

		// 求不拖尾0（0后面跟1）的位置p
		for (; k != 0; k >>= 1, p++) {
			if ((k & 1) == 1)
				c1++;
			else if (c1 > 0)
				break;
		}

		// 将p位置1
		k = 1 << p;
		x |= k;
		// 将p后所有位置0
		x &= ~(k - 1);
		// 补全c1-1个1
		x |= (1 << c1 - 1) - 1;
		a[1] = x;
	}

发表于 2016-04-09 12:33:48 回复(0)

neuxs

import java.util.*;

public class CloseNumber {
    public int[] getCloseNumber(int x) {
        // write code here
        int[] res=new int[2];
        int num=getOneNum(x);
        int left=x-1;
        int right=x+1;
        while(left>0){
            if(num==getOneNum(left))
                break;
            left--;
        }
        while(true){
            if(num==getOneNum(right))
                break;
            right++;
        }
        res[0]=left;
        res[1]=right;
        return res;
    }
    public int getOneNum(int x){
        int count=0;
        while(x!=0){
            if((x & 1)==1){
                count++;
            }
            x>>=1;
        }
        return count;
    }
}

发表于 2015-11-25 21:57:19 回复(3)

majihong1988

vector<int> getCloseNumber(int x) {
		// write code here
		vector<int> out;
		out.push_back(findLe(x));
		out.push_back(findGe(x));
		return out;

	}
	int findGe(int n){
		unsigned t1 = n&(-n);
		unsigned t2 = n + t1;
		return t2 | ((n^t2) / t1) >> 2;
	}
	int findLe(int n){
		unsigned t1 = (n + 1)&(~n);//最右边的0位置 ;
		if (t1 > 0){
			int t2 = n / t1*t1;//n最右边0右边的1置为0；
			unsigned t3 = t2&(-t2); //t2最右边的1
			unsigned t4 = t3 / (t1<<1);
			unsigned t5 = t2^t3;
			return t5 | ((t3 - 1) / t4*t4);
		}
		else{
			unsigned t1 = n&(-n);//n最右边的1
			return n ^ ((t1 >> 1) | t1);
		}
	}
};

发表于 2015-07-24 18:36:46 回复(0)

渣渣辉123

class CloseNumber {
public:
    vector<int> getCloseNumber(int x) {
        vector<int> res;
        int count=getonecount(x);
        int lower=x-1;
        int larger=x+1;
        while(getonecount(lower)!=count)lower--;
        res.push_back(lower);
        while(getonecount(larger)!=count)larger++;
        res.push_back(larger);
        return res;
        
    }
    int getonecount(int x)
    {
        int count=0;
        for(;x;count++)
            x=x&(x-1);
        return count;
    }
};

发表于 2020-03-31 17:44:17 回复(0)

7EdgXiao

public int[] getCloseNumber(int x) {
int[] ret = new int[2];
String s = Integer.toBinaryString(x);
int count = getOneCount(s);
int left = x-1;
int right = x+1;
while(left>=0){
String s1 = Integer.toBinaryString(left--);
int count1 = getOneCount(s1);
if(count == count1){
ret[0] = left+1;
break;
}
}
while(true){
String s2 = Integer.toBinaryString(right++);
int count2 = getOneCount(s2);
if(count == count2){
ret[1] = right-1;
break;
}
}
return ret;
}

private Integer getOneCount(String n){
int count = 0;
for(int i = 0; i < n.length(); i++){
if(n.charAt(i) == '1'){
count++;
}
}
return count;
}

发表于 2020-03-22 23:48:58 回复(0)

最接近的数

问题信息

热门推荐

通过挑战的用户

相关试题