iOS面试必背的算法面试题

1、实现二分查找算法

int binarySearchWithoutRecursion(int array[], int low, int high, int target) {

while (low <= high) {
       int mid = low + (high - low) / 2;
        if (array[mid] > target) {
            high = mid - 1;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            //找到目标
            return mid;
        }
    }
    return -1;
}

递归实现

int binarySearch(const int arr[], int low, int high, int target)
{
   int mid = low + (high - low) / 2;

    if(low > high) {
        return -1;
    } else{
        if(arr[mid] == target) {
            return mid;
        } else if(arr[mid] > target) {
            return binarySearch(arr, low, mid-1, target);
        } else {
            return binarySearch(arr, mid+1, high, target);
        }
    }
}

2、 对以下一组数据进行降序排序（冒泡排序）。“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++) {
        int exchanged = 0;
        for(int j = 0; j < num - 1 - i; j++) {
            if(array[j] < array[j+1]) {
                array[j] = array[j]^array[j+1];
                array[j+1] = array[j+1]^array[j];
                array[j] = array[j]^array[j+1];
                exchanged = 1;
            }
        }
        if (exchanged == 0) {
            break;
        }
    }

    for(int i = 0; i < num; i++) {
        printf("%d ", array[i]);
    }
}

3、 对以下一组数据进行升序排序（选择排序）。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

void sort(int a[],int n)
{
    int i, j, min;

    for(i = 0; i < n - 1; i++) {
        min = i;
        for(j = i + 1; j < n; j++) {
            if(a[min] > a[j]) {
                min = j;
            }
        }

        if(min != i) {
            a[i] = a[i] ^ a[min];
            a[min] = a[min] ^ a[i];
            a[i] = a[i] ^ a[min];
        }
    }
}

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

    return 0;
}

4、 快速排序算法

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

        if (i < j) {
            a[i] = a[j];
        }


        while (i < j && key < a[i]) {
            i++;
        }

        if (i < j) {
            a[j] = a[i];
        }
    }

    a[i] = key;

    sort(a, left, i-1);

    sort(a, i+1, right);

}

5、 归并排序

void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {

    int i = startIndex;

    int j = midIndex + 1;

    int 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) {

    int midIndex;

    if (startIndex < endIndex) {

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

    return 0;   
}

6、 二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。
ADECBHGF
先序+中序遍历还原二叉树：先序遍历是：ABDEGCFH 中序遍历是：DBGEACHF
首先从先序得到第一个为A，就是二叉树的根，回到中序，可以将其分为三部分：
左子树的中序序列DBGE，根A，右子树的中序序列CHF
接着将左子树的序列回到先序可以得到B为根，这样回到左子树的中序再次将左子树分割为三部分：
左子树的左子树D，左子树的根B，左子树的右子树GE
同样地，可以得到右子树的根为C
类似地将右子树分割为根C，右子树的右子树HF，注意其左子树为空
如果只有一个就是叶子不用再进行了，刚才的GE和HF再次这样运作，就可以将二叉树还原了

7、 实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”，进阶：去掉首尾空格，每个单词间只保留一个空格。

void reverse(char *start, char *end) {
    if (start == NULL || end == NULL) {
        return;
    }

    //翻转字符
    while (start < end) {
        char tmp = *start;
        *start = *end;
        *end = tmp;

        start++;
        end--;
    }
}

char *reverseStrings(char * s){
    if (s == NULL) {
        return '\0';
    }

    //去除多余空格
    char *str = s;
    //去除首部空格
    while(*str != '\0') {
        if (*str != ' ') {
            s = str;
            break;
        }
        str++;
    }
    str = s;
    int i,j;
    i = 0;
    j = 0;
    //去除中间或尾部空格
    while(*(str+i) != '\0') {
        if (*(str+j) == ' ') {
            if (*(str+j+1) == ' ') {
                j++;
                continue;
            } else if (*(str+j+1) == '\0' ) {
                //去掉尾部空格
                *(str+i) = '\0';
                break;
            }
        } else if (*(str+j) == '\0' ) {
                //去掉尾部空格
                *(str+i) = '\0';
                break;
        } 
        if (*(str+i) != *(str+j)) {
            *(str+i) = *(str+j);
        }
        i++;
        j++; 
    }

    char *start,*end;
    start = s;
    end = s;

    while(*end != '\0') {
        end++;
    }
    end--;

    reverse(start,end);

    //翻转单词
    start = s;
    end = s;

    while (*start != '\0') {
        if (*start == ' ') {
            start++;
            end++;
        } else if (*end == ' ' || *end == '\0'){
            end--;
            reverse(start,end);
            start = ++end;
        } else {
            end++;
        }
    }

    return s;
}

int main(int argc, const char * argv[]) {

    char *str = reverseStrings("have a brilliant future");
    while (*str != '\0') {
        printf("%c", *str++);
    }

    return 0;
}

8、字符串匹，输出子串第一次出现的下标，具体要求如下：
给定主串“ababcabc”,模式串“abc”，输出结果为：2
给定主串 “aaaa”,模式串“bb”，输出结果为：-1
当模式串为空串的时候，输出结果应为：0
请实现findStringIndex函数。

int findStringIndex(char * inputs, char * matchs){
    if (inputs == NULL || matchs == NULL) {
        return -1;
    }

    if (*matchs == '\0') {
        return 0;
    }

    int i = 0,j = 0;
    while (*(inputs + i) != '\0' && *(matchs + j) != '\0') {
        if (*(inputs + i) == *(matchs + j)) {
            i++;
            j++;
        } else {
            i = i-j+1;
            j = 0;
        }
    }
    //模式串到串尾说明匹配成功，返回下标
    if (*(matchs + j) == '\0') {
            return i-j;
    }
    return -1;
}

int main(int argc, const char * argv[]) {
    printf("index = %d", findStringIndex("ababcabc", "abc"));
    return 0;
}

9、字符串匹配进阶，KMP算法：

void generateNextArr(char *s,int *next) {
    //初始化
    int k = -1,j = 0;
    //next[0]初始化成-1
    *next = -1;

    while (j < strlen(s) - 1) {
        if (k == -1 || *(s + j) == *(s + k)) {
            j++;
            k++;
            //s[j]==s[next[k]]必然会失配
            if (*(s + j) != *(s+k)) {
                *(next + j) = k;
            } else {
                *(next + j) = *(next + k);
            }
        } else {
            k = *(next + k);
        }
    }

}

int kmpMatch(char *inputs, char *matchs) {
    if (inputs == NULL || matchs == NULL) {
        return -1;
    }
    //模式串为空串时返回0
    if (*matchs == '\0') {
        return 0;
    }
    int inputLen = strlen(inputs);
    int len = strlen(matchs);

    int *next = (int *)malloc(len*sizeof(int));

    //生成next数组：失配时模式串下标跳转的位置
    generateNextArr(matchs, next);

    int i = 0,j = 0;
    while (i < inputLen  && j < len) {
        if (j == -1 || *(inputs + i) == *(matchs + j)) {
            i++;
            j++;
        } else {
            j = *(next + j);
        }
    }
    if (*(matchs + j) == '\0') {
        return i-j;
    }
    free(next);
    return -1;
}

int main(int argc, const char * argv[]) {
    printf("index = %d", kmpMatch("aabcbbabcb", "abc"));
    return 0;
}

10、如何实现一个数组每个元素依次向右移动k位，后面的元素依次往前面补。比如: [1, 2, 3, 4, 5] 移动两位变成[4, 5, 1, 2, 3]。
思路：三次反转
后K位反转：12354
前部分反转：32154
整体全部反转：45123

int * reverse1(int *arr, int start, int end) {
    while (start < end) {
        arr[start] = arr[start] ^ arr[end];
        arr[end] = arr[end] ^ arr[start];
        arr[start] = arr[start] ^ arr[end];
        start++;
        end--;
    }
    return arr;
}
int * moveK(int *arr, int numSize, int k) {
    reverse1(arr, numSize - k, numSize-1);
    reverse1(arr, 0, numSize-k-1);
    reverse1(arr, 0, numSize-1);

    return arr;
}

int main(int argc, const char * argv[]) {
    int arr[5] = {1,2,3,4,5};
    int numSize = sizeof(arr) / sizeof(int);
    moveK(arr, numSize, 2);
    for (int i = 0; i < numSize; i++) {
        printf("%d ",arr[i]);
    }
    return 0;
}

11、 给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。

char findChar(char *s){
    if (s == NULL) {
        return ' ';
    }
    int hashTable[256];
    memset(hashTable, 0, sizeof(hashTable));
    char *p = s;
    while(*p != '\0') {
        hashTable[*p]++;
        p++;
    }
    p = s;

    while(*p != '\0') {
        if (hashTable[*p] == 1) {
            return *p;
        }
        p++;
    }

    return ' ';
}

int main(int argc, const char * argv[]) {

    char *inputStr = "abaccddeeef";

    char ch = findChar(inputStr);

    printf("%c \n", ch);

    return 0;

}

12、 如何实现链表翻转（链表逆序）？
思路：每次把第二个元素提到最前面来。

#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,*q;

    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;

}

13、删除链表中的重复元素，每个重复元素需要出现一次，如给定链表 1->2->2->3->4->5->5，输出结果应当为 1->2->3->4->5。请实现下面的deleteRepeatElements函数：

typedef struct NODE {

    struct NODE *next;

    int num;

} node;

node *deleteRepeatElements(node *head) {
    if (head == NULL) {
        return head;
    }

    struct ListNode* pNode = head;

    while (pNode && pNode->next) {
        if (pNode->val == pNode->next->val) {
            struct ListNode *tempNode = pNode->next;
            pNode->next = pNode->next->next;
            free(tempNode);
        } else {
            pNode=pNode->next;
        }
    }
    return head;
}

14、删除链表中重复的元素，只保留不重复的结点。如：1->1->2->3->4->4->5，输出结果：2->3->5，请实现下面的deleteRepeatElements函数。

typedef struct NODE {

    struct NODE *next;

    int num;

} node;

node *deleteRepeatElements(node *head) {
    if (head == NULL) {
        return head;
    }
    //头结点有可能会被删除,先创建一个头结点
    node *pHead = (node *)malloc(sizeof(node));
    pHead->next = head;
    node *current = pHead;

    while(current->next && current->next->next) {
        if (current->next->val == current->next->next->val) {
            node *tempNode = current->next;
            while(tempNode && tempNode->next && tempNode->val == tempNode->next->val) {
                tempNode = tempNode->next;
            }
            current->next = tempNode->next;
        } else {
            current = current->next;
        }
    }
    return pHead->next;
}

15、 打印2-100之间的素数。
判断素数思路：通过分析我们可知5以上的自然数都可以用6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5来代替,又因6x,6x+2=2(3x+1),6x+3=3(2x+1),6x+4=2*(3x+2)以上都不可能是素数，所以只需要判断6x-1,6x+1,6x+5（6x两侧的数）即可。

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)
{

    if(n == 2  ||  n == 3) {
        return 1;
    }

    if(n % 6 != 1 && n % 6 != 5) {
        return 0;
    }

    for(int i = 5; (i * i) <= n; i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) {
            return 0;
        }
    }

    return 1;
}

16、计算100以内素数的个数

int countPrime(int n) {
    int i,j,count = 0;
    //开辟空间
    int *prime = (int *)malloc(sizeof(int) * n);
    //初始默认所有数为素数
    memset(prime, 1, sizeof(int) * n);
    for (i = 2; i < n; i++) {
        if (prime[i]) {
            count++;
            for (j = i + i; j < n; j += i) {
                //标记不是素数
                prime[j] = 0;
            }
        }
    }
    return count;
}

17、 求两个整数的最大公约数。

int gcd(int a, int b) {

    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

转自：https://www.jianshu.com/p/746495327da6