題目匯總https://leetcode-cn.com/tag/math/
357. 計算各個位數(shù)不同的數(shù)字個數(shù)中等（沒弄懂）
365. 水壺問題中等（需要看題解）
367. 有效的完全平方數(shù)簡單[?]
368. 最大整除子集中等
372. 超級次方中等（不做了）
396. 旋轉函數(shù)中等（不做了）
397. 整數(shù)替換中等
400. 第N個數(shù)字中等（題目描述沒看懂）
413. 等差數(shù)列劃分中等[?]
357. 計算各個位數(shù)不同的數(shù)字個數(shù)中等
給定一個非負整數(shù) n，計算各位數(shù)字都不同的數(shù)字 x 的個數(shù)，其中 0 ≤ x < 10n 。
示例:
輸入: 2
輸出: 91
解釋: 答案應為除去11,22,33,44,55,66,77,88,99外，在 [0,100) 區(qū)間內的所有數(shù)字。
思路：動態(tài)規(guī)劃
365. 水壺問題中等
有兩個容量分別為 x 升 和 y 升的水壺以及無限多的水。請判斷能否通過使用這兩個水壺，從而可以得到恰好 z 升的水？
如果可以，最后請用以上水壺中的一或兩個來盛放取得的 z 升水。
你允許：
裝滿任意一個水壺
清空任意一個水壺
從一個水壺向另外一個水壺倒水，直到裝滿或者倒空
示例 1:
輸入: x = 3, y = 5, z = 4
輸出: True
示例 2:
輸入: x = 2, y = 6, z = 5
輸出: False
思路：最大公約數(shù)
這里涉及到一個數(shù)學定理裴蜀定理裴蜀定理
具體解釋如下：
若a,b是整數(shù),且gcd(a,b)=d，那么對于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù)，特別地，一定存在整數(shù)x,y，使ax+by=d成立。
對于這道題而言，如果所需要的水量是兩個水壺容量的最大公約數(shù)的倍數(shù)，（就是看x和y的最大公約數(shù)能否整除z），且水量不大于兩個水壺的容量之和，那么必然可以用這兩個水壺操作得到所需要的水量。
class Solution {//執(zhí)行用時：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;
}
//最大公約數(shù)
public int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x % y);
}
}
367. 有效的完全平方數(shù)簡單
給定一個正整數(shù) num，編寫一個函數(shù)，如果 num 是一個完全平方數(shù)，則返回 True，否則返回 False。
說明：不要使用任何內置的庫函數(shù)，如sqrt。
示例 1：
輸入：16
輸出：True
示例 2：
輸入：14
輸出：False
思路一：數(shù)學規(guī)律
連續(xù)個奇數(shù)的和1 + 3 + 5 + 7 + ... + (2n - 1) = n2，利用這個公式將num連續(xù)減去若干個從 1 開始的奇數(shù)，如果 num 最終減為 0 ，說明 num 是完全平方數(shù)。
class Solution {//執(zhí)行用時：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 {//執(zhí)行用時：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. 整數(shù)替換中等
給定一個正整數(shù) n，你可以做如下操作：
1. 如果 n 是偶數(shù)，則用n / 2替換 n。
2. 如果 n 是奇數(shù)，則可以用n + 1或n - 1替換 n。
n 變?yōu)?1 所需的最小替換次數(shù)是多少？
示例 1:
輸入:8
輸出:3
解釋:8 -> 4 -> 2 -> 1
示例 2:
輸入:7
輸出:4
解釋:7 -> 8 -> 4 -> 2 -> 1或7 -> 6 -> 3 -> 2 -> 1
思路一：遞歸
class Solution {//執(zhí)行用時：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個數(shù)字中等
在無限的整數(shù)序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 個數(shù)字。
注意: n 是正數(shù)且在32位整數(shù)范圍內 ( n < 231)。
示例 1:
輸入:3
輸出:3
示例 2:
輸入:11
輸出:0
說明:
第11個數(shù)字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
413. 等差數(shù)列劃分中等
如果一個數(shù)列至少有三個元素，并且任意兩個相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。
數(shù)組 A 包含 N 個數(shù)，且索引從0開始。數(shù)組 A 的一個子數(shù)組劃分為數(shù)組 (P, Q)，P 與 Q 是整數(shù)且滿足 0<=P<Q<N 。
如果滿足以下條件，則稱子數(shù)組(P, Q)為等差數(shù)組：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函數(shù)要返回數(shù)組 A 中所有為等差數(shù)組的子數(shù)組個數(shù)。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三個子等差數(shù)組: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
思路：動態(tài)規(guī)劃
class Solution {//執(zhí)行用時：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]結尾的等差數(shù)列的個數(shù)
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;
}
}
