- 在线等，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仅由字符“(” 或“ ) ”组成。
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：输入里不要出现空格
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;
}
}
-
- qq_19857675 这个答案我运行出来结果不对呢，按题中给的例子，运行出来结果是0，应该是4
- 大约 3 年之前 回复
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;
}
}
-
- qq_19857675 您试试用S = “ ( ( ) ) ) ) ( ”测出来结果是3，但正确的应该是4呢
- 大约 3 年之前 回复
