PHP 非典型 算法题
有一母牛,到4岁可生育,每年一头,所生均是一样的母牛,到15岁绝育,不再能生,20岁死亡,问n年后有多少头牛。
/** * 计算某年的牛数量 * @param int $year 第几年 * @param int $birthYear 生育年 * @param int $oldYear 停止生育年 * @param int $deadYear 死亡年 * @return int 总数 */ function cow_num(int $year, int $birthYear = 4, int $oldYear = 15, int $deadYear = 20): int { // 初始数量1头牛1 static $num = 1; for ($i = 1; $i <= $year; $i++) { if ($i >= $birthYear and $i <= $oldYear) { $num++; // 每生一头牛则递归这一过程,他的时间要减去他的出生年数 cow_num($year - $i); } if ($i == $deadYear) { $num--; } } return $num; } echo cow_num(8);
一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。
/** * 1-n编号猴子,数到m就踢出去,求最后一个猴子号码 * @param int $m 数到m * @param int $n n个猴 * @return int 最后猴子号码 */ function monkey(int $m, int $n) { // 生成n个猴 $list = range(1, $n); $i = 1; while (count($list) != 1) { // 踢第m个猴子 if ($i == $m) { $k = key($list); unset($list[$k]); // 指针在末尾时候被删除需要重置 if(!key($list)){ reset($list); } $i = 1; continue; } // 下一个猴 $i += 1; $no = next($list); // 移动到末尾需要重置 if ($no === false) { reset($list); } } return current($list); } $res = monkey($m = 3,$n = 10); echo $res;
function king($n, $m) { $monkeys = range(1, $n); //创建1到n数组 $i = 0; // 循环条件为猴子数量大于1 while (count($monkeys) > 1) { // $i为数组下标;$i+1为猴子标号 if (($i + 1) % $m == 0) { // 余数等于0表示正好第m个,删除,用unset删除保持下标关系 unset($monkeys[$i]); } else { // 如果余数不等于0,则把数组下标为$i的放最后,形成一个圆形结构 array_push($monkeys, $monkeys[$i]); unset($monkeys[$i]); } // $i循环+1,不断把猴子删除,或 push到数组 $i++; } return current($monkeys); // 猴子数量等于1时输出猴子标号,得出猴王 } echo king(10, 3);
- 一个如下数字三角形,寻找一条从顶部到底部的最佳路线,使得路径上所经过数字之和最大.只许求出最大值
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
class Solution
{
// 子状态保存:任一数到最低端的最大和保存在这里
public $mem = [];
public function maxSum(array $arr, int $x, int $y): int
{
// 边界状态
if ($x == count($arr) - 1) {
return $arr[$x][$y];
}
$max1 = $arr[$x][$y] + $this->maxSum($arr, $x + 1, $y);
$max2 = $arr[$x][$y] + $this->maxSum($arr, $x + 1, $y + 1);
$this->mem[$x][$y] = max($max1, $max2);
return $this->mem[$x][$y];
}
}
$arr = [
[7],
[3, 8],
[8, 1, 0],
[2, 7, 4, 4],
[4, 5, 2, 6, 5],
];
$solution = new Solution;
$res = $solution->maxSum($arr, 0, 0);
var_dump($res);
有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
/** * F(1) = 1 * F(2) = 2 * F(3) = F(2)+F(1) // 因为最后一步只能走1步或者走2步 * ... * F(n) = F(n-1)+F(n-2) // n为总共多少层级 */ class Solution { public function climb($n): int { if ($n == 1 || $n == 2) { return $n; } return $this->climb($n - 1) + $this->climb($n - 2); } } $res = (new Solution)->climb(10); var_export($res);
给定长度为n的序列a,从a中抽取出一个子序列,这个子序列需要单调递增.问最长的上升子序列(LIS)的长度
function solution($arr) { $result = []; foreach ($arr as $key => $value) { $result[$key] = 1; } for ($i = 0; $i < count($arr); $i++) { for ($j = 0; $j < $i; $j++) { if ($arr[$i] > $arr[$j]) { $result[$i] = max($result[$i], $result[$j] + 1); } } } return $result; } $arr = array(5, 6, 2, 7, 4, 0, -1, 2, 9); $n = solution($arr); var_dump($n);
给定两个字符串 s 和 t,编写一个函数来判断 t 是否是 s 的字母异位词
使用了数组function solution(string $s, string $t) { if (strlen($s) != strlen($t)) { return false; } $res = []; for ($i = 0; $i < strlen($s); $i++) { $res[$s[$i]] = $res[$s[$i]] ?? 0; $res[$t[$i]] = $res[$t[$i]] ?? 0; $res[$s[$i]] += 1; $res[$t[$i]] -= 1; } foreach ($res as $value) { if ($value != 0) { return false; } } return true; } var_dump(solution('anagram', 'nagaraa'));
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
使用栈class Solution { public function isPair($a, $b) { $arr = [$a, $b]; $i = ['[', ']']; $j = ['(', ')']; $k = ['{', '}']; if (empty(array_diff($i, $arr)) || empty(array_diff($j, $arr)) || empty(array_diff($k, $arr))) { return true; } return false; } public function run(string $str) { $stack = []; for ($i = 0; $i < strlen($str); $i++) { $cnt = count($stack); $current = $str[$i]; $top = $stack[$cnt - 1] ?? null; if (!$this->isPair($top, $current)) { array_push($stack, $current); } else { array_pop($stack); } } return count($stack) == 0; } } $str = '{[]}'; var_dump((new Solution)->run($str));
给定一个数组 T 代表了未来几天里每天的温度值,要求返回一个新的数组 D,D 中的每个元素表示需要经过多少天才能等来温度的升高。
示例: T:[23, 25, 21, 19, 22, 26, 23] D:[ 1, 4, 2, 1, 1, 0, 0] function solution(array $arr) { $stack = []; $result = []; foreach ($arr as $i => $value) { while ((($cnt = count($stack)) != 0) && ($arr[$stack[$cnt - 1]] < $value)) { $result[$stack[$cnt - 1]] = $i - $stack[$cnt - 1]; array_pop($stack); } array_push($stack, $i); } while (($cnt = count($stack)) > 0) { $result[array_pop($stack)] = 0; } ksort($result); var_dump($result); } solution([23, 25, 21, 19, 22, 26, 23]);
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]function solution(array $arr, $k) { $deque = []; $cnt = count($arr); $res = []; for ($i = 1; $i < $cnt; $i++) { $value = $arr[$i]; $start = $i; $end = $start + $k; // 从deque末尾开始对比,如队尾的值比当前值小则出队 while (!empty($deque) && $arr[$deque[count($deque) - 1]] < $value) { array_pop($deque); } array_push($deque, $i); // 如果队头部超过了k,需要移除 if ($deque[0] == $i - $k) { var_dump($deque); array_shift($deque); } // 窗口移动中,将双端队列头部最大值保存下来 if ($i >= $k - 1) { $res[$i - $k + 1] = $arr[$deque[0]]; } } return $res; } $arr = [1, 3, -1, -3, 5, 3, 6, 7]; $k = 3; // [3, 3, 5, 5, 6, 7]; var_dump(solution($arr, $k));
求最大子列和,给定一个序列,最大子列和为所有连续子列元素的和中最大者。计算给定整数序列的最大子列和。
例如 [-1, 2, -1, 4, -1, 2] 结果为 6/** * 遍历所有情况 O(n^2) */ function max_sub_seq_sum1($arr) { $cnt = count($arr); $sum = null; $max = null; for ($i = 0; $i < $cnt; $i++) { $sum = 0; for ($j = $i; $j < $cnt; $j++) { $sum += $arr[$j]; if (is_null($max) || ($sum > $max)) { $max = $sum; } } } return $max; } /** * 分而治之 O(n*log2n) */ function divideAndConquer($list, $left, $right, $flag) { if ($left == $right) { return $list[$left]; } $center = (int) floor(($left + $right) / 2); // 左边和 $leftSum = divideAndConquer($list, $left, $center, 'l'); // 右边和 $rightSum = divideAndConquer($list, $center + 1, $right, 'r'); // 向左求和 $leftMax = 0; $leftBorderSum = 0; for ($i = $center; $i >= $left; $i--) { $leftBorderSum += $list[$i]; if ($leftBorderSum > $leftMax) { $leftMax = $leftBorderSum; } } // 向右求和 $rightMax = 0; $rightBorderSum = 0; for ($j = $center + 1; $j <= $right; $j++) { $rightBorderSum += $list[$j]; if ($leftBorderSum > $rightMax) { $rightMax = $rightBorderSum; } } return max($leftSum, $rightSum, $leftBorderSum + $rightBorderSum); } $arr = []; for ($i = 0; $i < 10000; $i++) { $arr[] = mt_rand(1, 10); } $data = $arr; $t1 = microtime(true); $max = max_sub_seq_sum1($arr); $t2 = microtime(true); var_dump($max); // 54993 var_dump($t2 - $t1);// 2.3381989002228 $max = divideAndConquer($data, 0, count($data) - 1, 'in'); $t3 = microtime(true); var_dump($max); // 54993 var_dump($t3 - $t2); // 0.0081760883331299 // 在线处理 // 只要某个地方的和出现了负数就应该重新从零加,因为负数不可能让后面的和变得更大 function onlineProcess($arr) { $max = null; $len = count($arr); $nowSum = 0; for ($i = 0; $i < $len; $i++) { $nowSum += $arr[$i]; if ($nowSum < 0) { $nowSum = 0; } else { if (!$max || $nowSum > $max) { $max = $nowSum; } } } return $max; }
最后更新于 2021-06-28 08:15:09 并被添加「PHP 非典型 算法题」标签,已有 810 位童鞋阅读过。
此处评论已关闭