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

> 作者：zning（https://ning.ae） · 发布：2020/06/10 22:53 下午 (UTC+8) · 原文：https://zning.me/15918008140272.html

今下午一个小时三道题的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吧。