如果你遇到了什么算法题或脑筋急转弯题。可以留言给我。我们一起完善。
之前写过一篇关于学习与刷题的。【轻知识】算法的学习与刷LeetCode
学习与刷题请看那篇文章。资料要选择的看。
公司名 PHP 算法题
这样搜，去看考啥。或者LeetCode上弄个会员看大厂考什么。
我面试遇到的脑筋急转弯
1.烧绳子问题
一根绳子不规则，烧完它1个小时，怎么计时 30分钟。
答案：两头烧。（折叠烧不对。你就记住两头烧，这是面试官要的答案。）
(参考：烧绳子问题：烧一根不均匀的绳，从头烧到尾总共需要1个小时）
我面试遇到的算法题
-
给你四个坐标点，判断它们能不能组成一个矩形，如判断 ([0,0],[0,1],[1,1],[1,0]) 能组成一个矩形。
高频的高级排序
leetcode 912. 排序数组 只能用n log n的排序来做这道题。不然都超时。
归并
自上而下——递归
class Solution {
public function mergeSort(array $arr) :array {
$count = count($arr);
$this->_mergeSort($arr, 0, $count -1);
return $arr;
}
private function _mergeSort(array &$arr, $l, $r) {
if ($l >= $r) {
return ;
}
$mid = floor(($l + $r) / 2);
$this->_mergeSort($arr, $l, $mid);
$this->_mergeSort($arr, $mid + 1, $r);
$this->_merge($arr, $l, $mid, $r);
}
private function _merge(array &$arr, $l, $mid, $r) {
$aux = [];
for ($i=$l; $i <= $r; $i++) {
$aux[$i - $l] = $arr[$i];
}
$i = $l;
$j = $mid + 1;
for ($k=$l; $k <= $r; $k++) {
if ($i > $mid) {
$arr[$k] = $aux[$j - $l];
$j++;
} elseif ($j > $r) {
$arr[$k] = $aux[$i - $l];
$i++;
} elseif ($aux[$i - $l] < $aux[$j - $l]) {
$arr[$k] = $aux[$i - $l];
$i++;
} else {
$arr[$k] = $aux[$j - $l];
$j++;
}
}
}
}
自下而上——迭代
_merge方法不动。只改mergeSort。
class Solution {
public function mergeSort(array $arr) :array {
$count = count($arr);
for ($sz = 1; $sz <= $count ; $sz += $sz) {
for ($i=0; $i < $count; $i += $sz + $sz) {
$this->_merge($arr, $i, $i + $sz - 1, min($i + $sz + $sz - 1, $count - 1));
}
}
return $arr;
}
private function _merge(array &$arr, $l, $mid, $r) {
$aux = [];
for ($i=$l; $i <= $r; $i++) {
$aux[$i - $l] = $arr[$i];
}
$i = $l;
$j = $mid + 1;
for ($k=$l; $k <= $r; $k++) {
if ($i > $mid) {
$arr[$k] = $aux[$j - $l];
$j++;
} elseif ($j > $r) {
$arr[$k] = $aux[$i - $l];
$i++;
} elseif ($aux[$i - $l] < $aux[$j - $l]) {
$arr[$k] = $aux[$i - $l];
$i++;
} else {
$arr[$k] = $aux[$j - $l];
$j++;
}
}
}
}
延伸问题：归并排序求逆序对。 493. 翻转对
快排（Quick Sort）
递归：单路（边）
单路排下去。跟指定元素值相等的很多。则大于等于的那部分可能会过长。
class Solution {
function sortArray($nums) {
$this->_quickSort($nums, 0, count($nums) - 1);
return $nums;
}
private function _quickSort(&$arr, $l, $r) {
if ($l >= $r) {
return ;
}
$p = $this->_partition($arr, $l, $r);
$this->_quickSort($arr, $l, $p - 1);
$this->_quickSort($arr, $p + 1, $r);
}
private function _partition(&$arr, $l, $r) :int {
$randIndex = rand($l, $r);
[$arr[$l], $arr[$randIndex]] = [$arr[$randIndex],$arr[$l]];
$val = $arr[$l];
$j = $l;
for ($i=$l+1; $i <= $r; $i++) {
if ($arr[$i] < $val) {
[$arr[$j+1], $arr[$i]] = [$arr[$i],$arr[$j+1]];
$j++;
}
}
[$arr[$j], $arr[$l]] = [$arr[$l],$arr[$j]];
return $j;
}
}
递归：双路（边）
单路排下去。跟指定元素值相等的很多。则大于等于的那部分可能会过长。用双路。等于数均匀分开。解决一边过大。
private function _partition(&$arr, $l, $r) :int {
$randIndex = rand($l, $r);
[$arr[$l], $arr[$randIndex]] = [$arr[$randIndex],$arr[$l]];
$val = $arr[$l];
$i = $l + 1;
$j = $r;
while (true) {
while ($i <= $r && $arr[$i] < $val) {
$i++;
}
while ($j >= ($l + 1) && $arr[$j] > $val) {
$j--;
}
if ($i > $j) {
break;
}
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
$i++;
$j--;
}
[$arr[$l], $arr[$j]] = [$arr[$j], $arr[$l]];
return $j;
}
递归：三路（边）
小于 指定 值的，放右边，相等的放中间，大于的放左边。然后分别针对 右边跟左边再递归。对那种很多相等值的情况是有利的。
private function _quickSort(&$arr, $l, $r) {
if ($l >= $r) {
return ;
}
$randIndex = rand($l, $r);
[$arr[$l], $arr[$randIndex]] = [$arr[$randIndex],$arr[$l]];
$val = $arr[$l];
$lt = $l;
$gt = $r + 1;
$i = $l + 1;
while ($i < $gt) {
if ($arr[$i] < $val) {
[$arr[$i], $arr[$lt + 1]] = [$arr[$lt + 1], $arr[$i]];
$lt++;
$i++;
} elseif ($arr[$i] > $val) {
[$arr[$i], $arr[$gt - 1]] = [$arr[$gt - 1], $arr[$i]];
$gt--;
} else {
$i++;
}
}
[$arr[$l], $arr[$lt]] = [$arr[$lt], $arr[$l]];
$this->_quickSort($arr, $l, $lt - 1);
$this->_quickSort($arr, $gt, $r);
}
延伸问题：Quick Sort 的思路请求数组中第K大元素。
非递归（模拟栈）实现，请看《漫画算法 小灰的算法之旅》。
堆排序
php代码可以参考我临摹的代码 https://github.com/yanshinian/Algorithm-and-data-structure-PHP/tree/master/Heap-and-Priority-Queue
关于这个三个排序：我列的比较精简。如若你跟我一样笨拙。一时不好弄会。请看《算法与数据结构-综合提升 C++版》第三章跟第四章。讲的清晰明了。
刷题
目前累计140来道（刚入门的水平）。我最怕的是考hard级别的题（一道也没刷）。不过索性。只有大厂才会这么考。我简历都过不去。固然如此。以后也会把学算法当成乐趣。
如果想过算法关。是必须刷题的。慢慢就有感觉了。
比如，数组有序。就想到二分。
比如，链表，可以递归可以遍历。可以用dummyhead方便操作。用双指针检查环。
比如，树，逃不掉，dfs跟bfs。其他的就是在基础上做些事情。
推荐两本书：《剑指Offer：名企面试官精讲典型编程题》《程序员面试金典》
内容来源
- 《算法与数据结构-综合提升 C++版》
网友评论