算法是每個程序員必備的技能之一
今天給大家介紹一些,經典的算法集錦。掌握這些經典算法,在以後的面試過程中就不用擔心算法不過關啦。話不多說,來看實例吧。
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>