2021年9月底,百度NLP岗位面试题分享!
文 | 七月在线
编 | 小七
目录
FIGHTING
问题1：先序遍历（要求递归和迭代两种方式）
问题2：旋转数组寻找k
问题1、先序遍历（要求递归和迭代两种方式）
方法一：递归
树本身就有递归的特性，因此递归方法最简单，这里直接放上代码，需要说明的是，中序遍历，前序遍历和后序遍历可采用相同的代码模板完成实现。
时间复杂度：O(n)，n 为树的节点个数
空间复杂度：O(h)，h 为树的高度
方法二：迭代
代码如下：
时间复杂度：O(n)，n 为树的节点个数
空间复杂度：O(h)，h 为树的高度
问题2、旋转数组寻找k
思路一：暴力解法
直接遍历整个数组，找到目标值target
代码如下：
时间复杂度：O(n)
空间复杂度：O(1)
思路二：二分查找
先要设置整个数组的左右两端端点：left = 0，right = len(nums) - 1
1、若 target == nums[mid]，直接返回
2、若 nums[left] <= nums[mid]，说明左侧区间 [left,mid]「连续递增」。此时：
若 nums[left] <= target <= nums[mid]，说明 target 位于左侧。令 right = mid-1，在左侧区间查找；否则，令 left = mid+1，在右侧区间查找
3、否则，说明右侧区间 [mid,right]「连续递增」。
此时：若 nums[mid] <= target <= nums[right]，说明 target 位于右侧区间。令 left = mid+1，在右侧区间查找
否则，令 right = mid-1，在左侧区间查找
代码如下：
时间复杂度：O(logn)
空间复杂度：O(1)
— 推荐阅读 —
最新大厂面试题
AI开源项目论文
NLP ( 自然语言处理 )
CV（计算机视觉）
推荐
评论