IOS面試大全之常見(jiàn)算法
更新時(shí)間：2016年09月06日 09:36:04 投稿：daisy
之前看了很多面試題，感覺(jué)要不是不夠就是過(guò)于冗余，于是我將網(wǎng)上的一些面試題進(jìn)行了刪減和分類(lèi)，這篇文章先給大家分享一下IOS中的常見(jiàn)算法，有需要的可以參考借鑒。
這篇文字給大家分享了IOS面試中熟悉常見(jiàn)的算法，下面來(lái)一起看看吧。
1、 對(duì)以下一組數(shù)據(jù)進(jìn)行降序排序（冒泡排序）?！?4，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(" ");
}
}
}
2、 對(duì)以下一組數(shù)據(jù)進(jìn)行升序排序（選擇排序）。“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;
}
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("\n");
return 0;
}
5、 實(shí)現(xiàn)二分查找算法（編程語(yǔ)言不限）
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 //findthetarget
return mid;
}
//the array does not contain the target
return -1;
}
----------------------------------------
遞歸實(shí)現(xiàn)
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);
else
return binary_search(arr, mid+1, high, key);
}
}
6、 如何實(shí)現(xiàn)鏈表翻轉(zhuǎn)（鏈表逆序）？
思路：每次把第二個(gè)元素提到最前面來(lái)。
#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;
}
7、 實(shí)現(xiàn)一個(gè)字符串“how are you”的逆序輸出（編程語(yǔ)言不限）。如給定字符串為“hello world”,輸出結(jié)果應(yīng)當(dāng)為“world hello”。
int spliterFunc(char *p) {
char c[100][100];
int i = 0;
int 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;
}
8、 給定一個(gè)字符串，輸出本字符串中只出現(xiàn)一次并且最靠前的那個(gè)字符的位置？如“abaccddeeef”,字符是b,輸出應(yīng)該是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++;
}
if (i == 1) {
return 1;
} else {
return 0;
}
}
9、 二叉樹(shù)的先序遍歷為FBACDEGH,中序遍歷為：ABDCEFGH,請(qǐng)寫(xiě)出這個(gè)二叉樹(shù)的后序遍歷結(jié)果。
ADECBHGF
先序+中序遍歷還原二叉樹(shù)：先序遍歷是：ABDEGCFH 中序遍歷是：DBGEACHF
首先從先序得到第一個(gè)為A，就是二叉樹(shù)的根，回到中序，可以將其分為三部分：
左子樹(shù)的中序序列DBGE，根A，右子樹(shù)的中序序列CHF
接著將左子樹(shù)的序列回到先序可以得到B為根，這樣回到左子樹(shù)的中序再次將左子樹(shù)分割為三部分：
左子樹(shù)的左子樹(shù)D，左子樹(shù)的根B，左子樹(shù)的右子樹(shù)GE
同樣地，可以得到右子樹(shù)的根為C
類(lèi)似地將右子樹(shù)分割為根C，右子樹(shù)的右子樹(shù)HF，注意其左子樹(shù)為空
如果只有一個(gè)就是葉子不用再進(jìn)行了，剛才的GE和HF再次這樣運(yùn)作，就可以將二叉樹(shù)還原了。
10、 打印2-100之間的素?cái)?shù)。
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、 求兩個(gè)整數(shù)的最大公約數(shù)。
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;
}
總結(jié)
以上就是為大家整理的在IOS面試中可能會(huì)遇到的常見(jiàn)算法問(wèn)題和答案，希望這篇文章對(duì)大家的面試能有一定的幫助，如果有疑問(wèn)大家可以留言交流。
相關(guān)文章
本篇文章給大家分享一下在IOS中如何將Xcode9項(xiàng)目上傳到GitHub的教程方法，一起跟著學(xué)習(xí)分享下吧。2018-01-01
這篇文章主要介紹了iOS中仿QQ側(cè)滑菜單功能,在實(shí)現(xiàn)此功能之前，需要先了解UITabBarController的層級(jí)結(jié)構(gòu)，具體實(shí)現(xiàn)思路大家可以參考下本文2017-07-07
這篇文章主要為大家詳細(xì)介紹了iOS音樂(lè)后臺(tái)播放及鎖屏信息顯示，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
iOS中searchBar(搜索框)光標(biāo)初始位置后移
這篇文章主要介紹了iOS中searchBar(搜索框)光標(biāo)初始位置后移的關(guān)鍵代碼,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-08-08
不知道大家發(fā)現(xiàn)了沒(méi)，在現(xiàn)在的很多App中常使用圓角箭頭矩形, 如微博分組提示框, 地圖坐標(biāo)顯示點(diǎn)等。iPad 中有 UIPopoverController 類(lèi)供開(kāi)發(fā)使用, iPhone中就需要開(kāi)發(fā)人員定制了。那么下面這篇文中就來(lái)聊聊定制圓角箭頭矩形提示框，有需要的朋友們可以參考借鑒。2016-11-11
ios實(shí)現(xiàn)底部PopupWindow的示例代碼(底部彈出菜單)
這篇文章主要介紹了ios實(shí)現(xiàn)底部PopupWindow的示例代碼(底部彈出菜單),小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-01-01
本篇文章主要介紹了iOS 導(dǎo)航欄自帶頁(yè)面右滑pop使用示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-12-12
自從對(duì) iOS 的逆向初窺門(mén)徑后，我也經(jīng)常通過(guò)它來(lái)分析一些比較大的應(yīng)用，參考一下這些應(yīng)用中某些功能的實(shí)現(xiàn)。這個(gè)探索的過(guò)程樂(lè)趣多多，不僅能滿(mǎn)足自己對(duì)未知的好奇心，還經(jīng)常能發(fā)現(xiàn)一些意外的驚喜。這篇文章主要介紹了iOS通過(guò)逆向如何深入理解Block內(nèi)存模型的相關(guān)資料。2017-01-01
iOS獲取設(shè)備唯一標(biāo)識(shí)的8種方法
這篇文章主要為大家詳細(xì)介紹了iOS獲取設(shè)備唯一標(biāo)識(shí)的8種方法,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-11-11
iOS基于UIScrollView實(shí)現(xiàn)滑動(dòng)引導(dǎo)頁(yè)
這篇文章主要為大家詳細(xì)介紹了iOS基于UIScrollView實(shí)現(xiàn)滑動(dòng)引導(dǎo)頁(yè)的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-01-01