算法：数学知识
求两个数的最大公共因数
static long gcd(long x,long y) {
return y==0? x: gcd(y, x%y);
}
最大最小公倍数
求1-N之间三个数的最小公倍数的最大值？
思路：前提（根据数论，任意大于1的两个相邻的自然数，都是互质的）。
当n<=2 =》 最大为n
当n>2时
奇数：n*(n-1)*(n-2)
偶数不是三的倍数：n*(n-1)(n-3)
偶数并且是三的倍数：(n-1)*(n-2)(n-3)
我们可以知道，当n是奇数时，n 和n-2都是奇数，n-1是偶数,那么他们三个的公约数肯定不是2,而因为这三个数是连续的，所以大于2的数都不可能成为他们或其中任意两个数的公约数了.结果就是他们三个的乘积.
而当n为偶数时，n*(n-1)(n-2)肯定不行了，因为n和n-2都是偶数，那么只能将n-2改成n-3，即n(n-1)*(n-3),如果这三个数两两互质那么肯定就是结果了.
但是因为n和n-3相差3,所以当其中一个数能被3整除时，另一个肯定也可以.而当其中一个不可以时，另一个肯定也不可以.而因为n为偶数,n-3为奇数，所以2不可能成为他俩的公因子。对于大于3的数，肯定就都不可能成为这三个数或者其中任意两个数的公约数了.因此只需再对3进行判断：
如果n能整除3，那么，n*(n-1)(n-3)就肯定不行了，因为n和n-3有了公约数3，结果肯定小了，那么就只能继续判下一个即n(n-1)(n-4)而这样n-4又是偶数，不行，继续下一个n(n-1)(n-5) = n^3 -6n^2 + 5n 而如果这个可以 那个其值肯定要小于(n-1)(n-2)(n-3) = n^3 -6n^2+11n-6(对于n>1来说都成立),而(n-1)(n-2)(n-3)由上一个奇数结论可知是一个符合要求的，因此到n-5就不用判断了。直接选答案为(n-1)*(n-2)*(n-3)；
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
long n = input.nextInt();
if(n <= 2) { // n 小于 2
System.out.println(n);
}else if(n % 2 != 0) { // n 大于 2 且 n 为奇数
System.out.println(n * (n - 1) * (n -2));
}
// n 为偶数 且不能被3整除
else if(n % 3 != 0) {
System.out.println(n * (n - 1) * (n - 3));
}
else {
System.out.println((n - 1) * (n - 2) * (n - 3));
}
}
求一个数的因数（约数）有多少个
怎样求一个数有多少个因数？ 对于一个已知的自然数，要求出它有多少个因数，可用下列方法：
首先将这个已知数分解质因数，将此数化成几个质数幂的连乘形式，然后把这些质数的指数分别加一，再相乘，求出来的积就是我们要的结果。
例如：求360有多少个因数。 因为360分解质因数可表示为：360=2^3×3^2×5，２、３、５的指数分别是３、２、１，这样３６０的因数个数可这样计算出： ** ** （３＋１）（２＋１）（１＋１）＝２４个。 我们知道，360的因数有 1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360。所以正确。
从质数2开始，直到不能整除，然后加一，直到该数的根号值。
static int factors(long n) {
int res = 1, now;
for (int i = 2; i * i <= n; i++) {// 首先找到小于根号n的所有质数，
now = 1;
while (n % i == 0) {
n /= i;
now++;
}
if (now > 1)
res *= now;
}
return n > 1 ? res * 2 : res;
}
100! 有多少个因数：
BigInteger sum = new BigInteger("100");
BigInteger two = new BigInteger("2");
long res = 1, now;
BigInteger one = BigInteger.ONE;
for (BigInteger i = two; i.multiply(i).compareTo(sum) <=0; i = i.add(one) ) {
now = 1;
while (sum.mod(i).compareTo(BigInteger.ZERO) == 0) {
sum = sum.divide(i);
now ++;
}
if (now > 1) {
res *= now;
}
}
System.out.println(res*2);
一个数n分成多个数的和，使分开的数的乘积最大。
正整数N分成多个互不相同的整数和,乘积最大：
贪心策略：要使乘积做大，尽可能地将指定的n(n>4)拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。
例如： 10 = 2 + 3 + 4 + 1，然后把1加入最后一个，10 = 2 + 3 + 5 例如：26 = 2 + 3 + 4 + 5 + 6 + 6，最后多出的6平均分配，优先最后一位，即26 = 3 + 4 + 5 + 6 + 8
正整数n分成多个数的和，使分开的数的乘积最大：
分成的3的个数越多，那么得到的积最大，
n%3 = 0时，那么分成(n/3)*3
n%3 = 1时，那么分成(n/3-1)*3 *4
n%3 = 2时，那么分成(n/3)*3 *2
判断一个数是否是质数
int num = 43;
boolean flag = true;
for(int j = 2; j * j <= num; j++){
if(num % j == 0){
flag = false;
break;
}
}
if(flag){
System.out.println(n+"是质数");
}
204. 计数质数
暴力枚举解法，超时。
public int countPrimes(int n) {
if(n < 2){
return 0;
}
int count = 0;
boolean flag = true;
for(int i = 2; i < n; i++){
for(int j = 2; j * j <= i; j++){
if(i % j == 0){
flag = false;
break;
}
}
if(flag){
count++;
}else{
flag = true;
}
}
return count;
}
使用一个额外数组标记，遇到一个质数的时候，就把这个质数的倍数标记为合数。
public int countPrimes(int n) {
if(n < 2){
return 0;
}
boolean[] flag = new boolean[n];
//false 代表质数，true代表合数
int count = 0;
for(int i = 2; i < n; i++){
if(!flag[i]){
count ++;
if((long) i * i < n){
for(int j = i * i; j < n; j += i){
flag[j] = true;
}
}
}
}
return count;
}
数学知识
剑指 Offer 14- I. 剪绳子
数学解法。
public int cuttingRope(int n) {
// dp[i] 表示i段的 乘积
if (n <= 3) {
return n-1;
}
int a = n / 3;
int b = n % 3;
int result = 1;
switch (b) {
case 0:
result = (int)Math.pow(3,a);
break;
case 1:
result = (int)Math.pow(3,a-1)*4;
break;
case 2:
result = (int)Math.pow(3,a)*2;
break;
}
return result;
}
dp数组解法：
public int cuttingRope(int n) {
if (n < 3){
return n-1;
}
int[] dp = new int[n+1];
dp[2] = 1;
dp[3] = 2;
for (int i = 4; i < n + 1; i++){
int res = 0;
for (int j = 2; j <= i / 2; j++){
// 找最大值
res = Math.max(res, dp[j] * dp[i-j]);
res = Math.max(res, j * (i-j));
res = Math.max(res, j * dp[i-j]);
res = Math.max(res, dp[j] * (i-j));
}
dp[i] = res;
}
return dp[n];
}
剑指 Offer 49. 丑数
public int nthUglyNumber(int n) {
int[] arr = new int[n];
arr[0] = 1;
int a = 0,b = 0,c = 0;
for(int i = 1; i < n; i++){
int temp = Math.min(arr[a] * 2, Math.min(arr[b] * 3, arr[c] * 5));
if(temp == arr[a] * 2){
a ++;
}
if (temp == arr[b] * 3){
b ++;
}
if( temp == arr[c] * 5){
c ++;
}
arr[i] = temp;
}
return arr[n-1];
}
常用位操作
1. 利用或操作 | 和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
2. 利用与操作 & 和下划线将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
3. 利用异或操作 ^ 和空格进行英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
4. 判断两个数是否异号
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false
5. 不用临时变量交换两个数
^三个法则： 1，0^N = N; N^N = 0; 2，交换，结合 a ^ b = b ^ a; (a ^ b) ^ c = a ^ (b ^c)
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1
6. 加一
int n = 1;
n = -~n;
// 现在 n = 2
7. 减一
int n = 2;
n = ~-n;
// 现在 n = 1
5，6，7这三个操作就纯属装逼用的，没啥实际用处，大家了解了解乐呵一下就行。
常用习题
n&(n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1。
191. 位1的个数
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
2, 判断一个数是不是 2 的指数
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
剑指 Offer 65. 不用加减乘除做加法
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
未做29. 两数相除，不用/和%算商
3. 查找只出现一次的元素
a^a = 0; 0^b = b; a^c^b = a^b^c;
public int singleNumber(int[] nums) {
int a = nums[0];
for (int i = 1; i < nums.length; i++) {
a = a ^ nums[i];
}
return a;
}
剑指 Offer 56 - I. 数组中数字出现的次数
public int[] singleNumbers(int[] nums) {
int x = 0;
for (int num : nums) {
x ^= num;
}
//获取x最右边的1
int flag = x & (-x);
int res = 0;
for (int num : nums) {
if ((flag & num) == 0){
res ^= num;
}
}
return new int[]{res, x ^ res};
}
剑指 Offer 56 - II. 数组中数字出现的次数 II
public int singleNumber(int[] nums) {
int [] k = new int[32];
for(int i = 0 ; i < nums.length;i++){
for(int j = 0 ; j <32;j++){
k[j] += (nums[i]>>j & 1) == 1 ? 1 : 0;
}
}
int res = 0;
for(int i = 31;i>=0;i--){
res = res << 1;
if(k[i]%3 == 1){
res = (res | 1);
}
}
return res;
}
阶层相关的算法题：
172. 阶乘后的零
求一个数的阶乘末尾有几个0
转化问题：末尾有0->这个数必定含有2，5因数
->****
n!最多可以分解出多少个因子 2 和 5？**-> **
n!最多可以分解出多少个因子 5？例125！有几个因子5
125/5 = 25, 125 / 5*5 = 5, 125/5 *5 *5 = 1；
那么125可以分解为31。
public int trailingZeroes(int n) {
int res = 0;
long divisor = 5;
while (divisor <= n) {
res += n / divisor;
divisor *= 5;
}
return res;
}
793. 阶乘函数后 K 个零
首先找出左右边界，left=0，right=Long.MAX_VALUE。然后利用二分法找到满足阶乘函数后有k个0的左右边界。要利用上面的那个题，计算n!后面有几个0；
class Solution {
/* 主函数 */
int preimageSizeFZF(int K) {
// 左边界和右边界之差 + 1 就是答案
return (int)(right_bound(K) - left_bound(K) + 1);
}
/* 搜索 trailingZeroes(n) == K 的左侧边界 */
long left_bound(int target) {
long lo = 0, hi = Long.MAX_VALUE;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
hi = mid;
}
}
return lo;
}
/* 搜索 trailingZeroes(n) == K 的右侧边界 */
long right_bound(int target) {
long lo = 0, hi = Long.MAX_VALUE;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo - 1;
}
public long trailingZeroes(long n) {
long res = 0;
long divisor = 5;
while (divisor <= n) {
res += n / divisor;
divisor *= 5;
}
return res;
}
}
如何用算法高效寻找素数？
用一个数组标记素数的倍数为false，最后遍历数组即可
在标记时，范围从2--sprt(n)就可以。
public static int countPrimes(int n) {
//用于标记的数组
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for (int i = 2; i * i < n; i++) {
if (isPrim[i]) {
for (int j = i * i; j < n; j+=i) {
isPrim[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrim[i]) {
count++;
}
}
return count;
}
如何高效进行模幂运算(未做）
372. 超级次方
寻找缺失元素
位运算解法：
int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// 先和新补的索引异或一下
res ^= n;
// 和其他的元素、索引做异或
for (int i = 0; i < n; i++)
res ^= i ^ nums[i];
return res;
}
更好的解法：
int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// 新补的索引
res += n - 0;
// 剩下索引和元素的差加起来
for (int i = 0; i < n; i++)
res += i - nums[i];
return res;
}
高效寻找缺失和重复的数字
645. 错误的集合
使用一个boolean[]做标记，
public int[] findErrorNums(int[] nums) {
boolean[] b = new boolean[nums.length+1];
int[] arr = new int[2];
for (int i = 0; i < nums.length; i++) {
if (b[nums[i]]) {
arr[0] = nums[i];
}
b[nums[i]] = true;
}
for (int i = 1; i < b.length; i++) {
if (!b[i]) {
arr[1] = i;
}
}
return arr;
}
随机算法之水塘抽样算法
382. 链表随机节点
398. 随机数索引
当你遇到第
i个元素时，应该有1/i的概率选择该元素，1 - 1/i的概率保持原有的选择。
class Solution {
ListNode listNode;
public Solution(ListNode head) {
listNode = head;
}
public int getRandom() {
Random random = new Random();
ListNode node = listNode;
int res = 0,i = 0;//
while (node != null) {
//主要代码[0,i)
if (random.nextInt(++i) == 0) {
res = node.val;
}
node = node.next;
}
return res;
}
}
同理，如果要随机选择k个数，只要在第i个元素处以k/i的概率选择该元素，以1 - k/i的概率保持原有选择即可。代码如下：
/* 返回链表中 k 个随机节点的值 */
int[] getRandom(ListNode head, int k) {
Random r = new Random();
int[] res = new int[k];
ListNode p = head;
// 前 k 个元素先默认选上
for (int j = 0; j < k && p != null; j++) {
res[j] = p.val;
p = p.next;
}
int i = k;
// while 循环遍历链表
while (p != null) {
// 生成一个 [0, i) 之间的整数
int j = r.nextInt(++i);
// 这个整数小于 k 的概率就是 k/i
if (j < k) {
res[j] = p.val;
}
p = p.next;
}
return res;
}
- 求两个数的最大公共因数
- 最大最小公倍数
- 求一个数的因数（约数）有多少个
- 一个数n分成多个数的和，使分开的数的乘积最大。
- 判断一个数是否是质数
- 204. 计数质数
- 数学知识
- 剑指 Offer 14- I. 剪绳子
- 剑指 Offer 49. 丑数
- 常用位操作
- 1. 利用或操作 | 和空格将英文字符转换为小写
- 2. 利用与操作 & 和下划线将英文字符转换为大写
- 3. 利用异或操作 ^ 和空格进行英文字符大小写互换
- 4. 判断两个数是否异号
- 常用习题
- 191. 位1的个数
- 2, 判断一个数是不是 2 的指数
- 剑指 Offer 65. 不用加减乘除做加法
- 未做29. 两数相除，不用/和%算商
- 3. 查找只出现一次的元素
- 剑指 Offer 56 - I. 数组中数字出现的次数
- 剑指 Offer 56 - II. 数组中数字出现的次数 II
- 阶层相关的算法题：
- 172. 阶乘后的零
- 793. 阶乘函数后 K 个零
- 如何用算法高效寻找素数？
- 如何高效进行模幂运算(未做）
- 372. 超级次方
- 寻找缺失元素
- 高效寻找缺失和重复的数字
- 645. 错误的集合
- 随机算法之水塘抽样算法
- 382. 链表随机节点
- 398. 随机数索引