拼多多总共4道编程题
1.字符串解码
输入: 3a3b2c
输出: aaabbbcc
用python做很方便
s = input()
l = len(s)
t = 0
ans = ""
for i in range(l):
if (s[i] >= 'a' and s[i] <= 'z') or (s[i] >= 'A' and s[i] <= 'Z'):
num = int(s[t:i])
t = i + 1
for _ in range(num):
ans += s[i]
print(ans)
2.T 个关卡，每个关卡 n 个敌人，每个敌人的耐受值已知。
每一关是独立的，你需要打败所有敌人，现在有两种操作：选择两个敌人，每个耐受值 -1。选择一个敌人，直接消灭。求打败当前关卡所有敌人所需要操作的最小次数。（当前关卡的操作不会影响到之后的关卡）
#define _NOT_SECURE_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<map>
#include<string>
using namespace std;
int t, n, ans = 0;
int d[1005][205] = { 0 };
int f(int a, int len)
{
if (len == 1) return 1;
if (len % 2 == 0)
{
if (a == 1) { return len / 2; }
return min((len / 2) * a, len);
}
if (a == 1)
{
return min(len, len / 2 + 1);
}
return len;
}
int main()
{
cin >> t >> n;
for (int i = 0; i < t; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> d[i][j];
}
}
for (int i = 0; i < t; ++i)
{
sort(d[i], d[i] + n);
ans = 0;
for (int j = 0; j < n; ++j)
{
int t = d[i][j];
int k = j;
while (k < n && t == d[i][k]) { k++; }
ans += f(t, k - j);
j = k - 1;
}
cout << min(ans, n) << endl;
}
return 0;
}
/*
3 3
1 2 1
2 3 2
1 2 3
2
3
3
*/
3.3 种活动，n 个员工每人可以选想去参加的活动志愿，但最终只能去一个。
每个活动有人数限制以及单位价格。问能否安排所有的人去参加活动，如果可以，求出最少花费，如果不行，输出最多可以安排多少人去参加。(n <= 100)。
正确而简单的思路是「最小费用流」。源点向每个人连流量 1，费用 0 的边，每个人向志愿连流量 1 费用 0 的边，每个志愿向汇点连流量为人数限制，费用为单位价格的边，然后直接跑模板即可。
参考大佬: https://www.nowcoder.com/discuss/464538407297994752?sourceSSR=search
也可以用dp，但是我不会想不出来。个人觉得用dfs也是可以拿一些分的，但是没写完。
4.求一组数据的平均数和中位数。
直接暴力，能过80%
n = int(input())
r = [int(i) for i in input().split(' ')]
avg, med = [], []
s = 0
l = len(r)
for i in range(l):
s += r[i]
avg.append(int(s / (i + 1) + 0.5))
t = int(i / 2)
p = sorted(r[:i + 1])
if i % 2 == 0:
med.append(p[t])
else:
med.append(int((p[t] + p[t + 1]) / 2 + 0.5))
for i in range(l):
if i != l - 1:
print(avg[i], end = " ")
else:
print(avg[i], end = "\n")
for i in range(l):
print(med[i], end = " ")
使用二分，acn = int(input())
r = [int(i) for i in input().split(' ')]
mean = []
avg, med = [], []
s = 0
l = len(r)
def find(a, t):
r = len(t)
if r == 0:
t.append(a)
return
if a >= t[r - 1]:
t.append(a)
return
if a <= t[0]:
t.insert(0, a)
return
l = 0
while l <= r:
mid = int((l + r) / 2)
if a >= t[mid]:
if mid < r - 1 and a <= t[mid + 1]:
t.insert(mid + 1, a)
return
l = mid + 1
else:
if mid >= 1 and a >= t[mid - 1]:
t.insert(mid, a)
return
r = mid - 1
return
for i in range(l):
s += r[i]
avg.append(int(s / (i + 1) + 0.5))
find(r[i], mean)
t = int(i / 2)
if i % 2 == 0:
med.append(mean[t])
else:
med.append(int((mean[t] + mean[t + 1]) / 2 + 0.5))
for i in range(l):
if i != l - 1:
print(avg[i], end = " ")
else:
print(avg[i], end = "\n")
for i in range(l):
print(med[i], end = " ")
关注下方《学姐带你玩AI》🚀🚀🚀
算法工程师万能简历公式+200多个简历模板（中英文）
回复“简历”轻松获取！
码字不易，欢迎大家点赞评论收藏！