编程之美续

看完编程之美后看很多题，都会发现原来只是里面一些题目的变种（也大概因为看的是微软的笔试题吧。。），把原先的算法稍微一改，就变成了题目的解法，还是挺带劲的。

1. 反转单向链表：给出单向链表的头指针，要求把链表反转过来。

struct ListItem
{
	int value;
	struct ListItem* next;
};

ListItem* reverse( ListItem* pHead )
{
	//如果链表为空或只有一个元素，直接返回
	if( pHead==NULL || pHead->next == NULL )
		return pHead;
	ListItem* pNext=pHead->next;
       	ListItem* pCatch=pNext->next;
	pHead->next = NULL;
	while( pCatch != NULL )
	{
		pNext->next = pHead;
		pHead = pNext;
		pNext = pCatch;
		pCatch = pCatch->next;
	}
	pNext->next = pHead;
	pHead = pNext;
	return pHead;
}

[b]1.1 给定两个指针pHead和pStart， pHead是链表的头指针，把链表从pStart处反转过来，如：[\b]
1 -> 2 -> 3 -> 4 -> 5 -> NULL，pStart指向3，反转后变成：
3 -> 2 -> 1 -> 4 -> 5 -> NULL
可以看出，前面的例子是这个问题的特例，即当pStart指向链表的最后一个元素。因此，需要改的地方只有两处：

ListItem* reverse( ListItem* pHead, ListItem* pStart )
{
	//改动1：如果链表为空或只有一个元素，或pStart指向pHead,直接返回
	if( pHead==NULL || pHead == pStart || pStart == NULL )
		return pHead;
	ListItem* pNext=pHead->next;
       	ListItem* pCatch=pNext->next;
	pHead->next = pStart->next;	//改动2：末尾原为NULL，现为pStart->next（下同）
	while( pCatch != pStart->next )
	{
		pNext->next = pHead;
		pHead = pNext;
		pNext = pCatch;
		pCatch = pCatch->next;
	}
	pNext->next = pHead;
	return pStart;
}

2. 多个整数的最大公约数
前面我们提到两个整数的最大公约数，给出了三种做法，最后一种做法结合了一二种做法的优势。现在，如果有多个整数呢？有三种思路：
（1）递归求解，ngcd( arr[0,n-1] ) -> gcd( arr[n-1], ngcd( array[0,n-2] ) )，gcd我们使用最后一种做法：

int gcd( int a, int b )
{
	int base = 1;
	while( a!= b )
	{
		if( a&0x01 == 0 )
		{
			if( b&0x01 == 0 )
			{
				base <<= 1;
				a >>= 1;
				b >>= 1;
			}
			else
				a >>= 1;	
		}
		else
		{
			if( b&0x01 == 0 )
				b >>= 1;
			else
			{
				if( a> b )
					a -= b;
				else 
					b -= a;
			}
		}
	}
	return base*a;
}

//求多个数的最大公约数，函数接收数组的指针及数组大小
int ngcd1( int* array, int size )
{
	//递归求解
	if( size == 1 )
		return *array;
	return gcd( array[size-1], ngcd1( array, size-1 ) );
}

（2）化解递归：不难看出，上面的递归求解化解开来，就是依次求出arr[0,i]的最大公约数，然后通过求该公约数与arr[i+1]的最大公约数，最终得到arr[0,n-1]的公约数。

//继续使用上面的gcd
int ngcd3( int* array, int size )
{
	if( size == 1 )
		return array[0];
	int curGcd = gcd( array[0], array[1] );
	int i=2; 
	//当出现当前最大公约数为1时，无需再求剩下的元素的公约数了
	while( curGcd != 1 && i<size )
		curGcd = gcd( curGcd, array[i++] );
	return curGcd;
}

（3）辗转相除法：从数组中找出当前不为0的元素中的最小元素，剩下元素均余该元素，得到新的数组，直到最后只剩下一个元素不为0，该值即为最大公约数。过程如下：
(120, 168, 328, 624, 320) //当前最小非零元素为120，其余元素均模120
(120, 48, 88, 24, 80) //当前最小非零元素为24
(0, 0, 16, 24, 8 ) //当前最小非零元素为8
(0, 0, 0, 0, 8 ) //最大公约数为8

int ngcd2( int* scrArray, int size )
{
	int minIndex = 0;
	while( minIndex<size && !scrArray[minIndex++] );
	minIndex--;
	//if all elements are 0
	if( scrArray[minIndex] == 0 )
		return 0;
	int* array = new int[size];
	for( int i=0; i<size; i++ )
		array[i] = scrArray[i];
	int res = 1;

	//minElem 为非零元素中最小的那个
	int minElem = array[minIndex];
	for( int i=minIndex+1; i<size; i++ )
		if( array[i] && minElem > array[i] )
		{
			minElem = array[i];
			minIndex = i;
		}
	//找到当前最小非零元素，将其交换到第一个元素的位置
	array[minIndex] = array[0];
	array[0] = minElem;
	
	while( minElem>1 )
	{
		for( int i=1; i<size; i++ )
		{
			array[i] = array[i]%array[0];
			if( array[i] && array[i]<minElem )
			{
				minIndex = i;
				minElem = array[i];
			}
		}
		//如果minElem并没有改变，说明当前除了array[0]之外其余均为0了
		if( minElem == array[0] )
		{
			res = minElem;
			break;
		}
		array[minIndex] = array[0];
		array[0] = minElem;
	}
	delete[] array;
	return res;
}

3. 反转字符串：
本来这是一道挺简单的题目，但是题目说要尽量优化速度和空间，让我感觉压力蛮大。于是我决定上网瞧瞧，但是似乎没有找到挺好的结果。

char* reverse( char* str )
{
	//总共遍历了str两次，一次用于计算strlen，一次用于逐个交换。
	//使用到的额外的空间是两个用于遍历str的指针，一前一后
	int len = strlen(str);
	char* beg = str, *end = str+len-1;
	while( end > beg )
	{
		*end ^= *beg;
		*beg ^= *end;
		*end ^= *beg;
		end--;
		beg++;
	}
	return str;
}

3.1 如果以单词为单位进行反转呢？
即"I am a student" -> "student a am I"
策略：对整个字符串反转，然后再逐个单词反转回来。修改reverse为对字条串某一范围进行反转。

//end是有效下标
char* __reverse( char* str, int beg, int end )
{
	while( end>beg )
	{
		str[end] ^= str[beg];
		str[beg] ^= str[end];
		str[end] ^= str[beg];
		end--;
		beg++;
	}
	return str;
}

char* reverseByWord( char* str )
{
	int len = strlen( str );
	str = __reverse( str, 0, len-1 );
	int iStart =0, iEnd = 0;
	for( int i=0; i<len; i++ )
	{
		if( str[i] == ' ' )
		{
			iEnd = i-1;
			__reverse( str, iStart, iEnd );
			iStart = i+1;
		}
		else if( !((str[i]>='A'&&str[i]<='Z') or (str[i]>='a'&&str[i]<='z')) )
			iStart = i+1;
	}
	__reverse( str, iStart, len-1 );
	return str;
}

4. 约瑟夫环
约瑟夫环是昨晚同学问我的一个问题，问题的大致描述如下：
已知n个人（编号为1, 2, 3, ..., n）围成一圈，从编号为k的人开始报数1，数到m的那个人出列；接着又从出列的那个人的下一位开始报1，数到m的那个人出列，依此规律，求出最后剩下的那个人。
例如有n=5个人，m=2，从编号k=1的人开始报号，整个过程如下：
1 2 3 4 5 -> 2出列
3 4 5 1 -> 4出列
5 1 3 -> 1出列
3 5 -> 5出列
3 -> 最后剩下的人为3
可以通过模拟整个过程来求出最后剩下的那个人的序号，可是如果m，n很大的话，复杂度将会很高，尤其是用数组的时候，如何利用数学方法来求出最后那个人的序号呢？
通过上面的模拟过程，我们也大概可以看到，当有n个人时，第k个出列后，我们对剩下的n-1个人重新编号，编号方法如下：
k+1 -> 1
k+2 -> 2
k+3 -> 3
...
n -> n-k
1 -> 1-k+n
2 -> 2-k+n
...
k-1 -> n-1
这样，整个问题就变成一个n-1个人的小问题了。如果我们知道n-1个人这个问题中最后剩下的那个人的序号，那么通过上面的逆映射，我们便知道了n个人这个问题中最后剩下的那个人的序号。依次类推，要知道n-1个人最后剩下的那个人的序号，只要求出n-2个的，最后问题将会推到求出1个人的，而如果只有一个人，最后剩下的那个人的序号自然为1了。设fm[i]为i个人玩游戏，报数为m的人出列，最后剩下的那个人的编号（我怎么觉得有那么些绕口），那么有f[1]=1.如何从f[i-1]逆映射到f[i]呢？
设x'为某人在n个人时的编号，x为其在n-1个人时的编号，由上面的映射我们可以得到：
x' = (x+k)%n，其中k=m%n，因此，x'=(x+m)%n。问题在于，x'的范围在[0,n-1]，没有编号为n的人，而多了个编号为0的人，实际上，编号为0的人其编号为n。因此我们得到：
f[1] = 1
f[i] = (f[i-1]+m)%i，if (f[i-1]+m)%i == 0，f[i]=i
我们的目标就是求出f[n]，所以结果如下：

int josephus( int n, int m )
{
	int r = 1;
	for( int i=2; i<=n; i++ )
	{
		r = (r+m)%i;
		if( r == 0 )
			r = i;
	}
	return r;
}

如果从指定从编号为k的人开始报数1，结果是这样：

int josephus( int n, int m, int k )
{
	int r = josephus( n, m );
	return (r+k-1)%n;
}