编程之美-数字中的技巧1

· 1219 words · 3 minute read
2017年8月
算法

求二进制数中1的个数

解法1 使用位操作

int Count(Byte v){
    int num = 0;
    while(v){
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

ps:最好让1进行移动即 0x01 <<= 1;

解法2 相与

int Count(Byte v){
    int num = 0;
    while(v){
        v &= v-1;
        num++;
    }
    return num;
}

N!末尾有多少个0？

解法1 N! = K*10^M,且k不能被10整除，那么N!末尾有M个0，N!=2^x * 3^y * 5^z, 每一对2和5相乘可以得到一个10，于是 M = min(x,z)，x>=z，所以M = z. 总结：即计算1…N的因式分解中能被5整除的数。

ret = 0;
for(int i = 1; i <= N; i++){ 
    j = i;
    while(j % 5 == 0){
        j = j / 5;
        ret++；
    }
}
return ret;

解法2 z = [N/5] + [N/5^2] + [N/5^3]+…

ret = 0;
while(N){
    ret = ret + N/5;
    N = N/5;    
}
return ret;

求N!的二进制表示中最低位1的位置

解法1 该问题转化为求N!含有因数2的个数+1，即=[N/2]+[N/4]+[N/8]+[N/16]…+1 ？？？个人没看懂编程之美上的转换方式，还请大神们赐教

int lowestOne(int N){
    int Ret = 0;
    while(N){
        N >>= 1;
        Ret += N;
    }
    return Ret+1;
}

解法2 求N!含有因数的个数可以转换为N-N的二进制表示中1的数目

最大公约数问题

解法1 辗转相除法 f(x,y)表示x，y的公约数。f(x,y) = f(y,x%y) f(42,30) = f(30,12) = f(12,6) = f(6,0) ==> 6

int gcd(x,y){
    return y==0 ? x : gcd(y,x%y);
}

ps： 取模运算用到乘法，开销较大。

解法2 f(x,y) = f(y,x-y) (x>y),若x<y则先交换x,y

BigInteger gcd(BigInteger x, BigInteger y){
    if(x < y){
        gcd(y,x);   
    }
    if(y == 0){
        return x;
    }else{
        return gcd(y,x-y);
    }
}

ps: 迭代次数比解法1有相应增加

解法3 对于二进制的大整数求其公约数

  1. 若x,y均为偶数，f(x,y) = 2f(x/2,y/2) = 2f(x>>1,y>>1)
  2. 若x为偶数，y为奇数 f(x,y) = f(x/2,y)
  3. 若x为奇数，y为偶数 f(x,y) = f(x,y/2)
  4. 若x,y均为奇数，f(x,y) = f(y,x-y),该操作下一步一定会有除以2的操作

任意给定一个正整数N,求一个最小的正整数M(M > 1).使得N*M的十进制表示形式里只含有1和0.

解法1

转化问题！！！ 将该问题转化为，求一个最小的正整数X，使得X的十进制表示形式里只含有1和0，并且X被N整除。

因为N * M的取值就是1,10,11,100,101,110,111,……所以直接在这个空间搜索（枚举）。搜索这个序列直到找到一个能被N整除的数，它就是N*M，然后可计算出M。例如N=3时，搜索树如下：

上图中括号内表示模3的余数。括号外表示被搜索的数。左子树表示0，右子树表示1.上图中搜索到第二层（根是第0层）时遇到111，它模3余数为0.所以N*M=111, M=111⁄3=37。

//广度优先搜索
int get(int N){
    Queue<Integer> queue = new Queue<Integer>();
    queue.add(1);
    while(!queue.isEmpty()){
        int t = queue.poll();
        if(t % N == 0){
            return t;
        }
        queue.offer(t*10);
        queue.offer(t*10+1);
    }
}

解法2

该图是对解法1的优化，即对同一层，只存储第一次出现该余数的位置（因为本题是求最小的正整数）

寻找数组中的最大值和最小值

解法1

分治。在N个数中求最小值Min和最大值Max,我们只需分别求出前后N/2个数的Min和Max,然后取较小的Min,较大的的Max即可。总的比较次数为 1.5N

// list中，第0个为最大值，第1个为最小值
public List<Integer> search(int array, int start, int end){
    if(end-start <= 1){
        if(array[start] > array[end]){
            list.add(array[start]);
            list.add(array[end]);
        }else{
            list.add(array[end]);
            list.add(array[start]);
        }
    }
    list1 = search(array,start,(start+end)/2);
    list2 = search(array,(start+end)/2+1,end);

    //判断list1和list2联合起来后的最大值和最小值

    return list3;
}
Share