代码随想录算法训练营第九天 | leetcode:有效的括号,删除字符串中的所有相邻重复项,逆波兰表达式求值

Problem: 20. 有效的括号

#需要注意的地方

  1. 需要注意题目描述。不是左右括号都存在就符合题意,左括号必须以正确的顺序闭合,意思是”( [ ) ]”这种虽然符合左右括号都存在但是不符合括号顺序,需要修改为” [ ( ) ]”才对的,需要左右括号位置对称。
  2. 取$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. 删除字符串中的所有相邻重复项

#需要注意的地方

需要注意题目最后输出的是字符串,且有顺序要求。

解题方法

  1. 使用SplStack栈类解题,循环遍历目标字符串,依次入栈,与栈顶值对比,如果相等则pop弹出值,否则继续入栈。继续进行下一次循环。直到遍历结束。最后遍历栈,用字符串拼接栈的值,因为栈有先进后出的特性,所以需要注意最后是否需要反转字符串。
  2. 因为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 协议》,转载必须注明作者和本文链接
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!