LeetCode——数学

最大公约数最小公倍数
1. 生成素数列表
2. 最大公约数
进制转换
1. 7进制
2. 16进制
3. 26进制
阶乘
1. 统计阶乘尾部有多少个0
字符串加减法
1. 二进制加法
2. 字符串加法
相遇问题
1. 改变数组元素使所有的数组元素都相等
其他
1. 平方数
2. 3的n次方
3. 乘积数组

1. 最大公约数最小公倍数

1. 生成素数序列

素数分解
1. 每一个数都可以分解成素数的乘积
思路
1. 创建一个n+1大小的boolean数组和值为0的count变量
2. 因为素数是从2开始的，所以直接从2开始遍历，如果数组为true，说明不是素数，否则count++
3. 然后创建变量j，j=i*i，依次加i遍历，得到不是素数的数，将此位置上的数组设置为true

代码

public static int countPrimes(int n) {

    boolean[] notPrimes = new boolean[n + 1];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (notPrimes[i]) {
            continue;
        }
        count++;
        for (long j = (long) i * i; j < n; j += i) {
            notPrimes[(int) j] = true;
        }
    }
    return count;
}

2. 最大公约数

1. 最大公约数

利用辗转相除法

2. 最大公倍数

最小公倍数为两数的乘积除以最大公约数

代码

public static int gcd(int a, int b) {

    return b == 0 ? a : gcd(b, a % b);
}
public static int lcm(int a,int b){
    return a*b/gcd(a,b);
}

3. 进制转换

1. 7进制

思路
1. 如果需要转换的数为0，直接返回字符串0
2. 不为0则创建StringBuilder用于字符串的拼接，判断num是否为负，如果为负则转换为正数，最后结果添加“-”即可
3. 当num大于0，sb追加num%7的数，然后num=num/7
4. 得出结果要反转字符串，最后判断原始的数如果为负数，则添加“-”号，否则直接输出结果

代码

public static String convertToBase7(int num) {

    if (num == 0) {
        return "0";
    }
    StringBuffer sb = new StringBuffer();
    boolean isNegative = num > 0;
    if (!isNegative){
        num = -num;
    }
    while (num>0){
        sb.append(num%7);
        num /=7;
    }
    String res = sb.reverse().toString();
    return isNegative?res:"-"+res;
}

补充
1. java中static String toString(int num, int radix)可以将一个整数转换为radix进制表示的字符串
public String convertToBase7(int num){
```
return Integer.toString(num, 7);
```
}

2. 16进制

思路
1. 创建char数组存储1~f，创建StringBuilder用于拼接字符串
2. 当num不为0时，num&0b1111（0b表示是二进制）得到的值在map中查找对应的值，然后num无符号右移4位
3. 因为负数就要用它的补码形式，因此符号位不能有特殊的意义，需要使用无符号位右移，左边填0
  1. <<表示左移，不分正负数，低位补0
  2. 表示右移，如果该数为正，则高位补0，若为负数，则高位补1
  3. 表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，若该数为负数，则右移后高位同样补0

代码

public static String toHex(int num) {

    if (num == 0) {
        return "0";
    }
    char[] map = {

‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’};

    StringBuffer sb = new StringBuffer();
    while (num != 0) {
        sb.append(map[num & 0b1111]);
        num >>>= 4;
    }
    return sb.reverse().toString();
}

3. 26进制

思路
1. 因为是从1开始计算的，而不是从0开始的，因此需要对n执行-1，操作

代码

public static String convertToTitle(int n) {

    if (n == 0) {
        return "";
    }
    n--;
    return convertToTitle(n / 26) + (char) (n % 26 + 'A');
}

4. 阶乘

1. 统计阶乘尾部有多少个0

思路
尾部的0由2*5得来，2的数量明显多于5的数量，因此只要统计有多少个5即可

代码

public static int trailingZeros(int n){

    return n==0?0:n/5+trailingZeros(n/5);
}

5. 字符串加减法

1. 二进制加法

概述
思路
1. 取得字符串a，b的最后一个字节下标，创建变量carry用来记录是否需要进位，创建StringBuilder记录结果
2. while循环从后往前遍历字符串a，b
  1. 如果i>=0并且字符串a最后一位是1，carry++
  2. 如果j>=0并且字符串b最后一位是1，carry++
3. str追加结果
  1. 如果carry%2=0，说明需要进位，否则不需要
  2. carry /=2
  3. carry=2时，结果为1，说明需要进位
  4. carry=1时，结果为0，说明不需要进位

代码

public static String addBinary(String a, String b) {

    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    StringBuilder str = new StringBuilder();
    while (carry == 1 || i >= 0 || j >= 0) {
        if (i >= 0 && a.charAt(i--) == '1') {
            carry++;
        }
        if (j >= 0 && b.charAt(j--) == '1') {
            carry++;
        }
        str.append(carry % 2);
        carry /= 2;
    }
    return str.reverse().toString();
}

2. 字符串加法

思路
1. 跟上题一样，carry记录进位的数，字符串a，b从后往前遍历

代码

public static String addStrings(String num1, String num2) {

    StringBuilder str = new StringBuilder();
    int carry = 0;
    int i = num1.length() - 1;
    int j = num1.length() - 1;
    while (carry == 1 || i >= 0 || j >= 0) {
        int x = i < 0 ? 0 : num1.charAt(i--) - '0';
        int y = j < 0 ? 0 : num2.charAt(j--) - '0';
        str.append((x + y + carry) % 10);
        carry = (x + y + carry) / 10;
    }
    return str.reverse().toString();
}

5. 相遇问题

1. 改变数组元素使所有的数组元素都相同

概述
1. 每次可以对一个数组元素加一或者减一，求最小改变的次数
思路
1. 典型是相遇问题，移动距离最小的方式是所有元素都移动到中位数。
2. 设m为中位数。a和b是m两边的两个元素，且b>a。要使a和b相等，它们总移动次数为b-a，这个值等于(b-m)+(m-a)，也就是把这两个数移动到中位数的移动次数
3. 具体就是先将数组nums排序，创建遍历move记录移动次数，l，h记录开始和结尾下标
4. while循环，当l<=h时，move记录nums[h]-nums[l]，然后l++，h–，最后返回move即可

代码

public static int minMoves(int[] nums){

    Arrays.sort(nums);
    int move = 0;
    int l = 0;
    int h = nums.length-1;
    while (l<=h){
        move+=nums[h]-nums[l];
        l++;
        h--;
    }
    return move;
}

6. 多数投票问题

1. 数组中出现次数多于n/2的元素

思路1
1. 先对数组排序，最中间那个数出现次数一定多于n/2
思路2
1. 可以利用Boyer-Moore 投票算法，使得时间复杂度为O(N)。
  1. 使用cnt来统计一个元素出现的次数，当遍历到的元素和统计元素不相同时，令cnt–。如果前面查找了i个元素，且cnt==0，说明前i个元素没有majority，或者右majority，但是出现次数少于i/2，因为如果多有i/2的话cnt就一定不为0.此时剩下的n-i个元素中，majority的数目依然多于(n-i)/2，因此继续查找就能找出majority

代码

public static int majorityElement(int[] nums) {

    Arrays.sort(nums);
    return nums[nums.length / 2];
}
public static int majorityElement2(int[] nums) {
    int cnt = 0;
    int major = nums[0];
    for (int num : nums) {
        major = (cnt == 0) ? num : major;
        cnt = (major == num) ? cnt + 1 : cnt - 1;
    }
    return major;
}

7. 其他

1. 平方数

概述
思路
1. 平方序列：1,4,9,16…
2. 间隔：3,5,7…
3. 间隔为等差数列，使用这个特性可以从得到从1开始的平方序列

代码

public static boolean isPerfectSquare(int num){

    int isPer = 1;
    while (num>0){
        num -= isPer;
        isPer += 2;
    }
    return num==0;
}

2. 3的n次方

思路
1162261467是32位系统中，3的最高次幂19

代码

public static boolean isPowerOfThree(int n) {

    return n > 0 && (Math.pow(3, 19) % n == 0);
}

3. 乘积数组

概述
1. 给定一个数组，创建一个新数组，新数组的每个元素为原始数组中除了该位置上的元素之外所有元素的乘积
2. 要求时间复杂度为O(N)，并且不能使用除法
思路
1. 创建一个新数组products，先将数组元素填充为1。
2. 从前往后遍历（从1开始），记录当前下标i左边的乘积left，将left乘于products[i]，则记录了该下标的左边元素
3. 同理，从后往前遍历（从n-2开始），记录当前下标i的右边元素乘积right，将right乘于products[i]，则记录了该下标的右边元素

代码

public static int[] productExceptSelf(int[] nums) {

    int n = nums.length;
    int[] products = new int[n];
    Arrays.fill(products, 1);
    int left = 1;
    for (int i = 1; i < n; i++) {
        left *= nums[i - 1];
        products[i] *= left;
    }
    int right = 1;
    for (int i = n - 2; i >= 0; i--) {
        right *= nums[i + 1];
        products[i] *= right;
    }
    return products;
}