30 September 2019
LeetCode(23) -- 628, 633, 637
by Jerry Zhang
P628. Maximum Product of Three Numbers (Easy)
给一个数组，找到乘积最大的三个数。
我的思路
问题的关键是数组里面有负数。如果所有数都是负数，那么乘积想最大，就要取绝对值最小的三个数；如果有一个正数，那么乘积想最大，肯定要那个正数，以及绝对值最大的两个负数；如果有两个正数，则取那个较大的正数，同时取两个绝对值最大的负数； 如果有三个及以上的正数，那么乘积想最大，要么取前三大的正数，要么取一个最大的正数，乘以两个绝对值最大的负数。
还有一个办法，动态规划，后一个数要还是不要，取决于它代替任何一个数之后得到的乘积哪个更大。但是有一个问题，有可能一个负数并不能达到使乘积更大的效果，但是后两个连续的负数，乘积会更大。
我的代码
public class E_628_MaximumProductofThreeNumbers {
public int maximumProduct(int[] nums) {
// int p = 0, n = 0, z = 0;
// int l = nums.length;
// for (int i = 0; i < nums.length; i++) {
// if (nums[i] > 0) {
// p++;
// } else if (nums[i] < 0) {
// n++;
// } else {
// z++;
// }
// }
// Arrays.sort(nums);
// if (p == 0) {
// return nums[l - 1] * nums[l - 2] * nums[l - 3];
// } else if (p == 1) {
// return nums[0] * nums[1] * nums[l - 1];
// } else if (p == 2) {
//
// }
Arrays.sort(nums);
return Math.max(nums[0] * nums[1] * nums[nums.length - 1],
nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
}
}
看了答案，其实上面分析的那些，可以总结为两种结果：一是取最后三个数，二是取第一个和第二个以及最后一个数。所以答案就比较了一下这两种哪个更大，就要哪个。
答案 / 最优解
public class Solution {
public int maximumProduct(int[] nums) {
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
for (int n: nums) {
if (n <= min1) {
min2 = min1;
min1 = n;
} else if (n <= min2) { // n lies between min1 and min2
min2 = n;
}
if (n >= max1) { // n is greater than max1, max2 and max3
max3 = max2;
max2 = max1;
max1 = n;
} else if (n >= max2) { // n lies betweeen max1 and max2
max3 = max2;
max2 = n;
} else if (n >= max3) { // n lies betwen max2 and max3
max3 = n;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
}
P633. Sum of Square Numbers (Easy)
给一个非负整数c，判断是否存在两个整数a,b，使得a^2 + b^2 = c
我的思路
暴力求解就是挨个数试，一直试到c的开方。
我的代码
public class E_633_SumofSquareNumbers {
public boolean judgeSquareSum(int c) {
for (int i = 0; i <= Math.sqrt(c); i++) {
for (int j = 0; j <= i; j++) {
if (i * i + j * j == c) {
return true;
}
}
}
return false;
}
}
超时了。
答案
解法一：跟我的一样。省略了。
解法二：对于任意一个a，只需要看c-a^2是不是一个完全平方数即可。那么如何检测一个数是不是完全平方数呢？有以下理论：
第n个正整数的平方，就等于前n个奇数的和。
public class Solution {
public boolean judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) {
int b = c - (int)(a * a);
int i = 1, sum = 0;
while (sum < b) {
sum += i;
i += 2;
}
if (sum == b)
return true;
}
return false;
}
}
解法三：跟上一个方法类似，只是判断c-a^2是否是完全平方数时，不再通过上面的算法，而是用Java自带的sqrt方法，判断开方后是不是跟强转成int的本身相等。
public class Solution {
public boolean judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) {
double b = Math.sqrt(c - a * a);
if (b == (int) b)
return true;
}
return false;
}
}
Math.sqrt这个方法的时间复杂度是O(logc), 所以整体的时间复杂度为O(sqrt(c) logc)
解法四：Binary Search。还是检验c-a^2是不是完全平方数。但这次的方法是binary search。
public class Solution {
public boolean judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) {
int b = c - (int)(a * a);
if (binary_search(0, b, b))
return true;
}
return false;
}
public boolean binary_search(long s, long e, int n) {
if (s > e)
return false;
long mid = s + (e - s) / 2;
if (mid * mid == n)
return true;
if (mid * mid > n)
return binary_search(s, mid - 1, n);
return binary_search(mid + 1, e, n);
}
}
解法五：依据费马的某个定理，任何正整数n可以表示为两个平方数之和，当且仅当n的所有质因子中，形如(4k+3)的质因子出现的次数为偶数。
费马平方和定理的表述是：奇素数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
我不知道是不是通过这个定理推出的结论，但这个定理是我能在网上找到的唯一一个相关的定理了。
public class Solution {
public boolean judgeSquareSum(int c) {
for (int i = 2; i * i <= c; i++) {
int count = 0;
if (c % i == 0) {
while (c % i == 0) {
count++;
c /= i;
}
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
return c % 4 != 3;
}
}
最优解
public class Solution {
public boolean judgeSquareSum(int c) {
for (int i = 2; i * i <= c; i++) {
int count = 0;
if (c % i == 0) {
while (c % i == 0) {
count++;
c /= i;
}
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
return c % 4 != 3;
}
}
P637. Average of Levels in Binary Tree (Easy)
给一个二叉树，返回每一层上的平均值。
我的思路
树的层级遍历。普通树要用Queue，二叉树的话。。。也得用Queue。
我的代码
public class E_637_AverageOfLevelsInBinaryTree {
public List<Double> averageOfLevels(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<Double> res = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
long sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = queue.remove();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add((double)sum / size);
}
return res;
}
}
98%
最优解
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<double[]> aves = new ArrayList<>();
avgs(root, 0, aves);
List<Double> result = new ArrayList<>();
for (double[] a: aves) {
result.add(a[0] / a[1]);
}
return result;
}
private void avgs(TreeNode root, int level, List<double[]> averages) {
if (root == null) return;
double[] average = averages.size() > level? averages.get(level): new double[2];
average[0] += root.val;
average[1]++;
if (averages.size() <= level) {
averages.add(average);
}
avgs(root.left, level + 1, averages);
avgs(root.right, level + 1, averages);
}
}