Interview：算法岗位面试—上海某公司算法岗位(偏机器学习，互联网金融行业)技术面试考点之数据结构相关考察点—斐波那契数列、八皇后问题、两种LCS问题
ML崗位面試：上海某公司算法崗位(偏機(jī)器學(xué)習(xí)，互聯(lián)網(wǎng)金融行業(yè))技術(shù)面試考點之?dāng)?shù)據(jù)結(jié)構(gòu)相關(guān)考察點—斐波那契數(shù)列、八皇后問題、兩種LCS問題
Interview：算法崗位面試—上海某公司算法崗位(偏機(jī)器學(xué)習(xí)，互聯(lián)網(wǎng)金融行業(yè))技術(shù)面試考點之?dāng)?shù)據(jù)結(jié)構(gòu)相關(guān)考察點—斐波那契數(shù)列、八皇后問題、兩種LCS問題
導(dǎo)讀：其實，考察的知識點，博主都做過，但是，emmm，這些知識點，在我寫代碼中，幾乎不會用到，so，會遺忘。所以，還需要下功夫，去多回憶回憶啦。
? ? ? ? ?整個過程很nice。
目錄
數(shù)據(jù)結(jié)構(gòu)相關(guān)問題
1、生成斐波那契數(shù)列—yield的應(yīng)用
2、八皇后問題
3、兩種LCS問題——最長公共子序列和最長公共字符串
???????
數(shù)據(jù)結(jié)構(gòu)相關(guān)問題
1、生成斐波那契數(shù)列—yield的應(yīng)用
考察點： yield
1、yield的特點：
(1)、帶有 yield 的函數(shù)是生成器：帶有 yield 的函數(shù)在 Python 中被稱之為 generator生成器，當(dāng)使用一個yield的時候，對應(yīng)的函數(shù)就是一個生成器了。成器對象可以被for循環(huán)迭代，也可以手動執(zhí)行next或者send方法精準(zhǔn)控制這個生成器的內(nèi)部執(zhí)行，
(2)、yield是一個類似 return 的關(guān)鍵字：迭代一次遇到y(tǒng)ield時，就返回yield后面(右邊)的值。yield就是 return 返回一個值，并且記住這個返回的位置，下次迭代就從這個位置后(下一行)開始。
2、yield的兩大函數(shù)：
next：next方法就相當(dāng)于“下一步”生成哪個數(shù)，這一次的next開始的地方是接著上一次的next停止的地方執(zhí)行的。next方法第一次調(diào)用a.next()無法輸出參數(shù)，以后每次a.next(賦值)都等于函數(shù)體里面yield表達(dá)式的值。
send：send方法會首先把上一次掛起的yield語句的返回值通過參數(shù)設(shè)定，從而實現(xiàn)與生成器方法的交互。
注意：
(1)、當(dāng)send方法的參數(shù)為None時，它與next方法完全等價。但是注意，雖然這樣的代碼可以接受，但是不規(guī)范。所以，在調(diào)用send方法之前，還是先調(diào)用一次next方法為好。
(2)、其實next和send在一定意義上作用是相似的，區(qū)別是send可以傳遞yield表達(dá)式的值進(jìn)去，而next不能傳遞特定的值，只能傳遞None進(jìn)去。因此，我們可以看做c.next 和 c.send(None) 作用是一樣的。
3、yield的應(yīng)用：需要節(jié)約內(nèi)存不需要一把全部返回，每次使用的時候再去算，我們就會用到生成器。
? ? ? ?在 for 循環(huán)執(zhí)行時，每次循環(huán)都會執(zhí)行 fab 函數(shù)內(nèi)部的代碼，執(zhí)行到 yield b 時，fab 函數(shù)就返回一個迭代值，下次迭代時，代碼從 yield b 的下一條語句繼續(xù)執(zhí)行。而函數(shù)的本地變量看起來和上次中斷執(zhí)行前是完全一樣的，于是函數(shù)繼續(xù)執(zhí)行，直到再次遇到 yield。
2、八皇后問題
? ? ?八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計算機(jī)發(fā)明后，有多種計算機(jī)語言可以解決此問題。
考察點：考察結(jié)構(gòu)性編程的能力
理解：在8行8列的棋盤上擺放8個皇后，使之不能互相攻擊——任意兩個不在同一行、同一列或同一斜線上。典型的回溯算法。
首先，我們要想到某種方法來解決沖突檢測問題，即不能令棋子處于能相互吃掉的位置——相鄰、左右、對角線。
其次，運用回溯的方法，求得問題的解。此處具體為函數(shù)的遞歸調(diào)用，當(dāng)調(diào)用到棋盤的最后一行，便跳出，求得解。|
最后，將解打印出來。難點在于對遞歸調(diào)用函數(shù)的理解。
1、python八行代碼簡單實現(xiàn)的八皇后問題
def queen(lists, current=0): #current當(dāng)前狀態(tài)if current == len(lists):print(lists)return 0for col in range(len(lists)): #外for循環(huán)lists[current], flag = col, True #列表內(nèi)賦值，初始化標(biāo)記for row in range(current): #內(nèi)for循環(huán)取出每一行，if判斷，同列或者對角線，標(biāo)記為false，且跳出當(dāng)前層的for循環(huán)if lists[row] == col or abs(col - lists[row]) == current - row: flag = Falsebreakif flag: #if判斷，合法位置才進(jìn)行遞歸調(diào)用queen(lists, current+1) res=queen([None]*8)2、利用yield函數(shù)實現(xiàn)的八皇后問題
?Algorithm：【Algorithm算法進(jìn)階之路】之利用yield函數(shù)解決八皇后問題
3、兩種LCS問題——最長公共子序列和最長公共字符串
Algorithm：C++/python語言實現(xiàn)之求旋轉(zhuǎn)數(shù)組最小值、求零子數(shù)組、求最長公共子序列和最長公共子串、求LCS與字符串編輯距離
總結(jié)
以上是生活随笔為你收集整理的Interview：算法岗位面试—上海某公司算法岗位(偏机器学习，互联网金融行业)技术面试考点之数据结构相关考察点—斐波那契数列、八皇后问题、两种LCS问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Interview：算法岗位面试—10.
- 下一篇： Interview：算法岗位面试—上海某