编程之好

编程之美
前段日子又看了编程之美，后来闲着无聊学python去了，想着书将要送人，还是先总结一下，不然怕又要忘了，呵呵。

主要看的章节是第二、第三章，因为对数独有特别的感情，所以还顺带看了一四章关于数独的那两节。

1. 对于一个字节的无符号整形变量，求其二进制表示中“1”的个数。
最简单的莫过于用/跟%一个位一个位地测试：

int count( unsigned char n ){int num = 0;while( n ){if ( n%2 == 1 )num++;n >>= 1;}return num;}

算法的复杂度为O(n)，但是操作符/跟%的代价都比较高。我比较喜欢的解法是这个：

int count( unsigned char n ){int num = 0;while( n ){n &= (n-1);num++;}return num;}

把复杂的/跟%转换成&和-，循环的次数是1的个数。
1.1 给定两个正数A和B，问把A改变为B需要改变多少位(bit)：我觉得就是对A、B先做一次异或，再计算有多少个1，即count(A^B).
1.2 给定一个整个n，判断它是否为2的方幂：n>0 && ((n&(n-1))==0)

2. 给定一个整数N，那么N的阶乘N!末尾有多少个0呢？N!的二进制表示中最低位1的位置又是在哪里呢？
其实这两道题的做法基本是一样的。对于十进制的N!，其末尾的0是由2*5取得的，2出现的次数很多，任何一个偶数都能提供一个因数2，而对于5，只有5，10，15这些能提供，25将提供两次5，125将贡献3个5，因此，只要计算N!中提供的5的个数，便可以计算出末尾有多少个0了，每个5决定一个末尾的0.
那么N!二进制表示最低位1呢？全是由*2造成的。从1乘起，只要每*2一次，0x1就会被左移一次，带来一个0，因此，只要计算N!提供的2的个数，例如2，6，10等提供一个2， 4提供两个，8提供3个....

//N!的十进制表示末尾有多少个0int decCountLastZero( int n ){int ret = 0;while( n ){n /= 5;ret += n;}}//N!的二进制表示末尾有多少个0int binCountLastZero( int n ){int ret = 0;while( n ){n >>= 1;ret += n;}return ret;}

不过，第二个问题有另一个更好的解法，就是N-(N二进制表示中1的个数)

3. 海量ID号中，其中有一个ID号超过了半数，找出这个ID。
解决的思路是每次取出两个不同的ID号来，然后把它们剔除。最后剩下的相同的ID号就是这个超过半数的ID。如下：

//假设以int来做IDtypedef int ID;ID find( ID* ids, int N ){ID candidate;int nTimes;//对所有ID进行一次遍历，nTimes用于标识两个不相等的ID号。for ( int i=nTimes=0; i<N; i++ ){if( nTimes == 0 ){candidate = ids[i];nTimes = 1;}else{if( candidate == ids[i] )nTimes ++;elsenTimes --;}}return candidate;}

3.1 如果是有三个ID，它们的数量都超过了ID总数的1/4呢？
原本我们只需要一个nTimes来标识与当前candidate重复的ID的数量，现在有了3个ID，虽然我们同样也是每次取出4个不同的ID删掉，直到最后不再有4个不同的ID可以删除了之后，肯定最后剩下的ID号就是这3个ID号的重复，但是这次需要多个nTimes来维护4个不同的ID了:

typedef int ID;struct Record{ID rId;int count;Record( int c = 0 ){ count = c; }};void printTop3ID( ID* ids, int n ){Record rec[4];int i=0;while( i<n ){for( int j=0; j<4; j++ ){while( rec[j].count == 0 ){ID cand = ids[i++];int k=0;for( k=0; k<4; k++ ){if( rec[k].count>0 && rec[k].rId == cand ){rec[k].count++;break;}}if( k == 4 ){rec[j].count ++;rec[j].rId = cand;}}}for( int j=0; j<4; j++ )rec[j].count --;}for( int j=0; j<4; j++ ){if( rec[j].count > 0 )cout<<rec[j].rId<<endl;}}

4. 求两个正整数的最大公约数
辗转相除法：假设用f(x,y)表示x,y的最大公约数，取k=x/y，b=x%y，则x=ky+b，如果一个数能同时整除x和y，那么它必能同时整除y和b，而能够同时整除y和b的数也必能同时整除x和y，即x和y的最大公约数和y和b的最大公约数是相等的，即f(x,y)=f(y,x%y)，如此便把原问题转换为求两个更小数的最大公约数，直到其中一个为0，剩下的另外一个就是两者最大的公约数。

int gcd1( int x, int y ){assert( x>0 && y>0 );while( y ){int t = x;x = y;y = t%y;}return x;}

假如x,y很大，取模运算的开销会很大，可以用减号运算来代替取模运算：

int gcd2( int x, int y ){assert( x>0 && y>0 );while( x!=y ){if( x>y )x -= y;elsey -= x;}return x;}

因为用了减号来替换原先的取模运算，循环的次数增加了，最不幸的是，gcd2(100000,1)将会走100000个循环！
深入辗转相除法，如果y=k*y', x=k*x'，那么f(x,y)=k*f(x', y')。另外，如果x=p*x'且p是素数，并且y%p!=0（即y不能被p整除），那么f(x,y)=f(p*x', y)=f(x',y),这里，2无疑是p的最佳人选。

int gcd3( int x, int y ){assert( x>0 && y>0 );int base = 1;while( x!=y ){if( x&0x1 == 0 ){if( y&0x1 == 0 ){base <<= 1;x >>= 1;y >>= 1;}elsex >>= 1;}else{if( y&0x1 == 0 )y >>= 1;else{if( x>y )x -= y;elsey -= x;}}}return base*x;}

5. 给定两个字符串s1和s2，要求判定s2是否能够被通过s1做循环移位得到的字符串包含，例如，s1='aabcd'和s2='cdaa'返回true而s1='abcd'，s2='acbd'返回false。
最直接的办法是通过对s1做len(s1)次循环并依次判断s2是否是该次循环得到的字符串的子字符串。当然，这样算法的复杂度约为O(n1*n2)，其中n1为len(s1)而n2为len(s2)。
其实可以直接对s1做一次复制，得到一个新的字符串s3=s1s1，如果s2是s3的子串的话，那么通过循环移位s1可以包含s2。不过在这之前，要先判断len(s1)>len(s2)。

bool isSubRotate( char* s1, char* s2 ){if( strlen(s1) < strlen(s2) )return false;int len = strlen(s1);char* s3 = new char[len*2+1];strncpy( s3, s1, len );strncpy( s3+len, s1, len );bool res = !(strstr(s3, s2) == NULL );delete s3;return res;}

5.1 插播：strstr的实现

char* my_strstr( const char* str1, const char* str2 ){const char* buf, *sub;if( !*str2 )return const_cast<char*>(str1);while( *str1 ){buf = str1;sub = str2;do{if( !*buf )return const_cast<char*>(str1);}while( *buf++ == *sub++ );str1 ++;}return NULL;}

6. 字符串的距离
对于两个不相同的字符串，可以通过以下的方法将其变得相同：
（1）修改一个字符
（2）增加一个字符
（3）替换一个字符
例如，对于"abcdefg"和"abcdef"，我们可以通过增加/减少一个"g"的方式来达到目的，它们的距离为1。给定两个字符串，计算它们的距离。
应该考虑如何将这个问题转化成规模较小的同样的问题。如果有两个串A="xabcdae"和B="xfdfa"，它们的第一个字符是相同的，只要计算A[2,..7]和B[2,5]的距离就可以了。对于两个第一个字符不同的串，可以进行如下操作：
（1）一步操作后，再计算A[2,...,]和B[1,...,]的距离
（2）一步操作后，再计算A[1,...,]和B[2,...,]的距离
（3）一步操作后，再计算A[2,...,]和B[2,...,]的距离
可以用动态规则来做。
假设strA，strB的长度分别为lenA，lenB，result[i][j]表示strA[i,lenA]跟strB[j,lenB]的距离:

int strdist( const char* strA, const char* strB ){int lenA = strlen(strA), lenB = strlen(strB);int** result = new int*[lenA+1];for( int i=0; i<lenA+1; i++ )result[i] = new int[lenB+1];//初始化边界for( int i=0; i<=lenA; i++ )result[i][lenB] = lenA-i;for( int i=0; i<=lenB; i++ )result[lenA][i] = lenB-i;for( int i=lenA-1; i>=0; i-- )for( int j=lenB-1; j>=0; j-- ){if( strA[i] == strB[j] )result[i][j] = result[i+1][j+1];elseresult[i][j] = minOfThree( result[i+1][j+1],result[i][j+1],result[i+1][j] )+1;}int ret = result[0][0];for( int i=0; i<lenA+1; i++ )delete[] result[i];delete[] result;return ret;}

7. 重建二叉树：给出二叉树的前序、中序，要求重建二叉树。

template<typename T>struct Node{T value;Node *left, *right;Node( T v, Node* l=NULL, Node* r=NULL ):value(v), left(l), right(r){}};template<typename n>Node<T>* rebuild( T* pPreOrder, T* pInOrder, int len ){//pPreOrder是前序遍历的数组//pInOrder是后序遍历的数组//len是数组的长度，其实就是树结点的个数if( pPreOrder==NULL || pInOrder==NULL || len<1 )return NULL;Node<T>* subroot = new Node<T>(pPreOrder[0]);if( len == 1 )return subroot;//如果len=1，该树只有一个叶子结点T* rightInOrder=pInOrder;while( *rightInOrder != *pPreOrder )rightInOrder ++;int leftLen = rightInOrder-pInOrder;int rightLen = len-leftLen-1;subroot->left = rebuild( pPreOrder+1, pInOrder, leftLen );subroot->right = rebuild( pPreOrder+1+leftLen, rightInOrder+1, rightLen );return subroot;}

8. 判断链表是否有环，如果有，返回指向环入口结点的指针，否则返回NULL
Note:这是3.11的程序改错，因为要求保持程序的基本框架，所以使用了下面的方法（其实是从网上看过来的），如果是我自己写，我估计就拿LinkList的结点地址去哈希了，一旦找到相同地址的结点，即可判断环的入口，或者遇到NULL，说明没有环。
遵循原先程序的框架，要判断是否有环，必须有两个指针以不同的步长来遍历链表，如果哪天他们相遇了，说明这个链表肯定有环，但是至于环的入口，得重头再找（在知道有环的情况下找入口）。

LinkList* IsCyclicLinkList( LinkList* pHead ){//pCur走一步，pStart走两步，pCycle指向pCur和pStart重合的地方，如果有的话LinkList* pCur, *pStart, *pCycle;pCur = pStart = pHead;pCycle = NULL;while( pCur != NULL && pStart != NULL ){if( pStart->next == NULL )return NULL;pStart = pStart->next->next;pCur = pCur->next;if( pStart == pCur ){pCycle = pStart;break;}}//测试是否有环if( pCycle != NULL )//有环，接下来将找环的入口点{//pCur从头找起，pStart则从重合的地方开始，如果pStart和pCur遇上了，说明pCur就是环的入口了//不然环的入口就是pCyclepCur = pHead;while( pCur != pCycle ){pStart = pCycle;while( pStart != pCur && pStart != pCycle )pStart = pStart->next;if( pStart == pCur )return pCur;pCur = pCur->next;}return pCycle;}return NULL;}

查看更多 下一篇