在 TikTok 的面试中,CSOAHELP遇到了两道技术题目。以下是这些题目的详细描述和我们辅导的解答过程。
问题 1:删除一个字符后判断是否是回文
![](https://csoahelp.com/wp-content/uploads/2024/06/a8903157273d8096c601eff9daf0c1b-1024x304.png)
问题描述
给定一个字符串 s
,如果最多删除一个字符后它能成为回文,则返回 true
。
示例:
- 输入:
s = "aba"
输出:true
- 输入:
s = "abca"
输出:true
(解释:你可以删除字符 'c'。) - 输入:
s = "abc"
输出:false
我的解答
为了解决这个问题,我实现了以下函数:
- 辅助函数:
is_palindrome(string)
- 这个函数检查给定字符串是否是回文,通过将字符串与其反转后的字符串进行比较。
![](https://csoahelp.com/wp-content/uploads/2024/06/image-24-1024x178.png)
- 主函数:
validPalindrome(s)
- 这个函数使用两个指针,
left
和right
,分别从字符串的开头和结尾开始。它检查这些指针所指的字符是否相同。如果不同,它会检查删除left
指针或right
指针所指的字符后,剩下的字符是否是回文。如果是,则返回true
,否则继续检查下一个字符。
- 这个函数使用两个指针,
![](https://csoahelp.com/wp-content/uploads/2024/06/image-25-1024x554.png)
面试官和我的交流记录:
面试官:可以确认一下,空字符串是否被认为是回文吗?
我:空字符串应该返回 False
。如果输入为空字符串,我们应该返回 False
。
面试官:好的,你可以开始编写代码了。
我:好的,我会在代码中处理这种特殊情况。
面试官:你的算法思路是什么?
我:我会使用两个指针,分别从字符串的两端向中间移动。如果发现不相等的字符,我会尝试删除其中一个字符,然后检查剩余部分是否是回文。
面试官:可以详细说明一下吗?
我:比如说,对于字符串 "abca",左指针从索引 0 开始,右指针从索引 3 开始。首先检查 s[left]
是否等于 s[right]
,这是对的,所以我们将左指针移动到 1,右指针移动到 2。接着检查 s[left]
是否等于 s[right]
,这不对,所以我们尝试删除左指针或右指针所指的字符,然后检查剩余部分是否是回文。
面试官:听起来很合理,你可以开始编写代码了。
问题 2:检测无向图中是否存在环
![](https://csoahelp.com/wp-content/uploads/2024/06/86d1a9722cd8782d168fde1e0dc8fbd.png)
问题描述
判断一个无向图中是否存在环。
示例:
- 输入:
[[1,2],[1,3],[2,3]]
输出:true
(解释:节点 1, 2 和 3 构成一个环。) - 输入:
[[1,2],[2,3],[3,4],[1,5]]
输出:false
(解释:图中不存在环。)
我的解答
为了解决这个问题,我实现了一个使用深度优先搜索(DFS)算法的辅助函数来检测无向图中的环。
- 辅助函数:
dfs(node, parent, visited, graph)
- 这个函数在图上进行深度优先搜索(DFS),将节点标记为已访问。它通过确保访问过的邻居节点不是当前节点的父节点来检查环。
![](https://csoahelp.com/wp-content/uploads/2024/06/image-26-1024x476.png)
- 主函数:
has_cycle(edges)
- 这个函数首先根据给定的边构建图,然后遍历所有节点,从每个未访问的节点开始进行 DFS,以检测任何环。
![](https://csoahelp.com/wp-content/uploads/2024/06/image-27-1024x742.png)
面试官和我的交流记录:
面试官:图是连通的还是可能不连通的?
我:图可能是不连通的。我们需要检查每个节点。
面试官:输入是一组边吗?比如 [1, 2]
表示可以从 1 到 2 吗?
我:是的,输入是一组边,每条边连接两个节点。
面试官:你的算法思路是什么?
我:我会使用 DFS 从每个节点开始遍历,如果在同一次遍历中看到同一个节点两次,就说明存在环。
面试官:可以详细说明一下吗?
我:比如说,对于输入 [[1,2],[1,3],[2,3]]
,我们从节点 1 开始,访问它的邻居节点 2,然后访问节点 2 的邻居节点 3,再访问节点 3 的邻居节点 1。由于节点 1 已经访问过,说明存在环。
面试官:听起来很合理,你可以开始编写代码了。
面试总结
两个题目分别涉及了删除字符后检查回文和使用 DFS 检测无向图中的环。这些任务要求我对数据结构和算法设计有深入的理解。
后续我与面试官讨论了一些公司相关的问题,比如她认为有趣的项目是什么,我应聘岗位的职责是什么等。
后续的feedback十分的不错,如果你也有面试的需要,欢迎购买我们的面试辅助服务。
![](https://csoahelp.com/wp-content/uploads/2024/05/image-39.png)