编程之美

前段日子又看了编程之美，后来闲着无聊学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!的十进制表示末尾有多少个0
int decCountLastZero( int n )
{
	int ret = 0;
	while( n )
	{
		n /= 5;
		ret += n;
	}
}
//N!的二进制表示末尾有多少个0
int 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来做ID
typedef 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 ++;
			else
				nTimes --;
		}
	}
	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;
		else
			y -= 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;
			}
			else
				x >>= 1;
		}
		else
		{
			if( y&0x1 == 0 )
				y >>= 1;
			else
			{
				if( x>y )
					x -= y;
				else
					y -= 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];
			else
				result[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就是环的入口了
		//不然环的入口就是pCycle
		pCur = 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;
}