- 有一母牛，到4岁可生育，每年一头，所生均是一样的母牛，到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /**
* 计算某年的牛数量
* @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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* 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;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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级台阶。要求用程序来求出一共有多少种走法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* 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）的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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 的字母异位词
使用了数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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'));
|
- 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
使用栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| 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 中的每个元素表示需要经过多少天才能等来温度的升高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 示例:
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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| /**
* 遍历所有情况 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;
}
|
