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（计算机视觉）