2021年9月底,百度NLP崗位面試題分享!
文 | 七月在線
編 | 小七
目錄
FIGHTING
問題1：先序遍歷（要求遞歸和迭代兩種方式）
問題2：旋轉(zhuǎn)數(shù)組尋找k
問題1、先序遍歷（要求遞歸和迭代兩種方式）
方法一：遞歸
樹本身就有遞歸的特性，因此遞歸方法最簡單，這里直接放上代碼，需要說明的是，中序遍歷，前序遍歷和后序遍歷可采用相同的代碼模板完成實現(xiàn)。
時間復(fù)雜度：O(n)，n 為樹的節(jié)點個數(shù)
空間復(fù)雜度：O(h)，h 為樹的高度
方法二：迭代
代碼如下：
時間復(fù)雜度：O(n)，n 為樹的節(jié)點個數(shù)
空間復(fù)雜度：O(h)，h 為樹的高度
問題2、旋轉(zhuǎn)數(shù)組尋找k
思路一：暴力解法
直接遍歷整個數(shù)組，找到目標值target
代碼如下：
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
思路二：二分查找
先要設(shè)置整個數(shù)組的左右兩端端點：left = 0，right = len(nums) - 1
1、若 target == nums[mid]，直接返回
2、若 nums[left] <= nums[mid]，說明左側(cè)區(qū)間 [left,mid]「連續(xù)遞增」。此時：
若 nums[left] <= target <= nums[mid]，說明 target 位于左側(cè)。令 right = mid-1，在左側(cè)區(qū)間查找；否則，令 left = mid+1，在右側(cè)區(qū)間查找
3、否則，說明右側(cè)區(qū)間 [mid,right]「連續(xù)遞增」。
此時：若 nums[mid] <= target <= nums[right]，說明 target 位于右側(cè)區(qū)間。令 left = mid+1，在右側(cè)區(qū)間查找
否則，令 right = mid-1，在左側(cè)區(qū)間查找
代碼如下：
時間復(fù)雜度：O(logn)
空間復(fù)雜度：O(1)
— 推薦閱讀 —
最新大廠面試題
AI開源項目論文
NLP ( 自然語言處理 )
CV（計算機視覺）
推薦