写在前面
真心吐槽一下百度的线上笔试用的AMCAT平台,竟然禁止使用本地IDE,必须线上提交代码,而且切到下一题返回不到上一题,且编码环境非常不友好,总的来说还是自己太菜了。
第一题
题目原型大概是:给定一个正整数数组arr,每次选择数组中的一个数-K, 其余的数-m, 问需要几次才能让所有数均小于等于0。
这题条件给的数组长度达到了$10^9$,也不知道测试数据怎么把数组传进来了(笔试只要实现接口,接口参数为vector
解决方法:用一个优先队列q去维护最大值,将最大值减(K-m),然后push回队列里。这样保证了每次操作后数之间的差值和题中操作等价,但整体的每个值也增加了m。 如果答案计数为ans, 则要保证每次队列中的值大于ans*m,即q.top>ans*m。
样例:
4 7 8 2 5
3 1
out:
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int K, int m) {
int ans = 0, cur;
priority_queue<int> q;
for(int v : arr) {
q.push(v);
}
while(!q.empty()) {
cur = q.top();
q.pop();
if(cur <= ans * m) break;
cur -= (K-m);
q.push(cur);
++ ans;
}
return ans;
}
int main() {
vector<int> arr;
int n, x, K, m;
while(cin >> n) {
arr.clear();
while(n--) {
cin >> x;
arr.push_back(x);
}
cin >> K >> m;
cout << solve(arr, K, m) << endl;
}
}
某大佬给出的解法:二分ans, 区间[0, max(arr[i])]。由于每个数每次一定要-m(-K相当于-(K-m)-m, k>m)。把所有数-ans*m,将小于等于0的排除。剩下的数总共要减ans*(K-m)。
$$ \sum \lceil \frac{max(arr[i]-ans*m, 0)}{K-m} \rceil \leq ans $$
注意每一下除完结果要取ceil.
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int K, int m) {
int l = 0, r = 1e9; // r看数据范围
int ans, cnt = 0, v2;
while(l < r) {
ans = l + ((r-l) >> 1);
cnt = 0;
for(int v: arr) {
v2 = v - ans * m;
if(v2 > 0) {
cnt += ceil(v2 / (K - m + 0.0));
}
}
// 能保证减为0,但不是不确定是最少次数,ans可以更小。
if(cnt <= ans) {
r = ans;
}
else {
l = ans + 1;
}
}
return l; // or r, not ans
}
int main() {
vector<int> arr;
int n, x, K, m;
while(cin >> n) {
arr.clear();
while(n--) {
cin >> x;
arr.push_back(x);
}
cin >> K >> m;
cout << solve(arr, K, m) << endl;
}
}
第二题
题目意思是给定一个字符串s,要求任意两个相同字符之间的间隔大于等于k。(abbba, 两个a的间距为3)如果不存在符合条件的解输出-1,如果存在,输出字典序最小的。
思路:假设题目不要求字典序,则可以按照词频排序,然后取最高频率的字符作为隔板。
隔板间距确定为:(字符串长度-同为最高频字符的字符种数)=(隔板间距+1)*(最高频字符的频数-1)
如:abcfabcfabceab
摆放规则: a ___ a ___ a ___ a
,先不考虑间距
由于b和a同词频率,所以只有 ab__ ab__ ab__ ab
。
而剩下的字母一定可以插空到上面序列中,继续按照词频从高到低。 abc_abc_ abc_ ab
->abcfabcfabc_ab
->abcfabcfabceab
一旦最高词频的字符数确定,间隔也就可以确定。剩下的字符按照词频大小插入即可。时间复杂度为O(n)
现在题目增加了字典序最小的约束,仍可以考虑贪心的做法。
每个位置以字典序枚举字符是否满足符合条件:
- 字符的前k个里是否存在与之重复的字符。
- 字符后面剩下的位置是否能够保证满足k间距的定义。(不是原问题的子问题,因为这里可以不考虑字典序,因为只要满足k间隔,余串必然能找一组字典序最小的解)
约束1,可以用一个数组存储当前要操作的字符前一次出现的位置,进行O(1)比较。
约束2,可以直接判断 (最高频字符的频数-1)*(k+1)+同为最高频字符的字符种数 <= 剩余串的长度
。需要求的两个变量可以每次通过暴力统计得到。但是我们可以借助三个数组结构来实现时间复杂度O(1)的维护。
Pair数组A
: 当前出现所有字符按照频数排序(同时存频数freq和字母ch),如bacde…, 则b出现的次数>a出现的次数。数组B
:B[i]表示出现频数为i的最后一个元素在A数组中的位置。我们假设b出现4次,a和c出现3次,d出现2次,e出现1次。则B[4]=0, B[3]=2, B[2]=3数组C
:C[ch]表示字符ch在A中位置为C[ch]
- 首先预处理得到这三个数组初始值。
- 取一个字母ch
- 取最高频率A[0].freq以及个数B[A[0].freq]+1。(如果ch频率是最高的,个数需要减1)计算是否满足,偌满足,执行3,否则执行2
- 先用i=C[ch]找到其在A中的位置,得到A[i].freq,然后用freq在中找到A数组这个freq下的最后一个元素并交换, A[i].freq--, A数组更新完毕。同时在交换时候更新C数组两个字符的位置值。
- B[A[i].freq+1]--,B数组更新完毕。
代码比较复杂,黑盒测试一些简单的例子,不保证完全正确。
#include<bits/stdc++.h>
using namespace std;
struct node {
char ch;
int freq;
node(){}
node(int a, char b):freq(a),ch(b){}
bool operator<(const node& other) const {
return freq > other.freq;
}
};
void reduceAndSwap(vector<node>& A, int* B, int* C, int i, int j) {
// update B
--B[A[i].freq];
// update A
--A[i].freq;
swap(A[i].ch, A[j].ch);
swap(A[i].freq, A[j].freq);
// update C
C[A[i].ch] = i;
C[A[j].ch] = j;
}
string solve(string& str, int k) {
const int char_num = 256;
int cnt[char_num]={0};
vector<char> v_chs;
vector<node> A;
int B[str.size()]={0}; // or unodered_map
int C[char_num] = {0};
int last_see[char_num];
memset(last_see, -1, sizeof(last_see));
for(char ch : str) {
++cnt[ch];
}
for(int i = 0; i < char_num; ++i) {
if(cnt[i] != 0) {
A.push_back(node(cnt[i], char(i)));
v_chs.push_back(char(i));
}
}
sort(A.begin(), A.end());
for(int i = 0; i < A.size(); ++i) {
C[A[i].ch] = i;
B[A[i].freq] = i;
}
// trick
int i = A[A.size()-1].freq;
int iter_freq = i-1;
while(iter_freq) {
B[iter_freq] = B[i];
--iter_freq;
}
char res[str.size()+1];
res[str.size()] = 0;
int max_freq=-1, max_freq_cnt = 1;
for(int i = 0; i < str.size(); ++i) {
for(char ch : v_chs) {
if(last_see[ch] != -1 && last_see[ch] + k >= i) continue;
if(A[C[ch]].freq == 0) continue;
max_freq = A[0].freq;
max_freq_cnt = B[A[0].freq]+1;
if(A[C[ch]].freq == max_freq) {
--max_freq_cnt;
if(max_freq_cnt == 0) {
max_freq = A[1].freq;
max_freq_cnt = B[A[1].freq]+1; // ch数目少1后,还是属于最多的字符。
}
}
if(max_freq == 0 || (max_freq-1)*(k+1) + max_freq_cnt <= str.size()-i-1) {
res[i] = ch;
last_see[ch] = i;
reduceAndSwap(A, B, C, C[ch], B[A[C[ch]].freq]);
break;
}
}
if(res[i] == 0) {
return "-1";
}
}
return string(res);
}
int main() {
string str;
int k;
while(cin >> str) {
cin >> k;
cout << solve(str, k) << endl;
}
}
第三题
给定一个01字符串, 允许对该字符串进行k次修改(将一位0改成1),求k次修改后的最长全1的字串长度。字符串最大长度10^5
思路:由于修改的k必定是集中在一个区间的,使用一个滑动窗口来选择字串。
滑动窗口右边界扩张的条件是,当前窗口内的1的个数+k>=窗口大小,因为右边界的右边可能为1。
否则,左边界右移。
未测试,欢迎指出问题。
#include<bits/stdc++.h>
using namespace std;
// 100100110 2
// 100000110 2
int solve(string& str, int k) {
int beg= 0, end = 1;
int one_cnt = str[0] - '0';
int max_ones = one_cnt;
while(end <= str.size()) {
if(one_cnt + k >= end - beg) {
++end;
if(end <= str.size()) {
one_cnt += (str[end-1] - '0');
max_ones = max(max_ones, one_cnt+min(k, end-beg-one_cnt));
}
}
else {
one_cnt -= str[beg++] - '0';
}
}
return max_ones;
}
int main() {
string str;
int k;
while(cin >> str) {
cin >> k;
cout << solve(str, k) << endl;
}
}
本文由 shinelin 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Apr 6, 2019 at 07:07 am