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