Desc: 做出来了,或者理解了,但是速度太慢了,都记录在此.

answer:

more:

1. 用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，

   最多可以从y个小球中找出较轻的那个，求y与x的关系式。
   answer:
   x=1, y=3: if a=b, c is the lighter, else the lighter is the lighter…

   do this recursively. so y=3\^x;

   more: Q:球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球?

   A:13个球也是可以做的。就是分成4个、4个、5个，先拿两个四个上去，如果平衡，则问题出在5个那组，就在5个里任拿三个设为C1C2C3，再拿三个正常的，分别放两边，若平衡就简单啦，若不平衡，就出现C1C2C3重，或C1C2C3轻，相当于就知道那个特别的球是比较重或者比较轻啦，接下就不用说了

   如果不平衡，假设现在是A重B轻，

   取A1+A2+B1放天平一边(设为左边)，

   再取A3+A4+B2放另一边（右），

   若平衡，就在B3/B4任拿一个跟C1上去称就行了，

   如果不平衡，那么假设

   情况一：左重

   则是A1/A2/B2有问题

   直接把A1A2放两边称，重的那个有问题，如果平

   衡就是B2有问题

   情况二：右重

   就是 A3/A4/B1有问题，方法同上

   ,,,,,称3次的话,最多可以辨别3的3次方,也就是27个球,传统的2的3次方只能辨别8个球.

2. 输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

   \#include \<iostream\>\ \#include \<algorithm\>\ \#include \<iterator\>\ \#include \<cassert\>\ \ using std::cout;\ using std::cin;\ using std::endl;\ using std::copy;\ using std::ostream\_iterator;\ \ void PermuAuxi( char szStr[], int iStart, int iEnd ){\ if( iStart \>= iEnd ){\ copy( &szStr[0], &szStr[iEnd], ostream\_iterator\<char\>(cout, "") );\ cout \<\< endl;\ return;\ }\ \ for( int i = iStart; i \< iEnd; i++ ){\ std::swap( szStr[iStart], szStr[i] );\ PermuAuxi( szStr, iStart + 1, iEnd );\ std::swap( szStr[iStart], szStr[i] );\ }\ }\ void Permutation( char \*szStr ){ if( szStr == NULL ) return; PermuAuxi( szStr, 0, strlen(szStr) );\ }\ \ int main( int argc, char \*argv[] ){\ char szStr[256];\ cout \<\< "Input string:\\n";\ cin \>\> szStr;\ cout \<\< "Permutation:\\n";\ Permutation( szStr );\ }\ /\*Sample output:\ Input string:\ abc\ Permutation:\ abc\ acb\ bac\ bca\ cba\ cab\ 请按任意键继续. . .\ \*/

3. 给定链表的头指针和一个结点指针，在O(1)时间删除该结点。\ 链表结点的定义如下：

   struct ListNode

   {

     int        m\_nKey;
   
     ListNode\*  m\_pNext;
   

   };

   函数的声明如下：

   void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

   分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。
   answer:\

   Copy the data from tobedeleted’s next to tobedeleted. then delete tobedeleted. The special case is

   tobedelete is the tail, then we must iterate to find its predecessor.

   The amortized time complexity is O(1).

   \ void DeleteNode(stNode\* pListHead, stNode\* pToBeDeleted){\ if( pListHead == NULL || pToBeDeleted == NULL ) return;\ \ \ stNode \*pNode = pToBeDeleted-\>\_next;\ if( pNode ){\ pToBeDeleted-\>\_data = pNode-\>\_data;\ pToBeDeleted-\>\_next = pNode-\>\_next;\ delete pNode;\ }\ }

4. 一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？
   answer:
   A:路在左边,B说的话是错的.

   B:路在左边,A说的话是错的.

   如果有一个人说F,则那个人肯定是诚实国的人.并且相信他,路在右边

   如果都说T,则路肯定是在左边..

   因为说谎国的人对于以上两句话都只会回答T.

5. 用递归的方法判断整数组a[N]是不是升序排列

6. 不用乘法或加法增加7倍：\ 7 = 8 - 1 则：(x<<3)-x

   7 = (16-2)/2 则：(x<<4 - x<<1)>>1

7. 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。

   例如输入“I am a student.”，则输出“student. a am I”。

   \#include "stdafx.h"\ void ReverseStrOrder( char \*szStr ){\ assert( szStr );\ \ int len = strlen( szStr ); // Reverse string.\ int iPost = len - 1;\ int iPrev = 0;\ while( iPrev \< iPost ){\ szStr[iPrev] = szStr[iPrev] \^ szStr[iPost];\ szStr[iPost] = szStr[iPrev] \^ szStr[iPost];\ szStr[iPrev] = szStr[iPrev] \^ szStr[iPost];\ iPrev++;\ iPost--;\ }\ cout \<\< szStr \<\< endl;\ \ char \*p = szStr;\ char \*pFirst = NULL, \*pLast = NULL;\ while( \*p != '\\0' )\ {\ pFirst = p;\ while( \*p != '\\0' && \*p != ' '/\* && \*p != ',' && \*p != '.' && \*p != '!' && \*p != ';' \*/) p++;\ pLast = p - 1;\ \ while( pFirst \< pLast ) std::swap( \*pFirst++, \*pLast-- );\ \ if( \*p != '\\0' ) p++;\ }\ }\ int main(){\ char szStr[256] = "I am a student.";\ ReverseStrOrder( szStr );\ cout \<\< szStr \<\< endl;\ }\ /\*Sample output:\ .tneduts a ma I\ student. a am I\ 请按任意键继续. . .\ \*/

8. 用一种算法使含通配符字符串相匹配.

   \#include "stdafx.h"\ \ bool IdxKMP( const char \*szMain, const char\* szSearch, const int pos, const int \*next ){\ assert( szMain != NULL && szSearch != NULL && next != NULL );\ \ int i = pos, j = 0;\ int lenMain = static\_cast\<int\>(strlen(szMain));\ int lenSearch = static\_cast\<int\>(strlen(szSearch));\ \ while( i \< lenMain && j \< lenSearch )\ {\ if( j == -1 || szMain[i] == szSearch[j] || szSearch[j] == '?' ){\ i++;\ j++;\ }\ else if( szSearch[j] == '\*' ){\ j++;\ while( i \< lenMain && szMain[i] != szSearch[j] ) i++;\ }\ else\ j = next[j];\ }\ \ if( j \>= lenSearch )\ return true;\ else\ return false;\ }\ \ void GetNext( const char \*szSearch, int \*next ){\ assert( szSearch != NULL && next != NULL );\ \ int i = 0, j = -1;\ int len = strlen( szSearch );\ next[0] = -1;\ while( i \< len - 1 )\ {\ if( j == -1 || szSearch[i] == szSearch[j] ){\ i++;\ j++;\ next[i] = j;\ }\ else\ j = next[j];\ }\ \ }\ bool Wildcard( const char \*szMain, const char\* szSearch ){\ assert( szMain != NULL && szSearch != NULL );\ \ int \*next = NULL;\ next = new int[strlen(szSearch)];\ // Preprocess.\ GetNext( szSearch, next );\ \ // Process.\ bool ret = IdxKMP( szMain, szSearch, 0, next );\ \ // Postprocess.\ delete []next;\ \ return ret;\ }\ int main(){\ const char \*sMain("My notadepad");\ const char \*sSearch("\*not\*p?d");\ cout \<\< std::boolalpha \<\< Wildcard( sMain, sSearch ) \<\< endl;\ }

9. 有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
   Caution: 注意审清题,m+1的长度的字符串,m个字符要匹配,联接不是合并.

   \#include \<iostream\>\ \#include \<string\>\ \#include \<climits\>\ \#include \<cmath\>\ \#include \<fstream\>\ \#include \<vector\>\ \ using namespace std;\ \ \#define INFINITY INT\_MAX\ \#define MAX\_VERTEX\_NUM 100\ \ int m;\ typedef struct{\ int \*vexs;\ int (\*arcs)[MAX\_VERTEX\_NUM];\ int vexnum, arcnum;\ }MGraph;\ \ struct stMatGraph{\ explicit stMatGraph( int nVex, string \*pVertices = NULL, bool \*\*ppArcs = NULL )\ :\_nVex(nVex), \_pVertices(pVertices), \_ppArcs(ppArcs){}\ \ string \*\_pVertices;\ bool \*\*\_ppArcs;\ \ int \_nVex;\ };\ \ bool IsMatched( const string &str1, const string &str2 ){\ int idx1 = m;\ int idx2 = m - 1;\ while( idx2 \>= 0 && str1[idx1] == str2[idx2] ){\ idx1--;\ idx2--;\ }\ \ if( idx2 \< 0 )\ return true;\ else\ return false;\ }\ \ void CreateGraph( stMatGraph \*pGraph, vector\<string\> &vecStr ){\ \ pGraph-\>\_nVex = vecStr.size();\ pGraph-\>\_pVertices = new string[pGraph-\>\_nVex];\ for( int i = 0; i \< pGraph-\>\_nVex; i++ )\ pGraph-\>\_pVertices[i] = vecStr[i];\ \ pGraph-\>\_ppArcs = new bool \*[pGraph-\>\_nVex];\ for( int i = 0; i \< pGraph-\>\_nVex; i++ ){\ pGraph-\>\_ppArcs[i] = new bool[pGraph-\>\_nVex];\ memset( pGraph-\>\_ppArcs[i], 0, sizeof(bool)\*pGraph-\>\_nVex );\ }\ \ for( int i = 0; i \< pGraph-\>\_nVex; i++ )\ for( int j = 0; j \< pGraph-\>\_nVex; j++ ){\ pGraph-\>\_ppArcs[i][j] = IsMatched( pGraph-\>\_pVertices[i], pGraph-\>\_pVertices[j] );\ }\ }\ \ \ void DeleteMatGraph( stMatGraph \*pGraph ){\ for( int i = 0; i \< pGraph-\>\_nVex; i++ )\ delete [](pGraph-\>\_ppArcs[i]); /\*[]pGraph-\>\_ppArcs[i]?\*/\ delete []pGraph-\>\_ppArcs;\ delete []pGraph-\>\_pVertices;\ }\ \ bool g\_bVisited[MAX\_VERTEX\_NUM];\ std::vector\<string\> g\_vecStrRecord;\ int Count = 0;\ int MaxCount = numeric\_limits\<int\>::min();\ bool g\_bContinued = true;\ /\*\ void DFSAuxi( stMatGraph \*pGraph, int i ){\ if( g\_bContinued )\ {\ g\_bVisited[i] = true;\ \ g\_vecStrRecord.push\_back( pGraph-\>\_pVertices[i] );\ Count++;\ if( MaxCount \< Count ){\ MaxCount = Count;\ \ // Test circular.\ vector\<string\>::iterator iter = g\_vecStrRecord.begin();\ string strLast = g\_vecStrRecord.back();\ \ int idx1 = 1, idx2 = 0;\ while( idx1 \< m + 1 && (\*iter)[idx1++] == strLast[idx2++] )\ ;\ if( idx1 \>= m + 1 ){\ cerr \<\< "Have circular.\\n";\ g\_bContinued = false;\ return;\ }\ \ for( ; iter != g\_vecStrRecord.end(); iter++ )\ cout \<\< \*iter \<\< " ";\ cout \<\< endl;\ }\ for( int j = 0; j \< pGraph-\>\_nVex; j++ ){\ if( pGraph-\>\_ppArcs[i][j] && !g\_bVisited[j] )\ DFSAuxi( pGraph, j );\ }\ Count--;\ g\_vecStrRecord.pop\_back();\ g\_bVisited[i] = false;\ }\ }\ \*/\ void DFSAuxi( stMatGraph \*pGraph, int i ){\ g\_bVisited[i] = true;\ \ g\_vecStrRecord.push\_back( pGraph-\>\_pVertices[i] );\ Count++;\ if( MaxCount \< Count ){\ MaxCount = Count;\ \ vector\<string\>::iterator iter = g\_vecStrRecord.begin();\ for( ; iter != g\_vecStrRecord.end(); iter++ )\ cout \<\< \*iter \<\< " ";\ cout \<\< endl;\ }\ for( int j = 0; j \< pGraph-\>\_nVex; j++ ){\ if( pGraph-\>\_ppArcs[i][j] && !g\_bVisited[j] )\ DFSAuxi( pGraph, j );\ }\ Count--;\ g\_vecStrRecord.pop\_back();\ g\_bVisited[i] = false;\ }\ \ void DFSTraverse( stMatGraph \*pGraph ){\ for( int i = 0; i \< pGraph-\>\_nVex; i++ )\ if( !g\_bVisited[i] )\ DFSAuxi( pGraph, i );\ }\ int main(){\ int n;\ ifstream inFile("2.txt");\ cout \<\< "Input the number of string:\\n";\ cin \>\> n;\ cout \<\< "Input the length of string:\\n";\ cin \>\> m;\ m--;\ vector\<string\> vecStr;\ string str;\ for( int i = 0; i \< n; i++ ){\ cin \>\> str;\ vecStr.push\_back( str );\ }\ cout \<\< endl;\ \ stMatGraph \*pGraph = new stMatGraph( n );\ CreateGraph( pGraph, vecStr );\ DFSTraverse( pGraph );\ cout \<\< "Maximum count:" \<\< MaxCount \<\< endl;\ \ DeleteMatGraph( pGraph );\ \ delete pGraph;\ }\ /\*\ Input the number of string:\ 14\ Input the length of string:\ 4\ abcd\ bcde\ cdea\ deab\ eaba\ abab\ deac\ cdei\ bcdf\ cdfi\ dfic\ cdfk\ bcdg\ babc\ \ abcd\ abcd bcde\ abcd bcde cdea\ abcd bcde cdea deab\ abcd bcde cdea deab eaba\ abcd bcde cdea deab eaba abab\ abcd bcde cdea deab eaba abab babc\ bcde cdea deab eaba abab babc abcd bcdf\ bcde cdea deab eaba abab babc abcd bcdf cdfi\ bcde cdea deab eaba abab babc abcd bcdf cdfi dfic\ Maximum count:10\ 请按任意键继续. . .\ \*/

10. 一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值\

    </span>比如{3，2，4，3，**6} **可以分成{3，2，4，3，**6} m=1; **

    {3,6}{2,4,3} m=2

    **{3,3}{2,4}{6} m=3 **所以m的最大值为3。

    \#include "stdafx.h"\ const int gc\_Size = 8;\ int arr[gc\_Size] = {1,1,1,3,2,4,3,6};\ int g\_iChosen[gc\_Size];\ \ bool StatSum( int nCntChosen, int leftSum ){\ bool ret = false;\ if( leftSum \< 0 ) return false;\ if( leftSum == 0 ) return true;\ \ for( int i = 0; i \< gc\_Size; i++ ){\ if( g\_iChosen[i] == 0 && !ret ){\ g\_iChosen[i] = nCntChosen + 1;\ bool tmpRet = StatSum( nCntChosen, leftSum - arr[i]);\ ret |= tmpRet;\ if( !tmpRet ) g\_iChosen[i] = 0;\ }\ }\ \ return ret;\ }\ \ // Return maximum split pieces.\ int AverSplit(){\ int sumTotal = accumulate( &arr[0], &arr[gc\_Size], 0 );\ // You have to sort by ascending order.\ // 当你选择的时候,越大的是在n个slice中唯一一个splitted的数组中的\ // 例如: 1,1,1,2,3,3,4,6.\ // 如果1,1,1,4入选,则不行.\ // 6则是其中一个splitted数组的不二选择.\ sort( &arr[0], &arr[gc\_Size], greater\<int\>() );\ \ int maxSlice = 1;\ int slice = 2;\ // slice肯定是sumTotal的余数,并且不可能大于arr的最大的数.\ while( slice \< sumTotal/2 && sumTotal/slice \>= arr[0] )\ {\ while( sumTotal % slice != 0 ){\ slice++;\ if( !(slice \< (sumTotal \>\> 2) && sumTotal/slice \>= arr[0]) )\ break;\ }\ \ memset( g\_iChosen, 0, sizeof(int)\*gc\_Size );\ int nCntChosen = 0;\ int sumSplitted = sumTotal/slice;\ while( nCntChosen \< slice ){\ if( StatSum( nCntChosen, sumSplitted) )\ nCntChosen++;\ else\ break;\ }\ if( nCntChosen \>= slice )\ maxSlice = slice;\ slice++;\ }\ \ \ return maxSlice;\ }\ \ int main(){\ cout \<\< AverSplit() \<\< endl;\ }

11. 求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

    \#include "stdafx.h"\ /\*\ 求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}.\ \*/\ const int gc\_iSize = 9;\ int arr[gc\_iSize] = {7,9,4,6,2,5,4,3,5};\ int seq[gc\_iSize][gc\_iSize];\ \ int GetLDS(){\ int ret = 0;\ seq[0][0] = 1;\ // [i] 第i个序列.\ // [j] 选中第j个数.\ for( int i = 1; i \< gc\_iSize; i++ )\ for( int j = 0; j \< gc\_iSize; j++ )\ {\ if( i == 0 || j == 0 ){\ if( arr[i] \<= arr[j] )\ seq[i][j] = 2;\ else\ seq[i][j] = 1;\ }\ else if( i \> j && arr[i] \<= arr[j] )\ seq[i][j] = std::max( seq[j][j] + 1, seq[i][j-1] );\ else\ seq[i][j] = seq[i][j-1];\ }\ for( int i = 0; i \< gc\_iSize; i++ )\ {\ for( int j = 0; j \< gc\_iSize; j++ ){\ cout \<\< seq[i][j] \<\< " ";\ }\ cout \<\< endl;\ }\ \ return seq[gc\_iSize-1][gc\_iSize-1];\ }\ int main(){\ cout \<\< GetLDS() \<\< endl;\ }\ \ /\*\ 1 0 0 0 0 0 0 0 0\ 1 1 1 1 1 1 1 1 1\ 2 2 2 2 2 2 2 2 2\ 2 2 2 2 2 2 2 2 2\ 2 2 3 3 3 3 3 3 3\ 2 2 2 3 3 3 3 3 3\ 2 2 3 3 3 4 4 4 4\ 2 2 3 3 3 4 5 5 5\ 2 2 2 3 3 4 4 4 4\ 4\ 请按任意键继续. . .\ \*/

12. 输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

    例如输入数组{32,** </span>321}**，则输出这两个能排成的最小数字32132。

    请给出解决问题的算法，并证明该算法。

    \#include "stdafx.h"\ \ /\*\ 输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。\ 例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。\ 请给出解决问题的算法，并证明该算法。\ \*/\ const int gc\_Size = 5;\ const int gc\_MaxNumLength = 10;\ int arr[gc\_Size] = { 32, 321, 123, 422, 43 };\ char \*g\_szStr1 = new char[gc\_MaxNumLength\*2+1];\ char \*g\_szStr2 = new char[gc\_MaxNumLength\*2+1];\ \ int CMP( const void \*str1, const void \*str2 ){\ strcpy( g\_szStr1, \*(const char\*\*)str1 );\ strcat( g\_szStr1, \*(const char\*\*)str2 );\ \ strcpy( g\_szStr2, \*(const char\*\*)str2 );\ strcat( g\_szStr2, \*(const char\*\*)str1 );\ \ return strcmp( g\_szStr1, g\_szStr2 );\ }\ void DoTask(){\ char \*\*ppStr = NULL;\ ppStr = new char \*[gc\_MaxNumLength+1];\ for( int i = 0; i \< gc\_Size; i++ ){\ \*(ppStr + i) = new char[gc\_MaxNumLength+1];\ sprintf( \*(ppStr +i), "%d", arr[i] );\ }\ qsort( ppStr, gc\_Size, sizeof(char\*), CMP );\ \ for( int i = 0; i \< gc\_Size; i++ )\ cout \<\< \*(ppStr + i) \<\< " ";\ \ for( int i = 0; i \< gc\_Size; i++ )\ delete [](\*(ppStr + i));\ delete []ppStr;\ }\ \ int main(){\ DoTask();\ delete []g\_szStr1;\ delete []g\_szStr2;\ }

13. 函数将字符串中的字符’*‘移到串的前部分，前面的非’*‘字符后移，但不能改变非’*‘字符的先后顺序，

    函数返回串中字符’*‘的数量。如原始串为：ab**cd**e*12，

    处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）。

    \#include "stdafx.h"\ /\*\ 函数将字符串中的字符'\*'移到串的前部分，前面的非'\*'字符后移，但不能改变非'\*'字符的先后顺序，\ 函数返回串中字符'\*'的数量。如原始串为：ab\*\*cd\*\*e\*12，\ 处理后为\*\*\*\*\*abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）\ \*/\ /\*\ \#include "stdafx.h"\ \ int MoveAsterisk( char \*str ){\ assert( str != NULL );\ \ int len = strlen( str );\ int iAsterisk = len - 1;\ int iNonAsterisk = len - 1;\ int nCnt = 0;\ \ // Find first asterisk.\ while( iAsterisk \>= 0 && str[iAsterisk] != '\*' ) iAsterisk--;\ iNonAsterisk = iAsterisk - 1;\ \ while( iAsterisk \>= 0 && iNonAsterisk \>= 0 )\ {\ while( iAsterisk \>= 0 && str[iAsterisk] != '\*' ) iAsterisk--;\ while( iNonAsterisk \>= 0 && str[iNonAsterisk] == '\*' ){ iNonAsterisk--;}\ if( iAsterisk \>= 0 && iNonAsterisk \>= 0 ){\ str[iAsterisk] = str[iAsterisk] \^ str[iNonAsterisk];\ str[iNonAsterisk] = str[iAsterisk] \^ str[iNonAsterisk];\ str[iAsterisk] = str[iAsterisk] \^ str[iNonAsterisk];\ nCnt++;\ }\ }\ \ return nCnt;\ }\ \*/\ int MoveAsterisk( char \*szStr ){\ assert( szStr != NULL );\ \ int len = strlen( szStr );\ \ char \*pAsterisk = szStr + len - 1;\ char \*pNonAsterisk = szStr + len - 1;\ \ while( pAsterisk \>= szStr ){\ if( \*pAsterisk != '\*' )\ \*pNonAsterisk-- = \*pAsterisk;\ pAsterisk--;\ }\ \ int nCnt = pNonAsterisk - pAsterisk;\ while( pNonAsterisk \>= szStr )\ \*pNonAsterisk-- = '\*';\ \ return nCnt;\ }\ \ int main(){\ char str[256] = "ab\*\*cd\*\*e\*12";\ cout \<\< MoveAsterisk( str ) \<\< endl;\ cout \<\< str \<\< endl;\ }

14. 求两个串中的第一个最长子串.

    如”abractyeyt”,”dgdsaeactyey”的最大子串为”actyet”。

    \#include "stdafx.h"\ /\*\ 求两个串中的第一个最长子串.\ 如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。\ \*/\ \ // Get first longest substring.\ void GetFLS( char \*pOut, const char \*str1, const char \*str2 ){\ assert( pOut != NULL && str1 != NULL && str2 != NULL );\ \ const char \*p1 = str1;\ const char \*p2 = str2;\ const char \*pMaxIdx = NULL;\ int maxLen = 0;\ while( \*p1 != '\\0' )\ {\ p2 = str2;\ while( \*p2 != '\\0' )\ {\ const char \*pTmp1 = p1;\ while( \*p2 != '\\0' && \*pTmp1 != \*p2 ) p2++;\ \ while( \*pTmp1 != '\\0' && \*p2 != '\\0' && \*pTmp1 == \*p2 ){\ pTmp1++;\ p2++;\ }\ \ if( maxLen \< pTmp1 - p1 ){\ maxLen = pTmp1 - p1;\ pMaxIdx = p1;\ }\ }\ \ p1++;\ }\ \ if( pMaxIdx ){\ while( maxLen-- ) \*pOut++ = \*pMaxIdx++;\ }\ \ \*pOut = '\\0';\ \ }\ \ int main(){\ char str1[256] = "abractyeyt";\ char str2[256] = "dgdsaeactyey";\ char result[256];\ GetFLS( result, str1, str2 );\ cout \<\< result \<\< endl;\ }\ /\*\ actyey\ 请按任意键继续. . .\ \*/

15. 给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里.

    \#include "stdafx.h"\ /\*\ 给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里.\ \*/\ inline int RandInt( int low,int high ){\ return rand()%(high-low+1) + low;\ }\ void Shuffle( int \*poker, int N = 54 ){\ srand( (unsigned)time(NULL) ) ;\ \ for( int i = 0; i \< N; i++ )\ poker[i] = i;\ \ for( int i = 0; i \< N; i++ )\ std::swap( poker[i], poker[RandInt(i,N-1)] );\ }\ \ int main(){\ /\*\ 0 \~ 12 代表红桃\ 13 \~ 25 代表黑桃\ 26 \~ 38 代表方块\ 39 \~ 51 代表梅花\ 52 \~ 53 代表大小王\ \*/\ int poker[54];\ Shuffle( poker );\ copy( &poker[0], &poker[54], ostream\_iterator\<int\>(cout, " ") );\ cout \<\< endl;\ }

16. 写一个函数，检查字符串是否是整数，如果是，返回其整数值。

    （或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）

    \#include "stdafx.h"\ /\*\ 写一个函数，检查字符串是否是整数，如果是，返回其整数值。\ （或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）\ \*/\ long Str2Long( const char \*szStr, int len ){\ if( len \> 2 )\ return Str2Long( szStr, len - 1 )\*10 + (szStr[0] == '-' ? -(int)(unsigned char)szStr[len-1] + '0' : (int)(unsigned char)szStr[len-1] - '0');\ else\ return szStr[0] == '-' ? -(int)(unsigned char)szStr[1] + '0' : (szStr[0] == '+' ? (int)(unsigned char)szStr[1] - '0' : (((int)(unsigned char)szStr[0] - '0')\*10 + (int)(unsigned char)szStr[1] - '0'));\ }\ \ int main(){\ char szStr[256] = "-1245";\ cout \<\< Str2Long( szStr, 5 ) \<\< endl;\ }

17. 求整数随机数构成的数组中找到长度>=3的最长的等差数列

    输出等差数列由小到大**: **

    如果没有符合条件的就输出[0,0]

    格式：

    输入[1,3,0,5,-1,6]

    输出[-1,1,3,5]

    要求时间复杂度，空间复杂度尽量小.

    \#include "stdafx.h"\ /\*\ 求整数随机数构成的数组中找到长度\>=3的最长的等差数列\ 输出等差数列由小到大: \ 如果没有符合条件的就输出[0,0]\ 格式：\ 输入[1,3,0,5,-1,6]\ 输出[-1,1,3,5]\ 要求时间复杂度，空间复杂度尽量小.\ \*/\ const int gc\_iSize = 6;\ int arr[gc\_iSize] = {1,3,0,5,-1,6};\ \ // Get longest Arithmetic Progression.\ void GetLAP(){\ sort( &arr[0], &arr[gc\_iSize] );\ \ int len = arr[gc\_iSize-1] - arr[0];\ int \*cntPro = new int[len];\ memset( cntPro, 0, sizeof(int)\*len );\ \ int \*ai = new int[len];\ for( int i = 0; i \< gc\_iSize; i++ )\ for( int j = i + 1; j \< gc\_iSize; j++ )\ {\ int d = arr[j] - arr[i];\ if( cntPro[d] == 0 ){\ ai[d] = arr[j];\ cntPro[d]++;\ }\ else{\ if( d == arr[i] - ai[d] )\ cntPro[d]++;\ }\ }\ \ int idxMax = 0;\ for( int i = 1; i \< len; i++ )\ if( cntPro[idxMax] \< cntPro[i] ){\ idxMax = i;\ }\ \ int cnt = cntPro[idxMax];\ for( int i = 0; i \< gc\_iSize; i++ )\ for( int j = i + 1; j \< gc\_iSize; j++ )\ {\ if( idxMax == arr[j] - arr[i] ){\ if( cnt-- == idxMax )\ cout \<\< arr[i] \<\< " ";\ cout \<\< arr[j] \<\< " ";\ }\ }\ cout \<\< endl;\ \ delete []cntPro;\ delete []ai;\ }\ int main(){\ GetLAP();\ }

18. 输入一个字符串，输出该字符串中对称的子字符串的最大长度。

    比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

    \#include "stdafx.h"\ /\*\ 输入一个字符串，输出该字符串中对称的子字符串的最大长度。\ 比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。\ \*/\ // Get longest symmetry substring.\ void GetLSS( char \*pOut, const char \*str ){\ assert( pOut != NULL && str != NULL );\ \ const char \*p = str;\ \ const char \*maxP = NULL;\ int maxNum = numeric\_limits\<int\>::min();\ if( p[0] == p[1] ){\ maxNum = 2;\ maxP = p;\ }\ p++;\ while( \*p != '\\0' && \*(p+1) != '\\0' )\ {\ int idx = 1;\ while( (p-idx) \>= str && \*(p+idx) != '\\0' && \*(p-idx) == \*(p+idx) ){\ if( maxNum \< 2\*idx+1 ){ maxNum = 2\*idx+1; maxP = p-idx; }\ idx++;\ }\ \ idx = 1;\ while( (p-idx+1) \>= str && \*(p+idx) != '\\0' && \*(p-idx+1) == \*(p+idx) ){\ if( maxNum \< 2\*idx ){ maxNum = 2\*idx; maxP = p-idx+1; }\ idx++;\ }\ p++;\ }\ \ cout \<\< maxNum \<\< endl;\ \ for( int i = 0; i \< maxNum; i++ )\ \*(pOut + i) = \*(maxP + i);\ \*(pOut + maxNum) = '\\0';\ }\ int main(){\ char szStr[256] = "google";\ char pOut[256];\ GetLSS( pOut, szStr );\ \ cout \<\< pOut \<\< endl;\ }

19. 求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）.

    \#include "stdafx.h"\ /\*\ 求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”.\ \*/\ void GetMCID( char \*pOut, const char \*szStr ){\ assert( pOut != NULL && szStr != NULL );\ \ int nCnt = 0;\ int nMaxCnt = 0;\ const char \*pRecord = NULL;\ const char \*p = szStr;\ while( \*p != '\\0' )\ {\ int c = (int)(unsigned char)\*p;\ nCnt = 0;\ if( isdigit(c) )\ {\ nCnt++;\ if( nMaxCnt \< nCnt ){ pRecord = p; nMaxCnt = nCnt; }\ p++;\ while( \*p != '\\0' && isdigit(c) ){\ if( (int)(unsigned char)\*p != c + 1 )\ break;\ \ nCnt++;\ if( nMaxCnt \< nCnt ){ pRecord = p; nMaxCnt = nCnt; }\ c = (int)(unsigned char)\*p;\ p++;\ }\ }\ p++;\ }\ \ \*(pOut + nMaxCnt) = '\\0';\ while( --nMaxCnt \>= 0 ){\ \*(pOut + nMaxCnt) = \*pRecord--;\ }\ \ }\ \ int main(){\ char szStr[256] = "ads3sl456789DF3456ld345AA";\ char szOut[256];\ GetMCID( szOut, szStr );\ \ cout \<\< szOut \<\< endl;\ }

20. 一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。

    \#include "stdafx.h"\ /\*\ 一串首尾相连的珠子(m个)，有N种颜色(N\<=10)，\ 设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。\ 并分析时间复杂度与空间复杂度。\ \*/\ int num[10];\ void GetShortestStrContainN( const string &str, string &shortestStr ){\ int iStart = 0, iEnd = 0;\ int iDone = 0x0;\ int iShortestLen = str.length();\ int iLen = str.length();\ int iRecordStart = 0;\ \ // First, stat. the the string with N colors.\ while( iDone != 0x3ff ){\ iDone |= 0x1 \<\< (str[iEnd] - '0');\ num[str[iEnd] - '0']++;\ iEnd++;\ }\ iEnd--;\ \ while( iStart \< iLen )\ {\ int iCurLen;\ if( iEnd \> iStart )\ iCurLen = iEnd - iStart + 1;\ else\ iCurLen = iEnd + iLen - iStart;\ \ if( iShortestLen \> iCurLen){\ iShortestLen = iCurLen;\ iRecordStart = iStart;\ }\ \ while( iStart \< iLen && num[str[iStart] - '0'] \<= 1 ){\ iEnd = (iEnd + 1)%iLen;\ if( iEnd == iStart )\ iStart++;\ else\ num[str[iEnd]-'0']++;\ }\ num[str[iStart]-'0']--;\ iStart++;\ }\ \ cout \<\< "start:" \<\< iRecordStart \<\< ", len:" \<\< iShortestLen \<\< endl;\ if( iLen - iRecordStart \< iShortestLen ){\ shortestStr = str.substr( iRecordStart );\ shortestStr += str.substr( 0, iShortestLen - iLen + iRecordStart );\ }\ else\ shortestStr.assign( str, iRecordStart, iShortestLen );\ }\ \ int main(){\ string str;\ string sMain;\ cin \>\> sMain;\ GetShortestStrContainN( sMain, str );\ cout \<\< str \<\< endl; \ }\ /\*\ 0134521065768921201221411\ start:2, len:12\ 345210657689\ 请按任意键继续. . .\ \ 6576892120122141101345210\ start:19, len:11\ 34521065768\ 请按任意键继续. . .\ \*/

21. 一个100米长的部队行军，一个传令兵从队伍尾到队伍头，然后再从队伍头返回队伍尾，这时队伍正好走了100米，整个过程队伍和传令兵的速度不变，那么传令兵走了多少米？

    设士兵速度x，队伍y

    [100/(x-y)+100/(x+y)]*y=100

    解得

    x=（1+根号2）y

    路程与速度成正比（时间相同）

    士兵路程为100（1+根号2）

    就是241.4米左右。

22. 两个圆相交，交点是A1，A2。现在过A1点做一直线与两个圆分别相交另外一点B1，B2。

    B1B2可以绕着A1点旋转。问在什么情况下，B1B2最长.
    当A1A2⊥B1B2时B1B2最长

    设弦A1B1、A1B2所在圆分别为⊙O1、⊙O2，取A1B1、A1B2的中点C、D，连结O1C、O2D

    则B1B2＝A1B1＋A1B2＝2A1C＋2A1D＝2CD

    当A1A2与B1B2不垂直时，四边形O1O2DC是直角梯形，定有O1O2＞CD

    此时B1B2＝2CD＜2O1O2

    当A1A2⊥B1B2时，四边形O1O2DC是矩形，定有O1O2＝CD

    此时B1B2＝2CD＝2O1O2为最大.

23. 用测量器和50尺** **如何测量河对岸的巨石高度？\ \ 通过测量h和d求出θ角,然后沿河岸走一定距离\

    
    成θ角的时候X即为所求.</span>

24. 求Fibonacci数列中第k个与前面所有数互质的数（除前面两个数 1，1 ）。