PHP インタビューの一般的な基本アルゴリズム (コード例付き)

この記事では、PHP に関する関連知識を提供します。主に、フィボナッチ数再帰法、ファイル ディレクトリのスキャン、二分検索、その他の問題など、一般的な基本アルゴリズムに関する関連コンテンツを紹介します。見てみましょう。実際のコードをベースにしていますので、皆様のお役に立てれば幸いです。

推奨学習: 「PHP ビデオ チュートリアル 」

序文

PHP とは世界で最高の言語である PHPer にはアルゴリズムは冗長であるとかつて考えられており、面接ではアルゴリズムが少し検討されることがよくあります。ほとんどの面接状況では誰もがバブル ソートを書くように求められると思いますが、PHPer の中には、バブル ソートもありません。ソートには書くのに長い時間がかかります (私もそうです)

一般的に、インタビューを処理するには次のアルゴリズムで十分です。 ！ ！間違いがある場合は、コメントして修正してください。ありがとうございます。

#完了

#フィボナッチ数列

• #フォルダーのスキャン

• 二分検索

• バブル ソート

• クイック ソート

• LeetCode 質問 1
TODO

##ヒープソート

• 選択ソート

• リンク リスト フリップ

• ダイナミック プログラミング

• <?php
  class Algorithmic {
      /***
       * 斐波那契数递归法，f(n) = f(n-1) + f(n-2) 递归层级太多，调用栈爆满，100层
       */
      function fib($n) {
          if ($n < 2) {
              return 1;
          } else {
              return $this->fib($n - 1) + $this->fib($n - 2);
          }
      }
      /***
       * 使用数组存储每一个fib(n)的数值，空间复杂度增加
       * @param $dir
       * @return array
       */
      function fib2($n) {
          if ($n < 2) {
              return 1;
          } else {
              $arr = [1, 1];
              for ($i = 2; $i <= $n; $i++) {
                  $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
              }
          }
          return $arr[$n];
      }
      /***
       * 使用两个临时变量存储前两个值fib(n)的数值，空间复杂度增加比数组降低
       * @param $dir
       * @return array
       */
      function fib3($n) {
          if ($n < 2) {
              return 1;
          } else {
              $last = 1;  //等式第二项
              $lastLast = 1;  //等式第一项
              for ($i = 2; $i <= $n; $i++) {
                  $current = $last + $lastLast;
                  $lastLast = $last;
                  $last = $current;
              }
              return $current;
          }
      }
      /***
       * 扫描文件目录
       * @param $dir
       * @return array
       */
      function scanFile($dir) {
          $fileList = [];
          if (is_dir($dir)) {
              $dh = opendir($dir);
              while ($file = readdir($dh)) {
                  if ($file == &#39;.&#39; || $file == &#39;..&#39;) continue;  //linux下一切皆文件
                  $newDir = $dir . &#39;/&#39; . $file;
                  if (is_dir($newDir)) {
                      $fileList[][$file] = $this->scanFile($newDir);
                  } else {
                      $fileList[] = $file;
                  }
              }
              closedir($dh);
          }
          return $fileList;
      }
      /***
       * 二分查找
       */
      function binarySort($arr, $target) {
          if (!is_array($arr) || count($arr) < 2) {
              return $arr;
          }
          $len = count($arr);
          $start = 0;
          $end = $len - 1;
          while ($start <= $end) {
              $middle = floor(($start + $end) / 2) ;
              if ($arr[$middle] == $target) {
                  return $middle;
              } elseif ($arr[$middle] < $target) {
                  $start = $middle + 1;
              } else {
                  $end = $middle - 1;
              }
          }
          return false;
      }
      /***
       * 冒泡排序
       */
      function bubbleSort($arr) {
          for ($i = count($arr) - 1; $i > 0; $i--) {
              for ($j = 0; $j < $i; $j++) {
                  if ($arr[$j+1] < $arr[$j]) {
                      $temp = $arr[$j];
                      $arr[$j] = $arr[$j+1];
                      $arr[$j+1] = $temp;
                  }
              }
          }
          return $arr;
      }
      /***
       * 快排序
       */
      function quickSort($arr) {
          if (!is_array($arr) || count($arr) < 2) {
              return $arr;
          }
          $base = $arr[0];
          $left = [];
          $right = [];
          for ($i = 1; $i <= count($arr) - 1; $i++) {
              if ($arr[$i] < $base) {
                  $left[] = $arr[$i];
              } else {
                  $right[] = $arr[$i];
              }
          }
          return array_merge(array_merge($this->quickSort($left),[$base]), $this->quickSort($right));
      }
      /***
       * 两数之和， LeetCode第一题
       * @param $arr
       */
      function twoSum($arr, $sum = 8){
          $tempArr = [];
          foreach ($arr as $k => $v) {
              if (isset($tempArr[$v])) {
                  return [$k, $tempArr[$v]];
              }
              $tempArr[$sum-$v] = $k;
          }
          return [];
      }
  }
  $algorithmic = new Algorithmic();
  //var_dump($algorithmic->scanFile("./"));
  //var_dump($algorithmic->twoSum([4,5,3,4,5,67,787]));
  //var_dump($algorithmic->fib3(4));  // 1 1 2 3 5
  //var_dump($algorithmic->binarySort([1,3, 4, 5,7,9], 3));  //
  var_dump($algorithmic->quickSort([14,5,13,114,4,3,167,87,14]));

  推奨学習: 「

  PHP ビデオ チュートリアル
」

以上がPHP インタビューの一般的な基本アルゴリズム (コード例付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。