面试算法题归总

1.将数组中的0移到最前面

提供一个数组 s[10] = {4,0,0,1,2,0,5,0,3,0}, 将其中的0移到最前面且不改变非0值的顺序,
上面例子的结果是: res[10] = {0,0,0,0,0,4,1,2,5,3};

冒泡排序

void swap0_bubbleSort(int a[], int len) {
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(a[j+1] == 0) {
                int tmp = a[j+1];
                a[j+1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

时间复杂度： O(n2)

插入排序

void swap0_insertSort(int a[], int len) {
    for(int i = 1; i < len; i++) {
        int tmp = a[i];
        int j = i;
        
        for(;j > 0 && tmp == 0;j--) {
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

时间复杂度：O(n2)

遍历交换

void swap0_exchange(int a[], int len) {
    for(int i = len - 1,k = len - 1; i >= 0; i--) {
        //k指向0的元素位置，i指向非0的元素位置
        if(a[i] != 0) {
            int tmp = a[k];
            a[k] = a[i];
            a[i] = tmp;
            
            k--;
        }
    }
}

时间复杂度：O(n)

2.斐波那契数列

青蛙跳一次可以跳1阶，可以跳2阶，问跳到n阶有多少种跳法

解析：
跳到n阶时，只有可能是n-1阶处再跳1阶，或者可能是n-2阶处再跳2阶
复合斐波那契数列，动态方程：
f(n) = f(n-1)+f(n-2)

int jumpFloor(int n) {
    if(n == 0 || n == 1)
        return n;
    
    int f1 = 0,f2 = 1;
    for(int i = 2; i < n; i++) {
        int tmp = f1 + f2;
        f1 = f2;
        f2 = tmp;
    }
    
    return f2;
}