vivo-2021Java笔试-愚人节拆礼品盒问题

描述

小v所在的公司即将举行年会，年会方案设计过程中必不可少的一项就是抽奖活动。小v在本次活动中被委以重任，负责抽奖活动的策划；为了让中奖的礼物更加精美且富有神秘感，打算采用礼品盒来包装奖品，此时小v发挥了自己的创意想捉弄一下获奖的同事，便采取了多重包装来包装奖品。

现给出一个字符串，并假定用一对圆括号( )表示一个礼品盒，0表示奖品，你能据此帮获奖者算出最少要拆多少个礼品盒才能拿到奖品吗？

输入：一行字符串，仅有'(‘、’)’、’0′ 组成，其中一对'(‘ ‘)’表示一个礼品盒，‘0’表示奖品；输入的字符串一定是有效的，即'(‘ ‘)’一定是成对出现的。

输出：输出结果为一个数字，表示小v要拆的最少礼品盒数量

输入样例 1 ：(()(()((()(0)))))

输出样例 1：5

输入样例 2 ：(((0)))

输出样例 2：3

解决这个题目首先得理解这个意思，和理清楚思路才能更好的写出代码，因此这里我画一个图来帮助理解，就以样例1为例：

假设H就是我们要的奖品0，每一个框就是一个礼盒，代表”()”。首先要拆最外层A，然后看到有B和C两个大礼盒，可以选择先拆B或者C，假设拆到B是空礼盒，那得继续拆C，然后拆了C又遇到D和E两个大礼盒，以此类推。因此按照此思路要拆到奖品H，最少的路线是A-C-E-F-H，所以这个题最少要拆5次，最多的路线也就是运气最差的路线，所有礼盒都拆完才拆到H，那就是A-B-C-D-E-F-G-H，运气最差也最多拆8次而已。但是在实际情况中，我们都是随机拆的，所以拆到礼盒的次数也就是5-8次之间。因此根据思路可以编写出以下求最少和最多次数的代码。

public static int solutionMix(String str) {
		int sum = 0; // 要拆的次数
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '0') {
				break; // 拆到奖品了
			} else if (str.charAt(i) == '(') {
				sum++; // 拆开包装，还不确定，先算上这次
			} else {
				sum--; // "()"确定是空盒子，计算最少次数就丢弃不算了
			}
		}
		return sum;
	}

public static int solutionMax(String str) {
		int sum = 0;// 要拆的次数
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				sum++; // 因为"()"代表一个礼盒，所以只要遇到"("算拆一次就好了
			} else if (str.charAt(i) == '0') {
				return sum; // 拆到奖品就退出了
			}
		}
		return sum;
	}

好了，写个main方法跑一下看看结果吧：