算法是每個程序員必備的技能之一
今天給大家介紹一些，經典的算法集錦。掌握這些經典算法，在以後的面試過程中就不用擔心算法不過關啦。話不多說，來看實例吧。
1、用PHP實現楊輝三角
楊輝三角
解題思路：設置兩個變量分別為行數和列數，第一列和最後一列的值都為1（即代碼中的$j = 0和$i = $j）,中間的數值計算方式為上一行的本列數+上一行的前一列數（即$a[$i][$j] = $a[$i-1][$j-1] + $a[$i-1][$j]）
PHP代碼實現如下：
<code>"; }/<code>
2、寫一段代碼判斷單向鏈表中有沒有形成環，如果形成環，請找出環的入口處即P點。
解題思路：定義兩個指針：慢指針（slow）,快指針（ fast）。slow指針一次走1個結點，fast指針一次走2個結點。如果鏈表中有環，那麼慢指針一定會再某一個時刻追上快指針(slow == fast)。如果沒有環，則快指針會第一個走到NULL。
PHP代碼如下：
<code>class Node{
public $data=null;
public $next=null;
}
function eatList(Node $node) {
$fast = $slow = $node;
$first_target = null;
if($node->data == null) {
return false;
}
while (true) {
if($fast->next != null && $fast->next->next != null) {
$fast = $fast->next->next; //快指針一次走兩步
$slow = $slow->next; //慢指針一次走一步
} else {
return false;
}
if($fast == $slow) { //慢指針追上快指針,說明有環
$p1 = $node; //p1指針指向head節點,p2指針指向它們第一次相交的點,然後兩個指針每次移動一步,當它們再次相交,即為環的入口
$p2 = $fast;
while($p1 != $p2) {
$p1 = $p1->next;
$p2 = $p2->next;
}
return $p1; //環的入口節點
}
}
}/<code>3、有1000瓶藥水，其中只有一瓶有毒。現在用小白鼠進行實驗，小白鼠只要服用任意量有毒藥水就會在24小時內死亡。問至少要用多少隻小白鼠進行實驗才能檢測出哪瓶藥水有毒？
解題思路：把每一瓶水按順序編號並用二進制標示，如下：
0000000001 （第1瓶）
0000000010 （第2瓶）
0000000011 （第3瓶）
......
1111101000 （第1000瓶）
接下來，從右到左從每一位上為1的瓶子裡取出一滴藥水混合成一瓶並依次編號。比如從右邊第一位開始，把為1的藥水混合並編號為1號瓶；第二位中把所有為1的藥水混合並編號為2號瓶，依次類推。
把10只小白鼠從右到左依次排列，且餵食編號從1到10的瓶子裡的藥水。24小時後，死掉的小白鼠位置上標記為1，其餘的標記為0，把結果轉換成十進制，即為有毒的藥水編號。
4、約瑟夫環算法
有15個基督徒和15個非基督徒在海上遇險，為了能讓一部分人活下來不得不將其中15個人扔到海里面去。
於是有個人想了個辦法就是大家圍成一個圈，由某個人開始從1報數，報到9的人就扔到海里面，他後面的人接著從1開始報數，報到9的人繼續扔到海里面，直到扔掉15個人。
由於上帝的保佑，15個基督徒都倖免於難，問這些人最開始是怎麼站的，哪些位置是基督徒哪些位置是非基督徒。
PHP代碼如下：
<code>public function circle($arr, $key)
{
$counter = $index = $num = 0;
while ($counter < 15) {
if ($arr[$index]) {
$num += 1;
if ($num == $key) {
$arr[$index] = false;
$counter += 1;
$num = 0;
}
$index += 1;
}
}
return $arr;
}/<code>
5、判斷下面擴號是否閉合，左右對稱即為閉合： ((()))，)(())，(())))，(((((())，(()())，()()。
解題思路：我們可以通過棧來實現，遇到左括號進棧,遇到右括號出棧(如果棧裡沒有,說明不閉合),遍歷到最後元素,判斷棧內為空,即為閉合
PHP代碼如下：
<code>function checkStr($str)
{
$stack = [];
for ($i = 0; $i < strlen($str); $i++) {
if ($str[$i] == '(') {
$stack[] = $str[$i];
} elseif ($str[$i] == ')') {
if (empty($stack)) {
return false;
}
array_pop($stack);
}
}
if (count($stack) > 0) {
return false;
}
return true;
}/<code>6、五人分魚
A、B、C、D、E五人在某天夜裡合夥捕魚 最後疲憊不堪各自睡覺
第二天A第一個醒來 他將魚分為5份 扔掉多餘的1條 拿走自己的一份
B第二個醒來 也將魚分為5份 扔掉多餘的1條 拿走自己的一份
然後C、D、E依次醒來也按同樣的方式分魚 問他們至少捕了多少條魚？
解題思路：使用窮舉法，假設有x條魚，那麼 x-1除以5可以整除；剩下的魚的數量為((x-1)/5)*4,這個數量同樣滿足前邊的條件。
python代碼如下：
<code>def fish(): """ 五人分魚 """ fish = 1 while True: total = fish enough = True for _ in range(5): if (total - 1) % 5 == 0: total = (total - 1) // 5 * 4 else: enough = False break if enough: print(fish) break fish += 1/<code>
7、歸併排序
排序思想：把一個數組平分成兩個數組，然後分別再把兩個數組分別平均分成兩個數組，直到每個數組中只有一個元素為止；然後依次把兩個數組排序合併成有序的數組直到最終合併完成
python代碼如下：
<code>def merge_sort(arr):
""" 歸併法/分治法排序 """
if len(arr) < 2:
return arr[:]
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
print(left)
print(right)
print('\n')
result = []
index_left, index_right = 0, 0
while index_left < len(left) and index_right < len(right):
if left[index_left] <= right[index_right]:
result.append(left[index_left])
index_left += 1
else:
result.append(right[index_right])
index_right += 1
result += left[index_left:]
result += right[index_right:]
return result/<code>8、選擇排序
排序原理：取需排序數組的第一個值，作為基準比較值，然後從第二個值開始循環，依次跟這個基準值做比較，如果比基準值小，則交換位置。第二次循環，則取第二個值作為基準值，依此類推。
python代碼如下：
<code>def select_sort(origin_items): """ 選擇排序算法 """ items = origin_items[:] for i in range(len(items) -1): min_index = i for j in range(i + 1, len(items)): if items[j] < items[min_index]: min_index = j items[i], items[min_index] = items[min_index], items[i] return items/<code>
9、冒泡排序
排序思想：從第一個數組元素開始，依次比較相鄰兩個元素的值，保持大的數值在後邊，那麼第一次循環過後，最大的一個數就到了最後的位置。
第二次循環從0開始到倒數第二個元素，因為最後一個元素已經是最大的了，無需在進行比較，然後重複上述步驟，依次類推。
python代碼如下：
<code>def bubble_sort(origin_items): """ 冒泡排序算法 """ items = origin_items[:] for i in range(len(items) - 1): for j in range(0, len(items) - 1 -i): if items[j] > items[j + 1]: items[j], items[j + 1] = items[j + 1], items[j] return items/<code>
