leetcode
leetcode 1901 ~ 1950
Excel 表中某个范围内的单元格

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

难度:

标签:

题目描述

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 <= r2c1 <= c2

找出所有满足 r1 <= x <= r2c1 <= 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 由大写英文字母、数字、和 ':' 组成

代码结果

运行时间: 27 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 使用 IntStream 和 flatMap 生成所有可能的列和行组合。
 * 2. 对于每一个列和行的组合,使用映射将其格式化为字符串并收集到列表中。
 */

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<String> cellsInRange(String s) {
        char startCol = s.charAt(0);
        char endCol = s.charAt(3);
        int startRow = s.charAt(1) - '0';
        int endRow = s.charAt(4) - '0';
        return IntStream.rangeClosed(startCol, endCol)
                        .boxed()
                        .flatMap(col -> IntStream.rangeClosed(startRow, endRow)
                                                  .mapToObj(row -> (char) col + String.valueOf(row)))
                        .collect(Collectors.toList());
    }
}

解释

方法:

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

时间复杂度:

O(n*m log(n*m))

空间复杂度:

O(n*m)

代码细节讲解

🦆
你是如何计算列号`col1`和`col2`的?为什么要在`ord(s[0])`或`ord(s[3])`的基础上减去`ord('A')`然后再加1?
计算列号`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,以此类推。
🦆
题解中提到对结果列表进行排序,但列表是如何保证在没有排序之前就已经按照要求的非递减顺序排列的?
题解中通过双重循环遍历行和列,第一个循环是按行从小到大,内部循环是按列从小到大。因此,单元格名称本来就是按照行优先,然后是列的顺序添加到列表中的。即使在不进行显式排序的情况下,生成的单元格列表已经是按照行和列的顺序排列的。然而,为了确保结果的严格性和一致性,作者可能还是选择了显式的排序步骤。
🦆
在单元格名称构造时,为什么使用`chr(col + ord('A') - 1)`来得到列的字母表示?这个表达式是如何工作的?
在构造单元格名称时,我们需要将数字索引转换回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`差距很大,会对算法的性能有什么影响?
如果`col1`和`col2`之间的差距很大,意味着需要遍历并构造更多的单元格名称。这将导致时间复杂度和空间复杂度增加。具体来说,算法的时间复杂度是O(n*m),其中n是行的数量,m是列的数量。如果列的范围很大,会显著增加循环的迭代次数,进而增加算法运行时间和使用的内存。因此,当列数非常多时,算法的性能会受到影响,可能导致处理速度变慢和更高的内存消耗。

相关问题