华为OD机试中的“箱子之字形摆放”问题是一个经典的数组处理和模拟算法问题。以下是对该问题的详细解析:
一、题目描述
有一批箱子,用一个字符串来表示每个箱子上的编号(编号由字母和数字组成)。要求将这批箱子按照之字形顺序摆放在宽度为n的空地上,并输出它们的摆放位置。之字形摆放要求每行的箱子是交替从左到右,或者从右到左摆放的,形成类似“Z”字形的排列。
二、输入描述
输入只有一行字符串,格式为“str n”,其中str是表示箱子的字符串,n是空地的宽度(也即每行可以摆放的箱子数量)。
三、输出描述
输出箱子的摆放结果,每行输出一组摆放好的箱子,并且不应该输出多余的空行。
四、解题思路
为了正确地按照之字形摆放箱子,可以将这个问题分解为以下几个步骤:
- 初始化矩阵:根据宽度n,创建一个二维数组(或列表),每一行用于存放按照之字形摆放的字符。
- 确定每个字符的位置:通过遍历字符串中的每个字符,使用行索引来确定字符应该放置在哪一行。如果当前字符应该从左往右摆放,则按照正常顺序填充;如果当前字符应该从右往左摆放,则需要将字符放置在倒数位置。
- 交替顺序控制:通过对当前字符的索引值进行模运算,判断当前行是需要从左到右还是从右到左摆放。可以通过一个标志位来控制当前行的摆放方向。
- 输出矩阵:最后将每一行的字符拼接成字符串输出。
五、具体实现
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class ZigZagBoxesSimplified {
public static void main(String[] args) {
// 创建Scanner对象以读取输入,本例中未使用输入,直接使用了定义好的字符串
Scanner sc = new Scanner(System.in);
// 定义一个包含字母和数字的字符串,用于后续处理
String line = sc.nextLine();
// 将字符串按空格分割为两部分,第一部分为字母串,第二部分为数字
String[] strings = line.split(" ");
// 将字符串中的数字转换为整数,用于确定列的宽度
int n = Integer.parseInt(strings[1]);
// map key用来存放每一行的下标,value对应的字符串
Map<Integer, String> map = new HashMap<>();
// 提取字母串,用于后续的处理
String letterStr = strings[0];
// 遍历字母串,根据列的宽度进行分组
for (int i = 0; i < letterStr.length(); i++) {
// 计算当前字符属于第几列
int columnIdx = i/n;
// 根据列的奇偶性决定字符的存放顺序
int index;
// 如果是偶数列,那么是正序,奇数列是倒序
if (columnIdx % 2 == 0) {
// 索引正序
index = i % n;
}else {
// 如果是奇数列,那么是倒序
index = n - 1 - i % n;
}
// 获取当前索引下的字符串,如果不存在则返回空字符串
String str = map.getOrDefault(index, "");
// 将当前字符添加到对应的字符串末尾
String val = str + letterStr.charAt(i);
// 将更新后的字符串存回map
map.put(index, val);
}
// 遍历map,打印每一行的字符串
for (int key : map.keySet()) {
System.out.println(map.get(key));
}
}
}
六、示例
示例1:
- 输入:
ABCDEFG 3
- 输出:
AFG
BE
CD
示例2:
- 输入:
HELLOWORLD 4
- 输出:
HOD
ELW
LOR
(注意:由于示例2的字符串长度不是4的倍数,因此最后一行可能不满4个箱子,但这不影响之字形摆放的规则。)
七、运行示例解析
输入解析
- 输入字符串为
ABCDEFG 3
。 strings[0]
为ABCDEFG
,表示字母串。strings[1]
为3
,表示每列的宽度。
代码逻辑解析
-
初始化:
- 创建一个
Scanner
对象sc
来读取输入(尽管在这个例子中未使用)。 - 读取输入行
line
并将其按空格分割成strings
数组。 - 将
strings[1]
转换为整数n
,即每列的宽度为 3。 - 创建一个
HashMap
map
,键为整数(表示列中的行索引),值为字符串(表示该行中的字符)。
- 创建一个
-
处理字母串:
- 遍历字母串
letterStr
中的每个字符。 - 计算当前字符的列索引
columnIdx
,使用i / n
(整数除法)。 - 根据列索引的奇偶性决定字符在行中的位置:
- 偶数列(0, 2, …):字符按正序添加到行中。
- 奇数列(1, 3, …):字符按倒序添加到行中。
- 计算字符在行中的索引
index
:- 偶数列:
index = i % n
- 奇数列:
index = n - 1 - i % n
- 偶数列:
- 使用
map.getOrDefault(index, "")
获取当前行索引下的字符串(如果不存在则为空字符串)。 - 将当前字符添加到该字符串的末尾,并更新
map
。
- 遍历字母串
-
输出结果:
- 遍历
map
,按行索引的顺序打印每行的字符串。
- 遍历
运行示例解析
输入:ABCDEFG 3
- 字母串:
ABCDEFG
- 列宽:
3
处理过程:
-
字符
A
:- 列索引
0
(偶数列) - 行索引
0
(index = 0 % 3 = 0
) map
更新为{0=A}
- 列索引
-
字符
B
:- 列索引
0
(偶数列) - 行索引
1
(index = 1 % 3 = 1
) map
更新为{0=A, 1=B}
- 列索引
-
字符
C
:- 列索引
0
(偶数列) - 行索引
2
(index = 2 % 3 = 2
) map
更新为{0=A, 1=B, 2=C}
- 列索引
-
字符
D
:- 列索引
1
(奇数列) - 行索引
2
(index = 3 - 1 - (0 % 3) = 2
,倒序) map
更新为{0=A, 1=B, 2=CD}
- 列索引
-
字符
E
:- 列索引
1
(奇数列) - 行索引
1
(index = 3 - 1 - (1 % 3) = 1
,倒序) map
更新为{0=A, 1=BE, 2=CD}
- 列索引
-
字符
F
:- 列索引
1
(奇数列) - 行索引
0
(index = 3 - 1 - (2 % 3) = 0
,倒序) map
更新为{0=AF, 1=BE, 2=CD}
- 列索引
-
字符
G
:- 列索引
2
(偶数列) - 行索引
0
(index = 3 % 3 = 0
) map
更新为{0=AFG, 1=BE, 2=CD}
- 列索引
输出结果:
AFG
BE
CD
简单来说就是
以输入ABCDEFG 3
为例,详细步骤如下:
- 初始化哈希表为空。
- 处理字符
A
:列索引0
(偶数列),行索引0
,更新哈希表为{0=A}
。 - 处理字符
B
:列索引0
(偶数列),行索引1
,更新哈希表为{0=A, 1=B}
。 - 处理字符
C
:列索引0
(偶数列),行索引2
,更新哈希表为{0=A, 1=B, 2=C}
。 - 处理字符
D
:列索引1
(奇数列),行索引2
(从右到左),更新哈希表为{0=A, 1=B, 2=CD}
。 - 处理字符
E
:列索引1
(奇数列),行索引1
(从右到左),更新哈希表为{0=A, 1=BE, 2=CD}
。 - 处理字符
F
:列索引1
(奇数列),行索引0
(从右到左),更新哈希表为{0=AF, 1=BE, 2=CD}
。 - 处理字符
G
:列索引2
(偶数列),行索引0
,更新哈希表为{0=AFG, 1=BE, 2=CD}
。 - 输出结果:
AFG BE CD