| Tom的生日礼物 | |
| 描述: |
四月一日快到了，Tom想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Tom为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。 用()表示一个盒子，A表示礼物，Tom想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。 |
| 运行时间限制: | 无限制 |
| 内存限制: | 无限制 |
| 输入: |
本题目包含多组测试，请处理到文件结束。 |
| 输出: |
对于每组测试，请在一行里面输出愚人指数。 |
| 样例输入: |
((((A)()))()) |
| 样例输出: |
4 |
| 答案提示: | |
解题
左右分别考虑
左边开始拆的时候：遇到(一次拆盒子，)说明这次拆盒子无效
((()) A(())),如这种情况,只需要一次就好了
题目没有说明左右拆的情况，我两边都进行了考虑
这个题目有点坑的是，求得是最小拆盒子的次数，但是在你不知道这个盒子是否空的时候，提交空的盒子不拆能够通过，否则通不过。
这个应该考得就是你的思考问题全面不全面吧，面试的时候有这样的题目，自己能够发现和面试官讨论最好了
import java.util.LinkedList;
import java.util.Scanner;
public class Main2{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
char[] strA = in.nextLine().toCharArray();
int count = getCount(strA);
System.out.println(count);
} in.close();
}
/**
* 左右拆盒子次数的最小值
* @param strA
* @return
*/
public static int getCount(char[] strA){
int left = getLeftCount(strA);
int right = getRightCount(strA);
return left>right?right:left;
}
/**
* 右边开始拆
* ):一次拆盒子，count++
* (:说明这次是无效的拆盒子，所以count--
* @param strA
* @return
*/
public static int getRightCount(char[] strA){
if(strA==null||strA.length==0){
return 0;
}
int count = 0;
LinkedList<Character> stack = new LinkedList<Character>();
for(int i=strA.length-1;i>=0;i--){
if(strA[i]=='A'){
return count;
}
if(strA[i]==')'){
stack.push(')');
count++;
}else if(strA[i] == '('){
stack.pop();
count--;
}
}
return count;
}
/**
* 左边开始拆
* (:一次拆盒子，count++
* ):说明这次是无效的拆盒子，所以count--
* @param strA
* @return
*/
public static int getLeftCount(char[] strA){
if(strA==null||strA.length==0){
return 0;
}
int count = 0;
LinkedList<Character> stack = new LinkedList<Character>();
for(int i=0;i<strA.length;i++){
if(strA[i]=='A'){
return count;
}
if(strA[i]=='('){
stack.push('(');
count++;
}else if(strA[i] == ')'){
stack.pop();
count--;
}
}
return count;
}
}