美文网首页
2018-08-09

2018-08-09

作者: 修一辰 | 来源:发表于2018-08-09 00:53 被阅读9次

    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("\n");

            }

            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("\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、 实现二分查找算法(编程语言不限)

    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;

    }

    ----------------------------------------

    递归实现

    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、 如何实现链表翻转(链表逆序)? 

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

    #include

    #include

    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、 实现一个字符串“how are you”的逆序输出(编程语言不限)。如给定字符串为“hello world”,输出结果应当为“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、 给定一个字符串,输出本字符串中只出现一次并且最靠前的那个字符的位置?如“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 \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、 二叉树的先序遍历为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;

    }

    相关文章

      网友评论

          本文标题:2018-08-09

          本文链接:https://www.haomeiwen.com/subject/blwfbftx.html