2015年真题代码
1. 求马鞍点
思路：创建ma和mi数组分别存储最大最小值，其中，ma[ i ] = j 表示第 i 行的最大值在第 j 列。最后遍历一遍max数组。假设没有重复的数字。
const int N = 1000;
int a[N][N];
int n, m, max, min;
int ma[N], mi[N];
int main() {
scanf("%d %d", &n, &m); //n行m列
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
scanf("%d", &a[i][j]);
}
}
// 找行最大
for(int i = 0; i < n; i++) {
int maxIndex = -0x3f;
for(int j = 0; j < m; j++) {
if(a[i][j] > maxIndex) {
maxIndex = a[i][j];
ma[i] = j; // 第i行的最大值下标为j
}
}
}
// 找列最小
for(int i = 0; i < m; i++) { //第i列第j行
int minIndex = 0x3f;
for(int j = 0; j < n; j++) {
if(a[j][i] < minIndex) {
minIndex = a[j][i];
mi[i] = j; // 第i列的最小值下标为j
}
}
}
for(int i = 0 ;i < n; i++) {
int k = ma[i]; //k存储的是第i行最大值的列数
if (mi[k] == i) cout << i << " " << k;
}
return 0;
}
2. 类三路归并
题目：设计一个算法，给出一个有序列，按模3余0 余1 余2排序。
// 我写的是无序序列，在三路划分后进行快速排序
void quickSort(int l, int r) {
if (l > r) return;
int i = l, j = r ,temp = a[l];
while(i < j) {
while(i < j && a[j] > temp) j--;
if(i < j) { a[i] = a[j]; i++; }
while(i < j && a[i] < temp) i++;
if(i < j) { a[j] = a[i]; j--; }
}
a[i] = temp;
quickSort(l, i - 1);
quickSort(i + 1, r);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int i = 0, j = 0, k = n - 1;
while(j <= k) {
int temp = a[j] % 3;
if (temp == 0) swap(a[i++], a[j++]);
else if(temp == 1 ) j++;
else swap(a[j], a[k--]);
}
// cout << a[0] << " " << a[i-1];
quickSort(0, i-1);
quickSort(i, k-1);
quickSort(k, n-1);
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
}
2016年真题代码
1. 数组无序，实现输出一个有序单循环链表。
（在没有其他思路的情况下硬解是最直接的）
2. 找出某个结点的所有祖先结点。（中序+深搜）
3. 集群环境中为不同运行时间的计算机分配相同的任务，使得总消耗时间最短。
int n, m, ans, idx, t[N];
int f[N]; //f数组存储每台机器已耗费的时间
int main() {
scanf("%d %d", &n, &m); //n个任务m台机器
for(int i = 1; i <= m; i++) {
scanf("%d", &t[i]); //输入每台机器处理该任务需要耗费的时间
}
for(int i = 1;i <= n; i++) {
int cur = 2e9;
idx = 0; // 第i个任务加入index机器中 且耗费的时间为min
for(int j = 1; j <= m; j++) {
if( cur > f[j] + t[j]) {
cur = f[j] + t[j];
idx = j; // 更新cur值且更新下标
}
}
f[idx] += t[idx]; // 更新所用时间
}
cout << f[idx];
return 0; //最后保存的idx就是最后的时长
}
2017年真题代码
1. 二进制数中1的个数
// 此时的时间复杂度只与1有关
int countOne2(int num) {
int count = 0;
while(num > 0) {
// 原理： 每次取出最后一位和1做逻辑与操作
if((num & 1) == 1) count++;
num>>=1; // num = (num >> 1);
}
return count;
}
// 时间复杂度为O(logn)
int countOne1(int num) {
int c = 0;
while(num > 0) {
if(num % 2 == 1) c++;
num = num / 2;
}
return c;
}
/*
O(1) 把a做单位数过滤，默认32位，int型
*/
int countOne3(int num) {
int m_1 = 0x55555555; // 0101 8对
int m_2 = 0x33333333; // 0011 8对
int m_4 = 0x0f0f0f0f; // 00001111 4对
int m_8 = 0x00ff00ff;
int m_16 = 0x0000ffff;
int b = (num & m_1) + ((num >> 1) & m_1);
int c = (b & m_2) + ((b >> 2) & m_2);
int d = (c & m_4) + ((c >> 4) & m_4);
int e = (d & m_8) + ((d >> 8) & m_8);
int f = (e & m_16) + ((e >> 16) & m_16);
return f;
}
2. 快排改进算法
// 取中位数的快速排序 最坏情况下的时间复杂度为O(nlogn)
void quickSortMidian(int a[], int left, int right) {
int mid = left + ((right - left) >> 1);
int temp = a[mid];
int i = left, j = right;
if(j <= i) return; //这个真是不能忘 不然它跳不出来 会越界的
while(i < j) {
while (i < j && a[i] < temp) i++;
if(i < j) {
swap(a[i], a[j]);
j--;
}
while(i < j && a[j] > temp) j--;
if(i < j) {
swap(a[j], a[i]);
i++;
}
}
a[i] = temp;
quickSortMidian(a, left, i - 1);
quickSortMidian(a, i + 1, right);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
scanf("%d", &a[i]);
}
quickSortMidian(a, 0, n-1);
}
// 3路划分
void quick3way(int a[], int left, int right) {
if(right <= left) return;
int i = left, j = right, mid = left + 1;
int x = a[left];
while(mid <= j) {
if(a[mid] < x) {
swap(a[i], a[mid]);
i++; mid++;
} else if(a[mid] > x) {
swap(a[j], a[mid]);
j--;
cout << endl;
} else {
mid ++;
}
} // 区域划分为了 a[i...i-1] < x = a[i .. j] < a[j+1 .. right]
// i指向的是第一个等于x的位置 而j指向的是等于x的最后一个数
quick3way(a, left, i - 1);
quick3way(a, mid, right);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
scanf("%d", &a[i]);
}
quick3way(a, 0, n-1);
}
3. M*N的方格中，确定a到b的最近距离
typedef pair<int, int> PII;
// 假设障碍物为1 通路为0
const int N = 1000;
int n, m, res; //n行m列
int a[N][N], v[N][N], w[N][N];
int st[2], de[2];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //偏移量
queue<PII> q;
stack<PII> s;
void bfs() {
if (q.empty()) return; //队列为空时 返回
// 如果是1的话表示为障碍
// 如果是0的话表示为通路 进而判断是否已访问
// 如果没访问过 则更新w 并且加入队列 如果访问过就不管了
// 第一次遍历到b结点时停止
while(!q.empty()) {
int size = q.size(); //此时队列的长度
for (int i = 0; i < size; i++) {
PII p1 = q.front();
q.pop();
for(int k = 0; k < 4; k++) {
int x = p1.first + dx[k], y = p1.second + dy[k];
if(x >= 1 && x <= n && y >= 1 && y <= m && v[x][y] == -1 && a[x][y] == 0) {
v[x][y] = 0;
w[x][y] = w[p1.first][p1.second] + 1;
PII p2(x,y);
q.push(p2);
}
if (x == de[0] && y == de[1]) {
w[x][y] = res = w[p1.first][p1.second] + 1;
return;
}
}
}
}
}
void findroot(PII p, int root) {
if(root == 1) {
PII p1(st[0], st[1]);
s.push(p1);
return;
}
for(int k = 0; k < 4; k++) {
int x = p.first + dx[k], y = p.second + dy[k];
if(x >= 1 && x <= n && y >= 1 && y <= m && w[x][y] == root - 1) {
PII p1(x,y);
s.push(p1);
findroot(p1, root - 1);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
memset(v, -1, sizeof v); // 结点均未访问
scanf("%d%d", &st[0], &st[1]); //起点
scanf("%d%d", &de[0], &de[1]); //目的地
PII p1(st[0], st[1]);
PII p2(de[0], de[1]);
q.push(p1);
bfs();
findroot(p2, res);
while (!s.empty()) {
PII p = s.top(); s.pop();
cout << "(" << p.first << "," << p.second << ") " << endl;
}
return 0;
}
2018年真题
查找优化
问题： 已知一个含有n个元素的数组，我们需要找到其中的最大值和最小值，假设存在着一种需要比较2n次的方法，请问是否存在更优的算法，如果存在请给出思路说明，不存在的话请说明理由。
解：存在把数组两两一堆分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是n/2次；在前面分组的基础上，可以得出结论，最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最小值和最大值的查找分别需要比较n/2次和n/2次，这样就可以找到了，比较的次数为3n/2次。
找英雄数
解法：和找众数类似。对于当前元素，如果栈空，则入栈，如果栈不为空，则与栈顶元素进行比较，相等则入栈，反之则出栈栈顶元素，最后遍历一遍，count大于总个数的一半，返回正确结果。
// 输入 9
// 1 2 3 1 1 1 2 1 1
int n, m, hero, ans;
vector<int> a;
int st[1024];
void heroNumber() {
int top = -1;
for(int i = 0; i < a.size(); i++) {
// 如果栈空或元素相等 元素直接入栈
if(top == -1 || st[top] == a[i]) st[++top] = a[i];
else top--; // 如果有不同的直接抵消 进行下一个元素判断
}
if(top == -1) cout << "error" << endl;
else {
for(int i = 0; i < a.size(); i++) {
if(a[i] == st[top]) ++ans;
}
if (ans > (n / 2)) {
cout << st[top];
} else cout << "error" << endl;
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &m);
a.push_back(m);
}
heroNumber();
}
求出数组A和B的交集
// 如果运算数小，可以使用位运算来做
int n, m, max_a, max_b, ans;
int a[N], b[N];
int main() {
scanf("%d %d", &n, &m);
max_a = max_b = -10e9;
for(int i = 1 ; i <= n; i++) {
scanf("%d", &a[i]);
max_a = (a[i] > max_a ? a[i] : max_a);
}
for(int i = 1 ; i <= m; i++) {
scanf("%d", &b[i]);
max_b = (b[i] > max_b ? b[i] : max_b);
}
int len = max(max_b, max_a);
int sa[len], sb[len];
memset(sa, 0, sizeof sa);
memset(sb, 0, sizeof sb);
for(int i = 1; i <= n; i++) {
sa[a[i]] = 1;
}
for(int i = 1; i <= m; i++) {
sb[b[i]] = 1;
}
for(int i = 1; i <= n; i++) {
if (sa[a[i]] == sb[a[i]]) {
cout << a[i];
ans++;
}
}
if(ans == 0) cout << "无" <<endl;
return 0;
}
合并k重链表
题目：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
时间复杂度： O(Nlog k )，其中k 是链表的数目。弹出操作时，比较操作的代价会被优化到 O(logk) 。同时，找到最小值节点的时间开销仅仅为O(1)。最后的链表中总共有 N个节点。空间复杂度：创造一个新链表的需要O(n)开销
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if(len == 0) return NULL;
priority_queue<int, vector<int>, greater<int>> heap;
// 构造小根堆
ListNode *ans = new ListNode(0), *p = ans;
for(int i = 0; i < len; i++) {
ListNode *cur = lists[i];
while(cur) {
int x = cur->val;
heap.push(x);
cur = cur->next;
}
}
while(heap.size() > 0) {
int a = heap.top(); heap.pop();
ListNode *cur = new ListNode(a);
//cout << "a's value is" << a->val;
p->next = cur;
p = p->next;
}
return ans->next;
}
求序列中所有和为m的子集
题目：给定一个序列，设计算法求出元素和为M的所有子集合（让子集合里面的数据加起来刚好等于设定的值M）
思想：类似于全排列问题，对于一个位置上有取或不取几种两种选择，对每个位置深搜+剪枝，打印路径即为所有子集数。
int path[N], a[N];
int n, m, idx;
void fun(int k, int m) {
if(k>=n) return;
if (a[k] == m) {
path[idx++] = a[k];
for(int i = 0; i < idx; i++) {
cout << path[i] << " ";
}
cout << endl;
idx --; // 模拟的时候漏了这个
fun(k+1, m);
} else if(a[k] > m) {
fun(k+1, m);
} else {
// 取当前位
path[idx++] = a[k]; // 存路径
fun(k + 1, m - a[k]);
// 如果不取
idx --; //恢复现场
fun(k + 1, m);
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
fun(0, m);
return 0;
}
2019年真题代码
-
Prime算法
#include <iostream> #include <vector> #include <queue> using namespace std; const int N = 20; int dis[N][N], vset[N], e[N]; //dis存储邻接矩阵，vset数组记录结点访问，e记录最短距离 int n, m, sum; int a, b, w; int mins, idx; int minTree(int x) { vset[x] = 1; for(int i = 1; i <= n; i++) { if(i!=x && dis[x][i] < INT_MAX) { e[i] = dis[x][i]; } else e[i] = INT_MAX; } for(int i = 2; i <= n; i++) { mins = INT_MAX; for(int j = 1; j <= n; j++) { if(vset[j] == 0 && e[j] < mins) { mins = e[j]; idx = j; } } sum += mins; vset[idx] = 1; cout << "mins is " << mins << endl; for(int j = 1; j <= n; j++) { if(vset[j] == 0 && dis[idx][j] < e[j]) { e[j] = dis[idx][j]; } } } return sum; } int main() { scanf("%d%d", &n, &m); memset(vset, 0, sizeof vset); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i!=j) dis[i][j] = INT_MAX; else dis[i][j] = 0; } } while(m--) { scanf("%d%d%d", &a, &b, &w); dis[a][b] = dis[b][a] = w; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cout << dis[i][j] << " "; } cout << endl; } // 从第一个岛屿开始 minTree(1); cout << sum; } -
略
-
#include <vector> #include <queue> int n, k, res; int main() { //升序 greater priority_queue<int, vector<int>, greater<int>> heap; //降序 priority_queue <int,vector<int>,less<int> >q; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &k); heap.push(k); //建立小根堆 } while(heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); res += (a + b); heap.push(a+b); } cout << heap.top(); }