IOS面試大全之常見算法

更新時(shí)間：2016年09月06日 09:36:04 投稿：daisy

之前看了很多面試題，感覺要不是不夠就是過于冗余，于是我將網(wǎng)上的一些面試題進(jìn)行了刪減和分類，這篇文章先給大家分享一下IOS中的常見算法，有需要的可以參考借鑒。

這篇文字給大家分享了IOS面試中熟悉常見的算法，下面來一起看看吧。

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)行升序排序（選擇排序）?！?6, 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)二分查找算法（編程語言不限）

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è)元素提到最前面來。

#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”的逆序輸出（編程語言不限）。如給定字符串為“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、二叉樹的先序遍歷為FBACDEGH,中序遍歷為：ABDCEFGH,請(qǐng)寫出這個(gè)二叉樹的后序遍歷結(jié)果。

ADECBHGF

先序+中序遍歷還原二叉樹：先序遍歷是：ABDEGCFH 中序遍歷是：DBGEACHF

首先從先序得到第一個(gè)為A，就是二叉樹的根，回到中序，可以將其分為三部分：

左子樹的中序序列DBGE，根A，右子樹的中序序列CHF

接著將左子樹的序列回到先序可以得到B為根，這樣回到左子樹的中序再次將左子樹分割為三部分：

左子樹的左子樹D，左子樹的根B，左子樹的右子樹GE

同樣地，可以得到右子樹的根為C

類似地將右子樹分割為根C，右子樹的右子樹HF，注意其左子樹為空

如果只有一個(gè)就是葉子不用再進(jìn)行了，剛才的GE和HF再次這樣運(yùn)作，就可以將二叉樹還原了。

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ì)遇到的常見算法問題和答案，希望這篇文章對(duì)大家的面試能有一定的幫助，如果有疑問大家可以留言交流。

您可能感興趣的文章: