iOS常见算法题

1、二分查找
已知一个有序数组, 和一个 key, 要求从数组中找到 key 对应的索引位置

int binaryFind(int *arr,int len,int key){
    int min=0,max=len-1,mid;
    while (min <= max) {
        mid = (min+max)/2;
        if (key < arr[mid]) {
            max = mid-1;
        } else if (key > arr[mid]) {
            min = mid+1;
        } else {
            return mid;
        }
    }
    return -1;
}

2、字符串反转

- (void)strReverseTest{
    char str[] = "32415";
    int len = strlen(str);
    for (int i=0; i<(len+1)/2; i++) {
        char temp = str[i];
        str[i] = str[len-1-i];
        str[len-1-i] = temp;
    }
    NSLog(@"%s",str); // C中打印数组得for循环,不方便
}

3、有序数组合并
将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}

- (void)arrayMergeTest {
    int a[] = {1,4,6,7,9};
    int b[] = {2,3,5,6,8,9,10,11,12};
    int lenA=5,lenB=9,result[lenA+lenB],i=0,j=0,k=0;
    while (i<lenA && j<lenB) {
        if (a[i]<b[j]) {
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }
    while (i<lenA) {
        result[k++] = a[i++];
    }
    while (j<lenB) {
        result[k++] = b[j++];
    }
    NSLog(@"end");
}

4、查找两个子视图的共同父视图

- (NSMutableArray*)findSuperview:(UIView*)view {
    NSMutableArray *array = [NSMutableArray array];
    UIView*spView = view.superview;
    while (spView) {
        [array addObject:spView];
        spView = spView.superview;
    }
    return array;
}
- (NSMutableArray*)findCommonSuperview:(UIView*)view1 view2:(UIView*)view2{
    NSMutableArray *array = [NSMutableArray array];
    NSArray *superviews1 = [self findSuperview:view1];
    NSArray *superviews2 = [self findSuperview:view2];
    int len = MIN(superviews1.count,superviews2.count);
    for (int i=0; i<len; i++) {
        UIView *super1 = superviews1[superviews1.count-1-i];
        UIView *super2 = superviews2[superviews2.count-1-i];
        if (super1 == super2) {
            [array addObject:super1];
        } else {
            break;
        }
    }
    return array;
}

5、求无序数组中的中位数
中位数：数组中最中间的那个数或最中间的那两个数的平均值
思路：先排序，再求中位数

float midValue(int arr[], int len){
    float mid = (len%2 == 0) ? (arr[len/2] + arr[len/2-1])/2.0 : arr[len/2];
    return mid;
}
void midValueSort(int arr[], int len){
    for (int i=0; i<len; i++) {
        for (int j=0; j<len-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
- (void)midValueTest {
    int arr[] = {5,1,3,6,100,8};
    midValueSort(arr,6);
    float mid = midValue(arr, 6);
    NSLog(@"%.1f",mid);
    
}

6、Hash算法
例:在一个字符串中找到第一个只出现一次的字符[核心思想:生成一个数组,数组中存储每个字符出现的次数]

char findFirstChar(char cha[], int len) {
    char result = '\0';
    int arr[128];
    for (int i = 0; i < 128; i++) {
        arr[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        arr[cha[i]]++;
    }
    for (int i = 0; i < len; i++) {
        if (arr[cha[i]] == 1) {
            result = cha[i];
            break;
        }
    }
    return result;
}
- (void)findFirstCharTest {
    char cha[] = "aabbcdddf";
    char result = findFirstChar(cha, 9);
    NSLog(@"%c",result);
}