描述
小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方法跑一下看看结果吧:
转载请注明:路飞博客 » vivo-2021Java笔试-愚人节拆礼品盒问题
热门推荐
- Java随机生成姓名、手机号、邮箱、住址代码
- vivo-2021Java笔试-智能手机产能问题
- com.mysql.jdbc.Driver和com.mysql.cj.jdbc.Driver的区别 serverTimezone设定
- Cannot resolve method findOne(java.lang.Long)
- Sort和PageRequest方法过时问题的解决办法
- NotBlank过时处理和@NotEmpty、@NotNull、@NotBlank 的区别
- Server Tomcat v8.5 Server at localhost was unable to start within 45
- request和response的setCharacterEncoding()方法