当前位置：首页 > news >正文

[Swift]LeetCode856. 括号的分数 | Score of Parentheses

news 来源：原创 2024/4/26 16:54:57

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10594301.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a balanced parentheses string S, compute the score of the string based on the following rule:

() has score 1
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Note:

S is a balanced parentheses string, containing only (and ).
2 <= S.length <= 50

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

提示：

S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50

Runtime: 4 ms

Memory Usage: 19.5 MB

 1 class Solution {
 2     func scoreOfParentheses(_ S: String) -> Int {
 3         var stack:[Int] = [Int]()
 4         var cur:Int = 0
 5         for c in S
 6         {
 7             if c == "("
 8             {
 9                 stack.append(cur)
10                 cur = 0
11             }
12             else
13             {
14                 cur = stack.removeLast() + max(cur * 2, 1)
15             }
16         }
17         return cur
18     }
19 }

4ms

 1 class Solution {
 2     func scoreOfParentheses(_ S: String) -> Int {
 3         guard S.count > 1 && S.count%2 == 0 else {
 4             return 0
 5         }
 6         
 7         var mulArr = [Int]()
 8         mulArr.append(0)
 9         var mulInx = 0
10         let strArr = Array(S)
11         for i in 0..<strArr.count-1 {
12             let phrase = "\(strArr[i])\(strArr[i+1])"
13             switch phrase{
14                 case "((":
15                     mulInx += 1
16                     if mulInx == mulArr.count  {
17                         mulArr.append(0)
18                     } 
19                 case "))":                
20                     mulArr[mulInx-1] += mulArr[mulInx]*2
21                     mulArr[mulInx] = 0
22                     mulInx -= 1
23                     
24                 case "()":
25                     mulArr[mulInx] += 1
26                 case ")(":
27                     continue
28                 default:
29                     continue
30             }
31         }
32         return mulArr[0]
33     }
34 }

8ms

 1 class Solution {
 2     func scoreOfParentheses(_ S: String) -> Int {
 3         guard S.count % 2 == 0 else {
 4             // this means that it is an invalid parentheses combination
 5             return -1
 6         }
 7         
 8         var sum: Int = 0 
 9         var stack: [Character] = []
10         var shouldCount: Bool = false 
11         for character in S {
12             if character == "(" {
13                 stack.append("(")
14                 shouldCount = true 
15             } else {
16                 // if character == ")"
17                 stack.removeLast()
18                 if shouldCount {
19                     sum += Int(pow(Double(2), Double(stack.count)))
20                     shouldCount = false 
21                 }
22             }
23         }
24         return sum
25     }
26 }

12ms

 1 class Solution {
 2     func scoreOfParentheses(_ S: String) -> Int {
 3         if S.count == 0 {
 4             return 0
 5         }
 6         let chars = Array(S)
 7         
 8         // O(n)方法，因为每一次括号的嵌套都会乘以2，所以对于一个基础"()"，
 9         // 它前面有多少个开"("，就要乘以多少个2，2^(d-1),d是"()"自己的"("加上前面发现的开"("
10         // 把(()(()))转化为 -> (()) + ((())) = 2^1 + 2^2 = 6
11         var sum = 0, leftCount = 0
12         var stack = [Character]()
13         
14         for char in chars {
15             if char == "(" {
16                 // add to stack
17                 leftCount += 1
18             } else {
19                 if let previous = stack.last, previous == "(" {
20                     sum += Int(pow(Double(2), Double(leftCount - 1)))
21                 }
22                 leftCount -= 1
23             }
24             stack.append(char)
25         }
26         
27         return sum
28     }
29 }

12ms

 1 class Solution {
 2     func scoreOfParentheses(_ S: String) -> Int {
 3     var arr = [0]    
 4     for c in Array(S) {
 5         if c == "(" {
 6             arr.append(0)
 7         } else {
 8             let last = arr.removeLast()
 9             if last == 0 {
10                 arr[arr.count-1] += 1
11             } else {
12                 arr[arr.count-1] += (2 * last)
13             }
14         }
15     }    
16     return arr.last!
17   }
18 }

16ms

 1 class Solution {        
 2     func scoreOfParentheses(_ S: String) -> Int {
 3         if let result = Int(S) {
 4             return result
 5         }
 6         
 7         var array = Array(S).map({ String($0) })
 8         var i = array.count - 1
 9         while i > 0 {
10             if array[i - 1] == "(" && array[i] == ")" {
11                 array.remove(at: i)
12                 array[i - 1] = "1"
13                 i -= 1
14             }
15             
16             i -= 1
17         }
18         
19         return Int(scoreOfParentheses(array)) ?? 0
20     }
21     
22     func scoreOfParentheses(_ string: [String]) -> String {
23         if string.count == 1 {
24             return string[0]
25         }
26         var string = string
27         
28         var i = string.count - 1
29         while i > 0 {
30             let index = i
31             
32             if let num1 = Int(String(string[index])), 
33                 let num2 = Int(String(string[index - 1])){
34                 string.remove(at: index)
35                 string[index - 1] = String(num1 + num2)
36                 i -= 1
37             }
38             i -= 1
39         }
40         
41         i = string.count - 1
42         while i > 1 {
43                 let index = i
44             
45                 if string[index] == ")", string[index - 2] == "(", 
46                     let num = Int(string[index - 1]) {
47                     string.remove(at: index)
48                     string.remove(at: index - 1)
49                     string[index - 2] = String(num * 2)
50                     i -= 2
51                 }
52             i -= 1
53         }
54         
55         return scoreOfParentheses(string)
56     }
57 }