???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条回答 默认 最新

  • 安果移不动 2017-01-21 15:39
    已采纳

    package com.example.xietiaozhe;

    /**

    • Name: Test
    • Action:
    • Author: liuan
    • creatTime:2017-01-21 23:23 */

    public class Test {
    /**
    * 一个由N个括号组成的字符串S,开括号” ( “ 和闭括号 “ ) “ ,
    * 目标是将S分成两个部分,
    * 使得第一部分中的开放括号的数量等于第二部分中的闭合括号的数量。
    * 更正式地说,我们正在寻找一个整数K
    *
    * 例如,给定S = “ ( ( ) ) ) ) ( ”,K等于4,因为:
    S的前四个字符“ ( ( ) ) ”,包含两个开括号
    S的剩余三个字符“ ) ) ( ”,包含两个闭括号。
    写一个函数
    *
    * @param args
    */
    public static void main(String[] args) {
    String s="(())))(";
    int solution = solution(s);
    System.out.println(solution);

    }
    
    private static int  solution(String s) {
        int number=0;
        int leftNumber=0;
        int rightNumber=0;
        for (int i = 0; i < s.length(); i++) {
            //左右情况判断
            if(s.charAt(i)=='('){
    
                leftNumber++;
            }else if(s.charAt(s.length()-i)==')'){
                rightNumber++;
            }
            if(leftNumber==rightNumber&leftNumber!=0){
                number=leftNumber*2;
            }
    
        }
    
        return  number;
    }
    

    }
    结果是4 求采纳

    已采纳该答案
    1 打赏 评论
  • dabocaiqq 2017-01-21 15:30
    打赏 评论

相关推荐 更多相似问题