10.16 腾讯笔试题解

10.16 腾讯笔试

心得：笔试题虽然看起来多了一点，但是每道题其实并不是很困难，掌握方法很快就能 AK

T1 链表结点的异或

模拟就行，注意一个是正向一个是反向

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a ListNode类 
     * @param b ListNode类 
     * @return ListNode类
     */
    ListNode* xorList(ListNode* a, ListNode* b) {
        // write code here
        vector<int> arr;
        vector<int> ans;
        while (a) {
            arr.push_back(a->val);
            a = a->next;
        }
        reverse(arr.begin(), arr.end());
        int i = 0;
        while (b && i < arr.size()) {
            ans.push_back(arr[i]^b->val);
            b = b->next; ++i;
        }
        while (b) {
            ans.push_back(b->val);
            b = b->next;
        }
        while (i < arr.size()) {
            ans.push_back(arr[i++]);
        }
        ListNode* hd = new ListNode(0);
        ListNode* p = hd;
        for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
            p->next = new ListNode(*it);
            p = p->next;
        }
        while (hd->next && hd->next->val == 0) hd = hd->next;
        if (hd->next == 0) {
            return new ListNode(0);
        }
        return hd->next;
    }
};

T2 修改 K 次数组求最小值

我们只需要贪心的修改每次贡献最大的一个元素就行。由于 K 的范围很小，用优先级队列搞定。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (auto& e : arr) cin >> e;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; ++i) {
        pq.emplace(arr[i] - __builtin_popcount(arr[i]), __builtin_popcount(arr[i]));
    }
    ll ans = 0;
    for (auto e : arr) ans += e;
    while (k--) {
        auto top = pq.top(); pq.pop();
        ans -= top.first;
        pq.emplace(top.second - __builtin_popcount(top.second), __builtin_popcount(top.second));
    }
    cout << ans << endl;
    return 0;
}

T3 队列模拟

由于数据的特殊性，[1, n] 的排列，因此我们直接贪心。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, e; cin >> n;
    deque<int> arr;
    for (int i = 0; i < n; ++i) {
        cin >> e;
        arr.push_back(e);
    }
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        int p;
        if (i % 2) {
            if (arr.front() > arr.back()) {
                p = arr.front(); arr.pop_front();
            } else {
                p = arr.back(); arr.pop_back();
            }
        } else {
            if (arr.front() < arr.back()) {
                p = arr.front(); arr.pop_front();
            } else {
                p = arr.back(); arr.pop_back();
            }
        }
        ans.push_back(p);
    }
    for (auto e : ans) cout << e << " "; cout << endl;
    return 0;
}

T4 计算区间内 1 的个数

由于我们要求区间 内的 的个数，转化为求 的 的个数比较好。下面介绍如何求解 的 的个数。

当 ，显然可以知道其中一半的位置都是 .

我们找到小于等于 最大的 ，有 ，对答案的贡献为：, 还剩下：。

剩下的部分无非是前部分的反转，因此我们可以递归的求解 ()，但是由于首位中 变为了 ，我们需要知道这一点。

当最后 时，如果我们记录的首位为 ，那么答案是 ，如果首位是 ，那么答案是 。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll cal(ll num, int bit) {
    if (num == 0) return 0;
    else if (num == 1) return bit;
    else if (num == 2) return 1;
    ll x = 0;
    while ((1ll << x) <= num) ++x;
    --x;
    num -= (1ll<<x);
    ll ans = 0;
    if (x > 0) {
        ans += (1ll<< (x-1));
    }
    return ans + cal(num, 1-bit);
}

int main() {
    ll L, R; cin >> L >> R;
    cout << cal(R, 1) - cal(L-1, 1) << endl;
    return 0;
}

T5 构造数组

给一个数组 ，希望我们找到两个数 X，Y 使得：

1. 生成, 或者 , 并且
2. 
3. 并且 最小

值得注意的是， 因此如果我们希望 ，那么 X，Y一定是异号的，或者 X = 0 or Y = 0。我们暂时忽略后一种情况。不失一般性，我们假设 ，那么有 ，

假定序列 是我们构造 时所选的下标，因此有：

因此，最后问题转化为找到一个 子序列，其和 ，并且有:

我们可以事先算出 所有的子序列构成的和，然后找到满足上式最小的一个。那么这样我们就顺利找到了所求的 和 。但是题目还要求这个子序列是如何选取的，这就是标准的背包问题，我们只需要套模板就行，下面给出代码：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define maxn 100005

int main() {
//     freopen("data.in", "r", stdin);
    int n; cin >> n;
    vector<int> arr(n);
    for (auto& e : arr) cin >> e;
    int sum = accumulate(arr.begin(), arr.end(), 0);
    unordered_set<int> ss;
    for (auto e : arr) {
        vector<int> newr;
        for (auto s : ss) {
            newr.push_back(s + e);
        }
        newr.push_back(e);
        for (auto e : newr) ss.insert(e);
    }
    int X = -1, Y = -1, d = INT_MAX;
    for (auto e : ss) {
        if (abs(sum - 2 *e) < d) {
            X = e, Y = e - sum;
            d = abs(sum - 2*e);
        }
    }
    // we should find the path
    vector<bool> f(maxn);
    vector<unordered_map<int, int>> last(n);
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        vector<bool> g = f;
        auto& e = arr[i];
        g[e] = 1;
        for (int j = 0; j < maxn; ++j) {
            if (f[j] && j + e < maxn) {
                g[j+e] = 1;
                last[i][j+e] = j;
            }
        }
        f = move(g);
    }
    if (!f[X]) cout << -1 << endl;
    else {
        int i = n-1, sum = X;
        vector<int> ans(n, 0);
        while (i >= 0) {
            if (last[i].count(sum)) {
                ans[i] = 1;
                sum = last[i][sum];
            }
            --i;
        }
        cout << X << " " << Y << endl;
        for (auto e : ans) if (e == 1) cout << "Y"; else cout << "X";
        cout << endl;
    }
    return 0;
}