IOS面试大全之常见算法

这篇文字给大家分享了IOS面试中熟悉常见的算法，下面来一起看看吧。
1、对以下一组数据进行降序排序（冒泡排序）。“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（"
"）;}else {printf（" "）;}}}

2、对以下一组数据进行升序排序（选择排序）。“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（"
"）;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、归并排序

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]）;}printf（"
"）;return 0;}

5、实现二分查找算法（编程语言不限）

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//findthetargetreturn mid;}//the array does not contain the targetreturn -1;}----------------------------------------递归实现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）;elsereturn binary_search（arr, mid+1, high, key）;}}

6、如何实现链表翻转（链表逆序）？

思路：每次把第二个元素提到最前面来。

#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（"
"）;}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;}

7、实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”。

int spliterFunc（char *p） {char c[100][100];int i = 0;int j = 0;while （*p ！= ""） {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（"
"）;}}return 0;}

8、给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“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 
", *outputStr）;return 0;}char *strOutPut（char *s） {char str[100];char *p = s;int index = 0;while （*s ！= ""） {if （compareDifferentChar（*s, p） == 1） {str[index] = *s;index++;}s++;}return &str;}int compareDifferentChar（char c, char *s） {int i = 0;while （*s ！= "" && i<= 1） {if （*s == c） {i++;}s++;}if （i == 1） {return 1;} else {return 0;}}

9、二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。

ADECBHGF

先序+中序遍历还原二叉树：先序遍历是：ABDEGCFH 中序遍历是：DBGEACHF

首先从先序得到第一个为A，就是二叉树的根，回到中序，可以将其分为三部分：
左子树的中序序列DBGE，根A，右子树的中序序列CHF
接着将左子树的序列回到先序可以得到B为根，这样回到左子树的中序再次将左子树分割为三部分：
左子树的左子树D，左子树的根B，左子树的右子树GE
同样地，可以得到右子树的根为C
类似地将右子树分割为根C，右子树的右子树HF，注意其左子树为空
如果只有一个就是叶子不用再进行了，刚才的GE和HF再次这样运作，就可以将二叉树还原了。
10、打印2-100之间的素数。

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

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

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

总结

以上就是为大家整理的在IOS面试中可能会遇到的常见算法问题和答案，希望这篇文章对大家的面试能有一定的帮助，如果有疑问大家可以留言交流。