準備 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);
}
先將陣列對半切分遞迴排序,再把兩個有序子陣列合併。需要一個暫存陣列來承接合併結果。
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。
判斷質數只需試除到 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 更能加分。有疑問歡迎留言討論。