Allen Sun的图书主页-查字典图书网

2010-05-06

书中的方法很好，但是个人认为判断条件过多从而不容易掌握。可以利用BFS+剪枝即可，容易理解。《编程之美读书笔记》中有关于此题的BFS解法，但是我认为他剪得不彻底，可以再多剪剪。

标准BFS搜索m*n，所有0，1组成的数可以构造出一颗二叉树从而进行BFS。每层的数字长度相同，每个节点的左右孩子为其末尾分别添加0，1。BFS可保证是从小到大进行测试。

由于是按层序遍历的，因此可以保证如果bitmap中某个余数的对应项被置为1，则表示对应该余数的最小n*m已经找到。今后只需对它扩展即可。因为假设该数为x，之后遍历到的与它同余的数位y，则x<y。由y扩展出来的子树和x扩展出来的子树相同，因此可以把y对应的子树剪枝

bitmap[i]==1表示mod n余i的最小数已经被找到并且已经放入队列中继续做其子树的扩展。
之后再遇到余i的数，其子树和已找到的的最小的数相同，所以不需要再进行扩展，因此可以舍弃不处理（即不入队）

复杂度：若最终结果为k位，每一层最多有n个节点（余数为0...n-1），
因此空间复杂度为n（队列中最多有n个不同余数的节点），时间复杂度为O(kn)

code:

struct slot
{
        slot():val(0),remainder(0){}
        slot( __int64 v, __int64 r ):val(v),remainder(r){}
        __int64 val ; __int64 remainder ;
};

void OnlyHasOneAndZero2( __int64 n )
{
        slot *Q = new slot[n+1] ;
        char *bitmap = new char[n] ;
        memset( bitmap, 0, sizeof(char)*n ) ;

        slot a ;
        __int64 rear, front, capacity ;
        __int64 left, right ;
        __int64 leftR, rightR ;

        rear = 0 ; front = 1 ; capacity = n ;
        if( n==1 ) //***注意当n为1时，1%1=0，此为特殊情况
                Q[++rear] = slot(1,0) ;
        else
                Q[++rear] = slot(1,1) ;

        while( true )
        {
                a = Q[front] ; //出栈做处理、判断
                if( ++front == capacity )
                        front = 0 ;

                if( a.remainder == 0 )
                {
                        printf( "n*m=%I64d , m=%I64dn", a.val, a.val/n ) ;
                        delete []Q ;
                        delete []bitmap ;
                        return ;
                }

                left = a.val*10 ; leftR = a.remainder*10%n ;
                right = a.val*10+1 ; rightR = (a.remainder*10+1)%n ;

                //只要bitmap中某位i被置1，则意味着mod n余i的最小数已经被找到
                //若其左孩子的余数未出现过，则将其bitmap位置1，并加入队列做下面的扩展
                if( !bitmap[leftR] )
                {
                        bitmap[leftR] = 1 ;

                        if( ++rear == capacity )
                                rear = 0 ;
                        Q[rear] = slot( left, leftR ) ;
                }
                if( !bitmap[rightR] )
                {
                        bitmap[rightR] = 1 ;

                        if( ++rear == capacity )
                                rear = 0 ;
                        Q[rear] = slot( right, rightR ) ;
                }
        }
}