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

相关文章

此处评论已关闭