2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關(guān)
1、七種常見(jiàn)的數(shù)組排序算法整理(C語(yǔ)言版本)
2、2019 算法面試相關(guān)(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(guān)(leetcode)--字符串
4、2019 算法面試相關(guān)(leetcode)--棧和隊(duì)列
5、2019 算法面試相關(guān)(leetcode)--優(yōu)先隊(duì)列
6、2019 算法面試相關(guān)(leetcode)--哈希表
7、2019 算法面試相關(guān)(leetcode)--樹(shù)、二叉樹(shù)、二叉搜索樹(shù)
8、2019 算法面試相關(guān)(leetcode)--遞歸與分治
9、2019 算法面試相關(guān)(leetcode)--貪心算法
10、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃(Dynamic Programming)
11、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃之背包問(wèn)題
動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。
動(dòng)態(tài)規(guī)劃的難點(diǎn)就是思路：
- 1、遞歸+記憶化 = 遞推
- 2、狀態(tài)的定義：opt[n],dp[n]...
- 3、狀態(tài)轉(zhuǎn)移方程：dp[n] = best_of(dp[n-1],dp[n-2],...)
- 4、最優(yōu)子結(jié)構(gòu)
動(dòng)態(tài)規(guī)劃 VS 回溯(遞歸) VS 貪心
- 回溯(遞歸)：重復(fù)計(jì)算
- 貪心：永遠(yuǎn)局部最優(yōu)
- 動(dòng)態(tài)規(guī)劃：記錄最優(yōu)子結(jié)構(gòu)，多種記錄值
爬樓梯
不同路徑 II
編輯距離
買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) III
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV
一、爬樓梯
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
根據(jù)題目來(lái)看，如果想爬到第n層，可以從第n - 2層一次爬2階，也可以從第n - 1層一次爬1階。
那么設(shè)爬到第n層的方法數(shù)為f(n),則f(n) = f(n - 1) + f(n - 2)
很容易可以看出，這是最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃例子：斐波拉契(Fibonacci)數(shù)列問(wèn)題，其狀態(tài)轉(zhuǎn)移方程為dp(n) = dp(n - 1) + dp(n - 2)
我們很容易想到用遞歸來(lái)做
var climbStairs = function(n){
return n <= 2 ? n : (climbStairs(n - 1) + climbStairs(n - 2))
}
然而在leetcode提交后卻是超時(shí)，原因就在于在climbStairs(n - 1)和climbStairs(n - 2)的遞歸過(guò)程中，存在很多重復(fù)計(jì)算，其時(shí)間復(fù)雜度是o(2n)
而動(dòng)態(tài)規(guī)劃相對(duì)于遞歸，有個(gè)明顯的特點(diǎn)就是：記憶化
遞歸+記憶化 = 遞推
所以我們可以添加一個(gè)緩存數(shù)組，將每次計(jì)算的值緩存下來(lái)
var climbStairs = function(n){
let dp = [1,2]
for(let i = 2;i < n; i++){
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n - 1]
}
時(shí)間復(fù)雜度則為o(n)
二、 不同路徑 II
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會(huì)有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來(lái)表示。
說(shuō)明：m 和 n 的值均不超過(guò) 100。
示例 1:
輸入: [
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
動(dòng)態(tài)規(guī)劃之所以難，就在于其思路，這道題目是中等難度。
其難點(diǎn)就在于思路，我們可以反著想，不去想機(jī)器人往哪里走，而去想機(jī)器人從哪里來(lái)，然后一直回溯。
由題目可知，機(jī)器人只能從左或者從上走過(guò)來(lái)
就很容易得出其狀態(tài)轉(zhuǎn)移方程為:
如果當(dāng)前沒(méi)有障礙物，dp[m][n] = dp[m - 1][n] + dp[m][n - 1]
如果有障礙物，則dp[m][n] = 0
var uniquePathsWithObstacles = function(obstacleGrid) {
if(obstacleGrid.length == 0) return 0
if(obstacleGrid[0][0]) return 0
let dp = []
for(let i = 0; i < obstacleGrid.length; i++){
dp[i] = []
}
dp[0][0] = 1
for(let i = 0; i < obstacleGrid.length; i++){
for(let j = 0; j < obstacleGrid[0].length; j++){
if(!i && !j) continue
if(obstacleGrid[i][j]) dp[i][j] = 0
else dp[i][j] = (i ? dp[i - 1][j] : 0) + (j ? dp[i][j - 1] : 0)
}
}
return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1]
};
時(shí)間復(fù)雜度為o(m*n)
以上兩題感覺(jué)動(dòng)態(tài)規(guī)劃好像沒(méi)那么難，思路并不是很難想？
然而并不是，因?yàn)樯厦鎯深}很‘動(dòng)態(tài)規(guī)劃’，本身屬于比較契合動(dòng)態(tài)規(guī)劃思路的
而有的題目，思路很難想，很難下手
比如：
三、 編輯距離
給定兩個(gè)單詞 word1 和 word2，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：
插入一個(gè)字符
刪除一個(gè)字符
替換一個(gè)字符
示例 1:
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
示例 2:
輸入: word1 = "intention", word2 = "execution"
輸出: 5
解釋:
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')
這算是比較經(jīng)典的動(dòng)態(tài)規(guī)劃題目了，難度為困難，不過(guò)leetcode通過(guò)率還挺高的。
DP兩部曲
1、首先找狀態(tài)定義，這里初看題，很容易是會(huì)定義成用DP[i]，然而這樣是沒(méi)辦法解決的，應(yīng)該是DP[i][j]，表示為單詞1的前i個(gè)字符要轉(zhuǎn)換成單詞2的前j個(gè)字符，最少需要的步數(shù)。
2、然后定義狀態(tài)轉(zhuǎn)移方程
狀態(tài)定義好后，狀態(tài)轉(zhuǎn)移方程也就不難列了。
如果單詞1第i+1個(gè)字符和單詞2第j+1個(gè)字符相同，那么就不用操作，則DP[i + 1][j + 1] = DP[i][j];
如果不相同,則有三種可能操作，即增，刪，替換。則取這三種操作的最優(yōu)值，即dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i + 1][j]));
即可得出代碼如下：
var minDistance = function(word1, word2) {
let m = word1.length, n = word2.length;
let dp = new Array();
for(let i = 0; i <= m; i++){
dp[i] = new Array();
dp[i][0] = i;
}
for(let i = 0; i <= n; i++){
dp[0][i] = i;
}
for(let i = 1; i <= m; i++) {
for(let j = 1; j <= n; j++) {
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[m][n];
};
時(shí)間復(fù)雜度為o(m*n)
四、股票買(mǎi)賣(mài)問(wèn)題
這是leetcode上的經(jīng)典的股票買(mǎi)賣(mài)系列問(wèn)題
買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) III
前兩題比較簡(jiǎn)單，第三題包含在第四題中。
下面看下: 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 k 筆交易。
注意: 你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。
示例 1:
輸入: [2,4,1], k = 2
輸出: 2
解釋: 在第 1 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣(mài)出，這筆交易所能獲得利潤(rùn) = 4-2 = 2 。
示例 2:
輸入: [3,2,6,5,0,3], k = 2
輸出: 7
解釋: 在第 2 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4 。
隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買(mǎi)入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3 。
首先，如果k大于給定的數(shù)組數(shù)量，就意味著可以盡可能多的買(mǎi)賣(mài)，也就是和第二題一致了。
而如果k小于數(shù)組數(shù)量，動(dòng)態(tài)規(guī)劃兩部曲
- 首先找狀態(tài)定義，簡(jiǎn)單的dp[i]并不能滿足要求，因?yàn)橛匈I(mǎi)賣(mài)兩種形式，所以我們應(yīng)該設(shè)置兩個(gè)狀態(tài)定義buy[i]和sell[i],i <= k
假設(shè)初始總金額為0，這里直接用dp[0][i]來(lái)表示在某天買(mǎi)入第i次后的總金額(可能會(huì)是負(fù)數(shù))，用dp[1][i]表示在某天賣(mài)出第i次后的總金額 - 然后確立狀態(tài)轉(zhuǎn)移方程：
在某天買(mǎi)入第i次，應(yīng)該是上次賣(mài)出后的總金額減去當(dāng)天股票價(jià)格p和上次買(mǎi)入后的總金額的最大值
即dp[0][i] = Math.max(dp[0][i], (i ? dp[1][i - 1] : 0) - p)
而在某天賣(mài)出第i次，應(yīng)該是上次買(mǎi)入后的總金額加上當(dāng)天股票價(jià)格p和上次賣(mài)出后的總金額的最大值
即dp[1][i] = Math.max(dp[1][i], dp[0][i] + p);
則代碼如下
var maxProfit = function(k, prices) {
if(prices.length <= 1 || k <= 0) return 0
if (prices.length/2 <= k) {
let maxProfit = 0;
for (let i = 1; i < prices.length; ++i) {
if (prices[i] > prices[i-1]) {
maxProfit += (prices[i] - prices[i-1]);
}
}
return maxProfit;
}
let dp = [new Array(k).fill(-Infinity),new Array(k).fill(0)]
for(let i = 0; i < prices.length; i++){
let p = prices[i];
for(let j = 0; j < Math.min(i + 1,k); j++){
dp[0][j] = Math.max(dp[0][j], (j ? dp[1][j - 1] : 0) - p);
dp[1][j] = Math.max(dp[1][j], dp[0][j] + p);
}
}
return dp[1].pop()
};
