1.14 拼多多2024校招笔试真题
1.14.1 多多的数字组合
【题目描述】
给定一个整数N,求一个最小值,要求:
1)各个数位的数字之和等于N
2)各个数位的数字各不相同
【解题思路】
由于每个数字0~9只能用一次,且要求为最小值,所以优先保证数字的位数最少。
同时对于相同的位数,由于和均为N的情况下,位数越小数字应该越大,因此可以使用贪心的方法。
从低位到高位,从9~0倒序依次枚举可以使用的数字,直到满足和等于N,否则无解。
考虑点: 数位,贪心
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int ans = 0, p = 1;
for (int i = 9; i > 0; i--) {
if (n >= i) {
n -= i;
ans += p * i;
p *= 10;
}
}
if (n > 0) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
1.14.2 多多的字符变换
【题目描述】
给定两个长度相同的字符串,支持两种变换方式:
1)交换任意两个相邻的字符,代价为0。
2)将任意一个字符a修改成字符b,代价为 |a - b|(绝对值)。
要求将两个字符串变成一样的字符串最小需要的代价之和。
【解题思路】
从两种变换方式的组合来看,由于方式(1)的代价为0,即可以无代价多次重复使用。
于是可以通过排序的方式,先将两个字符串变成有序字符串。
在排序后两个字符串对应位置的字符距离分别为最小值,且任意交互两组位置后的差值会大于等于原差值,因此排序后的差值即为最小值。
考虑点:字符串,比较,贪心
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
string X, Y;
while (cin >> N) {
cin >> X >> Y;
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
int ans = 0;
for (int i = 0; i < N; i++) {
ans += abs(X[i] - Y[i]);
}
cout << ans << endl;
}
return 0;
}
1.14.3 多多的骰子组合
【题目描述】
给出N个骰子(N≤1,000), 要求将这个骰子进行分类
两个骰子属于同类的定义是:
将其中一个骰子通过若干次上下、左右或前后翻转后,其与另一个骰子对应的6面数字均相等
【解题思路】
两两枚举每个骰子是否同类
因为骰子的变换方向只有3个:上下、左右和前后,并且每个方向翻转4次后会回归原本的状态
即最多进行4*4*4=64次旋转即可遍历到所有状态
判断同类后,进行归类的方法则可以自由选择:
- 选择其中一个骰子作为代表
- 最小表示法,以同类骰子最小的编号作为代表
- 并查集
- 等等
时间复杂度: O(N^2)
优化一:
实际上由于骰子的同构变换只有24种,6面骰子最多的状态为6!=720
于是本质不同
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
牛客独家出品,理工科求职必备攻略,适合岗位: 软件开发、数据库分析、软件测试、前端后端开发