幾道ｃ/ｃ++筆試題目

學無涯_思無涯 2013-09-12

展開全文

1、給一個數組，元素都是整數（有正數也有負數），尋找連續(xù)的元素相加之和為最大的序列。

如：1、-2、3、5、-4、6 連續(xù)序列3、5、-4、6的和最大。
如元素全為負數，則最大的和為0，即一個也沒有選。
/*
array[]     輸入數組
n           數組元素個數
            返回最大序列和
*/
int find_max_sum(int array[] , int n)

[cpp]view plaincopy
int find_max_sum(int array[] , int n)    
{    
    int i , max , sum;    
    sum = max = array[0];    
    for(i = 1 ; i < n ; ++i)    
    {    
        if(sum < 0)    
            sum = array[i];    
        else    
            sum += array[i];    
        if(sum > max)    
            max = sum;    
    }    
    if(max < 0)    
        max = 0;    
    return max;    
}    

2、給定一個字符串，求出其最長重復子串

例如：abcdabcd
最長重復子串是 abcd，最長重復子串可以重疊
例如：abcdabcda，這時最長重復子串是 abcda，中間的 a 是被重疊的。

直觀的解法是，首先檢測長度為 n - 1 的字符串情況，如果不存在重復則檢測 n - 2, 一直遞減下去，直到 1 。
這種方法的時間復雜度是 O(N * N * N)，其中包括三部分，長度緯度、根據長度檢測的字符串數目、字符串檢測。

改進的方法是利用后綴數組
后綴數組是一種數據結構，對一個字符串生成相應的后綴數組后，然后再排序，排完序依次檢測相鄰的兩個字符串的開頭公共部分。
這樣的時間復雜度為：生成后綴數組 O(N)，排序 O(NlogN*N) 最后面的 N 是因為字符串比較也是 O(N)
依次檢測相鄰的兩個字符串 O(N * N)，總的時間復雜度是 O(N^2*logN)，優(yōu)于第一種方法的 O(N^3)

[cpp]view plaincopy
#include <iostream>    
using namespace std;    
    
#define MAXCHAR 5000 //最長處理5000個字符    
    
char c[MAXCHAR], *a[MAXCHAR];    
    
int comlen( char *p, char *q )    
{    
    int i = 0;    
    while( *p && (*p++ == *q++) )    
        ++i;    
    return i;    
}    
int pstrcmp( const void *p1, const void *p2 )    
{    
    return strcmp( *(char* const *)p1, *(char* const*)p2 );    
}    
int main(void)    
{    
    char ch;    
    int  n=0;    
    int  i, temp;    
    int  maxlen=0, maxi=0;    
    printf("Please input your string:\n");    
    n = 0;    
    while( (ch=getchar())!='\n' )    
    {    
        a[n] = &c[n];    
        c[n++] = ch;    
    }    
    c[n]='\0';     // 將數組c中的最后一個元素設為空字符，以終止所有字符串    
    
    qsort( a, n, sizeof(char*), pstrcmp );    
    for(i = 0 ; i < n-1 ; ++i )    
    {    
        temp=comlen( a[i], a[i+1] );    
        if( temp>maxlen )    
        {    
            maxlen=temp;    
            maxi=i;    
        }    
    }    
    printf("%.*s\n",maxlen, a[maxi]);    
    return 0;    
}    

3、字符轉換成數字，數字轉換成數組

[cpp]view plaincopy
//字符轉換成數字，數字轉換成字符  
#include<stdio.h>  
void main()  
{  
    int i=0,j=0,x=0,num=0,n=1234;  
    char a[]={'1','2','3','4','\0'};  
    while(a[i])  
    {  
        num=num*10+(a[i]-'0');//字符串轉換為數字  
        i++;  
    }  
    printf("%d\n",num);  
    char temp[5],str[5];  
    while(n)  
    {  
        temp[j]=n%10+'0';//數字轉換為字符串  
        j++;  
        n/=10;  
    }  
    temp[j]=0;  
    j=j-1;  
    while(j>=0)  
    {  
        str[x]=temp[j];//將上面的逆序轉為正序  
        j--;  
        x++;  
    }  
    str[x]=0;  
    printf("%s\n",str);  
}  

4、求兩個數組的交集

問題：給你兩個排序的數組，求兩個數組的交集。
比如： A = 1 3 4 5 7， B = 2 3 5 8 9，那么交集就是 3 5.
思路：
1. 每一次從B數組中取一值，然后在A數組里逐個比較，如果有相等的，則保存。該算法復雜度為 O(MN). M, N 分別為數組 A B 的長度。
2. 因為A B 都排過序，所以，每一次從B數組取值后，可以利用二分查找看是否在數組A里有B所對應的值，這樣復雜度變成了O(N lg M)。這里，如果N 比 M 大，可以從A中取值，然后在B中判斷是否有A的值，這樣，復雜度為 O(M lg N)。
3. 利用hashtable. 先把A中的值存在hashtable里，然后對于每一個B中的值，判斷是否在A中存在，因為hashtable查找的平均復雜度為 O(1), 所以，整個算法復雜度為O(N), 但是，這里的空間復雜度為 O(M) 。但是，這種方法適合數組比較小的情況。因為如果A數組比較大，hashtable會出現collision的情況，這樣，查找的平均復雜度就不再是 O(1)。

本文方法：
因為數組A B均排過序，所以，我們可以用兩個“指針”分別指向兩個數組的頭部，如果其中一個比另一個小，移動小的那個數組的指針；如果相等，那么那個值是在交集里，保存該值，這時，同時移動兩個數組的指針。一直這樣操作下去，直到有一個指針已經超過數組范圍。

[java]view plaincopy
public LinkedList<Integer> intersection(int[] A, int[] B) {    
    if (A == null || B == null || A.length == 0 || B.length == 0) return null;    
    LinkedList<Integer> list = new LinkedList<Integer>();    
    int pointerA = 0;    
    int pointerB = 0;    
    while (pointerA < A.length && pointerB < B.length) {    
        if (A[pointerA] < B[pointerB]) pointerA++;    
        else if (A[pointerA] > B[pointerB]) pointerB++;    
        else {    
            list.add(A[pointerA]);    
            pointerA++;    
            pointerB++;    
        }    
    }    
    return list;     
}  

通過上面的算法可以得知，該算法復雜度為O(N + M).

5.0-9四則運算

[cpp]view plaincopy
#include <stdio.h>  
#include <string.h>  
#include <assert.h>  
int cal(int nNum1, char op, int nNum2)  
{  
    if(op == '+')  
    {  
        return nNum1 + nNum2;  
    }  
    if(op == '-')  
    {  
        return nNum1 - nNum2;  
    }  
    if(op == '*')  
    {  
        return nNum1 * nNum2;  
    }  
    if(op == '/')  
    {  
        return nNum1 / nNum2;  
    }  
}  
  
int calculate(int len, char *expstr)  
{  
    assert(expstr);  
    if(len < 3)  
    {  
        return -1;  
    }  
    char *p = expstr;  
    int nNum1 = p[0] - '0';  
    char op = p[1];  
    int nNum2 = p[2] - '0';  
    p += 3;  
    while(*p)  
    {  
        if(*p=='*' || *p=='/')  
        {  
            nNum2 = cal(nNum2, *p, p[1]-'0');  
        }  
        else  
        {  
            nNum1 = cal(nNum1, op, nNum2);  
            op = *p;  
            nNum2 = p[1] - '0';  
        }  
        p += 2;  
    }  
    return cal(nNum1, op, nNum2);  
}  
  
int main()  
{  
    char str[] = "8+7*2-9/3";  
    scanf("%s",&str);  
    int res = calculate(strlen(str), str);  
    printf("result: %d\n", res);  
  
    return 0;  
}  