代码随想录刷题记录 Day11

发表于 更新于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

To Do List

  • DAY 10 回顾
  • LeetCode 20. 有效的括号
  • LeetCode 1047. 删除字符串中的所有相邻重复项
  • LeetCode 150. 逆波兰表达式求值
  • DAY 11 总结

DAY 10 回顾

（）

LeetCode 20. 有效的括号 / Valid Parentheses

1
Difficulty: Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.
Translated by zh-CN 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

Example 1:

1
2
Input: s = "()"
Output: true

Example 2:

1
2
Input: s = "()[]{}"
Output: true

Example 3:

1
2
Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 104

  • s consists of parentheses only '()[]{}'.

    Translated by zh-CN s 仅由括号 '()[]{}' 组成

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = []
    if (s.length % 2 != 0) return false
    else {
        for (let i = 0; i < s.length; i++){
            if(s[i] === "(") stack.push(")")
            else if(s[i] === "[") stack.push("]")
            else if(s[i] === "{") stack.push("}")
            else if(s[i] !== stack.pop()) return false
        }
    }
    return stack.length === 0
};

PS:

LeetCode 1047. 删除字符串中的所有相邻重复项

1
Difficulty: Easy

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Translated by zh-CN 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

Example 1:

1
2
3
4
5
Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

Example 2:

1
2
Input: s = "azxxzy"
Output: "ay"

Constraints:

  • 1 <= s.length <= 105

  • s consists of lowercase English letters.

    Translated by zh-CN S 仅由小写英文字母组成。

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
    let result = []
    for (let i = 0; i < s.length; i++){
        if (!result.length || s[i] !== result[result.length-1]){
            result.push(s[i])
        } else result.pop()
    }
    return result.join('')
};

PS:

LeetCode 150. 逆波兰表达式求值 / Evaluate Reverse Polish Notation

1
Difficulty: Medium

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.

  • Each operand may be an integer or another expression.

  • The division between two integers always truncates toward zero.

  • There will not be any division by zero.

  • The input represents a valid arithmetic expression in a reverse polish notation.

  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

    Translated by zh-CN 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数。
    注意：
    有效的算符为 '+'、'-'、'*' 和 '/' 。
    每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。
    输入是一个根据逆波兰表示法表示的算术表达式。
    答案及所有中间计算结果可以用 32 位 整数表示。

Example 1:

1
2
3
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

1
2
3
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

1
2
3
4
5
6
7
8
9
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

  • 1 <= tokens.length <= 104

  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

    Translated by zh-CN tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  let st = [];
  for (let i = 0; i < tokens.length; i++) {
    if (isNaN(tokens[i])) {
      let n2 = st.pop();
      let n1 = st.pop();
      if (tokens[i] === "+") st.push(n1 + n2);
      else if (tokens[i] === "-") st.push(n1 - n2);
      else if (tokens[i] === "*") st.push(n1 * n2);
      else if (tokens[i] === "/") st.push((n1 / n2) | 0);
    } else st.push(Number(tokens[i]));
  }
  return st[0];
};

PS:

DAY 11 总结

…