文章目录
  1. 1. 对以下一组数据进行降序排序（冒泡排序）
  2. 2. 对以下一组数据进行升序排序（选择排序）
  3. 3. 快速排序算法
  4. 4. 归并排序
  5. 5. 实现二分查找算法（编程语言不限）
  6. 6. 如何实现链表翻转（链表逆序）？
  7. 7. 合并两个有序链表生成一个新的有序链表
  8. 8. 实现一个字符串”how are you”的逆序输出（编程语言不限）。
  9. 9. 给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？
  10. 10. 二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。
  11. 11. 打印2-100之间的素数。
  12. 12. 求两个整数的最大公约数。
  13. 13. 给出一个由小写字母组成的字符串，把所有连续出现的2个a替换成bb（2个b），但是对于超过两个连续的a，那么这些字符都不作替换。
  14. 14. 给出一个字符串，其中只包含括号（大中小括号“()[]{}”），括号可以任意嵌套。如果同样的左右括号成对出现并且嵌套正确，那么认为它是匹配的。
    1. 14.1. 相似问题
  15. 15. 写一个函数，找出一个数组中出现次数超过一半的数字，如果数字不存在，则返回-1。


















文中涉及到的算法在Xcode上运行时需要引入：#import "Foundation/Foundation.h"

对以下一组数据进行降序排序（冒泡排序）

“24，80，35，8，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
void sort()
{
    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(" ");
        }
    }
}
int main(int argc, const char * argv[]) {
    sort();
    return 0;
}

对以下一组数据进行升序排序（选择排序）

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
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;
}

快速排序算法

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
void sortDescend(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;
    
    sortDescend(a, left, i-1);
    sortDescend(a, i+1, right);
}
void sortAscend(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 && a[j] >= key)  { // 从右向左找第一个小于x的数
            j--;
        }
        if(i < j) {
            a[i++] = a[j];
        }
        
        while(i < j && a[i] < key) { // 从左向右找第一个大于等于x的数
            i++;
        }
        if(i < j) {
            a[j--] = a[i];
        }
    }
    a[i] = key;
    
    sortAscend(a, left, i - 1);
    sortAscend(a, i + 1, right);
}
int main(int argc, const char * argv[]) {
    int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};
    int len=sizeof(array)/sizeof(int);
    
    sortAscend(array,0,len-1);
    for (int i = 0; i < len; i++) {
        printf("%d, ", array[i]);
    }
    printf("\n\n");
    
    sortDescend(array,0,len-1);
    for (int i = 0; i < len; i++) {
        printf("%d, ", array[i]);
    }
    printf("\n");
    return 0;
}

归并排序

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
 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;
}

实现二分查找算法（编程语言不限）

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
//非递归实现
int BinarySearch(int array[], int len, int value)
{
    if (array == NULL || len <= 0) {
        return -1;
    }
    
    int low = 0;
    int high = len - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (array[mid] == value) {
            return mid;
        }
        else if (array[mid] > value) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    
    return -1;
}
//递归实现
int BinarySearch_Recursive(int array[], int low, int high, int value)
{
    if (low > high) {
        return -1;
    }
    
    int mid = low + (high - low) / 2;
    
    if (array[mid] == value) {
        return mid;
    }
    else if (array[mid] > value) {
        return BinarySearch_Recursive(array, low, mid - 1, value);
    }
    else {
        return BinarySearch_Recursive(array, mid + 1, high, value);
    }
}
int main(int argc, char *argv[])
{
    int i, j;
    int arr[10];
    for (i = 0; i < 10; i++) {
        arr[i] = i * 2;
    }
    
    printf("array: ");
    for (int i = 0; i < 10; i++) {
        printf("%d, ", arr[i]);
    }
    
    j = 10;
    printf("\ninput the search number: %d", j);
    int location  = BinarySearch(arr, 10, j);
    if (location != -1) {
        printf("\nexist1 with index: %d", location);
    }
    else {
        printf("\nnot existed in array!");
    }
    
    location = BinarySearch_Recursive(arr, 0, 9, j);
    if (location != -1) {
        printf("\nexist2 with index: %d", location);
    }
    else {
        printf("\nnot existed in array!");
    }
    
    return 0;
}

如何实现链表翻转（链表逆序）？

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

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
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;
}

合并两个有序链表生成一个新的有序链表

我们分析两个链表的过程：

首先从合并两个链表的头结点开始，链表1的头节点的值小于链表2的头结点的值，因此链表1的头结点就是合并链表的头节点，

继续合并剩下的链表，在两个链表中剩余的节点仍然是排序的，因此合并两个链表的步骤是一样的，我们还是比较两个头结点的值，

此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是合并剩余链表的头结点，我们把这个节点和前面合并链表时得到的链表的尾巴节点链接起来

按照上面的分析可知：每次合并的步骤都是一样的，由此我们想到了递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node* mergeList(node* head1,node* head2)
{
    if (head1 == NULL) return head2;
    else if(head2 == NULL) return head1;
    
    node* head3 = NULL;
    if (head1->num < head2->num) {
        head3 = head1;
        head3->next = mergeList(head1->next, head2);
    }
    else {
        head3 = head2;
        head3->next = mergeList(head1, head2->next);
    }
    return head3;
}

实现一个字符串”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
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;
}
int main(int argc, const char * argv[]) {
    char *str = "hello world";
    spliterFunc(str);
    return 0;
}

给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？

如 “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
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++;
    }
    char *res = str;
    return res;
}
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;
    }
}

二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。

ADECBHGF

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

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

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

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

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

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

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

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

打印2-100之间的素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int isPrime(int n)
{
    int i;
    for(i = 2; i <= sqrt(n); i++)
    if(n % i == 0)  return 0;
    return 1;
}
int main(int argc, const char * argv[]) {
    for (int i = 2; i < 100; i++) {
        int r = isPrime(i);
        if (r == 1) {
            printf("%d ", i);
        }
    }
    return 0;
}

求两个整数的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}
int main(int argc, const char * argv[]) {
    int r = gcd(10, 25);
    printf("%d ", r);
    return 0;
}

给出一个由小写字母组成的字符串，把所有连续出现的2个a替换成bb（2个b），但是对于超过两个连续的a，那么这些字符都不作替换。

例如：

bad -> bad（一个a，不替换）

baad -> bbbd（替换成bb）

baaad -> baaad（连续三个a，不替换）

apaapaaapaa -> apbbpaaapbb（这里连续的a出现了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
- (NSString*)replace:(NSString*)str
{
    NSMutableString *retString = [NSMutableString stringWithString:str];
    
    // 准备替换的字符串
    NSString*replaceString = @"bb";
    
    // 正则表达式 (^a{2}[^a]) 以aa（第三个字母不是a）开头，([^a]a{2}[^a]) 字符串中间的aa（前后都不是a），([^a]a{2}$) 以aa结尾（倒数第三个字母不是a）
    NSRegularExpression *regular = [[NSRegularExpression alloc] initWithPattern:@"(^a{2}[^a])|([^a]a{2}[^a])|([^a]a{2}$)" options:NSRegularExpressionCaseInsensitive error:nil];
    NSRange range;
    do{
        range = [regular rangeOfFirstMatchInString:retString options:NSMatchingReportProgress range:NSMakeRange(0, retString.length)];
        if(range.length ==4) {
            // 替换中间的aa
            [retString replaceCharactersInRange:NSMakeRange(range.location +1,2) withString:replaceString];
        }
        else if(range.length >0) {
            if(range.location ==0) {
                // 替换开头的aa
                [retString replaceCharactersInRange:NSMakeRange(range.location,2) withString:replaceString];
            }
            else {// 替换结尾的aa
                
                [retString replaceCharactersInRange:NSMakeRange(retString.length -2,2) withString:replaceString];
            }
        }
    } while (range.length >0);
    
    return retString;
}

给出一个字符串，其中只包含括号（大中小括号“()[]{}”），括号可以任意嵌套。如果同样的左右括号成对出现并且嵌套正确，那么认为它是匹配的。

例如：

() -> TRUE（匹配）

[()] -> TRUE（匹配，括号可以嵌套）

()() -> TRUE（匹配，括号可以并列排列）

({}([])) -> TRUE（匹配，括号可以任意嵌套，大括号不必在外）

) -> FALSE（不匹配，缺少左括号）

(} -> FALSE（不匹配，左右括号不一样）

{)(} -> FALSE（不匹配，左右括号相反）

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
- (BOOL)isMatch:(NSString *)str
{
    // 采用进站出站的思想，遍历完字符串时如果array为空则匹配成功，否则失败
    NSMutableArray *array = [NSMutableArray array];
    for ( int i = 0; i < str.length; i++ ) {
        int tag = [self createTagWithString:[str substringWithRange:NSMakeRange(i, 1)]];
        if (tag != 0) {
            int lastTag = [[array lastObject] intValue];
            if ( (lastTag + tag) == 0 ) {
                [array removeLastObject];
            }
            else {
                [array addObject:@(tag)];
            }
        }
    }
    return array.count == 0;
}
- (int)createTagWithString:(NSString *)str
{
    if ([str isEqualToString:@"("] ) {
        return -1;
    }
    else if ( [str isEqualToString:@")"] ) {
        return 1;
    }
    else if ( [str isEqualToString:@"["] ) {
        return -2;
    }
    else if ( [str isEqualToString:@"]"] ) {
        return 2;
    }
    else if ( [str isEqualToString:@"{"] ) {
        return -3;
    }
    else if ( [str isEqualToString:@"}"] ) {
        return 3;
    }
    return 0;
}

相似问题

给定一个如下的字符串(1,(2,3),(4,(5,6)7))括号内的元素可以是数字，也可以是括号，请实现一个算法清除嵌套的括号，比如把上面的表达式的变成：(1,2,3,4,5,6,7)，表达式有误时请报错。

参考答案：

如果只是判断整个表达式是否有错误，然后去掉里面的圆括号，那么一个循环就可以了。不过我们只需要加两个变量分别来记录左圆括号和右圆括号的个数。这里假设逗号总是正确的情况下，代码如下：

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
int main(int argc, const char * argv[]) {
    int left = 0;
    int right = 0;
    NSString *str = @"(1,(2,3),(4,(5,6)7))";
    NSMutableString *newStr = [NSMutableString string];
    
    for (int i = 0; i < str.length; ++i ) {
        NSString *item = [str substringWithRange:NSMakeRange(i, 1)];
        if ([item isEqualToString:@"("]){
            left++;
            continue;
        }
        
        if ([item isEqualToString:@")"]) {
            right++;
            // 处理(1,)这样的结构
            NSString *pre = [str substringWithRange:NSMakeRange(i-1, 1)];
            if ([pre isEqualToString:@","]) {
                NSLog(@"error");
            }
            continue;
        }
        
        // 防止输出 1,2,3,4,5,67 这样的结果
        if (newStr.length > 0 && ![item isEqualToString:@","] && ![newStr hasSuffix:@","]) {
            [newStr appendFormat:@",%@",item];
        } else {
            [newStr appendString:item];
        }
    }
    if (left != right) {
        NSLog(@"error");
    }
    NSLog(@"new str: %@",newStr);
    
    return 0;
}

写一个函数，找出一个数组中出现次数超过一半的数字，如果数字不存在，则返回-1。

例如：

[0, 1, 2] –> -1（每个数字只出现1次）

[0, 1, 2, 1] –> -1（1出现了2次，刚好一半）

[0, 1, 2, 1, 1] –> 1（1出现了3次，超过一半）

（注：数组不是按从小到达排序的，也许排序之后更容易找到这个数，但是有没有更好、更快的方法在不重新调整顺序的情况得到结果？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- (int)mode:(NSArray *)array
{
    // 将集合中得数字转存到字典中，数字做key，对应出现的次数做value
    NSMutableDictionary *modeMap = [NSMutableDictionary dictionary];
    [array enumerateObjectsUsingBlock:^(id obj,NSUInteger idx,BOOL *stop) {
        NSString *key = obj;
        id count = modeMap[key];
        int i = [(NSNumber *)count intValue];
        [modeMap setObject:@(i +1) forKey:key];
    }];
    
    __block int retInt =-1;
    // 遍历字典，找出其中value大于集合一半的key并返回
    [modeMap.allKeys enumerateObjectsUsingBlock:^(id obj,NSUInteger idx,BOOL *stop) {
        NSString *key = obj;
        int mode = [modeMap[key] intValue];
        if(mode > array.count /2) {
            retInt = key.intValue;
            *stop =YES;
        }
    }];
    return retInt;
}