记一次OJ测试赛算法实现思路

lsekfe

今下午一个小时三道题的OJ测试赛告一段落。首先一首《凉凉》送给自己。整天工作CRUD以及近期代码几乎没碰，再加上OJ刷题的日子已经过去五年了，导致犯了好几个傻瓜的基础错误，浪费了原本就宝贵的时间。题二原本估计能拿一半分的（如果后台样例形式在我估计之中的话）。
　　现就测试赛三题中的前两题进行算法实现思路的整理。首先是本文中题目并不是原封不动的摘抄，这里只对关键要求进行回忆和描述，同时为了避免不必要的麻烦，因此题目描述进行了一定变形，但基本逻辑一致。另外我的思路不一定是正确和最优的，欢迎留言讨论。
　　使用语言： Java。编译器可使用标准类以及java.util.*类。
　　题一：数组与遍历
　　题目描述： 一家公司有n个营业点，编号从1到n，每次会对第i个营业点到第j个营业点供应m个货物。现有多条供货记录放置在一个二维数组里。假如有5个营业点，供货记录如下：[[1,2,10],[2,3,30],[2,5,60]]。程序需要计算出每个供货点接到的货物个数，本例返回结果应为[10,100,90,60,60]。二维数组大小、营业点个数有最高限制(不过我记得不深了，忘记是5000000还是50000000了)，0＜i＜j＜n。
　　解题思路： 本题形参表第一个为供货记录，二维数组；第二个为营业点个数，int型。本题很简单，简单的思路就是在二维数组遍历前建好以营业点为数量的一维数组。后遍历二维数组，再取第二层数组信息依次作为i,j,m，建循环由i到j，作为一维数组的下标，并加m进该一维数组元素中。
　　本题唯一注意的地方是自建一维数组下标。数组下标是0开头，n-1为最后一个。
　　题二：字符串
　　题目描述： 根据所输入字符串进行还原。例如样例WOSHINI[2BA]，程序应该返回WOSHINIBABA。如样例[3WO]SHINI[2BA]，应返回WOWOWOSHINIBABA。样例有嵌套的情况，例如WOSHI[3NI[2BA]]，则应该是WOSHINIBABANIBABANIBABA。程序样例给出的嵌套不多于10层。
　　解题思路： 我这题当时做的时候没考虑嵌套情况。其实就是将字符串拆为字符，通过遍历判断中括号范围进行预先拼接，后与无括号部分进行最终拼接。
　　本来寻思这个题后面样例再怎么说有两三个非嵌套的吧……但是根据提交成绩来看好像就一个……另外这个题的弱智问题犯得太多了，不是丢int声明就是char转int的时候忘了根据ASCII码进行-'0'，尤其是最后这个错误，愣是查了半天代码才看出来这个错。改过来的时候就剩10分钟了……真的闹心啊……数据结构、算法和ACM学的东西全还给杨老师、沙老师和寰哥了……日了狗了……
　　目测此题也可以通过栈和递归实现。欢迎大佬给本蒟蒻分享方法。
　　题三：树
　　由于时间有限，这个题没有时间看和做了。好像是个最小生成树问题。有心人可以在留言区评论。
　　由于这是测试赛，题目并不怎么难……这么看来正式赛专业组已经凉透了，只能大众组求虐了……做成这个熊样真的很暴露问题，以此为契机，计划每天做几个题，多刷刷LeetCode吧。