编程之好续

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

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;}elsea >>= 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]的公约数。

//继续使用上面的gcdint 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 0if( 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;}

查看更多 下一篇