拼多多2021校招笔试真题

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;
}

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;
}

3、多多的骰子组合

【题目描述】

给出N个骰子（N≤1,000）, 要求将这个骰子进行分类

两个骰子属于同类的定义是：

将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等

【解题思路】
两两枚举每个骰子是否同类
因为骰子的变换方向只有3个：上下、左右和前后，并且每个方向翻转4次后会回归原本的状态
即最多进行4*4*4=64次旋转即可遍历到所有状态
判断同类后，进行归类的方法则可以自由选择：
	选择其中一个骰子作为代表
	最小表示法，以同类骰子最小的编号作为代表
	并查集
	等等
时间复杂度: O(N^2)

优化一：
实际