平衡括号的成本-yiteyi-C++库

当每个左括号都有一个右括号，如“（）”或“（（））”或“（（））”等时，括号被称为平衡括号。不正确的平衡包括“（”或“）”（）这里的任务是纠正括号的顺序，使其以最小的成本完成。把括号移到一个括号以上要花1美元。如果括号无法平衡，则打印-1。 例如：

null

输入：（）输出：0 说明： 已经平衡了输入：））(( 产出：4 说明： 首先，在位置1 ^圣去最后一个位置，花费3美元，所以我们得到（（））。然后，）在位置1 ^圣去2号 ^钕职位成本1。所以，最后我们得到（）。因此，总成本为4。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

算法：

把大括号串起来。
运行循环到字符串大小以存储开始和结束大括号的计数。
检查开口撑杆的数量是否等于闭合撑杆的数量。
如果大括号不相等，则打印-1，说明字符串无法平衡。否则继续。
最初，检查0 ^th 索引字符串是否包含左大括号或右大括号。如果我们得到一个大括号，然后在数组中索引0处存储+1，否则如果存在大括号，则在0处放置-1 ^th 指数
现在从1开始运行一个循环 ^圣索引到数组长度。
- 如果索引i处存在开口大括号，则将+1添加到上一个索引i-1处的值，并将总和存储在索引i处。
- 如果索引i处存在右大括号，则将-1添加到上一个索引i-1处的值，并将总和存储在索引i处。
- 如果索引i处的值为负值，即小于0，则将数组[i]的绝对值添加到变量中（下面程序中的ans）。
最后我们得到了变量ans中的最小成本。

以下是上述方法的实施情况：

C++

                         // CPP code to calculate the minimum cost                       
                         // to make the given parentheses balanced                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     costToBalance(string s)                       
                         {                       
                                                 if                                     (s.length() == 0)                       
                                                 cout << 0 << endl;                       
           
                                                 // To store absolute count of                       
                                                 // balanced and unbalanced parenthesis                       
                                                 int                                     ans = 0;                       
           
                                                 // o(open bracket) stores count of '(' and                       
                                                 // c(close bracket) stores count of ')'                       
                                                 int                                     o = 0, c = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < s.length(); i++) {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 o++;                       
                                                 if                                     (s[i] ==                                     ')'                                     )                       
                                                 c++;                       
                                                 }                       
           
                                                 if                                     (o != c)                       
                                                 return                                     -1;                       
           
                                                 int                                     a[s.size()];                       
                                                 if                                     (s[0] ==                                     '('                                     )                       
                                                 a[0] = 1;                       
                                                 else                       
                                                 a[0] = -1;                       
           
                                                 if                                     (a[0] < 0)                       
                                                 ans +=                                     abs                                     (a[0]);                       
           
                                                 for                                     (                                     int                                     i = 1; i < s.length(); i++) {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 a[i] = a[i - 1] + 1;                       
                                                 else                       
                                                 a[i] = a[i - 1] - 1;                       
                                                 if                                     (a[i] < 0)                       
                                                 ans +=                                     abs                                     (a[i]);                       
                                                 }                       
           
                                                 return                                     ans;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string s;                       
                                                 s =                                     ")))((("                                     ;                       
           
                                                 cout << costToBalance(s) << endl;                       
           
                                                 s =                                     "))(("                                     ;                       
                                                 cout << costToBalance(s) << endl;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to calculate the                       
                         // minimum cost to make the                       
                         // given parentheses balanced                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     costToBalance(String s)                       
                                                 {                       
                                                 if                                     (s.length() ==                                     0                                     )                       
                                                 System.out.println(                                     0                                     );                       
                                   
                                                 // To store absolute count                       
                                                 // of balanced and unbalanced                       
                                                 // parenthesis                       
                                                 int                                     ans =                                     0                                     ;                       
                                   
                                                 // o(open bracket) stores count                       
                                                 // of '(' and c(close bracket)                       
                                                 // stores count of ')'                       
                                                 int                                     o =                                     0                                     , c =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < s.length(); i++)                       
                                                 {                       
                                                 if                                     (s.charAt(i) ==                                     '('                                     )                       
                                                 o++;                       
                                                 if                                     (s.charAt(i) ==                                     ')'                                     )                       
                                                 c++;                       
                                                 }                       
                                   
                                                 if                                     (o != c)                       
                                                 return                                     -                                     1                                     ;                       
                                   
                                                 int                                     []a =                                     new                                     int                                     [s.length()];                       
                                                 if                                     (s.charAt(                                     0                                     ) ==                                     '('                                     )                       
                                                 a[                                     0                                     ] =                                     1                                     ;                       
                                                 else                       
                                                 a[                                     0                                     ] = -                                     1                                     ;                       
                                   
                                                 if                                     (a[                                     0                                     ] <                                     0                                     )                       
                                                 ans += Math.abs(a[                                     0                                     ]);                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < s.length(); i++)                       
                                                 {                       
                                                 if                                     (s.charAt(i) ==                                     '('                                     )                       
                                                 a[i] = a[i -                                     1                                     ] +                                     1                                     ;                       
                                                 else                       
                                                 a[i] = a[i -                                     1                                     ] -                                     1                                     ;                       
                                                 if                                     (a[i] <                                     0                                     )                       
                                                 ans += Math.abs(a[i]);                       
                                                 }                       
                                   
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 String s;                       
                                                 s =                                     ")))((("                                     ;                       
                                   
                                                 System.out.println(costToBalance(s));                       
                                   
                                                 s =                                     "))(("                                     ;                       
                                                 System.out.println(costToBalance(s));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

Python3

                         # Python 3 code to calculate the minimum cost                       
                         # to make the given parentheses balanced                       
                         def                                     costToBalance(s):                       
                                                 if                                     (                                     len                                     (s)                                     =                                     =                                     0                                     ):                       
                                                 print                                     (                                     0                                     )                       
           
                                                 # To store absolute count of                       
                                                 # balanced and unbalanced parenthesis                       
                                                 ans                                     =                                     0                       
           
                                                 # o(open bracket) stores count of '(' and                       
                                                 # c(close bracket) stores count of ')'                       
                                                 o                                     =                                     0                       
                                                 c                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (s)):                       
                                                 if                                     (s[i]                                     =                                     =                                     '('                                     ):                       
                                                 o                                     +                                     =                                     1                       
                                                 if                                     (s[i]                                     =                                     =                                     ')'                                     ):                       
                                                 c                                     +                                     =                                     1                       
           
                                                 if                                     (o !                                     =                                     c):                       
                                                 return                                     -                                     1                       
           
                                                 a                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     len                                     (s))]                       
                                                 if                                     (s[                                     0                                     ]                                     =                                     =                                     '('                                     ):                       
                                                 a[                                     0                                     ]                                     =                                     1                       
                                                 else                                     :                       
                                                 a[                                     0                                     ]                                     =                                     -                                     1                       
           
                                                 if                                     (a[                                     0                                     ] <                                     0                                     ):                       
                                                 ans                                     +                                     =                                     abs                                     (a[                                     0                                     ])                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     len                                     (s)):                       
                                                 if                                     (s[i]                                     =                                     =                                     '('                                     ):                       
                                                 a[i]                                     =                                     a[i                                     -                                     1                                     ]                                     +                                     1                       
                                                 else                                     :                       
                                                 a[i]                                     =                                     a[i                                     -                                     1                                     ]                                     -                                     1                       
                                                 if                                     (a[i] <                                     0                                     ):                       
                                                 ans                                     +                                     =                                     abs                                     (a[i])                       
           
                                                 return                                     ans                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 s                                     =                                     ")))((("                       
           
                                                 print                                     (costToBalance(s))                       
                                                 s                                     =                                     "))(("                       
                                                 print                                     (costToBalance(s))                       
                                   
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# code to calculate the                       
                         // minimum cost to make the                       
                         // given parentheses balanced                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     costToBalance(                                     string                                     s)                       
                                                 {                       
                                                 if                                     (s.Length == 0)                       
                                                 Console.WriteLine(0);                       
                                   
                                                 // To store absolute count                       
                                                 // of balanced and unbalanced                       
                                                 // parenthesis                       
                                                 int                                     ans = 0;                       
                                   
                                                 // o(open bracket) stores count                       
                                                 // of '(' and c(close bracket)                       
                                                 // stores count of ')'                       
                                                 int                                     o = 0, c = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < s.Length; i++)                       
                                                 {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 o++;                       
                                                 if                                     (s[i] ==                                     ')'                                     )                       
                                                 c++;                       
                                                 }                       
                                   
                                                 if                                     (o != c)                       
                                                 return                                     -1;                       
                                   
                                                 int                                     []a =                                     new                                     int                                     [s.Length];                       
                                                 if                                     (s[0] ==                                     '('                                     )                       
                                                 a[0] = 1;                       
                                                 else                       
                                                 a[0] = -1;                       
                                   
                                                 if                                     (a[0] < 0)                       
                                                 ans += Math.Abs(a[0]);                       
                                   
                                                 for                                     (                                     int                                     i = 1; i < s.Length; i++)                       
                                                 {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 a[i] = a[i - 1] + 1;                       
                                                 else                       
                                                 a[i] = a[i - 1] - 1;                       
                                                 if                                     (a[i] < 0)                       
                                                 ans += Math.Abs(a[i]);                       
                                                 }                       
                                   
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     s;                       
                                                 s =                                     ")))((("                                     ;                       
                                   
                                                 Console.WriteLine (costToBalance(s));                       
                                   
                                                 s =                                     "))(("                                     ;                       
                                                 Console.WriteLine (costToBalance(s));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

Javascript

                         <script>                       
           
                         // javascript code to calculate the                       
                         // minimum cost to make the                       
                         // given parentheses balanced                       
           
                                                 function                                     costToBalance( s)                       
                                                 {                       
                                                 if                                     (s.length == 0)                       
                                                 document.write(0);                       
                                   
                                                 // To store absolute count                       
                                                 // of balanced and unbalanced                       
                                                 // parenthesis                       
                                                 var                                     ans = 0;                       
                                   
                                                 // o(open bracket) stores count                       
                                                 // of '(' and c(close bracket)                       
                                                 // stores count of ')'                       
                                                 var                                     o = 0, c = 0;                       
                                   
                                                 for                                     (                                     var                                     i = 0; i < s.length; i++)                       
                                                 {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 o++;                       
                                                 if                                     (s[i] ==                                     ')'                                     )                       
                                                 c++;                       
                                                 }                       
                                   
                                                 if                                     (o != c)                       
                                                 return                                     -1;                       
                                   
                                                 var                                     a =                                     new                                     Array(s.Length);                       
                                                 if                                     (s[0] ==                                     '('                                     )                       
                                                 a[0] = 1;                       
                                                 else                       
                                                 a[0] = -1;                       
                                   
                                                 if                                     (a[0] < 0)                       
                                                 ans += Math.abs(a[0]);                       
                                   
                                                 for                                     (                                     var                                     i = 1; i < s.length; i++)                       
                                                 {                       
                                                 if                                     (s[i] ==                                     '('                                     )                       
                                                 a[i] = a[i - 1] + 1;                       
                                                 else                       
                                                 a[i] = a[i - 1] - 1;                       
                                                 if                                     (a[i] < 0)                       
                                                 ans += Math.abs(a[i]);                       
                                                 }                       
                                   
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 var                                     s;                       
                                                 s =                                     ")))((("                                     ;                       
                                   
                                                 document.write(costToBalance(s) +                                     "<br>"                                     );                       
                                   
                                                 s =                                     "))(("                                     ;                       
                                                 document.write(costToBalance(s) +                                     "<br>"                                     );                       
           
                         // This code is contributed by bunnyram19.                       
                         </script>                       

输出：

时间复杂性： O（N），N=字符串长度

辅助空间： O（N）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章