IOS面试大全之常见算法

时间:2022-05-08 10:27:48

这篇文字给大家分享了IOS面试中熟悉常见的算法,下面来一起看看吧。

1、 对以下一组数据进行降序排序(冒泡排序)。“24,17,85,13,9,54,76,45,5,63”

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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”

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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、 快速排序算法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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、 归并排序

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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、 实现二分查找算法(编程语言不限)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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、 如何实现链表翻转(链表逆序)?

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#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、 实现一个字符串“how are you”的逆序输出(编程语言不限)。如给定字符串为“hello world”,输出结果应当为“world hello”。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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,请写出这个二叉树的后序遍历结果。

?
1
ADECBHGF

先序+中序遍历还原二叉树:先序遍历是:ABDEGCFH 中序遍历是:DBGEACHF

首先从先序得到第一个为A,就是二叉树的根,回到中序,可以将其分为三部分:

左子树的中序序列DBGE,根A,右子树的中序序列CHF

接着将左子树的序列回到先序可以得到B为根,这样回到左子树的中序再次将左子树分割为三部分:

左子树的左子树D,左子树的根B,左子树的右子树GE

同样地,可以得到右子树的根为C

类似地将右子树分割为根C,右子树的右子树HF,注意其左子树为空

如果只有一个就是叶子不用再进行了,刚才的GE和HF再次这样运作,就可以将二叉树还原了。

10、 打印2-100之间的素数。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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、 求两个整数的最大公约数。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
 
}

总结

以上就是为大家整理的在IOS面试中可能会遇到的常见算法问题和答案,希望这篇文章对大家的面试能有一定的帮助,如果有疑问大家可以留言交流。

原文链接:http://blog.csdn.net/yangshebing21/article/details/51292477