腾讯 秋招 2023.09.15 编程题目与题解（研发岗）

发表于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

1、牛妹的数链们

牛妹有一堆数链，这些数链里面的数字都杂乱无章，牛妹想整理一下这世数字，把它们从小到大排成一个数链。

样例

1
2
3
4
5
输入：
[{1,3,5},{2,4,6},{1,2,3,4,5,6}]

输出：
{1,1,2,2,3,3,4,4,5,5,6,6}

备注

  • \(0\le val\le 10^9\)
  • 总元素个数\(\le 10^5\)

解答

这里仅提供一种最暴力的做法：将所有节点都存在数组中，排完序后重新成链。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
public:
    ListNode* solve(vector<ListNode*>&a){
        vector<ListNode*>b;
        for(ListNode*head:a){
            for(ListNode*p=head;p!=nullptr;p=p->next){
                b.push_back(p);
            }
        }
        sort(b.begin(),b.end(),[](ListNode *a,ListNode *b){return a->val<b->val;});
        for(int i=0;i+1<b.size();i++)
            b[i]->next=b[i+1];
        b.back()->next=nullptr;
        return b[0];
    }
};

2、小Q的奇偶操作数组

小Q有一个长度为\(n\)的数组，它对这个数组有\(k\)次操作机会，操作如下：

可以选择数组中的任意一个数字并改变它。

  1. 如果选择的数字\(x\)是奇数，那么这个奇数乘以\(2\)，即\(x=x\ast2\)
  2. 如果选择的数字\(x\)是偶数，那么这个偶数乘以\(2\)再加\(1\)，即\(x=x\ast 2+1\)

小Q想让这\(k\)次操作之后，数组元素之和最小，请你输出这个最小值是多少？

保证最终的元素之和不超过\(10^{18}\)。

输入

第一行两个正整数\(n\)和\(k\)，用空格隔开。

第二行输入\(n\)个正整数\(a_i\)，每个\(a_i\)代表数组的元素。

  • \(1\le n\le 200000\)
  • \(1\le k\le 200000\)
  • \(1\le a_i\le 10000000\)

输出

输出一个整数，代表\(k\)次操作之后，数组元素之和的最小值。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
5 3
1 2 3 5 2

输出：
20

提示：
其中一种方案是:
1. 将第一个元素：1=>2
2. 将第一个元素：2=>5
3. 将第二个元素：2=>5
总共3次操作，最后元素为5 5 3 5 2，数组元素之和为20

解答

每次只需要取出数组中最小的元素值进行操作即可。我们可以使用贪心选择性质如下证明：

假设现在数组中，最小元素是\(x\)，而选择的元素是\(y\)，并且满足\(y>x\)。那么哪怕\(y\)是偶数，\(x\)是奇数，最终得到的数组和的差值满足\(2y-(2x+1)=2(y-x)-1>0\)，也就是说，只要选择了\(y\)，最终得到的一定不是最优解。

每次寻找最小的数这个过程我们可以使用最小堆来完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n,k,x;
    priority_queue<ll,vector<ll>,greater<ll>>q;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        q.push(x);
    }
    for(int i=1;i<=k;i++){
        ll x=q.top();q.pop();
        ll w=x&1?x<<1:x<<1|1;
        q.push(w);
    }
    ll ans=0;
    while(!q.empty()){
        ans+=q.top();q.pop();
    }
    printf("%lld\n",ans);
}

3、赛道

牛牛组织了一场拉力赛，在一条水平的赛道上，共有\(n\)辆赛车，在当前时刻，牛牛记录下来了从左到右每辆车的位置\(p_1,p_2,\dots,p_n(0 \le p_1 < p_2 < \dots < p_n)\)，假设起点处位置为\(0\)，因此它们当前的排名依次为: \(n,n-1,n-2,\dots,1\)。现在牛牛知道在位置\(p_i\)处的车辆速度为\(v_i\)，假设所有的车保持匀速行驶，牛牛想知道在\(t\)个单位时间后，有多少赛车的排名上升？

注：如果在\(t\)个单位时间后有两辆车的位置相同，则这两辆车的排名相同。一辆车的排名为在它前面的车辆的个数加\(1\)。

输入

第一行输入两个正整数\(n,t\)。

第二行输入\(n\)个由空格隔开的整数\(p_1,p_2,\dots,p_n\)。

第三行输入\(n\)个由空格隔开的整数\(v_1,v_2,\dots,v_n\)。

  • \(1\le n\le 10^5,0\le p_i\le 10^5,1\le v_i\le 100,1\le t\le 1000\)

输出

输出\(t\)个单位时间之后排名上升的赛车数量。

样例

1
2
3
4
5
6
7
8
9
10
输入：
3 1
1 2 3
3 1 3

输出：
1

提示：
原本排行第3的车在1个单位时间后到了4，而原本在第2的车在1个单位时间后到达位置3，而排行第1的车位置到达了6，因此只有1辆车的排名上升了。

解答

为了编码方便，我们重新将排名定义成：当前距离在它后面的车辆的个数加\(1\)，也就意味着这个排名数值越大越好。

计算出\(s_i=p_i+v_i\cdot t\)后，对原本所有的赛车重新进行排名。如果新排名的数值比原来高，那么就对其进行统计即可。这里需要注意的是新排名需要仔细处理距离相同的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int p[N],v[N],rk[N],s[N];
int main(){
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=n;i++){
        s[i]=p[i]+v[i]*t;
        rk[i]=i;
    }
    sort(rk+1,rk+n+1,[](int x,int y){return s[x]<s[y];});
    int ans=0;
    for(int i=1,j;i<=n;){
        for(j=i;s[rk[i]]==s[rk[j]];++j);
        for(int k=i;k<j;k++){
            if(i>rk[k]) ++ans;
        }
        i=j;
    }
    printf("%d\n",ans);
}

4、旋转串

对于一个字符串，如果把字符串的第一个字符放到最后，得到的新串就是原来字符串的旋转串。

一个字符串的旋转串的旋转串也是这个字符串的旋转串。即这种关系具有传递性。

例如abc的旋转串有：bca cab abc

如果存在一个字符串，既是\(x\)的旋转串也是\(y\)的旋转串，那么我们称\(x,y\)匹配。

请回答一系列字符串中是否有两个字符串匹配。

输入

第一行输入一个正整数\(T\)，表示输入数据的组数。

每组数据第一行为一个正整数\(n\)。

接下来\(n\)行，每行一个只含小写字母的字符串\(s\)。

  • \(1\le T\le 50,1\le n\le 5000\)

每个字符串的长度都相同且不会超过\(50\)

输出

如果存在两个字符串匹配，则输出YES，否则输出NO。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
2
3
abb
abc
bab
3
aba
abc
abb

输出：
YES
NO

解答

如果\(x\)和\(y\)匹配，那么意味着\(x\)串可以旋转操作得到\(y\)。此时，\(x\)通过旋转得到的最小字典序的字符串和\(y\)通过相同操作得到的字符串相同。

因为，我们求出每个字符串的最小旋转串，然后再判断是否有两个最小旋转串是否相同即可。

其中，求最小旋转串只需要暴力旋转每个字符串即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include <bits/stdc++.h>
using namespace std;

string to_min(string s){
    string a=s;
    int n=s.size();
    for(int i=1;i<n;i++){
        s=s.substr(1)+s[0];
        a=min(a,s);
    }
    return a;
}
bool solve(){
    int n;
    string s;
    cin>>n;
    unordered_set<string>st;
    for(int i=0;i<n;i++){
        cin>>s;
        s=to_min(s);
        if(st.count(s)) return 1;
        st.insert(s);
    }
    return 0;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        puts(solve()?"YES":"NO");
    }
}

5、红点和蓝点

有\(n\)个点，第\(i\)个点的坐标为\(x_i\)，第\(i\)个点的颜色为\(c_i\)。

如果\(c_i=0\)，则第\(i\)个点为红点。

如果\(c_i=1\)，则第\(i\)个点为蓝点。

每次你可以做以下两种操作之一：

  1. 选择一个红点，设这个红点的坐标为\(x\)，把这个点移动到\(x-1\)或\(x+1\)。
  2. 选择一个蓝点，将它变为红点。

你可以最多做\(k\)次操作2。求最少要进行多少次操作1可以使得意两个红点之间不存在蓝点。

即设两个红点分别在坐标\(x,y(x \le y)\)，则不存在任何一个蓝点的坐标在区间\([x,y]\)内。

输入

第一行两个整数\(\displaystyle{n,k(1\le n\le 200000,0\le k\le \sum_{i=1}^n c_i)}\)。

第二行\(n\)个整数\(x_1,x_2,\dots ,x_n(1\le x_1\le x_2\le \dots \le x_n \le 10^9)\)。

第三行\(n\)个整数\(c_1,c_2,\dots ,c_n(0\le c_i\le 1)\).

输出

输出一行一个整数表示答案。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
输入：
5 0
2 7 9 14 20
0 1 0 0 1

输出：
6

提示：
将第1红点移动到位置8，一共需要6次操作1。

输入：
5 1
2 7 9 14 20
0 1 0 0 1

输出：
0

提示：
将第2个蓝点修改为红点。

输入：
8 0
1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 0

输出：
7

解答

首先我们可以证明：如果要对蓝点染成红色，那么这些蓝点一定是相邻的。否则，将两块不相邻的蓝点染成红色后，还要将其中一块移动到中间间隔开的蓝点的另一端，这时还不如不对一块蓝点染色。因此，我们只考虑将连续一块的蓝点染成红色。

接下来我们使用双指针法来接解决这个问题。枚举每个点作为右端点\(r\)，找到一个最小的\(l\)使得区间\([l,r]\)内至多包含\(k\)个蓝色节点。那么我们只需要将区间外的节点移动到坐标范围\((x_{l-1},x_{r+1})\)即可（如果区间为空，那么我们不讨论）。这时，在这个区间左侧的所有节点都移动到坐标\(x_{l-1}+1\)，在这个区间右侧的坐标都移动到\(x_{r+1}-1\)即可。因此，其中一个候选答案为：

\[\sum_{x_i\le x_{l-1}} (x_{l-1}+1-x_i)+\sum_{x_i\ge x_{r+1}} (x_i-(x_{r+1}-1))\]

我们最终还要算上区间\((-\infty,x_1)\)和\((x_n,\infty)\)的情况，最终一共有\(n+1\)个候选答案，选其中一个最优即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200004;
int c[N],n,k;

ll x[N],s0[N],s1[N],s[N];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i]);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        c[i]==0?s0[i]=1:s1[i]=1;
    }
    x[0]=-10;x[n+1]=1e9+10;
    for(int i=1;i<=n+1;i++){
        if(c[i]==0) s[i]=x[i];
        s[i]+=s[i-1];
        s0[i]+=s0[i-1];
        s1[i]+=s1[i-1];
    }
    ll ans=1e18;
    for(int r=0,l=0;r<=n;r++){
        for(;s1[r]-s1[l]>k;++l);
        if(x[l]+1==x[r+1]) continue;
        ll dr=x[r+1]-1,dl=x[l]+1;
        ll sl=dl*s0[l]-s[l];
        ll sr=(s[n]-s[r])-dr*(s0[n]-s0[r]);
        ans=min(ans,sl+sr);
    }
    printf("%lld\n",ans);
}
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝