2019百度CPP笔试编程题

in 刷题 with 0 comment

写在前面

真心吐槽一下百度的线上笔试用的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)

现在题目增加了字典序最小的约束，仍可以考虑贪心的做法。
每个位置以字典序枚举字符是否满足符合条件：

  1. 字符的前k个里是否存在与之重复的字符。
  2. 字符后面剩下的位置是否能够保证满足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]

代码比较复杂，黑盒测试一些简单的例子，不保证完全正确。

#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

← → ↓ ↑
Comments are closed.