No Comments

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 非典型 算法题」标签，已有 629 位童鞋阅读过。

相关文章

此处评论已关闭