王道论坛机试指南学习笔记（三）数学问题
文章目录
1. 2的n次方
- 移位
//'<<','>>'为移位符号
//二进制中表示左右移动n位
//相当于十进制中2的n次方
1 << n；
- power
//普通求法，求x的n次方
public static int power(int x, int n){
int result = 1;
for (int i = 0; i < n; i++) {
result *= x;
}
return result;
}
2. 特殊值
- 最大值
int max = Math.max(a, b);
- 绝对值
int abs = Math.abs(x);
3. 取整
//向下取整
double x = Math.floor(y);
//向上取整
double x = Math.ceil(y);
//四舍五入
double x = Math.round(y);
4. 数位拆解
- 数学方法
-
按照数学思想，取余数，逐位计算
//将小于100000000的大整数分割存储为每位数的列表 public static List<Integer> splitBigInt(long x){ int y = 100000000; List<Integer> list = new ArrayList<>(); while (y>0){ int r = (int)x/y; list.add(r); x = x%y; y /= 10; } return list; } //将两个列表中的每位数依次相乘并加和 public static int specialMulti(List<Integer> a, List<Integer> b){ int result = 0; for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b.size(); j++) { result += a.get(i)*b.get(j); } } return result; }
- 代码方法
-
按照代码的思想，将数字转为String，直接计算
public static int specialMulti2(String a, String b){ int result = 0; for (int i = 0; i < a.length(); i++) { for (int j = 0; j < b.length(); j++) { result += (a.charAt(i)-'0')*(b.charAt(j)-'0'); } } return result; }
5. 进制转换
- n转10
//进制数在2~16之间
public static int changeSystem2Ten(int system, String str){
int length = str.length(), result = 0;
for (int i = length-1; i >= 0; i--) {
char ch = str.charAt(i);
int temp = 0;
if(ch>='0'&&ch<='9') temp = ch - '0';
else if(ch>='a'&&ch<='z') temp = ch-'a'+10;
else if(ch>='A'&&ch<='Z') temp = ch-'A'+10;
result += temp*power(system, length-i-1);
}
return result;
}
- 10转n
public static String changeSystemFromTen(int system, int num){
String result = "";
int r, temp;
if(num==0){
result = "0";
return result;
}
while (num!=0){
temp = num/system;
r = num%system;
String str = String.valueOf(r);
if(r>9){
switch (r){
case 10:
str = "A";
break;
case 11:
str = "B";
break;
case 12:
str = "C";
break;
case 13:
str = "D";
break;
case 14:
str = "E";
break;
case 15:
str = "F";
break;
}
}
result = str + result;
num = temp;
}
return result;
}
6. GCD & LCM
- GCD
-
欧几里得算法求最大公约数
-
代码
public static int GCD(int x, int y){ if(x<=0&&y<=0) return -1; else if (y==0) return x; else return GCD(y, x%y); }
- LCM
public static int LCM(int x, int y){
return x*y/GCD(x, y);
}
7. 质数
- 判断质数
public static boolean isPrime(int x){
if(x<0) return false;
if(x<2) return true;
int s = (int)Math.floor(Math.sqrt(x));
for (int i = 2; i <= s; i++) {
if(x%i==0)return false;
}
return true;
}
- 素数筛法
- 从2开始遍历区间内的全部整数，将每个素数的全部倍数标记为非素数
public static List<Integer> findPrimeInDomain(int max){
boolean[] mark = new boolean[max];
List<Integer> primeList = new ArrayList<>();
//初始化，默认全部数字为质数
for (int i = 0; i < max; i++) {
mark[i] = true;
}
for (int i = 2; i < max; i++) {
//当前为非质数，跳过
if(!mark[i]) continue;
//找到一个质数，加入列表
primeList.add(i);
//从i*i开始标记，因为小于i*i的非质数一定已经被小于i的质数标记过
for (int j = i*i; j < max; j+=i) {
mark[j] = false;
}
}
return primeList;
}
- 分解质因数
public static HashMap<Integer, Integer> factorizePrimeFactor(int x){
//使用哈希表，存储x中包含的质因数以及包含的个数
HashMap<Integer, Integer> resultMap = new HashMap<>();
//利用素数筛法，获取当前区间内的全部质数列表
List<Integer> primeList = findPrimeInDomain(x);
int index = 0, prime = primeList.get(index), count = 0;
//若x不为1，则继续分解
while (x!=1){
//当x能分解出多个质因数，循环分解
while (x%prime==0){
//若哈希表中已有此质数，则个数加一
if(resultMap.containsKey(prime)){
count = resultMap.get(prime)+1;
}
//若表中无此质数，则个数为1
else {
count = 1;
}
//使用put方法，覆盖原有质数的哈希对
resultMap.put(prime, count);
x /= prime;
}
//若当前质数不能整除x，则计算下一个质数
index += 1;
prime = primeList.get(index);
}
return resultMap;
}
8. 二分求幂
- 求a^b
- 循环求解效率低，需要执行b次乘法；
- 应该充分利用平方的概念，将b转化为二进制，求b分解出的2的n次方的和；
- 每次对1000取余，降低数量级，结果只要后三位。
public static int power2(int x, int n){
int result = 1;
while (n != 0){
if(n%2==1){
result *= x;
result %= 1000;
}
n /= 2;
x *= x;
x %= 1000;
}
return result;
}