美团 · 字符串 · 算法编程题
美团 字符串 时限 1 秒 / 256 MB

题目描述

小团有一个 n× m 的矩阵A， 他知道这是小美用一种特殊的方法生成的，具体规则如下:
小美首先写下一个 n'× m 的矩阵，然后小美每一次将这个矩阵上下翻转后接到原矩阵的下方。小美重复这个过程若干次（甚至可能是0次，也就是没有进行过这一操作），然后将操作后的矩阵交给小团。
小团想知道，小美一开始写下的矩阵是什么。因为小美可能有多种一开始的矩阵，小团想得到最小的矩阵（这里的最小指矩阵即 n'× m 的面积最小）。

输入输出

输入描述
输入包含两个整数n,m，表示小团矩阵的大小。
接下来n行，每行m个正整数，第i行第j列表示矩阵第i行第j列的数。
输出描述
输出包含一个矩阵，一共n'行m列，表示小美一开始最小的矩阵。

样例共 1 组

样例 1 · 小美一开始的矩阵可能有以下3种： 1. 1 0 1 0 1 0 2. 1 0 1 0 1 0 0 1 0 1 0 1 3. 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 其中最小的矩阵为第一种。
输入
8 3
1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1
输出
1 0 1
0 1 0

算法解析依据充分

考点：字符串

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：字符串

本题切入点

矩阵由「原矩阵 + 逐次上下翻转」拼成，本质是找最短的、在上下翻转意义下重复的周期：逐层比对确定最小行数 n'。

按字符逐个处理，或利用字符串的前后缀性质加速匹配。

思路框架（字符串 通法 · 非本题专属）

  1. 明确操作对象是字符还是子串、是否需要保持原顺序。
  2. 子串问题常用双指针 / 滑动窗口；回文问题可用中心扩展或哈希。
  3. 多模式匹配考虑 Trie 或 KMP；只需计数则用哈希表统计字符频次。
  4. 注意字符集大小写敏感性与输入是否带引号。

实现要点：Python 切片 s[l:r+1] 取子串；注意字符串不可变，频繁拼接改用 list。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 下标与切片边界差 1。
  • 忽略了大小写、空白字符的影响。

样例解读

样例 1：输入 8 3 / 1 0 1 / 0 1 0 / 0 1 0 / 1 0 1 / 1 0 1 / 0 1 0 / 0 1 0 / 1 0 1 → 输出 1 0 1 / 0 1 0

小美一开始的矩阵可能有以下3种：

1.

1 0 1

0 1 0

2.

1 0 1

0 1 0

0 1 0

1 0 1

3.

1 0 1

0 1 0

0 1 0

1 0 1

1 0 1

0 1 0

0 1 0

1 0 1

其中最小的矩阵为第一种。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：美团2023校招技术第6场编程题。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解