拼多多学霸批算法工程师在线笔试 20190728 场
1. 题目一
给定两个数组
A和B，其中数组A是几乎严格升序排列的，几乎的定义是只需改变其中一个数，即可满足完全升序排列。你的任务是从A中找到这个数组，并从数组B中选取一个数将其代替，使得A是严格升序排列的，请找出 B 中满足要求的最大数字，并输出有序数组，如不存在则输出 NO。
思路：从数组 A 中找到不满足完全升序的数字，也即 A[i] <= A[i-1]。此时，如果 A[i] 是数组 A 的最后一个元素，则只需要从 B 中找到大于 A[i-1] 的最大元素即可；如果 A[i] 不是数组 A 的最后一个元素，则需要从 B 中找到大于 A[i-1] 并且小于 A[i+1] 的最大元素。
只通过 70% 的原因是，可以替换 A[i] 也可以替换 A[i-1]，当时没有考虑到。
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
vector<int> A;
vector<int> B;
int temp;
char ch;
while (scanf("%d", &temp))
{
A.push_back(temp);
ch = getchar();
if (ch == '\n') break;
}
while (scanf("%d", &temp))
{
B.push_back(temp);
ch = getchar();
if (ch == '\n') break;
}
int num1 = 0;
int num2 = 0;
int pos = -1;
for (unsigned int i = 1; i < A.size(); i++)
{
if (A[i] <= A[i-1])
{
pos = i;
num1 = A[i-1];
if ((i + 1) < A.size())
{
num2 = A[i+1];
}
else num2 = -1;
break;
}
}
int data = num1;
for (unsigned int i = 0; i < B.size(); i++)
{
if (B[i] > num1)
{
if (num2 == -1)
{
if (B[i] > data)
data = B[i];
}
else{
if (B[i] < num2)
{
if (B[i] > data)
data = B[i];
}
}
}
}
if (data == num1)
{
cout << "No";
}
else
{
for (unsigned int i = 0; i < A.size(); i++)
{
if (i != pos) cout << A[i] << " ";
else cout << data << " ";
}
}
return 0;
}
2. 题目二
给定一个字符串数组，所有字符均为大写字母。请问，给定的字符串数组是否能通过更换数组中元素的顺序，从而首尾相连，形成一个环。
思路：所谓首尾相连能形成一个环，也即字符串数组中字符串的首尾元素正好都出现了偶数次。
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
vector< vector<char>> data;
vector<char> temp;
char ch;
while(1){
ch = getchar();
if (ch == ' ')
{
data.push_back(temp);
temp.clear();
}
else if (ch == '\n')
{
data.push_back(temp);
break;
}
else
{
temp.push_back(ch);
}
}
int num[26] = {0};
for (unsigned int i = 0; i < data.size(); i++)
{
char start = data[i][0];
int pos = start - 'A';
num[pos]++;
char endch = data[i][data[i].size()-1];
pos = endch - 'A';
num[pos]++;
}
bool flag = true;
for (int i = 0; i < 26; i++)
{
if (num[i] % 2 != 0)
{
flag = false;
break;
}
}
if (flag) cout << "true";
else cout << "false";
return 0;
}
3. 题目三
现在一共有
N个待执行的任务，每个任务需要 Pi 的时间完成执行。同时任务之间可能会有一些依赖关系，比如任务1可能依赖任务 2 和任务 3 ，那么任务 1 必须等任务 2 和任务 3 执行完成后才能开始执行。为了最小化任务的平均返回时长，请安排所有任务的执行顺序。假设在零时刻，所有 N 个任务已到达系统。
思路：我们用一个二维布尔数组来表示任务之间的依赖关系，比如 flag[i][j] 表示任务 j 的执行依赖于任务 i，同时统计每一个任务 i 当前依赖的任务数量 cnt[i]。当某一个任务依赖的任务数量为 0 时，当前任务可以被执行，但同时为了最小化所有任务的执行时间，我们需要先执行花费时间最短的任务。然后，随着任务的执行，我们更新数组 flag、cnt 和可以执行的任务直到所有任务都执行完毕即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;
bool compare(vector<int> a, vector<int> b) {return a[0] < b[0];}
int main()
{
int N, M;
cin >> N >> M;
vector<int> time(N);
for (int i = 0; i < N; i++)
{
cin >> time[i];
}
bool flag[N][N];
int cnt[N] = {0};
for (int i = 0; i < N; i++)
{
cnt[i] = 0;
for (int j = 0; j < N; j++)
flag[i][j] = false;
}
int data[M][2];
for (int i = 0; i < M; i++)
{
cin >> data[i][0] >> data[i][1];
cnt[data[i][1]-1]++;
flag[data[i][0]-1][data[i][1]-1] = true;
}
vector<int> temp;
vector<vector<int> > datab;
for (int i = 0; i < N; i++)
{
if (cnt[i] == 0)
{
//cout << i << endl;
temp.push_back(time[i]);
temp.push_back(i);
datab.push_back(temp);
temp.clear();
}
}
sort(datab.begin(), datab.end(), compare);
vector<int> result;
while (!datab.empty())
{
int task = datab[0][1];
result.push_back(task);
datab.erase(datab.begin());
for (int i = 0; i < N; i++)
{
if (flag[task][i])
{
flag[task][i] = false;
cnt[i]--;
if (cnt[i] == 0)
{
temp.push_back(time[i]);
temp.push_back(i);
datab.push_back(temp);
temp.clear();
}
}
}
sort(datab.begin(), datab.end(), compare);
}
for (int i = 0; i < N; i++)
cout << result[i] + 1 << ' ';
return 0;
}
获取更多精彩，请关注「seniusen」!
