這篇文章帶來四個經典演算法問題的基礎暴力解法。四個著名演算法分別是Pancake sorting， De Bruijn sequence， Convex hull algorithms， Knapsack problem。 這四個問題都非常經典，也衍生出了很多複雜的解法。然而在面試的時候如果碰到原問題或相似的問題，我認為只要寫出最基本的暴力解法就可以獲得一個起碼是weak hire的評價。四個演算法的定義都可以在連結裡面找到。
Pancake sorting的本質是排序。與其他排序的操作不同，我們在這裡面不能隨意的swap陣列內的元素，而只能reverse/flip前若干個元素組成的prefix subarray（A［0。。i］）。我們的目標是透過不斷的reverse操作，來將陣列排序。當然，reverse的操作越少越好。
暴力的演算法是，對於在陣列中第i大的元素（從小數第i個），我們希望它出現在陣列的第i個位置。這裡為了方便說明，陣列計數從1開始。我們找到這個目標元素，發現它出現在陣列中的位置j，reverse A［1。。j］，這時候第i大的元素出現在了陣列開頭。然後reverse A［1。。i］，這時候我們就把第i大的元素放在第i位上。值得注意的是，我們對要操作的元素，應該從最大的開始。因為在處理某元素的時候，可能會改變該元素之前已經排好的順序。因此如果從小到大，之前排好的序又被破壞，但是從大到小的順序不會。我們從最大的元素開始往前處理，每次找到剩餘陣列中最大的，然後透過兩次reverse將它放到屬於它的位置。看一下geeksforgeeks的程式碼。
int
pancakeSort
（
int
*
arr
，
int
n
）
{
// Start from the complete array and one by one reduce current size by 1
for
（
int
curr_size
=
n
；
curr_size
>
1
；
——
curr_size
）
{
// Find index of the maximum element in arr［0。。curr_size-1］
int
mi
=
findMax
（
arr
，
curr_size
）；
// Move the maximum element to end of current array
// if it‘s not already at the end
if
（
mi
！=
curr_size
-
1
）
{
// To move at the end， first move maximum number to beginning
flip
（
arr
，
mi
）；
// Now move the maximum number to end by reversing current array
flip
（
arr
，
curr_size
-
1
）；
}
}
}
可以看到，除了最小的元素，其他每個元素都需要兩次reverse操作才能去到對應的位置。所以最多需要2（n-1）次reverse操作。每次操作需要O（n）時間找到當前最大的元素，以及O（n）時間flip。所以該排序演算法的總時間複雜度是O（n^2）。 一個簡單的小最佳化是對於大小為2的陣列，最多隻需要reverse一次就可以讓它有序。因此最壞的情況可以縮減到2（n-2）+1次reverse操作。
Pancake sorting一個變形是burnt pancake problem，有興趣的可以看一下。基本的解法就是在處理第i個pancake的時候，在兩次flip之間插入如下操作：判斷它burnt的那一面是否朝上，如果不是則單獨將它額外flip一次。
推薦擴充套件閱讀：比爾蓋茨的論文
De Brujin Sequence的一個簡單問題是，找到長度最小的string，裡面包含了所有長度為4的substring（alphabet為數字0到9，需要包含的substring從0000到9999）（google面經題）。我們如果把最後的結果考慮成一個環形，那麼結果實際上長度為10^4。暴力DFS，用一個長度為10^4的陣列來做visited list。每一層嘗試把0到9中的每一個數字加到當前這一層的位置。藉助visited list判斷，如果此時獲得的新結果的最後四位數字組成的四位數沒有出現過，那麼就進入下一層DFS的遞迴。值得注意的是，當遞迴到最後一層的時候，我們要判斷每種wrap around的數字的情況（由結果的最後幾位和前幾位concatenate而成，相當於每一個經過環形介面的可能）。這裡我直接放stellari的解法了。（我測試過了。）
class
DeBruijn10
{
bool
DFS
（
int
ind
）
{
if
（
ind
==
upper
）
{
// No more number left
for
（
int
i
=
1
；
i
<=
n
-
1
；
++
i
）
{
// Still need to validate the numbers that “wrap around”
string
st
=
seq
。
substr
（
upper
-
n
+
i
，
n
-
i
）
+
seq
。
substr
（
0
，
i
）；
if
（
avail
［
stoi
（
st
）］
==
false
）
return
false
；
}
return
true
；
}
int
prefix
=
stoi
（
seq
。
substr
（
ind
-
（
n
-
1
），
n
-
1
））
*
10
；
for
（
int
i
=
0
；
i
<=
9
；
++
i
）
{
int
cur
=
prefix
+
i
；
// Try each possible choice at the current location
if
（
avail
［
cur
］）
{
// If this number hasn’t appeared so far
avail
［
cur
］
=
false
；
// then try it。
seq
［
ind
］
=
i
+
‘0’
；
if
（
DFS
（
ind
+
1
））
return
true
；
avail
［
cur
］
=
true
；
}
}
return
false
；
}
public
：
int
n
；
int
upper
；
vector
<
bool
>
avail
；
string
seq
；
DeBruijn10
（
int
_n
）
：
n
（
_n
），
upper
（
pow
（
10
，
n
）），
avail
（
upper
，
true
），
seq
（
upper
，
‘0’
）
{
avail
［
0
］
=
false
；
DFS
（
n
）；
}
}；
對於n=4的情況，這種寫法還是很快的。當然還有很多更好的解法。問題的本質是尋找歐拉回路，有很多經典演算法例如Fleury‘s和Hierholzer’s。對於為何是找歐拉回路，可以看擴充套件閱讀：
http：//
xwk。iteye。com/blog/2129
621
。
Convex Hull是說在二維平面內，給定一些點，找到最外層的一圈點，他們的連線將把其他剩餘的點都包含進去。
首先對於三個不共線的點A，B，C， 我們是否可以判斷出ABC這樣的走法是逆時針的呢？我們先假定A在最左邊，我們可以透過比較AB和AC之間的斜率得到。僅當AB的斜率小於AC的時候，ABC的走法是逆時針的。那如果A不在最左邊呢？其實ABC和BCA和CAB的本質是一樣的，所以我們只要找到三個點中最左邊的點，然後做相應的轉化就可以了。
回到找Convex Hull的問題上來。我們可以先找到最左邊的點作為起點（反證法易得，此點必然屬於Convex Hull的點集，最右邊，最上面，最下面的點均可）。然後我們依次尋找下一個端點直到回到最初的起點。對於已經確定的端點P，下一個端點是：對於一個站在P點上，看著其他的點的人來說，最靠右的點。換言之，如果下一個端點是Q，那麼對於任意的其他點R，PQR都是逆時針的。Q點可以透過O（n）次逆時針測試獲得。遍歷所有的點（除了P自己），對於一個可能的Q candidate，如果PQR的逆時針測試失敗的話，那麼這個R就成為了新的Q candidate。因為如果當前的PQR不是逆時針，那麼R一定對於P來說在這個Q candidate的右邊，因此R有資格成為了新的Q candidate。總的時間複雜度是O（n^2）。具體的程式碼可以看擴充套件閱讀裡的Jeff‘s Notes。
擴充套件閱讀：Jeff’s Notes。（裡面還有nlgn的解法）。
最後說說揹包問題裡的01揹包和完全揹包（取材於
dd大牛的《揹包九講》
）。
有N件物品和一個容量為V的揹包。第i件物品的所佔用的體積是c［i］，價值是w［i］。將哪些物品裝入揹包滿足物品所佔體積的總和不超過V，且價值總和最大。
01揹包是每個物品最多隻能取一個。狀態轉移方程是f［i］［v］=max{f［i-1］［v］，f［i-1］［v-c［i］］+w［i］}。
f［i］［v］代表的是，對於前i件物品，以及容量為v的子問題的答案。對於這個子問題，我們有兩種選擇，要麼不放第i件物品，也就是f［i-1］［v］，要麼放第i件物品。放的話，剩餘的體積只有v-c［i］，所以其他的價值最多隻能是f［i-1］［v-c［i］］。最後我們加上第i件物品的價值，和不放的情況比較，取最大值。這種解法的時間複雜度為O（VN），空間複雜度也是O（VN）。因為f［i］［v］只依賴於f［i-1］［v］，因此可以只維護兩個大小為V的陣列，空間複雜度可以輕易最佳化到O（V）。這裡甚至可以最佳化到只維護一個數組（依賴關係畫圖可知，若i為縱座標，v為橫座標，每個格子依賴左上方的格子，因此要從右邊逆序走）。
完全揹包是說每個物品最多可取無窮多個。首先我們想到，若兩件物品i、j滿足c［i］<=c［j］且w［i］>=w［j］，則將物品j去掉，不用考慮。然後對於每個物品i 來說，我們找到單放這個物品最多可以放x個（求解 argmax（x， x*c［i］ <= V））。對於物品i，縱然它有無限多個，揹包裡最多放x個，因此我們可以轉化成擁有x個物品i，但每個物品只能取一次的情況。因此就把完全揹包問題化解成了01揹包問題。當然還有更優的拆分方法，比如：“把第i種物品拆成費用為c［i］*2^k、價值為w［i］*2^k的若干件物品，其中k滿足c［i］*2^k 擴充套件閱讀：dd大牛的《揹包九講》 最後，到底該放什麼題圖才能吸引目光又不被舉報呢。。。放張神仙姐姐養養眼吧。
