IOS面试大全之常见算法
这篇文字给大家分享了IOS面试中熟悉常见的算法，下面来一起看看吧。
1、对以下一组数据进行降序排序（冒泡排序）。“24，17，85，13，9，54，76，45，5，63”
intmain(intargc,char*argv[]){
intarray[10]={24,17,85,13,9,54,76,45,5,63};
intnum=sizeof(array)/sizeof(int);
for(inti=0;i<num-1;i++){
for(intj=0;j<num-1-i;j++){
if(array[j]<array[j+1]){
inttmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
}
}
for(inti=0;i<num;i++){
printf("%d",array[i]);
if(i==num-1){
printf("\n");
}
else{
printf("");
}
}
}
2、对以下一组数据进行升序排序（选择排序）。“86,37,56,29,92,73,15,63,30,8”
voidsort(inta[],intn)
{
inti,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){
inttemp=a[i];
a[i]=a[index];
a[index]=temp;
}
}
}
intmain(intargc,constchar*argv[]){
intnumArr[10]={86,37,56,29,92,73,15,63,30,8};
sort(numArr,10);
for(inti=0;i<10;i++){
printf("%d,",numArr[i]);
}
printf("\n");
return0;
}
3、快速排序算法
voidsort(int*a,intleft,intright){
if(left>=right){
return;
}
inti=left;
intj=right;
intkey=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、归并排序
voidmerge(intsourceArr[],inttempArr[],intstartIndex,intmidIndex,intendIndex){
inti=startIndex;
intj=midIndex+1;
intk=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];
}
}
voidsort(intsouceArr[],inttempArr[],intstartIndex,intendIndex){
intmidIndex;
if(startIndex<endIndex){
midIndex=(startIndex+endIndex)/2;
sort(souceArr,tempArr,startIndex,midIndex);
sort(souceArr,tempArr,midIndex+1,endIndex);
merge(souceArr,tempArr,startIndex,midIndex,endIndex);
}
}
intmain(intargc,constchar*argv[]){
intnumArr[10]={86,37,56,29,92,73,15,63,30,8};
inttempArr[10];
sort(numArr,tempArr,0,9);
for(inti=0;i<10;i++){
printf("%d,",numArr[i]);
}
printf("\n");
return0;
}
5、实现二分查找算法（编程语言不限）
intbsearchWithoutRecursion(intarray[],intlow,inthigh,inttarget){
while(low<=high){
intmid=(low+high)/2;
if(array[mid]>target)
high=mid-1;
elseif(array[mid]<target)
low=mid+1;
else//findthetarget
returnmid;
}
//thearraydoesnotcontainthetarget
return-1;
}
----------------------------------------
递归实现
intbinary_search(constintarr[],intlow,inthigh,intkey)
{
intmid=low+(high-low)/2;
if(low>high)
return-1;
else{
if(arr[mid]==key)
returnmid;
elseif(arr[mid]>key)
returnbinary_search(arr,low,mid-1,key);
else
returnbinary_search(arr,mid+1,high,key);
}
}
6、如何实现链表翻转（链表逆序）？
思路：每次把第二个元素提到最前面来。
#include<stdio.h>
#include<stdlib.h>
typedefstructNODE{
structNODE*next;
intnum;
}node;
node*createLinkList(intlength){
if(length<=0){
returnNULL;
}
node*head,*p,*q;
intnumber=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;
}
returnhead;
}
voidprintLinkList(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){
returnhead;
}
node*p,*q;
p=head;
q=NULL;
while(p){
node*pNext=p->next;
p->next=q;
q=p;
p=pNext;
}
returnq;
}
intmain(intargc,constchar*argv[]){
node*head=createLinkList(7);
if(head){
printLinkList(head);
node*reHead=reverseFunc1(head);
printLinkList(reHead);
free(reHead);
}
free(head);
return0;
}
7、实现一个字符串“howareyou”的逆序输出（编程语言不限）。如给定字符串为“helloworld”,输出结果应当为“worldhello”。
intspliterFunc(char*p){
charc[100][100];
inti=0;
intj=0;
while(*p!='\0'){
if(*p==''){
i++;
j=0;
}else{
c[i][j]=*p;
j++;
}
p++;
}
for(intk=i;k>=0;k--){
printf("%s",c[k]);
if(k>0){
printf("");
}else{
printf("\n");
}
}
return0;
}
8、给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。
char*strOutPut(char*);
intcompareDifferentChar(char,char*);
intmain(intargc,constchar*argv[]){
char*inputStr="abaccddeeef";
char*outputStr=strOutPut(inputStr);
printf("%c\n",*outputStr);
return0;
}
char*strOutPut(char*s){
charstr[100];
char*p=s;
intindex=0;
while(*s!='\0'){
if(compareDifferentChar(*s,p)==1){
str[index]=*s;
index++;
}
s++;
}
return&str;
}
intcompareDifferentChar(charc,char*s){
inti=0;
while(*s!='\0'&&i<=1){
if(*s==c){
i++;
}
s++;
}
if(i==1){
return1;
}else{
return0;
}
}
9、二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。
ADECBHGF
先序+中序遍历还原二叉树：先序遍历是：ABDEGCFH中序遍历是：DBGEACHF
首先从先序得到第一个为A，就是二叉树的根，回到中序，可以将其分为三部分：
左子树的中序序列DBGE，根A，右子树的中序序列CHF
接着将左子树的序列回到先序可以得到B为根，这样回到左子树的中序再次将左子树分割为三部分：
左子树的左子树D，左子树的根B，左子树的右子树GE
同样地，可以得到右子树的根为C
类似地将右子树分割为根C，右子树的右子树HF，注意其左子树为空
如果只有一个就是叶子不用再进行了，刚才的GE和HF再次这样运作，就可以将二叉树还原了。
10、打印2-100之间的素数。
intmain(intargc,constchar*argv[]){
for(inti=2;i<100;i++){
intr=isPrime(i);
if(r==1){
printf("%ld",i);
}
}
return0;
}
intisPrime(intn)
{
inti,s;
for(i=2;i<=sqrt(n);i++)
if(n%i==0)return0;
return1;
}
11、求两个整数的最大公约数。
intgcd(inta,intb){
inttemp=0;
if(a<b){
temp=a;
a=b;
b=temp;
}
while(b!=0){
temp=a%b;
a=b;
b=temp;
}
returna;
}
总结
以上就是为大家整理的在IOS面试中可能会遇到的常见算法问题和答案，希望这篇文章对大家的面试能有一定的帮助，如果有疑问大家可以留言交流。