【华为OD机试】箱子之字形摆放

题目描述

有一批箱子（形式为字符串，设为str），
要求将这批箱子按从上到下以之字形的顺序摆放在宽度为 n 的空地，请输出箱子的摆放位置。

例如：箱子ABCDEFG，空地宽度为3，摆放结果如图：

则输出结果为：

AFG
BE
CD

输入描述

输入一行字符串，通过空格分隔，前面部分为字母或数字组成的字符串str，表示箱子；
后面部分为数字n，表示空地的宽度。例如：

ABCDEFG 3

输出描述

箱子摆放结果，如题目示例所示

AFG
BE
CD

备注

请不要在最后一行输出额外的空行

str只包含字母和数字，1 <= len(str) <= 1000

1 <= n <= 1000

测试样例1

输入：

ABCDEFG 3

输出：

AFG
BE
CD

解题思路

解题思路如下：

1. 输入处理：首先，我们需要读取输入，它由两部分组成：一个字符串str和一个整数n。这个整数n表示空地的宽度，也就是每行可以摆放的箱子数量。
2. 初始化：我们将字符串str转换为字符数组chars，这样可以方便我们按顺序访问每个字符。同时，我们初始化一个列表lists，它包含了n个空列表，用于存储按照之字形摆放的箱子。
3. 双指针法：我们使用一个索引index来跟踪当前要填充的行，以及一个布尔变量asc来指示我们是在向上填充（True表示递增）还是在向下填充（False表示递减）。
4. 填充箱子：我们遍历每个字符，根据asc的值来决定是递增还是递减index。如果index超出了lists的范围，我们翻转方向并重置index。
5. 之字形摆放：在填充每个列表时，我们根据asc的值来决定是将字符添加到lists[index]的开头还是末尾。由于题目要求是从上到下摆放，我们选择将字符添加到末尾。
6. 输出结果：最后，我们遍历lists中的每个子列表，并打印出每个子列表的内容，这样就得到了之字形摆放的箱子。
7. 特殊情况处理：如果输入的字符串长度小于n，我们不需要做特殊处理，因为代码已经能够正确处理这种情况。如果字符串长度大于n，我们的代码也能够处理，因为它会按照之字形的规则继续摆放箱子。

通过上述步骤，我们可以得到一个简洁且有效的解决方案。这个解决方案的时间复杂度是O(m)，其中m是输入字符串的长度，因为我们只需要遍历一次字符串。空间复杂度是O(n)，因为我们需要存储每行的字符。

Python代码解析

def solution(line):
    # 分割输入行，获取字符串和n的值
    str_part, n_str = line.split(" ")
    n = int(n_str)
    # 将字符串转换为字符数组
    chars = list(str_part)
    # 初始化列表，用于存储每个子列表
    lists = [[] for _ in range(n)]

    index = 0
    asc = True  # 标志位，指示当前是递增还是递减

    # 遍历字符数组，按照规则填充子列表
    for c in chars:
        if index == -1:
            index = 0
            asc = True
        if index == n:
            index = n - 1
            asc = False
        lists[index].append(c)

        if asc:
            index += 1
        else:
            index -= 1

    # 打印结果
    for sub_list in lists:
        print(''.join(sub_list))


def main():
    line = input()  # 读取输入
    solution(line)  # 调用solution函数并打印结果


if __name__ == "__main__":
    main()