前端面试常考算法

快速排序

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100005;
int a[N];void quick_sort(int a[], int l, int r) {if (l >= r) return;int x = a[l + r >> 1];int i = l - 1, j = r + 1;while (i < j) {while (a[++i] < x);while (a[--j] > x);if (i < j) swap(a[i], a[j]);}quick_sort(a, l, j);quick_sort(a, j+1, r);
} int main() {int n;cin >> n;for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}quick_sort(a, 0, n - 1);for (int i = 0; i < n; i++) {printf("%d ", a[i]);}return 0;
}

归并排序

#include<iostream>
#include<cstdio>
using namespace std;const int N = 100005;
int a[N], tmp[N];void merge_sort(int a[], int l, int r) {if (l >= r) return;int mid = l + r >> 1;merge_sort(a, l, mid);merge_sort(a, mid+1, r);int i = l, j = mid + 1, k = i;while (i <= mid && j <= r) {if (a[i] < a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}while (i <= mid)tmp[k++] = a[i++];while (j <= r)tmp[k++] = a[j++];for (int i = l; i <= r; i++) {a[i] = tmp[i];}
}int main(){int n;cin >> n;for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}merge_sort(a, 0, n-1);for (int i = 0; i < n; i++) {printf("%d ", a[i]);}cout << endl;return 0;
}

最长上升子序列

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int a[N], f[N];int main(){int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {f[i] = 1;for (int j = 1; j < i; j++) {if (a[j] < a[i])f[i] = max(f[i], f[j] + 1);}}int res = 0;for (int i = 1; i <= n; i++) {res = max(res, f[i]);}cout << res << endl;return 0;
}

最长公共子序列

#include<iostream>
#include<algorithm>
#include<cstring>const int N = 1010;
char a[N], b[N];
int f[N][N];using namespace std;int main(){int n, m;cin >> n >> m;cin >> a+1 >> b+1;for (int i = 1; i <= n; i++ ) {for (int j = 1; j <= m; j++) {f[i][j] = max(f[i-1][j], f[i][j-1]);if (a[i] == b[j]) {f[i][j] = max(f[i][j], f[i-1][j-1] + 1);}}}cout << f[n][m] << endl;return 0;
}