iOS 常遇到的面试算法题

1、手写代码实现一个冒泡排序？

//代码如下：
- (void)bubbleSortArray:(NSMutableArray *)array
{
    int count = [array count];
    for (int i = 0; i < (count-1); i ++) {
        for (int j = 0; j < (count - 1 - i); j ++) {
            if ([array[j] intValue] > [array[j+1] intValue]) {
                SWAP(array, j, (j+1));
            } 
        }
    }
    NSLog(@“%@“, array);
}

2、手写代码实现一个选择排序？

//代码如下：
- (void)selectSortArray:(NSMutableArray *)array
{
    int count = [array count];
    for (int i = 0; i < (count-1); i ++) {
      int min = i;
      for (int j = i; j < count; j ++) {
          if ([array[min] intValue] > [array[j] intValue]) {
              min = j;
          } 
      }
      if (min != i) {
        EXCHANGE(array, min, i);
      }
    }
    NSLog(@“%@“, array);
}

3、动态规划，1毛、3毛、5毛硬币找零的问题？

//代码如下：
- (NSInteger)calculateTotalAmount:(NSInteger)total
{
    NSMutableArray *array = [NSMutableArray array];
    [array addObjectsFromArray:@[@(0),@(1),@(2),@(1),@(2),@(1)]];
    for (int i = 6; i < (total +1); i ++) {
        NSInteger min = total;
        for (int j = 1; j <= (i / 2); j ++) {
            NSInteger value1 = [array[j] integerValue];
            NSInteger value2 = [array[i-j] integerValue];
            min = MIN(min, (value1 + value2));
      }
      [array insertObject:@(min) atIndex:i];
    } 
    return [array[total] integerValue];
}

4、手写代码实现反转单向链表？

//代码如下：
typedef sturct DXNode {
    int data;
    DXNode *next;
} DXNode;
DXNode* CreateNode(int data) {
    DXNode *node = (DXNode *)malloc(sizeof(DXNode));
    node -> data = data;
    node -> next = NULL;
    return node;
}
DXNode* AppendNode(DXNode *head, int data) {
    DXNode *node = CreateNode(data);
    DXNode *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p.right = node;
    return head;
}
DXNode* ReverseNode(DXNode *head) {
    DXNode *p = head;
    DXNode *newHead = NULL;
    while (p -> next != NULL) {
        DXNode *temp = p -> next;
        p -> next = newHead;
        newHead = p;
        p = temp;
    }
    return newHead;
}
int main()
{
    DXNode *node = CreateNode(0);
    for (int i = 0; i < 10; i ++) {
        node = AppendNode(node, i);
    }
    ResverNode(node);
}

5、手写代码实现一个双向链表？

//代码如下：
typedef sturct DXNode {
    int data;
    DXNode *left;
    DXNode *right;
} DXNode;
DXNode* CreateNode(int data) {
    DXNode *node = (DXNode *)malloc(sizeof(DXNode));
    node -> data = data;
    node -> left = node -> right = NULL;
    return node;
}
DXNode* AppendNode(DXNode *head, int data) {
    DXNode *node = CreateNode(data);
    DXNode *p = head;
    while (p != NULL) {
        p = p->right;
    }
    p.right = node;
    node.left = p;
    return head;
}
int main()
{
    DXNode *node = CreateNode(0);
    for (int i = 0; i < 10; i ++) {
        node = AppendNode(node, i);
    }
}

6、反转字符串?

//代码如下：
- (NSString *)reverseString:(NSString *)string
{
    NSMutableString *content = [string mutableCopy];
    for (int i = 0; i < (string.length +1)/2; i ++) {
        NSRange range1 = NSMakeRange(i, 1);
        NSRange range2 = NSMakeRange(string.length - i -1, 1);
        NSString *temp1 = [string substringWithRange:range1];
        NSString *temp2 = [string substringWithRange:range2];
        [content replaceCharactersInRange:range1 withString:temp2];
        [content replaceCharactersInRange:range2 withString:temp1];
    } 
    return content;
}

7、有序数组合并？

//代码如下：
- (void)orderArray:(NSArray *)array1 withArray2:(NSArray *)array2
{
    int p = 0, q = 0, i = 0;
    NSMutableArray *list = [NSMutableArray array];
    while ((p < [array1 count]) && (q < [array2 count])) {
        if (array1[p] < array2[q]) {
            [list addObject: array1[p] ];
            p ++;
        } else {
            [list addObject: array2[q] ];
            q ++;
        }
    }
    while ( p < [array1 count] ) {
        [list addObject: array1[p] ];
        p ++;
    }
    while ( q < [array2 count] ) {
        [list addObject: array2[q] ];
        q ++;
    }
}

8、找出1000内的完数，完数是能被整除的数的和为这个值。例如：6=1+2+3

//代码如下：
- (void)findPerfectNumberMethod
{
    for (int i = 0; i < 1000; i ++) {
      int sum = 0;
      for (int j = 1; j < i; j ++) {
        if (i % j == 0) {
          sum += j;
        }
      }
      if (sum == i) {
        NSLog(@"%@", @(i));
      }
    }
}