​LeetCode刷题实战401: 二进制手表

共 1905字,需浏览 4分钟

 ·

2021-10-08 18:07

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 二进制手表,我们先来看题面:
https://leetcode-cn.com/problems/binary-watch/

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

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


例如,下面的二进制手表读取 "3:25" 。



示例

示例 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
输出:[]


解题

https://www.freesion.com/article/4245180865/

  • 看了题目,看了很久才懂,其实题目就是时间中小时的数字二进制形式中1的个数加上分钟的数字二进制形式中1的个数之和要等于输入的n。

  • 首先,因为题目给了小时的范围是0-11,分钟的范围是0-59,然后小时和分钟二进制中的1的个数之和为n,我们可以枚举法将所有时间都理出来。

  • 然后将所有时间中符合二进制中1的个数之和为n的给存起来。

  • 最后打印出存起来的所有时间即可。

  • 不过打印的时候要注意,题目中要求的输出格式,小时没有输出要求,但是分钟若是小于10时就要在前面加个0在打印出来。

  • 按照输出格式,我们可以将符合题意的结果用字符串存起来,又因为结果不止一个,我们可以用vector< string >来存符合题意的所有时间。


  • class Solution {
    public:
        //计算一个数的二进制中有多少个1
        int sum_1(int num)
        
    {
            int sum = 0;
            while(num)
            {
                num = num & (num - 1);
                ++sum;
            }
            return sum;
        }
        vector<string> readBinaryWatch(int num) {
            vector<string> time;
            
            //枚举出所有时间,然后取其中符合题意的。
            for(int h = 0; h < 12; ++h)
            {
                for(int m = 0; m < 60; ++m)
                {
                    if(sum_1(h) + sum_1(m) == num)
                    {
                        if(m < 10)
                            time.push_back(to_string(h) + ":" + "0" + to_string(m));
                        else
                            time.push_back(to_string(h) + ":" + to_string(m));
                    }
                        
                }
            }
            
            return time;
        }
    };

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-400题汇总,希望对你有点帮助!


浏览 36
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报