您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

iOS 面試常見演算法題彙整與解法

編輯:iOS 開發綜合

準備 iOS 面試時,演算法幾乎是必考環節。以下整理了十一道高頻題目,涵蓋排序、查找、鏈表、字串與樹的遍歷,並附上可直接編譯執行的 C / Objective-C 程式碼,方便你邊看邊動手驗證。

一、氣泡排序(降序)

將「24,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(" ");
    }
}

二、選擇排序(升序)

每一輪從未排序區中挑出最小值,與該輪的起始位置交換。「86, 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;
}

三、快速排序

選定基準值(pivot),把比它小的丟左邊、比它大的丟右邊,再對左右兩段遞迴處理,平均時間複雜度 O(n log n)。

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);
}

四、合併排序(Merge Sort)

先將陣列對半切分遞迴排序,再把兩個有序子陣列合併。需要一個暫存陣列來承接合併結果。

void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {
    int i = startIndex, j = midIndex + 1, k = startIndex;
    while (i != midIndex + 1 && j != endIndex + 1) {
        if (sourceArr[i] >= sourceArr[j]) tempArr[k++] = sourceArr[j++];
        else tempArr[k++] = sourceArr[i++];
    }
    while (i != midIndex + 1) tempArr[k++] = sourceArr[i++];
    while (j != endIndex + 1) tempArr[k++] = sourceArr[j++];
    for (i = startIndex; i <= endIndex; i++) sourceArr[i] = tempArr[i];
}

void sort(int souceArr[], int tempArr[], int startIndex, int endIndex) {
    if (startIndex < endIndex) {
        int midIndex = (startIndex + endIndex) / 2;
        sort(souceArr, tempArr, startIndex, midIndex);
        sort(souceArr, tempArr, midIndex + 1, endIndex);
        merge(souceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

int main(int argc, const char * argv[]) {
    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};
    int tempArr[10];
    sort(numArr, tempArr, 0, 9);
    for (int i = 0; i < 10; i++) printf("%d, ", numArr[i]);
    printf("\n");
    return 0;
}

五、二分查找(迭代與遞迴)

前提:資料必須先排序。每次取中間值比對,把搜尋範圍砍半,時間複雜度 O(log n)。

// 迭代版
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 return mid;   // 找到目標
    }
    return -1;             // 不存在
}

// 遞迴版
int binary_search(const int arr[], int low, int high, int key) {
    int mid = low + (high - low) / 2;
    if (low > high) return -1;
    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);
}

六、鏈表翻轉(逆序)

思路很直白:每次都把「下一個節點」摘下來接到最前面,用三個指標(前、中、後)滾動推進即可。

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
    struct NODE *next;
    int num;
} node;

node *createLinkList(int length) {
    if (length <= 0) return NULL;
    node *head, *p, *q;
    int number = 1;
    head = (node *)malloc(sizeof(node));
    head->num = 1;
    head->next = head;
    p = q = head;
    while (++number <= length) {
        p = (node *)malloc(sizeof(node));
        p->num = number;
        p->next = NULL;
        q->next = p;
        q = p;
    }
    return head;
}

void printLinkList(node *head) {
    if (head == NULL) return;
    node *p = head;
    while (p) {
        printf("%d ", p->num);
        p = p->next;
    }
    printf("\n");
}

node *reverseFunc1(node *head) {
    if (head == NULL) return head;
    node *p = head, *q = NULL;
    while (p) {
        node *pNext = p->next;
        p->next = q;
        q = p;
        p = pNext;
    }
    return q;
}

int main(int argc, const char * argv[]) {
    node *head = createLinkList(7);
    if (head) {
        printLinkList(head);
        node *reHead = reverseFunc1(head);
        printLinkList(reHead);
        free(reHead);
    }
    free(head);
    return 0;
}

七、字串單字順序反轉

把「hello world」變成「world hello」。做法是先按空白切成陣列,再從尾往前輸出。

int spliterFunc(char *p) {
    char c[100][100];
    int i = 0, 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;
}

八、找出唯一且最靠前的字元

輸入「abaccddeeef」,只有 b 出現一次,輸出位置 2。直覺做法是對每個字元做一次全字串計數。

char *strOutPut(char *);
int compareDifferentChar(char, char *);

int main(int argc, const char * argv[]) {
    char *inputStr = "abaccddeeef";
    char *outputStr = strOutPut(inputStr);
    printf("%c \n", *outputStr);
    return 0;
}

char *strOutPut(char *s) {
    char str[100];
    char *p = s;
    int index = 0;
    while (*s != '\0') {
        if (compareDifferentChar(*s, p) == 1) {
            str[index] = *s;
            index++;
        }
        s++;
    }
    return &str;
}

int compareDifferentChar(char c, char *s) {
    int i = 0;
    while (*s != '\0' && i <= 1) {
        if (*s == c) i++;
        s++;
    }
    return (i == 1) ? 1 : 0;
}

九、由遍歷序列推導後序結果

已知先序為 FBACDEGH、中序為 ABDCEFGH,求後序遍歷。答案是:

ADECBHGF

還原節點的方法:先序的第一個元素必定是根節點;拿這個根回到中序序列中切一刀,左半邊就是左子樹、右半邊就是右子樹,如此遞迴下去即可還原整棵樹。

再舉一例:先序 ABDEGCFH、中序 DBGEACHF。

  1. 先序首元素 A 為根,中序被切成「DBGE / A / CHF」。
  2. 左子樹的先序首元素是 B,中序再切成「D / B / GE」。
  3. 右子樹的先序首元素是 C,中序切成「C / HF」,注意 C 沒有左子樹。
  4. 剩下的 GE、HF 依同樣規則處理,直到每個節點都是葉子為止。

十、輸出 2~100 之間的質數

判斷質數只需試除到 sqrt(n),這是第一個可以優化的重點。

int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}

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

十一、求兩數最大公因數

輾轉相除法(歐幾里得演算法),迴圈條件是餘數不為 0。

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;
}

總結

面試考演算法,考官真正想看的往往不是你能不能默背程式碼,而是你能否說清楚時間與空間複雜度、邊界條件(空陣列、單元素、重複值)如何處理。建議每寫完一題,主動補一句複雜度分析,並提出可能的優化方向,這通常比 AC 更能加分。有疑問歡迎留言討論。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved