题目汇总https://leetcode-cn.com/tag/math/
523. 连续的子数组和中等[✔]
535. TinyURL 的加密与解密中等（没做）
537. 复数乘法中等[✔]
553. 最优除法中等（不做了，题解才35）
592. 分数加减运算中等（不做了，题解才41）
593. 有效的正方形中等
598. 范围求和 II简单
628. 三个数的最大乘积简单[✔]
523. 连续的子数组和中等
给定一个包含非负数的数组和一个目标整数k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n×k，其中 n 也是一个整数。
示例 1：
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：
输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
- 数组的长度不会超过 10,000 。
- 你可以认为所有数字总和在 32 位有符号整数范围内。
思路一：优化的暴力，使用前缀和
class Solution {//执行用时：23 ms, 在所有 Java 提交中击败了33.08%的用户，2020/07/27
public boolean checkSubarraySum(int[] nums, int k) {
int[] sum = new int[nums.length];
sum[0] = nums[0];
for(int i = 1; i < nums.length; i++){
sum[i] = sum[i - 1] + nums[i];
}
for(int i = 0; i < nums.length - 1; i++){
for(int j = i + 1; j < nums.length; j++){
int subnum = sum[j] - sum[i] + nums[i];//从 i 到 j 的连续子数组的和
if (subnum == k || (k != 0 && subnum % k == 0)){
return true;
}
}
}
return false;
}
}
思路二：HashMap
class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了99.70%的用户，2020/07/27
public boolean checkSubarraySum(int[] nums, int k) {
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (k != 0)
sum = sum % k;
if (map.containsKey(sum)) {
if (i - map.get(sum) > 1) //连续子数组长度大于等于2
return true;
} else
map.put(sum, i);//map来保存每个sum值对应的索引
}
return false;
}
}
537. 复数乘法中等
给定两个表示复数的字符串。
返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
示例 1:
输入: "1+1i", "1+1i"
输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
示例 2:
输入: "1+-1i", "1+-1i"
输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。
注意:
- 输入字符串不包含额外的空格。
- 输入字符串将以 a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。
思路：数学公式
class Solution {//执行用时：7 ms, 在所有 Java 提交中击败了43.93%的用户，2020/07/27
public String complexNumberMultiply(String a, String b) {
String[] split1 = a.split("\\+"); //用“+”作为分隔符来分割字符串
String[] split2 = b.split("\\+");
int A = Integer.parseInt(split1[0]);//字符串表示的整数
int B = Integer.parseInt(split1[1].split("i")[0]);
int C = Integer.parseInt(split2[0]);
int D = Integer.parseInt(split2[1].split("i")[0]);
return (A * C - B * D) + "+" + (A * D + B * C) + "i";
}
}
593. 有效的正方形中等
给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。
一个点的坐标（x，y）由一个有两个整数的整数数组表示。
示例:
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
注意:
所有输入整数都在 [-10000，10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角（90度角）。
输入点没有顺序。
思路：
算出六个距离，四个边长相等，两个对角线相等
598. 范围求和 II简单
给定一个初始元素全部为 0，大小为 m×n 的矩阵 M 以及在 M上的一系列更新操作。
操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。
示例 1:
输入:
m = 3, n = 3，operations = [[2,2],[3,3]]
输出: 4
解释:
初始状态, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
执行完操作 [2,2] 后, M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
执行完操作 [3,3] 后, M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
注意:
- m 和 n 的范围是 [1,40000]。
- a 的范围是 [1,m]，b 的范围是 [1,n]。
- 操作数目不超过 10000。
思路：
每次操作都是左上角区域从（0, 0）到（a, b）的矩形，必定重叠，所以最小的 a 乘以最小的 b 就是所求。
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/29
public int maxCount(int m, int n, int[][] ops) {
if(ops.length == 0) return m * n;
int minX = Integer.MAX_VALUE;
int minY = Integer.MAX_VALUE;
for(int i = 0; i < ops.length; i++){
if(ops[i][0] < minX) minX = ops[i][0];
if(ops[i][1] < minY) minY = ops[i][1];
}
return minX * minY;
}
}
628. 三个数的最大乘积简单
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:
输入: [1,2,3,4]
输出: 24
注意:
- 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
- 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
思路一：排序
分为三种情况：
1.无序数组都是正数（包含0），找三个最大的数。
2.无序数组都是负数，仍然是找三个最大的数。
3.有正数(包括0)有负数。可能的形式就是三个正数或者是两负一正。
将数组进行升序排序，找到最大的三个正数，最小的二个负数，他们之间的最大值就是所求。
class Solution {//执行用时：12 ms, 在所有 Java 提交中击败了69.71%的用户,2020/07/29
public int maximumProduct(int[] nums) {
int len = nums.length;
if(len < 3)
return 0;
Arrays.sort(nums);
return Math.max(nums[len - 1] * nums[len - 2] * nums[len - 3],
nums[0] * nums[1] * nums[len - 1]);
}
}
思路二：
遍历一次数组得到最大的三个数和最小的两个数。
class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了99.47%的用户，2020/07/29
public int maximumProduct(int[] nums) {
int len = nums.length;
// 定义两个变量保存最小的两个数
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
// 定义三个变量保存最大的三个数
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
// 遍历一次数组，将各个合适的元素放到对应的位置
for(int i = 0; i < len; i++){
int cur = nums[i];
if(cur <= min1){//如果当前元素比最小负数小，把最小负数的值赋给次小负数，把当前元素赋给最小负数
min2 = min1;
min1 = cur;
} else if(cur <= min2){//如果当前元素比最小负数大，但是次小元素小，就当前元素赋给次小元素
min2 = cur;
}
if(cur >= max3){
max1 = max2;
max2 = max3;
max3 = cur;
} else if(cur >= max2){
max1 = max2;
max2 = cur;
}else if(cur >= max1){
max1 = cur;
}
}
return Math.max(max1 * max2 * max3,min1 * min2 * max3);
}
}
网友评论