首页 > 腾讯秋招第一次笔试(后台&综合)题解(2021/08/22)
头像
saipubw
编辑于 2021-08-22 22:25
+ 关注

腾讯秋招第一次笔试(后台&综合)题解(2021/08/22)

一共5道题,两个小时。整体难度偏低,一道模拟题,三道贪心题,一道动态规划题。

第一题(模拟题):
给一个链表,每个链表有一个数字i,i%m代表节点的颜色(因此一共m种颜色)
将链表按m种颜色拆分成m个链表,如果某种颜色未出现过就返回空链表。

直接按题意模拟即可。
为了简化时间复杂度,可以考虑缓存链表尾部的节点,方便插入。
时间复杂度O(N)

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param m int整型 
     * @param a ListNode类 指向彩带的起点,val表示当前节点的val,next指向下一个节点
     * @return ListNode类vector
     */
    vector<ListNode*> solve(int m, ListNode* a) {
        vector<ListNode*> ret;
        vector<ListNode**> bck;
        ret.resize(m);
        bck.resize(m);
        while (a!=nullptr)
        {
            if (ret[a->val%m]==nullptr)
            {
                ret[a->val%m]=new ListNode(a->val);
                bck[a->val%m]=&ret[a->val%m];
            }
            else
            {
                (*bck[a->val%m])->next=new ListNode(a->val);
                bck[a->val%m]=&((*bck[a->val%m])->next);
            }
            a=a->next;
        }
        return ret;
    }
};



第二题(贪心题):
有n个魔法球,每个球有一个能量,每次可以选一个球,获得这个球的所有能量,然后这个球消失。吸取一个球的时候,其他每个球的能量会增加,增量等于被吸取的能量。求能吸取的最多能量。

不难发现,应该尽可能先吸取能量最大的魔法球。因此按从大到小排序,然后模拟吸取的过程即可。注意取模来防止溢出。
时间复杂度O(TNlogN),这里N和T都小于1000,时间复杂度满足题目要求

#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
#define mod 1000000007
int ar[maxn];
int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &ar[i]);
        }
        sort(ar, ar + n, std::greater<int>());
        long long ans = 0, inc = 0;
        for (int i = 0; i < n; ++i)
        {
            ar[i] = (ar[i] + inc) % mod;
            inc = (inc + ar[i]) % mod;
            ans = (ans + ar[i]) % mod;
        }
        printf("%lld", ans);
    }
    return 0;
}
第三题(贪心题):
乘船问题,每个船可以坐一个或者坐两个人,如果坐两个人,体重的和一定要是偶数。
每艘船都有相同的最大载重限制,不能超载。
问最少需要多少船才能把人都运走。

首先,把人按照体重的奇偶分成两类人。显然奇数体重的人只能和奇数体重的人一起,偶数只能和偶数一起。因此我们分别计算两类人的结果然后相加即可得出结果。

搭配时,使用贪心的思想,每个人的搭档都应该尽可能的重(但是不至于超载)。因此首先对体重排序,然后利用双指针的思想,一头一尾,两面夹击扫描。

最终时间复杂度O(TNlogN),这里N和T都小于1000,时间复杂度满足题目要求

#include<bits/stdc++.h>
using namespace std;
#define maxn 5005
vector<int> g[2];
int solve(vector<int>& g,int w)
{
    sort(g.begin(), g.end());
    auto backit = --g.end();
    int ans = g.size();
    for (auto it = g.begin(); it != g.end();++it)
    {
        while (*it+*backit>w)
        {
            if (backit<=it)
                return ans;
            --backit;
        }
        if (backit<=it)
            return ans;
        --ans;
        --backit;
        if (backit<=it)
            return ans;
    }
    return ans;
}
int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n,w;
        scanf("%d%d", &n,&w);
        g[0].clear();
        g[1].clear();
        for (int i = 0; i < n;++i)
        {
            int temp;
            scanf("%d", &temp);
            g[temp % 2].push_back(temp);
        }
        int ans = solve(g[0],w) + solve(g[1],w);
        printf("%d", ans);
    }
    return 0;
}

第四题(贪心题):

给一个长度为n的字符串,求字典序最大的长度为k的子序列(子序列意味着可以不连续)

字典序最大,意味着我们应该在保证有解的情况下,尽可能的使得当前选取的字母最大。这是明显的贪心思想。
为了保证有解,当前选取的字母的右边剩下的字母必须大于等于len-1个,否则后面的字母不够用了。

一直贪心选取N次即可得到最优子序列。
每次选取时,可以一个for循环直接暴力遍历,则每次选取的时间复杂度O(N),也可以使用树状数组加速选取,每次选取的时间复杂度为O(logN)。
最终时间复杂度:暴力选取:O(N^2),树状数组加速贪心:O(NlogN)
这道题显然放水了,N=1000,因此直接暴力即可,不需要写树状数组加速。

#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
char str[maxn];
int len;
char solve(int &pos, int minlen)
{
    for (int i = pos + 1, lim = len - minlen + 1; i < lim; ++i)
    {
        if (str[i] > str[pos])
        {
            pos = i;
        }
    }
    pos += 1;
    return str[pos-1];
}
int main(void)
{
    int n, k, pos = 0;
    scanf("%d%d%s", &n, &k, str);
    len = strlen(str);
    for (int i = 0; i < k; ++i)
    {
        putchar(solve(pos, k - i));
    }
    putchar('\n');
    return 0;
}



第五题(动态规划题):

n 个图块,每个图块有一个数字,数字代表一种颜色。初始选择一个魔法图块,如果包含该图块的连续个图块数字相同,就可以变色。变色需要花费的代价是两个颜色的数字的差的绝对值。求把所有图块变成相同颜色的最小代价。

首先,不难发现,在变色的过程中会出现一个包含魔法图块的同颜色的区间。我们变色的过程就是不断左右扩张这个区间。变色只有两个选择,要么变成区间左边图块的颜色,要么变成右边的颜色,别的变色都是没有意义的。

因此,这显然是一个区间动态规划问题。

设dp[i][j][0/1]为所有可能的状态。第一维i代表区间左端点,第二维j代表区间右端点,第三维0/1代表区间的颜色是左端点的颜色还是右端点的颜色。设c为颜色的数组。

显然我们可以列出状态转移方程:
dp[i][j][0]=min(dp[i+1][j][0]+abs(c[i]-c[i+1]),dp[i+1][j][1]+abs(c[i]-c[j]))
dp[i][j][1]=min(dp[i][j-1][0]+abs(c[j]-c[i]),dp[i][j-1][1]+abs(c[j]-c[j-1]))
初始边界条件:当i==j时,dp[i][j][0]=dp[i][j][1]=0

根据状态转移方程,我们可以很容易求出最后的答案,即dp[0][n-1][0]和dp[0][n-1][1]中的最小值。

为了简化代码量,可以使用记忆化搜索。

最终时间复杂度为O(N^2)。题目给了N=500,说明更差的O(N^3)级别的算法也是能通过此题的。

#include<bits/stdc++.h>
using namespace std;
#define maxn 505
int ar[maxn],n;
int dp[maxn][maxn][2];
int magic = 0x3f3f3f3f;
int search(int i,int j,int k)
{
    if (dp[i][j][k]==magic)
    {
        if (k==0)
        {
            dp[i][j][k] = min
            (
                search(i + 1, j, 0)+abs(ar[i]-ar[i+1]), 
                search(i + 1, j, 1)+abs(ar[i]-ar[j])
            );
        }
        else
        {
            dp[i][j][k] = min
            (
                search(i, j - 1, 0)+abs(ar[j]-ar[i]), 
                search(i, j - 1, 1)+abs(ar[j]-ar[j-1])
            );
        }
    }
    return dp[i][j][k];
}
int main(void)
{
    int totans=magic;
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n;++i)
    {
        scanf("%d", &ar[i]);
        dp[i][i][0] = dp[i][i][1] = 0;
    }
    totans = min(search(0, n-1, 0), search(0, n-1, 1));
    printf("%d", totans);
    return 0;
}



全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐