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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
}
给一个长度不超过1E6的字符串S（只包含小写字母’a’~‘z’）和正整数k，求长度和S相同，字典序不超过S的，每个字符出现次数都是k的整数倍的字符串 之中 字典序最大的那个。
先二分答案求和S相同的位数。然后再贪心。
稍微有些复杂，见代码。
样例已经通过。并且自测了k = 2，len(s) = 4的全部数据和k = 2, len(s) = 6的部分数据。
class Solution用于求解。 namespace BrouteFource中封装了暴力求解的函数。
#include <bits/stdc++.h>
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) { // 全a
return 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 < t
if (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 <bits/stdc++.h>
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 <bits/stdc++.h>
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
前言 本文是橙子出于兴趣爱好对Java官方教程的尝试翻译几乎每日更新感兴趣的朋友...
jsp中让图片在div中居中显示，如上图 例子： 复制代码 代码如下: //CSS文件 styl...
文本整理仅仅是用记事本肯定是不行的，推荐使用notepad++ 换行 \n 空行^$ 去除所...
索引类似大学图书馆建书目索引，可以提高数据检索的效率，降低数据库的IO成本。M...
前两天在做一个站内版的企搜引擎，发现某些站点可以链接站点内容。。 奇怪之下看...
有时需要在系统中添加另一块磁盘。这就是 逻辑卷管理 Logical Volume Management...
今天给大家呈现一个原始的Ajax请求过程，虽然jquery的ajax要比原始的写法容易得...
通用 复制代码 代码如下: (:[a-z0-9!#$%'*+/=^_`{|}~-]+(:\.[a-z0-9!#$%'*+/=^_`...
python实现ROA算子边缘检测算法 讲解 略 代码 import numpy as np import cv2 as...
最近在仿造一个书城的网站： http://www.yousuu.com ,UI直接拿来用，前端后端自...
