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

2020/06/10 22:53 下午 posted in  技术 随记 comments

今下午一个小时三道题的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声明就是charint的时候忘了根据ASCII码进行-'0',尤其是最后这个错误,愣是查了半天代码才看出来这个错。改过来的时候就剩10分钟了……真的闹心啊……数据结构、算法和ACM学的东西全还给杨老师、沙老师和寰哥了……日了狗了……

目测此题也可以通过栈和递归实现。欢迎大佬给本蒟蒻分享方法。

题三:树

由于时间有限,这个题没有时间看和做了。好像是个最小生成树问题。有心人可以在留言区评论。

由于这是测试赛,题目并不怎么难……这么看来正式赛专业组已经凉透了,只能大众组求虐了……做成这个熊样真的很暴露问题,以此为契机,计划每天做几个题,多刷刷LeetCode吧。