???477
2017-01-22 12:52
采纳率: 100%
浏览 966
已采纳

在线等,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仅由字符“(” 或“ ) ”组成。

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • Littlechoc 2017-01-22 14:28
    已采纳
        public int solution(String input) {
            if (input == null || input.length() == 0) {
                return -1; // Input Error
            }
    
            // Step1: 统计开闭括号个数
            int leftTotal = 0; // 开括号个数
            for (int i = 0; i < input.length(); i++) {
                char ch = input.charAt(i);
                if (ch == '(') {
                    leftTotal++;
                } else if (ch == ')') {
                    // Do nothing
                } else {
                    return -1; // Input Error
                }
            }
            int rightTotal = input.length() - leftTotal; // 闭括号个数
    
            // Step2: 遍历计算
            int leftCount = 0;
            for (int i = 1; i <= input.length(); i++) {
                char ch = input.charAt(i - 1);
                if (ch == '(') {
                    leftCount++;
                }
                int rightCount = rightTotal - (i - leftCount); // 关键
                if (rightCount == leftCount) { // Success
                    return i;
                }
            }
    
            return 0; // Not Found
        }
    
    

    NOTE:输入里不要出现空格

    打赏 评论
  • baij1230 2017-01-22 13:34

    public class Solution {
    public int solution(String s) {
    char c1 = '(';
    char c2 = ')';
    int in = s.length();
    int i = in%2==0?in/2:in/2+1;
    int k1 = 0;
    int k2 = 0;
    int j = 0;
    char[] cs = s.toCharArray();
    for (int j1 = 0; j1 < i; j1++) {
    if(c1==cs[j1]){
    ++k1;
    }
    }
    for (int j2 = in-1; j2 > i; j2--) {
    if(c2==cs[j2]){
    ++k2;
    }
    }
    if(k1==k2){
    return k1;
    }else if(k1<k2){
    for (int k = 0; k < in-i; k++) {
    if(c1==cs[k+i]){
    ++k1;
    }else{
    --k2;
    }

                if(k1==k2){
                    j = k1;
                    break;
                }
            }
        }else{
            for (int k = in-1; k < i; k--) {
                if(c2==cs[k]){
                    --k1;
                }else{
                    ++k2;
                }
    
                if(k1==k2){
                    j = k2;
                    break;
                }
            }
        }
        return j;
    }
    

    }

    打赏 评论
  • baij1230 2017-01-22 14:15

    public class Solution {

    public int solution(String s) {
        char c1 = '(';
        char c2 = ')';
        int in = s.length();
        int i = in%2==0?in/2:in/2+1;
        int k1 = 0;
        int k2 = 0;
        int j = 0;
        char[] cs = s.toCharArray();
        for (int j1 = 0; j1 < i; j1++) {
            if(c1==cs[j1]){
                ++k1;
            }
        }
        for (int j2 = in-1; j2 > i; j2--) {
            if(c2==cs[j2]){
                ++k2;
            }
        }
        if(k1==k2){
            j = k1;
        }else if(k1<k2){
            for (int k = 0; k < in-i; k++) {
                if(c1==cs[k+i]){
                    ++k1;
                }else{
                    --k2;
                }
    
                if(k1==k2){
                    j = k1;
                    break;
                }
            }
        }else{
            for (int k = in-1; k > i; k--) {
                if(c2==cs[k]){
                    --k1;
                }else{
                    ++k2;
                }
    
                if(k1==k2){
                    j = k2;
                    break;
                }
            }
        }
        int q = in-1;
        int ini = 0;
        while(ini<j){
            if(cs[q--]==c2){
                ini++;
            }
        }
        return q;
    }
    

    }

    打赏 评论

相关推荐 更多相似问题