您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

iOS 面試常見題:經典演算法兩例

編輯:iOS 相關資訊

1. 約瑟夫問題(報數出列)

有 13 個人圍坐一圈,從第一人開始循環報數,數到 3 的人出列,最後剩下的人即為答案。以下用陣列模擬整個過程:

int people[13] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
int count = 0;   // 記錄報數
int number = 13; // 記錄存活人數
int i = 0;       // 記錄當前報數的人

while (number > 1) {
    if (people[i] != 0) {
        count++;          // 未被剔除則報數有效
    }
    if (count == 3) {
        people[i] = 0;    // 剔除
        count = 0;        // 報數歸零
        number--;         // 存活人數減一
    }
    i++;                  // 下一個人
    if (i == 13) {
        i = 0;            // 超出範圍回到第一人
    }
}

for (int j = 0; j < 13; j++) {
    if (people[j] > 0) {
        printf("最後剩下的是第 %d 人\n", people[j]);
    }
}

2. 在大量整數中找出重複的數字

有 1000000 個整數,每個數值範圍為 0~999999,找出其中重複出現的數字。這裡利用「以數值作為索引、以出現次數作為值」的桶計數思路:

#define COUNT 1000000

int main(void)
{
    int a[COUNT] = {0};
    for (int i = 0; i < COUNT; i++) {
        int number = arc4random() % COUNT; // 以隨機數作為索引
        a[number - 1]++;                    // 值作為出現次數
    }

    // 輸出重複的數字與出現次數
    for (int i = 0; i < COUNT; i++) {
        if (a[i] > 1) {
            printf("%d 出現了 %d 次\n", i + 1, a[i]);
        }
    }
    return 0;
}

這類題目考驗的是對基本資料結構與迴圈控制的掌握,理解計數排序(Counting Sort)的核心思想即可靈活應對。

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