题目汇总https://leetcode-cn.com/tag/math/
633. 平方数之和简单[✔]
640. 求解方程中等（还不会）
645. 错误的集合简单[✔]
670. 最大交换中等（看了题解才做出来）
672. 灯泡开关 Ⅱ中等（不做了，题解才17）
728. 自除数简单[✔]
753. 破解保险箱困难（不做了，题解才20）
633. 平方数之和简单
给定一个非负整数
c，你要判断是否存在两个整数a和b，使得 a2 + b2 = c。
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False
思路一：数学方法
class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了36.28%的用户，2020/07/30
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;
}
}
思路二：双指针
class Solution {//执行用时：5 ms, 在所有 Java 提交中击败了22.89%的用户,2020/07/30
public boolean judgeSquareSum(int c) {
long i = 0;
long j = (long)Math.sqrt(c);
while (i <= j){
if (i * i + j * j == c) return true;
else if(i * i + j * j > c) j--;
else i++;
}
return false;
}
}
640. 求解方程中等
求解一个给定的方程，将
x以字符串"x=#value"的形式返回。该方程仅包含'+'，' - '操作，变量x和其对应系数。
如果方程没有解，请返回“No solution”。
如果方程有无限解，则返回“Infinite solutions”。
如果方程中只有一个解，要保证返回值x是一个整数。
示例 1：
输入: "x+5-3+x=6+x-2"
输出: "x=2"
示例 2:
输入: "x=x"
输出: "Infinite solutions"
示例 3:
输入: "x=x+2"
输出: "No solution"
思路：
645. 错误的集合简单
集合
S包含从1到n的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组nums代表了集合S发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。
思路：
用一个数组来记录每个数字出现的次数，遍历整个数组，出现的次数为0的是丢失的数字，出现的次数为2的是重复出现的数字。
class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了96.42%的用户，2020/07/31
public int[] findErrorNums(int[] nums) {
int[] count = new int[nums.length + 1];//count记录每个数字出现的次数
for(int num: nums){
count[num]++;
}
int[] res = new int[2];
for(int i = 1; i < count.length; i++){
if(count[i] == 0){//出现的次数为0的是丢失的数字
res[1] = i;
}else if(count[i] == 2){//出现的次数为2的是重复出现的数字
res[0] = i;
}
}
return res;
}
}
670. 最大交换中等
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736，输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973，输出: 9973
解释: 不需要交换。
注意: 给定数字的范围是 [0, 108]
思路：
找到第一次递增时的下标，记录右边的最后的最大值的下标和左边的第一次小于最大值的下标，交换。
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，2020/07/31
public int maximumSwap(int num) {
char[] chars = String.valueOf(num).toCharArray();
int len = chars.length;
int index = 0;
for(int i = 1; i < len; i++){
if(chars[i] > chars[i - 1]){
index = i; //第一次递增时的下标i
break;
}
if(i == len - 1) return num;
}
int indexLeft = 0;
int indexRight = index;
//以index作为分割点，找到最右边最大值
for(int i = index; i < len; i++){
if(chars[i] >= chars[indexRight]){
indexRight = i;
}
}
//以index作为分割点，找到最左边最小值
for(int i = 0; i < index; i++){
if(chars[i] < chars[indexRight]){
indexLeft = i;
break;
}
}
swap(indexLeft, indexRight, chars);//交换两个元素
return Integer.parseInt(new String(chars));
}
public void swap(int i, int j, char[] num){
char temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
728. 自除数简单
自除数是指可以被它包含的每一位数除尽的数。
例如，128 是一个自除数，因为128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
还有，自除数不允许包含 0 。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：
输入：
上边界left = 1, 下边界right = 22
输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：每个输入参数的边界满足1 <= left <= right <= 10000。
思路：
遍历区间中的每个元素，判断它是不是自除数。
class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了85.99%的用户,2020/07/31
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> res = new ArrayList<>();
for(int i = left; i <= right; i++){
if(isselfDividingNum(i)){
res.add(i);
}
}
return res;
}
public boolean isselfDividingNum(int num){
int x = num;
if(num == 0) return false;
while(x != 0){
if(x % 10 == 0 || num % (x % 10) != 0){
return false;
}
x /= 10;
}
return true;
}
}
