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面试中可能会遇到的常见算法问题和答案,希望这篇文章对大家的面试能有一定的帮助,如果有疑问大家可以留言交流。