• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 297,  comments - 15,  trackbacks - 0
            from:
            http://blog.csdn.net/zhsenl/article/details/7515279 



            1、將一整數(shù)逆序后放入一數(shù)組中(要求遞歸實(shí)現(xiàn))
            void convert(int *result, int n) {
             if(n>=10)
              convert(result+1, n/10);
             *result = n%10; 
            }
            int main(int argc, char* argv[]) {
             int n = 123456789, result[20]={};
             convert(result, n);
             printf("%d:", n);
             for(int i=0; i<9; i++)
              printf("%d", result);
            }

            2、求高于平均分的學(xué)生學(xué)號(hào)及成績(jī)(學(xué)號(hào)和成績(jī)?nèi)斯ぽ斎耄?br style="word-wrap: break-word; " />double find(int total, int n) {
             int number, score,  average;
             scanf("%d", &number);
             if(number != 0) {
              scanf("%d", &score);
              average = find(total+score, n+1);
              if(score >= average)
               printf("%d:%d\n", number, score);
              return average;
             } else {
              printf("Average=%d\n", total/n);
              return total/n;
             }
            }
            int main(int argc, char* argv[]) {
             find(0, 0);
            }

            3、遞歸實(shí)現(xiàn)回文判斷(如:abcdedbca就是回文,判斷一個(gè)面試者對(duì)遞歸理解的簡(jiǎn)單程序)
            int find(char *str, int n) {
             if(n<=1) return 1;
             else if(str[0]==str[n-1]) return find(str+1, n-2);
             else  return 0;
            }

            int main(int argc, char* argv[]) {
             char *str = "abcdedcba";
             printf("%s: %s\n", str, find(str, strlen(str)) ? "Yes" : "No");
            }

            4、組合問(wèn)題(從M個(gè)不同字符中任取N個(gè)字符的所有組合)
            void find(char *source, char *result, int n) {
             if(n==1) {
              while(*source)
                 printf("%s%c\n", result, *source++);
             } else {
              int i, j;
              for(i=0; source != 0; i++);
              for(j=0; result[j] != 0; j++);
              for(; i>=n; i--) {
               result[j] = *source++;
               result[j+1] = '\0';
               find(source, result, n-1);
              }
             }
            }

            int main(int argc, char* argv[]) {
             int const n = 3;
             char *source = "ABCDE", result[n+1] = {0};
             if(n>0 && strlen(source)>0 && n<=strlen(source))
              find(source, result, 3);
            }

            5、分解成質(zhì)因數(shù)(如435234=251*17*17*3*2,據(jù)說(shuō)是華為筆試題)
            void prim(int m, int n) {
             if(m>n) {
              while(m%n != 0) n++;
              m /= n;
              prim(m, n);
              printf("%d*", n);
             }
            }
            int main(int argc, char* argv[]) {
             int n = 435234;
             printf("%d=", n);
             prim(n, 2);
            }
            6、尋找迷宮的一條出路,o:通路; X:障礙。(大家經(jīng)常談到的一個(gè)小算法題)
            #define MAX_SIZE  8
            int H[4] = {0, 1, 0, -1}; 
            int V[4] = {-1, 0, 1, 0};           
            char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},
                                             {'o','o','o','o','o','X','X','X'},
                                             {'X','o','X','X','o','o','o','X'},
                                         {'X','o','X','X','o','X','X','o'},
                                     {'X','o','X','X','X','X','X','X'},
            {'X','o','X','X','o','o','o','X'},
                     {'X','o','o','o','o','X','o','o'},
                                             {'X','X','X','X','X','X','X','X'}};
            void FindPath(int X, int Y) {
                if(X == MAX_SIZE || Y == MAX_SIZE) {
                   for(int i = 0; i < MAX_SIZE; i++)
            for(int j = 0; j < MAX_SIZE; j++)
                              printf("%c%c", Maze[j], j < MAX_SIZE-1 ? ' ' : '\n');
            }else for(int k = 0; k < 4; k++) 
            if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y]) {
                               Maze[X][Y] = ' ';
                               FindPath(X+V[k], Y+H[k]);
                               Maze[X][Y] ='o'; 
            }
            }
            int main(int argc, char* argv[]) {
                FindPath(1,0);
            }

            7、隨機(jī)分配座位,共50個(gè)學(xué)生,使學(xué)號(hào)相鄰的同學(xué)座位不能相鄰(早些時(shí)候用C#寫(xiě)的,沒(méi)有用C改寫(xiě))。
            static void Main(string[] args)
            {
             int Tmp = 0, Count = 50;   
             int[] Seats = new int[Count];   
             bool[] Students = new bool[Count];
             System.Random RandStudent=new System.Random();
             Students[Seats[0]=RandStudent.Next(0,Count)]=true;
             for(int i = 1; i < Count; ) {
                 Tmp=(int)RandStudent.Next(0,Count);
                 if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1) && (Seats[i-1] - Tmp) != -1) {
               Seats[i++] = Tmp;
            Students[Tmp] = true;
              }
             }
             foreach(int Student in Seats)
                 System.Console.Write(Student + " ");
             System.Console.Read();
            }

            8、求網(wǎng)格中的黑點(diǎn)分布。現(xiàn)有6*7的網(wǎng)格,在某些格子中有黑點(diǎn),已知各行與各列中有黑點(diǎn)的點(diǎn)數(shù)之和,請(qǐng)?jiān)谶@張網(wǎng)格中畫(huà)出黑點(diǎn)的位置。(這是一網(wǎng)友提出的題目,說(shuō)是他筆試時(shí)遇到算法題)
            #define ROWS 6
            #define COLS 7
            int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0};           // 各行黑點(diǎn)數(shù)和的情況
            int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1};        // 各列黑點(diǎn)數(shù)和的情況
            int iCount, iFound;
            int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];

            int Set(int iRowNo) {
            if(iRowNo == ROWS) { 
                    for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++) 
                       if(iColNo == COLS-1) {
                           printf("\nNo.%d:\n", ++iCount); 
                           for(int i=0; i < ROWS; i++)
                              for(int j=0; j < COLS; j++)
                                  printf("%d%c", Grid[j], (j+1) % COLS ? ' ' : '\n');
                           iFound = 1; // iFound = 1,有解
                       }
                } else {
                    for(int iColNo=0; iColNo < COLS; iColNo++) {
                        if(iPointsR[iRowNo] == 0) { 
                            Set(iRowNo + 1);
               } else if(Grid[iRowNo][iColNo]==0) { 
            Grid[iRowNo][iColNo] = 1; 
            iSumR[iRowNo]++; iSumC[iColNo]++;                                  if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo])
                                 Set(iRowNo);
            else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
                                 Set(iRowNo + 1);
                            Grid[iRowNo][iColNo] = 0;
                            iSumR[iRowNo]--; 
            iSumC[iColNo]--;
                        }
                    }
                }
            return iFound;     // 用于判斷是否有解
            }
            int main(int argc, char* argv[]) {
                if(!Set(0))
                    printf("Failure!"); 
            }

            9、有4種面值的郵票很多枚,這4種郵票面值分別1, 4, 12, 21,現(xiàn)從多張中最多任取5張進(jìn)行組合,求取出這些郵票的最大連續(xù)組合值。(據(jù)說(shuō)是華為2003年校園招聘筆試題)
            #define N 5
            #define M 5
            int k, Found, Flag[N];
            int Stamp[M] = {0, 1, 4, 12, 21};

            // 在剩余張數(shù)n中組合出面值和Value
            int Combine(int n, int Value) {
             if(n >= 0 && Value == 0) {
              Found = 1;
              int Sum = 0;
              for(int i=0; i<N && Flag != 0; i++) {
               Sum += Stamp[Flag];
               printf("%d ", Stamp[Flag]);
              }
              printf("\tSum=%d\n\n", Sum);
             }else for(int i=1; i<M && !Found && n>0; i++)
              if(Value-Stamp >= 0) {
               Flag[k++] = i;
               Combine(n-1, Value-Stamp);
               Flag[--k] = 0;
              }
             return Found;
            }

            int main(int argc, char* argv[]) {
             for(int i=1; Combine(N, i); i++, Found=0);
            }

            10、大整數(shù)數(shù)相乘的問(wèn)題。(這是2002年在一考研班上遇到的算法題)
            void Multiple(char A[], char B[], char C[]) {
                int TMP, In=0, LenA=-1, LenB=-1;
                while(A[++LenA] != '\0');
                while(B[++LenB] != '\0');
                int Index, Start = LenA + LenB - 1;
                for(int i=LenB-1; i>=0; i--) {
                    Index = Start--;
                    if(B != '0') {
                        for(int In=0, j=LenA-1; j>=0; j--) {
                            TMP = (C[Index]-'0') + (A[j]-'0') * (B - '0') + In;
                            C[Index--] = TMP % 10 + '0';
                            In = TMP / 10;
                        }
                        C[Index] = In + '0';
                    }
                }
            }

            int main(int argc, char* argv[]) {
                char A[] = "21839244444444448880088888889";
                char B[] = "38888888888899999999999999988";
            char C[sizeof(A) + sizeof(B) - 1];

                for(int k=0; k<sizeof(C); k++)
                    C[k] = '0';
                C[sizeof(C)-1] = '\0';

                Multiple(A, B, C);
                for(int i=0; C != '\0'; i++)
                    printf("%c", C);
            }

            11、求最大連續(xù)遞增數(shù)字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
            int GetSubString(char *strSource, char *strResult) {
                int iTmp=0, iHead=0, iMax=0;
                for(int Index=0, iLen=0; strSource[Index]; Index++) {
                    if(strSource[Index] >= '0' && strSource[Index] <= '9' && 
            strSource[Index-1] > '0' && strSource[Index] == strSource[Index-1]+1) {
                        iLen++;                       // 連續(xù)數(shù)字的長(zhǎng)度增1 
                    } else {                          // 出現(xiàn)字符或不連續(xù)數(shù)字
                        if(iLen > iMax) {
                        iMax = iLen;  iHead = iTmp; 
                        }        
                    // 該字符是數(shù)字,但數(shù)字不連續(xù)
                        if(strSource[Index] >= '0' && strSource[Index] <= '9') { 
                            iTmp = Index; 
            iLen = 1; 
                        }
                    }    
                }
                for(iTmp=0 ; iTmp < iMax; iTmp++) // 將原字符串中最長(zhǎng)的連續(xù)數(shù)字串賦值給結(jié)果串
                    strResult[iTmp] = strSource[iHead++];
                strResult[iTmp]='\0';
                return iMax;     // 返回連續(xù)數(shù)字的最大長(zhǎng)度
            }
            int main(int argc, char* argv[]) {
                char strSource[]="ads3sl456789DF3456ld345AA", char strResult[sizeof(strSource)];
            printf("Len=%d, strResult=%s \nstrSource=%s\n", 
            GetSubString(strSource, strResult), strResult, strSource);
            }

            12、四個(gè)工人,四個(gè)任務(wù),每個(gè)人做不同的任務(wù)需要的時(shí)間不同,求任務(wù)分配的最優(yōu)方案。(2005年5月29日全國(guó)計(jì)算機(jī)軟件資格水平考試——軟件設(shè)計(jì)師的算法題)。
            #include "stdafx.h"
            #define N 4
            int Cost[N][N] = { {2, 12, 5, 32},  // 行號(hào):任務(wù)序號(hào),列號(hào):工人序號(hào)
                                {8, 15, 7, 11},  // 每行元素值表示這個(gè)任務(wù)由不同工人完成所需要的時(shí)間
                                {24, 18, 9, 6},
                                {21, 1, 8, 28}};
            int MinCost=1000;
            int Task[N], TempTask[N], Worker[N];
            void Assign(int k, int cost) {
             if(k == N) {
              MinCost = cost; 
              for(int i=0; i<N; i++)
               TempTask = Task;
             } else {
              for(int i=0; i<N; i++) { 
               if(Worker==0 && cost+Cost[k] < MinCost) { // 為提高效率而進(jìn)行剪枝
                Worker = 1; Task[k] = i; 
                Assign(k+1, cost+Cost[k]); 
                Worker = 0; Task[k] = 0;
               }
              }
             }
            }
            int main(int argc, char* argv[]) {
             Assign(0, 0);
             printf("最佳方案總費(fèi)用=%d\n", MinCost);
             for(int i=0; i<N; i++)  /* 輸出最佳方案 */
              printf("\t任務(wù)%d由工人%d來(lái)做:%d\n", i, TempTask, Cost[TempTask]);
            }
            13、八皇后問(wèn)題,輸出了所有情況,不過(guò)有些結(jié)果只是旋轉(zhuǎn)了90度而已。(回溯算法的典型例題,是數(shù)據(jù)結(jié)構(gòu)書(shū)上算法的具體實(shí)現(xiàn),大家都親自動(dòng)手寫(xiě)過(guò)這個(gè)程序嗎?)
            #define N 8
            int Board[N][N];
            int Valid(int i, int j) {  // 判斷下棋位置是否有效
             int k = 1;
             for(k=1; i>=k && j>=k;k++)
              if(Board[i-k][j-k]) return 0;
             for(k=1; i>=k;k++)
              if(Board[i-k][j])  return 0;
             for(k=1; i>=k && j+k<N;k++)
              if(Board[i-k][j+k]) return 0;
             return 1;
            }

            void Trial(int i, int n) {  // 尋找合適下棋位置
             if(i == n) {
              for(int k=0; k<n; k++) {
               for(int m=0; m<n; m++)
                printf("%d ", Board[k][m]);
               printf("\n");
              }
              printf("\n");
             } else {
              for(int j=0; j<n; j++) {
               Board[j] = 1;
               if(Valid(i,j))
                Trial(i+1, n);
               Board[j] = 0;
              }
             }
            }

            int main(int argc, char* argv[]) {
             Trial(0, N);
            }

            14、實(shí)現(xiàn)strstr功能,即在父串中尋找子串首次出現(xiàn)的位置。(筆試中常讓面試者實(shí)現(xiàn)標(biāo)準(zhǔn)庫(kù)中的一些函數(shù))
            char * strstring(char *ParentString, char *SubString) {
             char *pSubString, *pPareString;
             for(char *pTmp=ParentString; *pTmp; pTmp++) {
              pSubString = SubString;
              pPareString = pTmp; 
              while(*pSubString == *pPareString && *pSubString != '\0') {
               pSubString++;
               pPareString++;
              }
              if(*pSubString == '\0')  return pTmp;
             }
             return NULL;
            }

            int main(int argc, char* argv[]) {
             char *ParentString = "happy birthday to you!";
             char *SubString = "birthday";
             printf("%s",strstring(ParentString, SubString));
            }

            15、現(xiàn)在小明一家過(guò)一座橋,過(guò)橋的時(shí)候是黑夜,所以必須有燈。現(xiàn)在小明過(guò)橋要1分,小明的弟弟要3分,小明的爸爸要6分,小明的媽媽要8分,小明的爺爺要12分。每次此橋最多可過(guò)兩人,而過(guò)橋的速度依過(guò)橋最慢者而定,而且燈在點(diǎn)燃后30分就會(huì)熄滅。問(wèn)小明一家如何過(guò)橋時(shí)間最短?(原本是個(gè)小小智力題,據(jù)說(shuō)是外企的面試題,在這里用程序來(lái)求解)
            #include "stdafx.h"
            #define N    5
            #define SIZE 64

            // 將人員編號(hào):小明-0,弟弟-1,爸爸-2,媽媽-3,爺爺-4
            // 每個(gè)人的當(dāng)前位置:0--在橋左邊, 1--在橋右邊
            int Position[N];    
            // 過(guò)橋臨時(shí)方案的數(shù)組下標(biāo); 臨時(shí)方案; 最小時(shí)間方案; 
            int Index, TmpScheme[SIZE], Scheme[SIZE];   
            // 最小過(guò)橋時(shí)間總和,初始值100;每個(gè)人過(guò)橋所需要的時(shí)間
            int MinTime=100, Time[N]={1, 3, 6, 8, 12};  
            // 尋找最佳過(guò)橋方案。Remnant:未過(guò)橋人數(shù); CurTime:當(dāng)前已用時(shí)間; 
            // Direction:過(guò)橋方向,1--向右,0--向左
            void Find(int Remnant, int CurTime, int Direction) {
                if(Remnant == 0) {                               // 所有人已經(jīng)過(guò)橋,更新最少時(shí)間及方案
                    MinTime=CurTime;
                    for(int i=0; i<SIZE && TmpScheme>=0; i++)
                        Scheme = TmpScheme;
                } else if(Direction == 1) {                        // 過(guò)橋方向向右,從橋左側(cè)選出兩人過(guò)橋
                    for(int i=0; i<N; i++)                    
                        if(Position == 0 && CurTime + Time < MinTime) { 
                            TmpScheme[Index++] = i;
                            Position = 1;
                            for(int j=0; j<N; j++) {
                                int TmpMax = (Time > Time[j] ? Time : Time[j]);
                                if(Position[j] == 0 && CurTime + TmpMax < MinTime) {
                                    TmpScheme[Index++] = j;    
                                    Position[j] = 1;        
                                    Find(Remnant - 2, CurTime + TmpMax, !Direction); 
                                    Position[j] = 0;        
                                    TmpScheme[--Index] = -1;
                                }
                            }
                            Position = 0;
                            TmpScheme[--Index] = -1;
                        }
                } else {        // 過(guò)橋方向向左,從橋右側(cè)選出一個(gè)人回來(lái)送燈
                    for(int j=0; j<N; j++) {
                        if(Position[j] == 1 && CurTime+Time[j] < MinTime) {
                            TmpScheme[Index++] = j;
                            Position[j] = 0;
                            Find(Remnant+1, CurTime+Time[j], !Direction);
                            Position[j] = 1;
                            TmpScheme[--Index] = -1;
                        }
                    }
                }
            }
            int main(int argc, char* argv[]) {
                for(int i=0; i<SIZE; i++)   // 初始方案內(nèi)容為負(fù)值,避免和人員標(biāo)號(hào)沖突
                    Scheme = TmpScheme = -1;

            Find(N, 0, 1);        // 查找最佳方案

                printf("MinTime=%d:", MinTime); // 輸出最佳方案
                for(int i=0; i<SIZE && Scheme>=0; i+=3)
                    printf("  %d-%d  %d", Scheme, Scheme[i+1], Scheme[i+2]);
                printf("\b\b  ");
            }

            16、2005年11月金山筆試題。編碼完成下面的處理函數(shù)。函數(shù)將字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改變非'*'字符的先后順序,函數(shù)返回串中字符'*'的數(shù)量。如原始串為:ab**cd**e*12,處理后為*****abcde12,函數(shù)并返回值為5。(要求使用盡量少的時(shí)間和輔助空間)
            int change(char *str) {     /* 這個(gè)算法并不高效,從后向前搜索效率要高些 */
             int count = 0;     /* 記錄串中字符'*'的個(gè)數(shù) */
             for(int i=0, j=0; str; i++) {  /* 重串首開(kāi)始遍歷 */
              if(str=='*') {    /* 遇到字符'*' */
               for(j=i-1; str[j]!='*'&&j>=0; j--) /* 采用類(lèi)似插入排序的思想,將*前面 */
                str[j+1]=str[j];     /* 的非*字符逐個(gè)后移,直到遇到*字符 */
               str[j+1] = '*';
               count++;
              }
             }
             return count;
            }
            int main(int argc, char* argv[]) {
             char str[] = "ab**cd**e*12";
             printf("str1=%s\n", str);
             printf("str2=%s, count=%d", str, change(str));
            }
            // 終于得到一個(gè)比較高效的算法,一個(gè)網(wǎng)友提供,估計(jì)應(yīng)該和金山面試官的想法一致。算法如下:
            int change(char *str) {
             int i,j=strlen(str)-1;
             for(i=j; j>=0; j--) {
              if(str!='*') {
               i--;
              } else if(str[j]!='*') {
               str = str[j];
               str[j] = '*';
               i--;
              }
             }
             return i+1;
            }

            17、2005年11月15日華為軟件研發(fā)筆試題。實(shí)現(xiàn)一單鏈表的逆轉(zhuǎn)。
            #include "stdafx.h"
            typedef char eleType;  // 定義鏈表中的數(shù)據(jù)類(lèi)型
            typedef struct listnode  { // 定義單鏈表結(jié)構(gòu)
             eleType data;
             struct listnode *next;
            }node;

            node *create(int n) {  // 創(chuàng)建單鏈表,n為節(jié)點(diǎn)個(gè)數(shù)
             node *p = (node *)malloc(sizeof(node)); 
             node *head = p;  head->data = 'A';
             for(int i='B'; i<'A'+n; i++) {    
              p = (p->next = (node *)malloc(sizeof(node)));
              p->data = i;
              p->next = NULL;  
             }
             return head;
            }

            void print(node *head) { // 按鏈表順序輸出鏈表中元素
             for(; head; head = head->next)
              printf("%c ", head->data); 
             printf("\n");
            }

            node *reverse(node *head, node *pre) { // 逆轉(zhuǎn)單鏈表函數(shù)。這是筆試時(shí)需要寫(xiě)的最主要函數(shù)
             node *p=head->next;
             head->next = pre;
             if(p) return reverse(p, head);
             else  return head;
            }

            int main(int argc, char* argv[]) {
             node *head = create(6);
             print(head);
             head = reverse(head, NULL);
             print(head);
            }

            18、編碼實(shí)現(xiàn)字符串轉(zhuǎn)整型的函數(shù)(實(shí)現(xiàn)函數(shù)atoi的功能),據(jù)說(shuō)是神州數(shù)碼筆試題。如將字符串 ”+123”?123, ”-0123”?-123, “123CS45”?123, “123.45CS”?123, “CS123.45”?0
            #include "stdafx.h"
            int str2int(const char *str) {    // 字符串轉(zhuǎn)整型函數(shù)
             int i=0, sign=1, value = 0;
             if(str==NULL)  return NULL;    // 空串直接返回 NULL
             if(str[0]=='-' || str[0]=='+') {   // 判斷是否存在符號(hào)位
              i = 1;
              sign = (str[0]=='-' ? -1 : 1);
             }
             for(; str>='0' && str<='9'; i++) // 如果是數(shù)字,則繼續(xù)轉(zhuǎn)換
              value = value * 10 + (str - '0');
             return sign * value;
            }

            int main(int argc, char *argv[]) {
             char *str = "-123.45CS67"; 
             int  val  = str2int(str);
             printf("str=%s\tval=%d\n", str, val);
            }

            19、歌德巴赫猜想。任何一個(gè)偶數(shù)都可以分解為兩個(gè)素?cái)?shù)之和。(其實(shí)這是個(gè)C二級(jí)考試的模擬試題)
            #include "stdafx.h"
            #include "math.h"
            int main(int argc, char* argv[]) {
             int Even=78, Prime1, Prime2, Tmp1, Tmp2;
             for(Prime1=3; Prime1<=Even/2; Prime1+=2) {
              for(Tmp1=2,Tmp2=sqrt(float(Prime1)); Tmp1<=Tmp2 && Prime1%Tmp1 != 0; Tmp1++);
              if(Tmp1<=Tmp2) continue;
              Prime2 = Even-Prime1;
              for(Tmp1=2,Tmp2=sqrt(float(Prime2)); Tmp1<=Tmp2 && Prime2%Tmp1 != 0; Tmp1++);
              if(Tmp1<=Tmp2) continue;
              printf("%d=%d+%d\n", Even, Prime1, Prime2);
             }
            }

            20、快速排序(東軟喜歡考類(lèi)似的算法填空題,又如堆排序的算法等)
            #include "stdafx.h"
            #define N 10
            int part(int list[], int low, int high) {  // 一趟排序,返回分割點(diǎn)位置
             int tmp = list[low];
             while(low<high) {
              while(low<high && list[high]>=tmp) --high;
              list[low] = list[high];
              while(low<high && list[low]<=tmp)  ++low;
              list[high] = list[low];
             }
             list[low] = tmp;
             return low;
            }
            void QSort(int list[], int low, int high) { // 應(yīng)用遞歸進(jìn)行快速排序
             if(low<high) {
              int mid = part(list, low, high);
              QSort(list, low, mid-1);
              QSort(list, mid+1, high);
             }
            }
            void show(int list[], int n) {    // 輸出列表中元素
             for(int i=0; i<n; i++)
              printf("%d ", list);
             printf("\n");
            }
            int main(int argc, char* argv[]) {
             int list[N] = {23, 65, 26, 1, 6, 89, 3, 12, 33, 8};
             show(list, N);      // 輸出排序前序列
             QSort(list, 0, N-1);     // 快速排序
             show(list, N);      // 輸出排序后序列
            }

            21、2005年11月23日慧通筆試題:寫(xiě)一函數(shù)判斷某個(gè)整數(shù)是否為回文數(shù),如12321為回文數(shù)。可以用判斷入棧和出棧是否相同來(lái)實(shí)現(xiàn)(略微復(fù)雜些),這里是將整數(shù)逆序后形成另一整數(shù),判斷兩個(gè)整數(shù)是否相等來(lái)實(shí)現(xiàn)的。
            #include "stdafx.h"
            int IsEchoNum(int num) {
             int tmp = 0;
             for(int n = num; n; n/=10)
              tmp = tmp *10 + n%10;
             return tmp==num;
            }

            int main(int argc, char* argv[]) {
             int num = 12321;
             printf("%d  %d\n", num, IsEchoNum(num));
            }

            22、刪除字符串中的數(shù)字并壓縮字符串(神州數(shù)碼以前筆試題),如字符串”abc123de4fg56”處理后變?yōu)?#8221;abcdefg”。注意空間和效率。(下面的算法只需要一次遍歷,不需要開(kāi)辟新空間,時(shí)間復(fù)雜度為O(N))
            #include "stdafx.h"
            void delNum(char *str) {
             int i, j=0;
            // 找到串中第一個(gè)數(shù)字的位子
             for(i=j=0; str && (str<'0' || str>'9'); j=++i);
             
             // 從串中第一個(gè)數(shù)字的位置開(kāi)始,逐個(gè)放入后面的非數(shù)字字符
             for(; str; i++)   
              if(str<'0' || str>'9') 
               str[j++] = str;
             str[j] = '\0';
            }

            int main(int argc, char* argv[]) {
             char str[] = "abc123ef4g4h5";
             printf("%s\n", str);
             delNum(str);
             printf("%s\n", str);
            }

            23、求兩個(gè)串中的第一個(gè)最長(zhǎng)子串(神州數(shù)碼以前試題)。如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。
            #include "stdafx.h"
            char *MaxSubString(char *str1, char *str2) {
             int i, j, k, index, max=0;
             for(i=0; str1; i++)
              for(j=0; str2[j]; j++) {
               for(k=0; str1[i+k]==str2[j+k] && (str2[i+k] || str1[i+k]); k++);
               if(k>max) {  // 出現(xiàn)大于當(dāng)前子串長(zhǎng)度的子串,則替換子串位置和程度
                index = j; max = k;
               }
              }
             char *strResult = (char *)calloc(sizeof(char), max+1);
             for(i=0; i<max; i++)  
              strResult = str2[index++];
             return strResult;
            }

            int main(int argc, char* argv[]) {
             char str1[] = "abractyeyt", str2[] = "dgdsaeactyey";
             char *strResult = MaxSubString(str1, str2);
             printf("str1=%s\nstr2=%s\nMaxSubString=%s\n", str1, str2, strResult);
            }

            24、不開(kāi)辟用于交換數(shù)據(jù)的臨時(shí)空間,如何完成字符串的逆序(在技術(shù)一輪面試中,有些面試官會(huì)這樣問(wèn))
            #include "stdafx.h"
            void change(char *str) {
             for(int i=0,j=strlen(str)-1; i<j; i++, j--){
              str ^= str[j] ^= str ^= str[j];
             }
            }
            int main(int argc, char* argv[]) {
             char str[] = "abcdefg";
             printf("strSource=%s\n", str);
             change(str);
             printf("strResult=%s\n", str);
             return getchar();
            }

            25、刪除串中指定的字符(做此題時(shí),千萬(wàn)不要開(kāi)辟新空間,否則面試官可能認(rèn)為你不適合做嵌入式開(kāi)發(fā))
            #include "stdafx.h"
            void delChar(char *str, char c) {
             int i, j=0;
             for(i=0; str; i++)
              if(str!=c) str[j++]=str;
             str[j] = '\0';
            }

            int main(int argc, char* argv[]) {
             char str[] = "abcdefgh"; // 注意,此處不能寫(xiě)成char *str = "abcdefgh";
             printf("%s\n", str);
             delChar(str, 'c');
             printf("%s\n", str);
            }

            26、判斷單鏈表中是否存在環(huán)(網(wǎng)上說(shuō)的筆試題)
            #include "stdafx.h"
            typedef char eleType;    // 定義鏈表中的數(shù)據(jù)類(lèi)型
            typedef struct listnode  {   // 定義單鏈表結(jié)構(gòu)
             eleType data;
             struct listnode *next;
            }node;

            node *create(int n) {    // 創(chuàng)建單鏈表,n為節(jié)點(diǎn)個(gè)數(shù)
             node *p = (node *)malloc(sizeof(node)); 
             node *head = p;  head->data = 'A';
             for(int i='B'; i<'A'+n; i++) {
              p = (p->next = (node *)malloc(sizeof(node)));
              p->data = i;
              p->next = NULL;
             }
             return head;
            }

            void addCircle(node *head, int n) { // 增加環(huán),將鏈尾指向鏈中第n個(gè)節(jié)點(diǎn)
             node *q, *p = head;
             for(int i=1; p->next; i++) {
              if(i==n) q = p;
              p = p->next;
             }
             p->next = q;
            }

            int isCircle(node *head) {   // 這是筆試時(shí)需要寫(xiě)的最主要函數(shù),其他函數(shù)可以不寫(xiě)
             node *p=head,*q=head; 
             while( p->next && q->next) { 
              p = p->next;
              if (NULL == (q=q->next->next)) return 0;
              if (p == q) return 1;
             }
             return 0; 
            }

            int main(int argc, char* argv[]) {
             node *head = create(12);
             addCircle(head, 8);   // 注釋掉此行,連表就沒(méi)有環(huán)了
             printf("%d\n", isCircle(head));
            }

            posted on 2012-06-03 12:02 chatler 閱讀(574) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): interview
            <2025年8月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(10)

            隨筆分類(lèi)(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

            • cloudward
            • 感覺(jué)這個(gè)博客還是不錯(cuò),雖然做的東西和我不大相關(guān),覺(jué)得看看還是有好處的

            network

            OSS

            • Google Android
            • Android is a software stack for mobile devices that includes an operating system, middleware and key applications. This early look at the Android SDK provides the tools and APIs necessary to begin developing applications on the Android platform using the Java programming language.
            • os161 file list

            overall

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            国产V亚洲V天堂无码久久久| 99久久国产亚洲高清观看2024| 久久精品www| 精品久久久噜噜噜久久久| 少妇高潮惨叫久久久久久| 精品多毛少妇人妻AV免费久久 | 成人免费网站久久久| 综合网日日天干夜夜久久| 2020国产成人久久精品| 99久久免费国产精品特黄| 国产成人精品久久| 亚洲午夜久久久久久噜噜噜| MM131亚洲国产美女久久| 99久久人妻无码精品系列蜜桃| 韩国三级大全久久网站| 激情五月综合综合久久69| 欧美久久久久久午夜精品| 精品久久久久久久国产潘金莲 | 久久涩综合| 久久久精品人妻一区二区三区蜜桃| 一本色道久久88—综合亚洲精品| 国内精品久久久人妻中文字幕| 狠狠色噜噜狠狠狠狠狠色综合久久| 国内精品久久久久久久久| 亚洲午夜无码AV毛片久久| 精品一二三区久久aaa片| 久久国产精品一区二区| 久久性精品| 国内精品九九久久久精品| 久久毛片免费看一区二区三区| 国产激情久久久久久熟女老人| 国产精品99久久精品| 一本一本久久a久久精品综合麻豆| 亚洲精品无码久久久影院相关影片| 久久青青草原精品影院| 亚洲国产成人精品女人久久久 | 久久国产成人午夜AV影院| 久久久久亚洲Av无码专| 久久久久亚洲av成人无码电影| 国产精品免费福利久久| 久久久网中文字幕|