php面试算法题技巧_PHPPYTHON经典算法面试题集算法实例解析面试通关宝典

本日给大家先容一些，经典的算法集锦。
节制这些经典算法，在往后的口试过程中就不用担心算法不过关啦。
话不多说，来看实例吧。

杨辉三角

解题思路：设置两个变量分别为行数和列数，第一列和末了一列的值都为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] . "\t"; } echo "<br>";}

解题思路：定义两个指针：慢指针（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; //环的入口节点 } }}

解题思路：把每一瓶水按顺序编号并用二进制标示，如下：0000000001 （第1瓶）0000000010 （第2瓶）0000000011 （第3瓶）......1111101000 （第1000瓶）接下来，从右到左从每一位上为1的瓶子里取出一滴药水稠浊成一瓶并依次编号。
比如从右边第一位开始，把为1的药水稠浊并编号为1号瓶；第二位中把所有为1的药水稠浊并编号为2号瓶，依次类推。
把10只小白鼠从右到左依次排列，且喂食编号从1到10的瓶子里的药水。
24小时后，去世掉的小白鼠位置上标记为1，别的的标记为0，把结果转换成十进制，即为有毒的药水编号。

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

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

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 += 17、归并排序

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

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('\n')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

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

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

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

第二次循环从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