腾讯软件开发笔试ac代码分享

第一题链表异或，没啥好说的，我选择了最稳妥的写法（虽然有点长）

/**
 * 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 *reverseList(ListNode *pre, ListNode *p)
    {
        if (!p)
            return pre;
        auto res = reverseList(p, p->next);
        p->next = pre;
        return res;
    }

    int count(ListNode *p)
    {
        int ans = 0;
        while (p)
        {
            ans++;
            p = p->next;
        }
        return ans;
    }

    ListNode *xorList(ListNode *a, ListNode *b)
    {
        int ca = count(a), cb = count(b);
        b = reverseList(nullptr, b);
        if (ca < cb)
        {
            swap(a, b);
            swap(ca, cb);
        }
        for (int i = 0; i < ca - cb; i++)
        {
            auto p = new ListNode(0);
            p->next = b;
            b = p;
        }
        ListNode *r = nullptr, *res = nullptr;
        bool flag = false;
        for (ListNode *p1 = a, *p2 = b; p1; p1 = p1->next, p2 = p2->next)
        {
            int val = p1->val == p2->val ? 0 : 1;
            auto p = new ListNode(val);
            if (!r)
            {
                r = res = p;
            } 
            else
            {
                r->next = p;
                r = p;
            }
        }
        while (res->next && res->val == 0)
        {
            auto p = res;
            res = res->next;
            delete p;
        }
        return res;
    }
};

第二题贪心，每次选择能变小最多的数就行，优先队列

int countOne(int x)
{
    int res = 0;
    while (x)
    {
        res++;
        x = x & (x - 1);
    }
    return res;
}

int main()
{
    int n, k;
    long long sum = 0;
    cin >> n >> k;
    vector<int> v(n);
    unordered_map<int, int> mp;
    auto cmp = [&mp](int a, int b) { return a - mp[a] < b - mp[b]; };
    priority_queue<int, vector<int>, decltype(cmp)> que(cmp);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
        mp.insert(make_pair(v[i], countOne(v[i])));
        que.push(v[i]);
        sum += v[i];
    }
    while (k--)
    {
        int top = que.top();
        int cnt = mp[top];
        que.pop();
        sum -= top - cnt;
        mp[cnt] = countOne(cnt);
        que.push(cnt);
    }
    cout<<sum;
    return 0;
}

第三题咋一看有点哈人，一开始以为是博弈搜索直接跳过了，后面回过头仔细看了看还是贪心，每次选最大最小就行了。想明白了就是五道题里最简单的一道- -！

int main()
{
    int n, tmp;
    cin >> n;
    deque<int> que;
    for (int i = 0; i < n; ++i)
    {
        cin >> tmp;
        que.push_back(tmp);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i % 2 == 1 && que.front() > que.back() || i % 2 == 0 && que.front() < que.back())
        {
            cout << que.front() << " ";
            que.pop_front();
        }
        else
        {
            cout << que.back() << " ";
            que.pop_back();
        }
    }
    return 0;
}

第四题首先要想明白这个公式，count(2ⁱ) = count(2^i-1) + 2^i-1 - count(2^i-1) = 2^i-1 。也就是说对于前2ⁱ个位置中1的个数是2^i-1。所以对于任意位置n，把n拆成2ⁱ+ d 递归处理就好了，递推公式：dp[n] = 2^i-1+ d - dp[d] (i = log2n 向下取整)。代码加了记忆化，其实加不加时间差不多

unordered_map<long long, long long> dp;
long long DFS(long long n)
{
    if (n == 0)
        return 0;
    else if (n <= 2)
        return 1;
    if(!dp.count(n))
    {
        long long i = log2l(n);
        long long d = n - pow(2, i);
        dp[n] = pow(2, i - 1) + d - DFS(d);
    }
    return dp[n];
}

int main()
{
    long long L, R;
    cin >> L >> R;
    cout << DFS(R) - DFS(L - 1);
    return 0;
}