PHP堆栈与回溯算法应用

PHP堆栈与回溯算法应用堆栈和回溯算法在解决某些问题时很有效。PHP虽然不是算法竞赛语言但理解这些算法对日常开发有帮助。今天说说PHP中堆栈和回溯算法的应用。用SplStack实现栈。php$stack new SplStack();$stack-push(10);$stack-push(20);$stack-push(30);echo $stack-pop() . \n; // 30echo $stack-pop() . \n; // 20echo $stack-top() . \n; // 10?用栈实现括号匹配。phpfunction isValidBrackets(string $s): bool{$stack new SplStack();$pairs [) (, ] [, } {];for ($i 0; $i strlen($s); $i) {$char $s[$i];if (in_array($char, [(, [, {])) {$stack-push($char);} elseif (in_array($char, [), ], }])) {if ($stack-isEmpty() || $stack-pop() ! ($pairs[$char] ?? null)) {return false;}}}return $stack-isEmpty();}var_dump(isValidBrackets(()[]{})); // truevar_dump(isValidBrackets(([)])); // falsevar_dump(isValidBrackets({[]})); // true?用回溯算法解决八皇后问题。phpfunction solveNQueens(int $n): array{$solutions [];$board array_fill(0, $n, -1);function backtrack(array $board, int $row, int $n, array $solutions): void{if ($row $n) {$solutions[] $board;return;}for ($col 0; $col $n; $col) {if (isSafe($board, $row, $col)) {$board[$row] $col;backtrack($board, $row 1, $n, $solutions);$board[$row] -1;}}}function isSafe(array $board, int $row, int $col): bool{for ($i 0; $i $row; $i) {if ($board[$i] $col) return false;if (abs($board[$i] - $col) abs($i - $row)) return false;}return true;}backtrack($board, 0, $n, $solutions);return $solutions;}$solutions solveNQueens(4);echo 四皇后问题有 . count($solutions) . 个解\n;foreach ($solutions as $i $solution) {echo 解 . ($i 1) . : ;foreach ($solution as $pos) echo $pos . ;echo \n;}?深度优先搜索。phpclass TreeNode{public function __construct(public string $value,public array $children []) {}}function dfs(TreeNode $node, string $target): ?string{if ($node-value $target) return $node-value;foreach ($node-children as $child) {$result dfs($child, $target);if ($result ! null) return $result;}return null;}?回溯算法解决子集问题。phpfunction subsets(array $nums): array{$result [[]];foreach ($nums as $num) {$count count($result);for ($i 0; $i $count; $i) {$subset $result[$i];$subset[] $num;$result[] $subset;}}return $result;}print_r(subsets([1, 2, 3]));?堆栈和回溯算法在特定场景中很有效。栈适合括号匹配、表达式求值等。回溯适合组合优化、搜索问题。PHP虽然性能不是最好但实现这些算法用于理解原理已经足够了。