算法是每个程序员必备的技能之一

今天给大家介绍一些，经典的算法集锦。掌握这些经典算法，在以后的面试过程中就不用担心算法不过关啦。话不多说，来看实例吧。

1、用PHP实现杨辉三角

杨辉三角

解题思路：设置两个变量分别为行数和列数，第一列和最后一列的值都为1(即代码中的$j = 0和$i = $j),中间的数值计算方式为上一行的本列数+上一行的前一列数(即$a[$i][$j] = $a[$i-1][$j-1] + $a[$i-1][$j])

PHP代码实现如下：

<?php //PHP实现杨辉三角$n = 10;//总行数for ($i = 0; $i < $n; $i++) {//i:行数 j:列数  for ($j = 0; $j <= $i; $j++) {    if ($i == $j || $j == 0) {      $a[$i][$j] = 1;    } else {      $a[$i][$j] = $a[$i-1][$j] + $a[$i-1][$j-1];    }    echo $a[$i][$j] . "";  }  echo "
";}

2、写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处即P点。

解题思路：定义两个指针：慢指针(slow),快指针( fast)。slow指针一次走1个结点，fast指针一次走2个结点。如果链表中有环，那么慢指针一定会再某一个时刻追上快指针(slow == fast)。如果没有环，则快指针会第一个走到NULL。

PHP代码如下：

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; //环的入口节点    }  }}

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代码如下：

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;    }

5、判断下面扩号是否闭合，左右对称即为闭合： ((()))，)(())，(())))，(((((())，(()())，()()。

解题思路：我们可以通过栈来实现，遇到左括号进栈,遇到右括号出栈(如果栈里没有,说明不闭合),遍历到最后元素,判断栈内为空,即为闭合

PHP代码如下：

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;    }

6、五人分鱼

A、B、C、D、E五人在某天夜里合伙捕鱼 最后疲惫不堪各自睡觉
第二天A第一个醒来 他将鱼分为5份 扔掉多余的1条 拿走自己的一份
B第二个醒来 也将鱼分为5份 扔掉多余的1条 拿走自己的一份
然后C、D、E依次醒来也按同样的方式分鱼 问他们至少捕了多少条鱼？

解题思路：使用穷举法，假设有x条鱼，那么 x-1除以5可以整除；剩下的鱼的数量为((x-1)/5)*4,这个数量同样满足前边的条件。

python代码如下：

def fish():""" 五人分鱼 """fish = 1while True:total = fishenough = Truefor _ in range(5):if (total - 1) % 5 == 0:total = (total - 1) // 5 * 4else:enough = Falsebreakif enough:print(fish)breakfish += 1

7、归并排序

排序思想：把一个数组平分成两个数组，然后分别再把两个数组分别平均分成两个数组，直到每个数组中只有一个元素为止；然后依次把两个数组排序合并成有序的数组直到最终合并完成

python代码如下：

def merge_sort(arr):""" 归并法/分治法排序 """if len(arr) < 2:return arr[:]mid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right) def merge(left, right):print(left)print(right)print('')result = []index_left, index_right = 0, 0while index_left < len(left) and index_right < len(right):if left[index_left] <= right[index_right]:result.append(left[index_left])index_left += 1else:result.append(right[index_right])index_right += 1result += left[index_left:]result += right[index_right:]return result

8、选择排序

排序原理：取需排序数组的第一个值，作为基准比较值，然后从第二个值开始循环，依次跟这个基准值做比较，如果比基准值小，则交换位置。第二次循环，则取第二个值作为基准值，依此类推。

python代码如下：

def select_sort(origin_items):""" 选择排序算法 """items = origin_items[:]for i in range(len(items) -1):min_index = ifor j in range(i + 1, len(items)):if items[j] < items[min_index]:min_index = jitems[i], items[min_index] = items[min_index], items[i]return items

9、冒泡排序

排序思想：从第一个数组元素开始，依次比较相邻两个元素的值，保持大的数值在后边，那么第一次循环过后，最大的一个数就到了最后的位置。

第二次循环从0开始到倒数第二个元素，因为最后一个元素已经是最大的了，无需在进行比较，然后重复上述步骤，依次类推。

python代码如下：

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