Excel 表中某个范围内的单元格

难度: Easy

Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：

<col> 即单元格的列号 c 。用英文字母表中的字母标识。
- 例如，第 1 列用 'A' 表示，第 2 列用 'B' 表示，第 3 列用 'C' 表示，以此类推。
<row> 即单元格的行号 r 。第 r 行就用整数 r 标识。

给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1> 表示 c1 列，<row1> 表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。

找出所有满足 r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。

示例 1：

输入：s = "K1:L2"
输出：["K1","K2","L1","L2"]
解释：
上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。

示例 2：

输入：s = "A1:F1"
输出：["A1","B1","C1","D1","E1","F1"]
解释：
上图显示了列表中应该出现的单元格。 
红色箭头指示单元格的出现顺序。

提示：

s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s 由大写英文字母、数字、和 ':' 组成

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        #提取出列号和行号
        col1 = ord(s[0]) - ord('A') + 1
        row1 = int(s[1])
        col2 = ord(s[3]) - ord('A') + 1
        row2 = int(s[4])

        cells = []
        for row in range(row1,row2+1):
            for col in range(col1,col2+1):
                cells.append(f"{chr(col+ord('A') - 1)}{row}")

        cells.sort(key=lambda cell:(ord(cell[0]) - ord('A'),int(cell[1])))

        return cells

Explain

题解首先通过计算字符和'ord'的差值来确定每个列的索引（从'A'开始计数）。接着将输入字符串s解析出起始和结束的行号和列号。利用双重循环遍历指定范围内的所有单元格，并按照Excel的格式构造单元格名称。最后，尽管结果已经是有序的，但代码中还包括了一个排序步骤，确保输出结果符合先按列后按行的顺序排列。

时间复杂度: O(n*m log(n*m))

空间复杂度: O(n*m)

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        # 提取出列号和行号
        col1 = ord(s[0]) - ord('A') + 1
        row1 = int(s[1])
        col2 = ord(s[3]) - ord('A') + 1
        row2 = int(s[4])

        cells = []
        # 遍历指定的行和列范围
        for row in range(row1, row2 + 1):
            for col in range(col1, col2 + 1):
                # 构造单元格名称并加入列表
                cells.append(f"{chr(col + ord('A') - 1)}{row}")

        # 对结果列表进行排序，确保按列再按行的顺序
        cells.sort(key=lambda cell: (ord(cell[0]) - ord('A'), int(cell[1])))

        return cells

Explore

计算列号`col1`和`col2`时，我们需要将Excel中的列字母转换为数字索引。例如，'A'应该转换为1，'B'转换为2，依此类推。在ASCII码中，'A'的值是65，因此，要获取正确的列索引，我们首先用`ord(s[0])`或`ord(s[3])`获取输入列字符的ASCII值，然后减去'A'的ASCII值（65），这样就能将'A'映射到0。但是，由于Excel中的列是从1开始计数的，所以我们需要在最后的结果上加1，使得'A'对应1，'B'对应2，以此类推。

题解中通过双重循环遍历行和列，第一个循环是按行从小到大，内部循环是按列从小到大。因此，单元格名称本来就是按照行优先，然后是列的顺序添加到列表中的。即使在不进行显式排序的情况下，生成的单元格列表已经是按照行和列的顺序排列的。然而，为了确保结果的严格性和一致性，作者可能还是选择了显式的排序步骤。

在构造单元格名称时，我们需要将数字索引转换回Excel的列字母。`col`变量是一个从1开始的列索引，而`ord('A')`是65。因此，为了将1映射到'A'，2映射到'B'等等，我们需要使用`chr(col + ord('A') - 1)`。这里，`col + ord('A') - 1`实质上是将列索引转回它对应的ASCII值，例如对于列1（'A'），计算结果为65，然后`chr(65)`转换为字符'A'。

如果`col1`和`col2`之间的差距很大，意味着需要遍历并构造更多的单元格名称。这将导致时间复杂度和空间复杂度增加。具体来说，算法的时间复杂度是O(n*m)，其中n是行的数量，m是列的数量。如果列的范围很大，会显著增加循环的迭代次数，进而增加算法运行时间和使用的内存。因此，当列数非常多时，算法的性能会受到影响，可能导致处理速度变慢和更高的内存消耗。