代码随想录算法训练营第九天 | leetcode：有效的括号,删除字符串中的所有相邻重复项,逆波兰表达式求值
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 20. 有效的括号
#需要注意的地方
- 需要注意题目描述。不是左右括号都存在就符合题意，左括号必须以正确的顺序闭合，意思是”( [ ) ]”这种虽然符合左右括号都存在但是不符合括号顺序，需要修改为” [ ( ) ]”才对的，需要左右括号位置对称。
- 取$stack->top() 注意要判断栈是否为空。
解题方法
使用一个栈，当循环变量目标字符串时，碰到左括号则入栈左括号对应的右括号，遇到右括号时则判断栈顶的右括号是否相同，相同则pop出栈，不相同则代表不对称，返回false。最后需要判断栈是否为空，为空的话代表当前字符串符合对称要求，返回true。否则返回false。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(n)
code
/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
if(strlen($s) % 2 != 0){
return false;
}
$data = [
"(" => ")" ,
"{" => "}" ,
"[" => "]"
];
$stack = new SplStack();
for ($i = 0; $i < strlen($s); $i++) {
if($data[$s[$i]]){
$stack->push($data[$s[$i]]);
}else{
//一定要判断栈是否为空再取top(),否则会报错
if(!$stack->isEmpty() && $stack->top() == $s[$i]){
$stack->pop();
}else{
return false;
}
}
}
return $stack->isEmpty();
}Problem: 1047. 删除字符串中的所有相邻重复项
#需要注意的地方
需要注意题目最后输出的是字符串，且有顺序要求。
解题方法
- 使用SplStack栈类解题，循环遍历目标字符串，依次入栈，与栈顶值对比，如果相等则pop弹出值，否则继续入栈。继续进行下一次循环。直到遍历结束。最后遍历栈，用字符串拼接栈的值，因为栈有先进后出的特性，所以需要注意最后是否需要反转字符串。
- 因为PHP的数组也集成了一些栈的特性，例如array_push,array_pop等特性，所以这题也可以使用数据来解题，并且数组可以使用implode直接转换为字符串。比较省事。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(n)
解法1
/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
if(strlen($s) % 2 != 0){
return false;
}/**
* @param String $s
* @return String
*/
function removeDuplicates($s) {
if(strlen($s) == 1){
return $s;
}
//当栈不为空，遍历依次与栈顶做对比，如果相等则出栈，遍历也进入下一次，如果不相等则继续入栈
$res = [];
$stack = new SplStack();
for ($i = 0; $i < strlen($s); $i++) {
if($stack->isEmpty() || $stack->top() != $s[$i]){
$stack->push($s[$i]);
}else{
$stack->pop();
}
}
//拼接字符串
$result = "";
while(!$stack->isEmpty()){
$result.= $stack->top();
$stack->pop();
}
//反转字符串
return strrev($result);
}解法2
/**
* @param String $s
* @return String
*/
function removeDuplicates($s) {
if(strlen($s) == 1){
return $s;
}
$res = [];
for ($i = 0; $i < strlen($s); $i++) {
if(empty($res) || end($res) != $s[$i]){
array_push($res, $s[$i]);
}else{
array_pop($res);
}
}
//因为res是数组没有先进后出的问题，所以字符串不用反转
$res = implode('', $res);
return $res;
}Problem: 150. 逆波兰表达式求值
#需要注意的地方
两个整数之间的除法总是 “向零截断” 。即：只取整数部分。
解题方法
逆波兰表达式相当于是二叉树中的后序遍历。遇到数字则入栈；遇到算符则取出栈顶两个数字（后出栈在前，前出栈在后）进行计算，并将结果压入栈中。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(n)
栈解法
/**
* @param String[] $tokens
* @return Integer
*/
function evalRPN($tokens) {
$stack = new SplStack();
for($i = 0; $i < count($tokens); $i++){
if(is_numeric($tokens[$i])){
$stack->push($tokens[$i]);
}else{
$nums1 = $stack->pop();
$nums2 = $stack->pop();
if($tokens[$i] == "-") $stack->push($nums2 - $nums1);
if($tokens[$i] == "+") $stack->push($nums2 + $nums1);
if($tokens[$i] == "*") $stack->push($nums2 * $nums1);
//两个整数之间的除法总是 向零截断 。即只取整数部分，向上ceil()向下floor()取整都不行
if($tokens[$i] == "/") $stack->push(intval($nums2 / $nums1));
}
}
return $stack->pop();
}数组解法
/**
* @param String[] $tokens
* @return Integer
*/
function evalRPN($tokens) {
$res = [];
for($i = 0; $i < count($tokens); $i++){
if(is_numeric($tokens[$i])){
array_push($res, $tokens[$i]);
}else{
$nums1 = array_pop($res);
$nums2 = array_pop($res);
if($tokens[$i] == "-") array_push($res, $nums2 - $nums1);
if($tokens[$i] == "+") array_push($res, $nums2 + $nums1);
if($tokens[$i] == "*") array_push($res, $nums2 * $nums1);
//两个整数之间的除法总是 向零截断 。即只取整数部分，向上ceil()向下floor()取整都不行
if($tokens[$i] == "/") array_push($res, intval($nums2 / $nums1));
}
}
return $res[0];
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号