该图片由Arek Socha在Pixabay上发布
这是题解系列上线后的第一篇文章,由于我刷的题目的难度目前都还是简单/中等,所以算法大神可以直接忽略我的文章了,文章中所给出的题解仅仅是作者个人的看法,欢迎各位读者讨论。目前的计划是每篇文章两道题,每周六发一次题解,我一直认为思维的碰撞可以产生智慧的火花,所以非常欢迎各位读者分享自己平常做题的题解,虽然「01二进制」目前的体量很小,但是并不影响他有一颗做大做强的心。
https://leetcode-cn.com/problems/binary-watch/
先看下题目中的几个数字的二进制数长什么样子:
他们都有一个共同特点, 那就是只有一个数是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;
}
}
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;
}
}