Leetcode题解——401/628

出其东门

发布于 2019-07-19 11:17:28

3880

发布于 2019-07-19 11:17:28

文章被收录于专栏：01二进制

该图片由Arek Socha在Pixabay上发布

这是题解系列上线后的第一篇文章，由于我刷的题目的难度目前都还是简单/中等，所以算法大神可以直接忽略我的文章了，文章中所给出的题解仅仅是作者个人的看法，欢迎各位读者讨论。目前的计划是每篇文章两道题，每周六发一次题解，我一直认为思维的碰撞可以产生智慧的火花，所以非常欢迎各位读者分享自己平常做题的题解，虽然「01二进制」目前的体量很小，但是并不影响他有一颗做大做强的心。

401 二进制手表

题目

https://leetcode-cn.com/problems/binary-watch/

题解

先看下题目中的几个数字的二进制数长什么样子：

1：1
2：10
4：100
8：1000
16：10000
32：100000

他们都有一个共同特点，那就是只有一个数是1，而且在二进制手表中只有12个小时和60分钟，算起来也不过才720，所以推荐使用暴力遍历。

思路：声明一个0 - 60 的数组dp[]，计算i的二进制的值后返回其二进制值中1的个数并赋值到dp[i]，最后在这720次中遍历下有哪些组合满足想加和为num的即可

代码

class Solution {
    public List < String > readBinaryWatch(int num) {
        List < String > strings = new ArrayList < > ();
        int[] dp = new int[60];
        for (int i = 0; i < dp.length; i++) dp[i] = calculate(i);
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (dp[i] + dp[j] == num)
                    strings.add(new String(i + ":" + (j >= 10 ? j : "0" + j)));
            }
        }
        return strings;
    }

    private int calculate(int i) {
        int res = 0;
        String s = Integer.toBinaryString(i);
        for (int j = 0; j < s.length(); j++) {
            if (s.charAt(j) == '1')
                res++;
        }
        return res;
    }
}

628 三个数的最大乘积

题目

https://leetcode-cn.com/problems/maximum-product-of-three-numbers/

题解

先排序，然后比较三个最大的正数和最小的两个负数及最大正数大乘积即可

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int x1 = nums[0] * nums[1] * nums[len-1];
        int x2 = nums[len-3] * nums[len - 1] * nums[len - 2];
        if (x1 >= x2) return x1;
        else return x2;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除

https