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