iOS面試題系列之常見(jiàn)算法

1. 對(duì)以下一組數(shù)據(jù)進(jìn)行降序排序（冒泡排序）?！?4，17，85，13，9，54，76，45，5，63”

int main(int argc, char *argv[]) {
    int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};
    int num = sizeof(array)/sizeof(int);
    for(int i = 0; i < num-1; i++) {
        for(int j = 0; j < num - 1 - i; j++) {  
            if(array[j] < array[j+1]) { 
                int tmp = array[j];     
                array[j] = array[j+1];  
                array[j+1] = tmp;   
            }
        }
    }
    for(int i = 0; i < num; i++) {
        printf("%d", array[i]); 
        if(i == num-1) {
            printf("\n");   
        }
        else {
            printf(" ");
        }
    }
}

2. 對(duì)以下一組數(shù)據(jù)進(jìn)行升序排序（選擇排序）?！?6, 37, 56, 29, 92, 73, 15, 63, 30, 8”

void sort(int a[],int n)
{
    int i, j, index;
    for(i = 0; i < n - 1; i++) {   
        index = i;
        for(j = i + 1; j < n; j++) { 
            if(a[index] > a[j]) {    
                index = j;       
            } 
        }
        if(index != i) {
            int temp = a[i];
            a[i] = a[index];
            a[index] = temp;
        }
    }
}
int main(int argc, const char * argv[]) {
    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};  
    sort(numArr, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d, ", numArr[i]);     
    }  
    printf("\n");
    return 0;
}

3. 快速排序算法

void sort(int *a, int left, int right) {
if(left >= right) {
return ;
}
int i = left;
int j = right;
int key = a[left];
while (i < j) {
while (i < j && key >= a[j]) {
j--;
}
a[i] = a[j];
while (i < j && key <= a[i]) {
    i++;
}
a[j] = a[i];
}
a[i] = key;
sort(a, left, i-1);
sort(a, i+1, right);

4. 實(shí)現(xiàn)二分查找算法（編程語(yǔ)言不限）

int bsearchWithoutRecursion(int array[],int low,int high,int target) {
while(low <= high) {
int mid = (low + high) / 2;
if(array[mid] > target)
high = mid - 1;
else if(array[mid] < target)
low = mid + 1;
else    //findthetarget
return mid;
}
//the array does not contain the target
return -1;
}
----------------------------------------
遞歸實(shí)現(xiàn)
int binary_search(const int arr[],int low,int high,int key)
{
int mid=low + (high - low) / 2;
if(low > high)
return -1;
else{
if(arr[mid] == key) 
return mid;
else if(arr[mid] > key)
return binary_search(arr, low, mid-1, key);
else
return binary_search(arr, mid+1, high, key);
}

5. 實(shí)現(xiàn)一個(gè)字符串“how are you”的逆序輸出（編程語(yǔ)言不限）。如給定字符串為“hello world”,輸出結(jié)果應(yīng)當(dāng)為“world hello”。

int spliterFunc(char *p) {
    char c[100][100]; 
    int i = 0;  
    int j = 0; 
    while (*p != '\0') {
        if (*p == ' ') {
            i++;   
            j = 0;   
        } else { 
            c[i][j] = *p;   
            j++;   
        }
        p++;
    }
    for (int k = i; k >= 0; k--) {
        printf("%s", c[k]);
        if (k > 0) {  
            printf(" ");      
        } else { 
            printf("\n");   
        }
    }
    return 0;      
}

6. 二叉樹(shù)的先序遍歷為FBACDEGH,中序遍歷為：ABDCEFGH,請(qǐng)寫出這個(gè)二叉樹(shù)的后序遍歷結(jié)果。

ADECBHGF

先序+中序遍歷還原二叉樹(shù)：先序遍歷是：ABDEGCFH 中序遍歷是：DBGEACHF
首先從先序得到第一個(gè)為A，就是二叉樹(shù)的根，回到中序，可以將其分為三部分：

左子樹(shù)的中序序列DBGE，根A，右子樹(shù)的中序序列CHF

接著將左子樹(shù)的序列回到先序可以得到B為根，這樣回到左子樹(shù)的中序再次將左子樹(shù)分割為三部分：

左子樹(shù)的左子樹(shù)D，左子樹(shù)的根B，左子樹(shù)的右子樹(shù)GE

同樣地，可以得到右子樹(shù)的根為C

類似地將右子樹(shù)分割為根C，右子樹(shù)的右子樹(shù)HF，注意其左子樹(shù)為空

如果只有一個(gè)就是葉子不用再進(jìn)行了，剛才的GE和HF再次這樣運(yùn)作，就可以將二叉樹(shù)還原了。

7. 打印2-100之間的素?cái)?shù)。

int main(int argc, const char * argv[]) {
    for (int i = 2; i < 100; i++) {
        int r = isPrime(i);   
        if (r == 1) {
            printf("%ld ", i);  
        }
    }
    return 0;
}
int isPrime(int n)
{
    int i, s;  
    for(i = 2; i <= sqrt(n); i++)
        if(n % i == 0)  return 0; 
    return 1;
}

8. 求兩個(gè)整數(shù)的最大公約數(shù)。

int gcd(int a, int b) {
    int temp = 0;  
    if (a < b) {  
        temp = a;      
        a = b;  
        b = temp;  
    }
    while (b != 0) {
        temp = a % b; 
        a = b; 
        b = temp; 
    }   
    return a;
    ```