???477
2017-01-21 15:21
采纳率: 100%
浏览 1.0k

Java 小白诚求编写一道很简单的算法题

大学算法考试题,我没好好学java,现在求大神帮忙,编写出来能运行出结果马上采纳

一个由N个括号组成的字符串S,开括号” ( “ 和闭括号 “ ) “ ,目标是将S分成两个部分,使得第一部分中的开放括号的数量等于第二部分中的闭合括号的数量。更正式地说,我们正在寻找一个整数K
0 <= K <= N,
S的前k个字符中的开括号的数目与S的后面 (N - K)个字符中的闭括号的数目相同。

例如,给定S = “ ( ( ) ) ) ) ( ”,K等于4,因为:
S的前四个字符“ ( ( ) ) ”,包含两个开括号
S的剩余三个字符“ ) ) ( ”,包含两个闭括号。

写一个函数
class Solution {public int solution(string S); }
给定字符串S,返回满足上述条件的K的值。(K总是存在并且是唯一的)。

例如,给定S =“(( ))))(”,函数应该返回4,如上所述。

假设:
N是在范围[0 ... 100,000]内的整数,
字符串S仅由字符” ( “ 或“ ) ”组成。

复杂度
预期最坏情况时间复杂度为O(N);
预期的最坏情况下的空间复杂度为O(1)(不计算输入参数所需的存储空间)。

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

相关推荐 更多相似问题