腾讯2024暑期实习笔试
Q1 小红的图上染色
题目描述
小红拿到了一个无向图,其中一些边被染成了红色,小红定义一个点为”好点“,当且仅当这个点的所有邻边都是红边。现在请你求出这个无向图”好点“的数量
注意:如果一个节点没有任何邻边,那么它也是好点
输入描述
第一行输入两个正整数\(m\),\(n\),代表节点的数量和边的数量。
接下来的m行,每行输入两个正整数\(u\), \(v\)和一个字符chr,代表节点u和v有一条边连接,如果chr为'R',代表这条边被染红;'W'代表未被染色
\(1 <= n, m <= 10^5\)
\(1 <= u, v <= n\)
输出描述
一个整数,代表“好点”的数量
示例1
输入 1
2
3
4
54 4
1 2 R
2 3 W
3 4 W
1 4 R
输出 1
1
说明: 只有1号节点是好点
解题思路
无向图使用邻接表构建出邻接表,再构建一个node的hashmap储存红边数量,最后判断邻接表长度是否等于红边数量。
1 | # edge: [["1", "2", "R"], ["2", "3", "W"], ["3", "4", "W"], ["1", "4", "R"]] |
Q2 小红的链表破裂
题目描述
小红拿到了一个链表。她准备将这个链表断裂成两个链表,再拼接到一起,使得链表从头节点到尾部升序。你能帮小红判断是否达成目的吗?
给定的为一个链表数组,你需要对于数组中每个链表进行一次“是”或“否”的回答,并返回布尔数组。
每个链表的长度不小于2,且每个链表中不包含两个相等的元素。所有链表的长度之和保证不超过\(10^5\)
示例1
输入: 1
[{1, 2, 3}, {2, 3, 1}, {3, 2, 1}]
输出: 1
[true, false, true]
说明:
第三个链表无论怎么操作都不满足条件
解题思路
只有三种情况:
- 升序
- 先升序后降序
- 先降序后升序
才能满足断裂后拼接在一起时满足升序的
1 | def check_sorted_linked_lists(arr): |
Q3 小红的连通图
题目描述
小红拿到了一个有n个节点的无向图,这个图初始并不是连通图。
现在小红想知道,添加恰好一条边使得这个图连通,有多少种不同的加边方案?
输入描述
第一行输入两个正整数\(n\), \(m\),用空格隔开。
接下来的m行,每行输入两个正整数\(u\), \(v\),代表节点u和节点v之间有一条边连接。
\(1 <= n, m <= 10^5\) \(1 <= u, v <= n\)
保证给出的图示不连通的。
输出描述
一个整数,代表加边的方案数
解题思路
我不会,让我想想...
Q4 小红的数组分割
题目内容
小红拿到了一个数组,她准备将数组分成k段,使得每段内部按位异或之后,再全部求和,小红希望最终这个和尽可能大,你能帮帮她吗(不能)
输入描述
输入包含两行,第一行两个正整数\(n\), \(k\),\(1 <= k <= n <= 400\),分别表示数组的长度和要分的段数。
第二行\(n\)个整数\(a_i\) (\(0 <= a_i <= 10^9\)),表示数组a的元素。
输出描述
输出一个正整数,表示最终的最大和
示例1
输入: 1
26 2
1 1 1 2 3 41
10
小红将数组分为了[1, 4], [5, 6]两个区间,得分分别为:\(1 \oplus 1 \oplus 1 \oplus 2 = 3\) 和 \(3 \oplus 4 = 7\),总得分为10。可以证明不存在比10更优的分割方案。
解题思路:
- 采用动态规划的方法,用dp table记录当前位置将数组分成若干段的最大异或和,我们尝试所有可能的分段方法,更新dp table以找到最大的异或和。
- 利用异或运算的逆运算是其本身,可以使用异或前缀和的方法快速计算任何一段异或和
1 | from typing import List |
Q5 小红的tencent矩阵
题目描述
小红拿到了一个字符矩阵,她可以从任意一个地点除法,希望走6步之后恰好形成“tencent”字符串,小红想知道,共有多少种不同的行走方案?
注意:每一步可以选择上,下,左,右任意一种方向行走,不可行走到矩阵外部。
输入描述
第一行输入两个正整数\(n\), \(m\),代表矩阵的行数和列数。
接下来的n行,每行输入一个长度为m,仅由小写字母组成的字符串,代表小红拿到的矩阵。
输出描述
一个整数,代表最终合法的方案数
示例1
输入: 1
2
3
43 3
ten
nec
ten
输出: 1
4
说明:
- 从左上角出发,右右下左左上
- 从左上角出发,右右下左左下
- 从左下角出发,右右上左左下
- 从左下角出发,右右上左左上
解题思路
dfs + 剪枝,符合加1,不符合直接返回
1 | def count_matrix(matrix: List[List[str]]): |