LeetCode题练习与总结：二进制手表--401

标签：LED bitCount -- 复杂度分钟 turnedOn 401 Integer LeetCode

一、题目描述

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

例如，下面的二进制手表读取 "4:51" 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例 1：

输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

输入：turnedOn = 9
输出：[]

提示：

0 <= turnedOn <= 10

二、解题思路

对于小时，我们有4个LED，对于分钟，我们有6个LED。我们需要考虑所有可能的时间组合，使得亮着的LED总数等于turnedOn。
对于小时的每一个可能值（0-11），我们需要找出所有可能的分钟值（0-59），使得小时和分钟的LED总数等于turnedOn。
对于每一个小时和分钟的组合，我们需要计算亮着的LED数量。这可以通过计算小时和分钟的二进制表示中1的个数来实现。
如果小时和分钟的LED总数等于turnedOn，我们就将这个时间加入到结果列表中。
最后，返回结果列表。

三、具体代码

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> times = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    times.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return times;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> result = solution.readBinaryWatch(1);
        System.out.println(result); // 输出示例1的结果
        result = solution.readBinaryWatch(9);
        System.out.println(result); // 输出示例2的结果
    }
}

在这段代码中，Integer.bitCount()方法用于计算一个整数的二进制表示中1的个数，即亮着的LED的数量。我们遍历所有可能的小时和分钟组合，检查它们的LED数量之和是否等于turnedOn。如果是，我们就使用String.format()来格式化时间字符串，并添加到结果列表中。注意，我们使用%02d来确保分钟始终是两位数，如果不足两位，则在前面补零。

四、时间复杂度和空间复杂度

1. 时间复杂度

我们有两个嵌套的循环，第一个循环遍历小时数（0-11），第二个循环遍历分钟数（0-59）。
对于每一个小时和分钟的组合，我们调用Integer.bitCount()方法来计算亮着的LED数量。
因此，总的时间复杂度是两个循环的乘积乘以Integer.bitCount()的复杂度。

具体来说：

外层循环（小时）运行12次。
内层循环（分钟）运行60次。
Integer.bitCount()的时间复杂度是O(1)，因为它只处理32位整数，并且有固定的操作数。

所以，总的时间复杂度是O(N^2)，其中N是分钟数，在本例中N=60。

2. 空间复杂度

我们需要存储所有可能的时间组合，这些组合的数量取决于输入turnedOn的值。
在最坏的情况下，当turnedOn为0时，我们有12个可能的小时和60个可能的分钟，所以最多会有720个时间组合。
我们还需要考虑递归调用栈的额外空间，但在这个问题中，我们没有使用递归，所以不需要考虑这部分。

具体来说：

结果列表times在最坏情况下的空间复杂度是O(1)，因为最大可能的组合数是固定的（720个）。

因此，总的空间复杂度是O(1)。尽管我们有一个列表来存储结果，但这个列表的大小不随输入规模（turnedOn的值）的增加而增加，而是由问题本身的限制决定的。

五、总结知识点

类定义 (public class Solution):定义了一个名为Solution的公共类。
方法定义 (public List<String> readBinaryWatch(int turnedOn)):定义了一个公共方法readBinaryWatch，它接受一个整数参数turnedOn并返回一个字符串列表。
数据结构 (List<String>):使用了Java的List接口，它是一个泛型接口，用于存储对象引用的序列，这里存储的是String类型的对象。
集合类 (ArrayList<String>):使用了ArrayList类，这是List接口的一个实现，提供了可调整大小的数组。
循环结构 (for循环):使用了两个嵌套的for循环来遍历所有可能的小时和分钟组合。
位操作 (Integer.bitCount()):调用了Integer.bitCount()方法，该方法计算一个整数的二进制表示中1的个数。
字符串格式化 (String.format()):使用了String.format()方法来格式化字符串，确保时间以正确的格式输出（小时和分钟）。
条件语句 (if):使用了if语句来检查小时和分钟的LED数量之和是否等于turnedOn。
方法调用 (times.add()):调用了ArrayList的add()方法来向列表中添加元素。
主方法 (public static void main(String[] args)):定义了main方法，它是Java程序的入口点。
对象创建 (Solution solution = new Solution();):使用了new关键字来创建Solution类的实例。
方法重载 (solution.readBinaryWatch(1)):调用了readBinaryWatch方法，并传递了一个参数。
标准输出 (System.out.println()):使用了System.out.println()方法来打印结果到控制台。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：LED,bitCount,--,复杂度,分钟,turnedOn,401,Integer,LeetCode
From： https://blog.csdn.net/weixin_62860386/article/details/143815888