拼多多2021-04-09春招笔试 服务端开发 解题报告 Apare_xzc

拼多多2021-04-09春招笔试 服务端开发 解题报告 Apare_xzc

2021-04-09 15:00-17:00

2小时4道编程题
100% 100% 46.7% 100%
第三题有两个case没写完

题目描述见代码注释

第一题：尖峰数组

差不多叫这个名字。
求一个先递增在递减的最大连续子数组的长度。简单DP

//拼多多2021-04-09 15:00 -17:00 
//春招服务端开发笔试题
//时长2小时，编程题4道 * 25分/道 
//
//第一题，给一个长度不超过200的数
//组，求最长的尖峰数组B的长度len
//B0 < B1 < B2 < Bk > B[k+1] > B[k+2] > B[len-1] /*
简单DP, 从左到右维护左端最大递增长度L[i]，
从右到左维护右端最大递减长度R[i]，然后取
ans = max(ans, L[i] + R[i] + 1)即可
L[i] = (i==0   || a[i]<=a[i-1]) ? 0 : L[i-1]+1
R[i] = (i==n-1 || a[i]<=a[i-1]) ? 0 : R[i+1]-1 
*/ 
#include 
using namespace std;
int a[200];
int L[200], R[200];
int main(void) {int n;cin>>n;for (int i = 0; i < n; ++i)cin >> a[i];L[0] = 0;for (int i = 1; i < n; ++i) {if (a[i] > a[i-1]) {L[i] = L[i-1] + 1;} else {L[i] = 0;}}R[n-1] = 0;for (int i = n-2; i >=0; --i) {if (a[i] > a[i+1]) {R[i] = R[i+1] + 1;}  else {R[i] = 0;}}int ans = 0;for (int i = 1; i < n-1; ++i) {if (L[i] && R[i]) {ans = max(ans, L[i] + R[i] + 1);}}cout << ans << endl;return 0;
} 

第二题 快乐数

从小到大暴力check

//第二题，一个数十进制形式如果除了0,1,只有最多一个其他数字N，
//那么就就是快乐数。比如 3, 120, 1777都是快乐数。现在输入一个
//数字x,求一个最小的y，是x的正整数倍,并且是快乐数。
//input:3
//output:3
//
//input: 235
//output:1410
//数据范围x<=200 
/*
从小到大暴力尝试即可。 
*/ 
#include 
using namespace std;
int main(void) {long long x;cin >> x;for (int i = 1; i < 1000000; ++i) {long long y = x * i;long long yy = y;set<int> st;while (y>0) {int d = y % 10;y /= 10;if (d > 1) {st.insert(d);}} if ((int)st.size() < 2) {cout<<yy<<endl;return 0;}}cout << -1 << endl;return 0;
} 

第三题：多多的字符串II

给一个长度不超过1E6的字符串S（只包含小写字母’a’~‘z’）和正整数k，求长度和S相同，字典序不超过S的，每个字符出现次数都是k的整数倍的字符串 之中 字典序最大的那个。
先二分答案求和S相同的位数。然后再贪心。
稍微有些复杂，见代码。
样例已经通过。并且自测了k = 2，len(s) = 4的全部数据和k = 2, len(s) = 6的部分数据。
class Solution用于求解。 namespace BrouteFource中封装了暴力求解的函数。

#include 
using namespace std;const int M = 1E6+10;namespace BrouteFource {bool HasPreStr(string& s) {int len = s.length();assert(len > 0);bool flag = false;for (int i = 0; i < len; ++i) {if (s[i] != 'a') {flag = true;break;}}if (!flag) { // 全areturn false;}if (s[len-1] != 'a') {s[len-1]--;return true;} else {int index = len-1;for (;index >= 0; --index) {if (s[index] == 'a') {s[index] = 'z';} else {break;}}assert(index >= 0);s[index]--;return true;}}void PrintBtoS(string s) {cout << s << endl;while (HasPreStr(s)) {cout << s << endl;}}bool check(string s, int k) {unordered_map<char,int> mp;for (auto x : s) {mp[x]++;}for (auto pr : mp) {if (pr.second % k > 0) {return false;}}return true;}string GetAns(string s, int k) {int len = s.length();if (len % k > 0) {return "-1";}string ans = "-1";while (1) {if (check(s, k)) {ans = s;break;}if (!HasPreStr(s)) {break;}}return ans;}
}class Solution {
private:static const int N;int cnt[300];int bucket[300];int k, t, len;char * s;char * p;int getRight();bool check(int mid);
public:Solution();~Solution();bool Input();string solve();int GetK() {return this->k;}string GetString() {return string(s);}
};
const int Solution::N = 1E6+10;Solution::Solution() {p = new char[N];s = new char[N];
}
Solution::~Solution() {delete []p;delete []s;
}
bool Solution::Input() {if (scanf("%d%s", &k, s) == EOF) {return false;}len = strlen(s);for (int i = 0; i < len; ++i) {assert(islower(s[i]));}t = len / k;return true;
}bool Solution::check(int mid) {memset(cnt, 0, sizeof(cnt));for (int i = 0; i <= mid; ++i) {p[i] = s[i];cnt[(int)s[i]]++;}memset(bucket, 0, sizeof(bucket));int curSumT = 0;for (int ch = 'a'; ch <= 'z'; ++ch) {curSumT += cnt[ch] / k + (cnt[ch] % k != 0);if (curSumT > t) {return false;}if (cnt[ch] % k > 0) {bucket[ch] += k - cnt[ch] % k;}}if (curSumT < t) {bucket['a'] += (t - curSumT) * k;}int index = mid + 1;for (int ch = 'a'; ch <= 'z'; ++ch) {while (bucket[ch]--) {p[index++] = (char)ch;}}p[len] = 0;return strcmp(p, s) <= 0;
}
int Solution::getRight() {set<char> st;int R = len;for (int i = 0; i < len; ++i) {st.insert(s[i]);if ((int)st.size() > t) {i = R;break;}}return R;
}
string Solution::solve() {if (len % k) {return "-1";}if (k == 1) {return string(s);}int L = -1;int R = getRight();while (R - L > 1) {int mid = (R + L) >> 1;if (check(mid)) {L = mid;} else {R = mid;}}if (L == len - 1) {return string(s);}if (L == -1) {assert(s[0] != 'a');memset(bucket, 0, sizeof(bucket));bucket[s[0]-1] = k - 1;bucket['z'] = (t-1) * k;int smallch = (char)(s[0] - 1);p[0] = smallch;int index = 1;while (bucket['z']--) {p[index++] = 'z';}while (bucket[smallch]--) {p[index++] = smallch;}assert(index == len);p[len] = 0;return string(p);}memset(bucket, 0, sizeof(bucket));memset(cnt, 0, sizeof(cnt));for (int i = 0; i <= L; ++i) {p[i] = s[i];cnt[s[i]]++;}int curSumT = 0;for (int ch = 'a'; ch <= 'z'; ++ch) {curSumT += cnt[ch] / k + (cnt[ch] % k != 0);if (cnt[ch] % k > 0) {bucket[ch] += k - cnt[ch] % k;}}assert(curSumT <= t);int index = L + 1;for (;index < len; ++index) {assert(s[index] != 'a');int smallch = s[index] - 1;if (curSumT == t) {bool flag = false;for (int ch = smallch; ch >= 'a'; --ch) {if (bucket[ch] > 0) {--bucket[ch];p[index++] = ch;for (ch = 'z'; ch >= 'a'; --ch) {while (bucket[ch]--) {p[index++] = (char)ch;}}assert(index == len && 1 == 1);p[len] = 0;return string(p);}}assert(flag);} else { // curSumT < tif (bucket[smallch] > 0) {p[index++] = (char)smallch;bucket[smallch]--;bucket['z'] += max(0, t - curSumT) * k;for (int ch = 'z'; ch >= 'a'; --ch) {while (bucket[ch]--) {p[index++] = (char)ch;}}assert(index == len && 2 == 2);p[len] = 0;return string(p);} else { //bucket[smallch] == 0++curSumT;bucket[smallch] = k - 1;bucket['z'] += max(0, (t - curSumT)) * k;p[index++] = smallch;for (int ch = 'z'; ch >= 'a'; --ch) {while (bucket[ch]--) {p[index++] = (char)ch;}}assert(index == len && 3 == 3);p[len] = 0;return string(p);}}}return "-1";
}int main(void) {freopen("in_k2_len6", "r", stdin);freopen("out_k2_len6", "a", stdout);Solution * pSol = new Solution();while(pSol->Input()) {string ans = pSol->solve();//std::cout << ans << "\n";string bfans = BrouteFource::GetAns(pSol->GetString(), pSol->GetK());//Gstd::cout << bfans << "\n";assert(ans == bfans);cout<<",\n    {'k':"<<pSol->GetK()<<",'s':'"<<pSol->GetString()<<"','ans':'"<<ans<<"'}";}delete pSol;return 0;
}

还写了个makedata.cpp 用来按照字典序顺序生成测试样例

#include 
using namespace std;bool HasNextStr(string& s) {string tmp = s;int len = s.length();if (len == 0) {return false;}bool flag = false;for (int i = 0; i < len; ++i) {assert(islower(s[i]));if (s[i] < 'z') {flag = true;break;}}if (!flag) {return false;}int i = len - 1;for (; i >= 0; --i) {if (s[i] == 'z') {s[i] = 'a';} else {break;}}assert(i>=0 && 1 == 1);//assert(i >= 0);s[i]++;return true;
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(0);freopen("in_k2_len6", "w", stdout);int k = 2;string s = "aaaaaa";do {cout << k << "\n" << s << "\n";} while(HasNextStr(s));return 0;
}

第四题：多多的数字猜想

求N!的M进制形式末尾有多少个0.

//求N! 的 M进制形式末尾有多少个0
//2 <= N,M <= 1E9/*
将M分解质因数，M = d1^x1 * d2^x2 * ... dk^xk 
然后求N！内每个质因数的个数pd1, pd2, pd3
然后答案为min(pdi/xi) 
*/ 
#include 
using namespace std;
int main(void) {int n,m;cin>>n>>m;vector<pair<int,int> > vd;int x = m;for (int i = 2; i <= x / i; ++i) {int cnt = 0;while (x % i == 0) {++cnt; x /= i;}if (cnt > 0) {vd.push_back(make_pair(i,cnt));}}if (x > 1) {vd.push_back(make_pair(x,1));}long long res = 1E13;for (auto pr : vd) {int d = pr.first;int c = pr.second;int y = n;long long tot = 0;while (y > 0) {y /= d;tot += y;}res = min(res, tot /  c);}cout << res << endl;	return 0;
} 

笔试过了，Good Luck。

2021.4.14 0:17

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！