title: 拆盒子问题

date: 2019-09-12 15:09:07

tags: vivo公司的笔试题

拆礼物盒问题

题目描述

四月一日快到了，Tom想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Tom为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，A表示礼物，Tom想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。

输入：只包含‘（’，‘）’，‘A’三种字符的字符串，其中A表示礼物

输出：最少需要拆盒子的次数

解题思路

由于题目没有说明是从左边开始拆还是右边开始拆，所以左右两边要分别考虑。左边开始拆的时候，遇到‘（’表示一次拆盒子，‘）‘说明这次拆盒子无效。比如（（（））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;
    }
}
           

原文链接：https://www.cnblogs.com/theskulls/p/5706712.html?tdsourcetag=s_pcqq_aiomsg