算法题：清除数字 (难度：简单)
题目描述：给定一个字符串 s，其中包含小写英文字母和数字。你需要重复执行以下操作，直到字符串中不再包含数字：找到第一个数字，并删除该数字以及它左侧最近的非数字字符。最终返回删除所有数字后的字符串。
示例：
-
输入: s = “abc”
-
输出: “abc” (字符串中没有数字)
-
输入: s = “cb34”
-
输出: “” (首先删除 ‘3’ 和 ‘b’，得到 “c4″，然后删除 ‘4’ 和 ‘c’，得到 “”)
解题思路：
本题可以使用栈来高效解决。我们从左到右遍历字符串：
- 初始化: 创建一个空栈。
- 遍历: 对于每个字符：
- 如果是数字，则尝试从栈顶弹出最近的非数字字符（如果栈非空）。
- 如果是非数字字符，则将其压入栈中。
- 结果: 遍历结束后，栈中剩余的字符即为最终结果。
PHP 代码实现：
<?php function clearDigits(string $s): string { $stack = []; for ($i = 0; $i < strlen($s); $i++) { $char = $s[$i]; if (is_numeric($char)) { if (!empty($stack)) { array_pop($stack); // 删除左侧最近的非数字字符 } } else { $stack[] = $char; // 将非数字字符压入栈 } } return implode("", $stack); // 将栈中字符拼接成字符串 } // 测试用例 $s1 = "abc"; $s2 = "cb34"; $s3 = "a1b2c3d4"; $s4 = "123abc456"; $s5 = "a1b2c3"; echo clearDigits($s1) . " "; // Output: abc echo clearDigits($s2) . " "; // Output: echo clearDigits($s3) . " "; // Output: echo clearDigits($s4) . " "; // Output: echo clearDigits($s5) . " "; // Output: ?>
登录后复制
时间复杂度: O(n)，其中 n 为字符串长度。每个字符最多被访问一次。 空间复杂度: O(n)，最坏情况下，栈中可能存储所有非数字字符。
改进建议: 代码中可以添加更详细的错误处理和输入校验，例如检查输入字符串是否为空或只包含数字等情况。 此外，可以考虑使用更简洁的代码风格，例如使用 ctype_di() 函数代替 is_numeric() 来判断字符是否为数字。
希望这个解答对您有所帮助！ 请记住，这只是一个示例，实际的代码实现可能需要根据具体需求进行调整。
以上就是清除数字的详细内容，更多请关注php中文网其它相关文章！
微信扫一扫打赏
支付宝扫一扫打赏
