题目汇总https://leetcode-cn.com/tag/math/
357. 计算各个位数不同的数字个数中等（没弄懂）
365. 水壶问题中等（需要看题解）
367. 有效的完全平方数简单[✔]
368. 最大整除子集中等
372. 超级次方中等（不做了）
396. 旋转函数中等（不做了）
397. 整数替换中等
400. 第N个数字中等（题目描述没看懂）
413. 等差数列划分中等[✔]
357. 计算各个位数不同的数字个数中等
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
示例:
输入: 2
输出: 91
解释: 答案应为除去11,22,33,44,55,66,77,88,99外，在 [0,100) 区间内的所有数字。
思路：动态规划
365. 水壶问题中等
有两个容量分别为 x 升 和 y 升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z 升的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z 升水。
你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1:
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
思路：最大公约数
这里涉及到一个数学定理裴蜀定理裴蜀定理
具体解释如下：
若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
对于这道题而言，如果所需要的水量是两个水壶容量的最大公约数的倍数，（就是看x和y的最大公约数能否整除z），且水量不大于两个水壶的容量之和，那么必然可以用这两个水壶操作得到所需要的水量。
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，2020/07/24
public boolean canMeasureWater(int x, int y, int z) {
if(x == 0 || y == 0){
if(x == z || y == z) return true;
return false;
}
if(x + y < z) return false;
return z % gcd(x, y) == 0;
}
//最大公约数
public int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x % y);
}
}
367. 有效的完全平方数简单
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
思路一：数学规律
连续个奇数的和1 + 3 + 5 + 7 + ... + (2n - 1) = n2，利用这个公式将num连续减去若干个从 1 开始的奇数，如果 num 最终减为 0 ，说明 num 是完全平方数。
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了21.73%的用户,2020/07/24
public boolean isPerfectSquare(int num) {
int odd = 1;
while(num > 0){
num -= odd;
odd += 2;
}
return num == 0;
}
}
思路二：二分查找
注意越界问题。
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
public boolean isPerfectSquare(int num) {
if(num == 1)
return true;
int left = 2;
int right = num / 2;
while(left <= right){
int mid = (right - left) / 2 + left;
//避免mid * mid越界，可以通过mid跟num/mid去判断，注意需要把num/mid强转成float
if(mid > (float)num / mid){
right = mid - 1;
}else if(mid < (float)num / mid){
left = mid + 1;
}else{
return true;
}
}
return false;
}
}
397. 整数替换中等
给定一个正整数 n，你可以做如下操作：
1. 如果 n 是偶数，则用n / 2替换 n。
2. 如果 n 是奇数，则可以用n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？
示例 1:
输入:8
输出:3
解释:8 -> 4 -> 2 -> 1
示例 2:
输入:7
输出:4
解释:7 -> 8 -> 4 -> 2 -> 1或7 -> 6 -> 3 -> 2 -> 1
思路一：递归
class Solution {//执行用时：8 ms, 在所有 Java 提交中击败了26.00%的用户
public int integerReplacement(int n) {
if (n == Integer.MAX_VALUE)
return 32;//最大值的时候
if(n == 1) return 0;
if(n % 2 == 0){
return 1 + integerReplacement(n/2);
}
else{
return 1 + Math.min(integerReplacement(n + 1), integerReplacement(n - 1));
}
}
}
思路二：位运算（自己想不出来，看题解也没分析明白）
400. 第N个数字中等
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
注意: n 是正数且在32位整数范围内 ( n < 231)。
示例 1:
输入:3
输出:3
示例 2:
输入:11
输出:0
说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
413. 等差数列划分中等
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
思路：动态规划
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
public int numberOfArithmeticSlices(int[] A) {
if(A == null || A.length <= 2)
return 0;
int[] dp = new int[A.length];//dp[i]表示以A[i]结尾的等差数列的个数
int sum = 0;
for(int i = 2; i < A.length; i++){
if(A[i - 1] - A[i] == A[i - 2] - A[i - 1]){
dp[i] = 1 + dp[i - 1];
sum += dp[i];
}
}
return sum;
}
}
