type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 2, 2024 03:04 PM
腾讯2024后台开发实习笔试
📝 主旨内容
“好点”的个数(思维)
小红拿到了一个无向图，其中一些边被染成了红色。小红定义一个点是“好点”，当且仅当这个点的所有邻边都是红边,现在请你求出这个无向图“好点”的数量。
注:如果一个节点没有任何邻边，那么它也是好点。
输入描述
第一行输入两个正整数n，m，代表节点的数量和边的数量，接下来的m行，每行输入两个正整数u，v和一个字符chr，代表节点u和节点v有一条边连接。如果chr为'R'，代表这条边被染红，"W"代表末被染色。
输出描述
一个整数，代表“好点”的数量
示例 1
输入
输出
说明
只有1号节点是好点。
题解(100%)
这里不能通过遍历每一个点，再遍历当前点的每一条边来解决，此时时间复杂度为O()。可以在输入边的时候就判断，如果不是红色的话，那么边的两个端点一定不是好点，此时时间复杂度为O()
升序链表(链表)
小红拿到了一个链表。她准备将这个链表断裂成两个链表，再拼接到一起，使得链表从头节点到尾部升序。你能帮小红判断能否达成目的吗?
给定的为一个链表数组，你需要对于数组中每个链表进行一次“是”或者“否”的答案回答，并返回布尔数组。
每个链表的长度不小于2，且每个链表中不包含两个相等的元素。所有链表的长度之和保证不超过
示例 1
输入
输出
说明
第三个链表无论怎么操作都不满足条件
题解(100%)
考察了链表，只需要确保判断每个链表都是O(N)的即可，关键是找到可能的间断点，还有就是一些边界情况了
形成连通图的方案数(并查集)
小红拿到了一个有几个节点的无向图，这个图初始并不是连通图。
现在小红想知道，添加恰好一条边使得这个图连通，有多少种不同的加边方案?
输入描述
第一行输入两个正整数n，m，用空格隔开。
接下来的m行，每行输入两个正整数u,v，代表节点u和节点之间有一条边连接
保证给出的图是不连通的。
输出描述
一个整数，代表加边的方案数。
示例 1
输入
输出
题解(100%)
一条边就可以使得图联通，说明会形成两个联通块，用DFS和BFS并查集等都可以求出联通块内点的数量，二者数量相乘即可(下面是更通用的写法，可以拓展到多个联通块)
最大异或和(区间DP)
小红拿到了一个数组，她准备将数组分割成k段，使得每段内部做按位异或后，再全部求和。小红希望最终这个和尽可能大，你能帮帮她吗?
输入描述
输入包含两行。
第一行两个正幣数 n,k,()，分别表示数组的长度和要分的段数。
第二行几个整数，表示数组a的元素.
输出描述
输出一个正整数，表示最终的最大和。
示例 1
输入
输出
说明
小红将数组分为了:
[1,4]和[5,6]这两个区同，得分分别为:和，总得分为3+7=10.可以证明不存在比10更优的分割方案
注:符号表示异或操作。
题解(30%?)
多少个“tencent”(状态机DP)
小红拿到了一个字符矩阵，她可以从任意一个地方出发，希望走6步后恰好形成"tencent"字符串。小红想知道，共有多少种不同的行走方案?
注:每一步可以选择上、下、左、右中任意一个方向进行行走。不可行走到矩阵外部。
输入描述
第一行输入两个正整数n,m，代表短阵的行数和列数接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，代表小红拿到的矩阵
输出描述
一个整数，代表最终合法的方案数。
示例 1
输入
输出
说明
第一个方案，从左上角出发，右右下左左上。
第二个方案，从左上角出发，右右下左左下。
第三个方案，从左下角出发，右右上左左下。
第四个方案，从左上角出发，右右上左左上。
题解(100%)
n和m的范围都是1000，直接DFS会超时，考虑用动态规划，4(四个方向)*6(tencent长度)*1000*1000恰好不会超时
🤗 总结归纳
两道DP，一道简单图论，一道思维，一道链表，整体偏简单
考试环境用的牛客，会锁定电脑和手机，监管不是很严格，考试时长两小时
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/tencent-2024-backend-test
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。