LeetCode精选题之数学

最大公约数：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

最小公倍数：

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

使用位操作和减法求解最大公约数：
对于 a 和 b 的最大公约数 f(a, b)，有：

• 如果 a 和 b 均为偶数，f(a, b) = 2*f(a/2, b/2);
• 如果 a 是偶数 b 是奇数，f(a, b) = f(a/2, b);
• 如果 b 是偶数 a 是奇数，f(a, b) = f(a, b/2);
• 如果 a 和 b 均为奇数，f(a, b) = f(b, a-b);

参考资料：CyC2018：Leetcode 题解 - 数学

1 计数质数–LeetCode204

统计所有小于非负整数 n的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

暴力法：

class Solution {
    public int countPrimes(int n) {
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                res++;
            }
        }
        return res;
    }

    private boolean isPrime(int x) {
        for (int i = 2; i < x; i++) {
            if (x%i == 0) {
                return false;
            }
        }
        return true;
    }
}

厄拉多塞筛法：在每次找到一个素数时，将能被素数整除的数排除掉。

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n+1];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrime[i]) {
                continue;
            }
            count++;
            for (int j = i+i; j < n; j += i) {
                notPrime[j] = true;
            }
        }
        return count;
    }
}

2 七进制数–LeetCode504

给定一个整数，将其转化为7进制，并以字符串形式输出。

示例 1:

输入: 100
输出: "202"

示例 2:

输入: -7
输出: "-10"

注意: 输入范围是 [-1e7, 1e7] 。

class Solution {
    public String convertToBase7(int num) {
        StringBuilder sb = new StringBuilder();
        // 负数统一转化为正数处理
        if (num < 0) {
            sb.append("-");
            num = -num;
        }
        // 找到最大的不超过num的7的幂次
        int dividend = 1;
        int temp = 0;
        while ((temp = dividend*7) <= num) {
            dividend = temp;
        }
        // 从高到低确定各位，注意条件的选择，不能选择num>0，因为对于7,49这类的数可以手推一下
        while (dividend > 0) {
            sb.append(num/dividend);
            num %= dividend;
            dividend /= 7;
        }
        return sb.toString();
    }
}

3 数字转换为十六进制数–LeetCode405

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

1. 十六进制中所有字母(a-f)都必须是小写。
2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
3. 给定的数确保在32位有符号整数范围内。
4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:
26

输出:
"1a"

示例 2：

输入:
-1

输出:
"ffffffff"

class Solution {
    public 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'};
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(map[num&0xf]);
            num = num>>>4;// 因为考虑的是补码形式，因此符号位就不能有特殊的意义，需要使用无符号右移，左边填 0
        }
        return sb.reverse().toString();
    }
}

4 Excel表列名称–LeetCode168

给定一个正整数，返回它在 Excel 表中相对应的列名称。

例如，

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

示例 1:

输入: 1
输出: "A"

示例 2:

输入: 28
输出: "AB"

示例 3:

输入: 701
输出: "ZY"

进制问题的变形。注意余数为26的时候，做一下变换。参考题解：windliang的题解

class Solution {
    public String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int remainder = n % 26;
            if (remainder == 0) {
                remainder = 26;
                n -= 1;
            }
            sb.append((char)('A'+remainder-1));
            n /= 26;
        }
        return sb.reverse().toString();
    }
}

5 阶乘后的零–LeetCode172

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            count += n / 5;
            n /= 5;
        }
        return count;
    }
}

对问题的归纳总结。规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5… 以此类推。参考题解：windliang

6 二进制求和–LeetCode67

给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

• 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 “0” ，就都不含前导零。

思路：整体思路是将两个字符串较短的用 000 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。

class Solution {
    public String addBinary(String a, String b) {
        int carry = 0; // 进位
        StringBuilder sb = new StringBuilder();
        for (int i = a.length()-1, j = b.length()-1; i >= 0 || j >= 0; i--, j--) {
            int sum = carry;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) {
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}

7 字符串相加–LeetCode415

给定两个字符串形式的非负整数 num1和num2，计算它们的和。

提示：

1. num1 和num2 的长度都小于 5100
2. num1 和num2 都只包含数字 0-9
3. num1 和num2 都不包含任何前导零
4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0; // 进位
        for (int i = num1.length() - 1, j = num2.length() - 1; 
        i >= 0 || j >= 0; i--, j--) {
            int sum = carry;
            sum += i >= 0 ? num1.charAt(i) - '0' : 0;
            sum += j >= 0 ? num2.charAt(j) - '0' : 0;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        if (carry != 0) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }
}

8 最少移动次数使数组元素相等 II–LeetCode462（Medium）

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:

输入:[1,2,3]
输出:2
说明：只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

这是一个经典的数学问题，当 x为这个 N个数的中位数时，可以使得距离最小。具体地，若 N为奇数，则 x必须为这 N个数中的唯一中位数；若 N为偶数，中间的两个数为 p和 q，中位数为 (p + q) / 2，此时 x只要是区间 [p, q]中的任意一个数即可。

然后使用快速选择寻找中位数。

class Solution {
    
    private static final Random random = new Random();
    
    public int minMoves2(int[] nums) {
        // 快速选择算法确定中位数
        int median = select(nums, 0, nums.length - 1, nums.length / 2);
        // 根据中位数确定最小移动次数
        int res = 0;
        for (int num : nums) {
            res += Math.abs(median - num);
        }
        return res;
    }

    // 快速选择算法
    private int select(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) {
            return nums[pivotIndex];
        } else if (pivotIndex > k) {
            return select(nums, left, pivotIndex - 1, k);
        } else {
            return select(nums, pivotIndex + 1, right, k);
        }
    }

    // 选定基准数据pivot，对[left, right]里面的数据进行划分，返回基准数据的位置
    private int partition(int[] nums, int left, int right) {
        if (right > left) {
            int randomIndex = left + random.nextInt(right - left + 1);
            swap(nums, left, randomIndex);
        }
        int pivot  = nums[left];
        int j = left;
        for (int i = left+1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

9 多数元素–LeetCode169

给定一个大小为 n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

排序法。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

摩尔投票法：寻找数组中超过一半的数字，这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数 。即如果把 该众数记为 +1 ，把其他数记为 −1 ，将它们全部加起来，和是大于 0 的。

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                count = 1;
                candidate = nums[i];
                continue;
            }

            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

10 有效的完全平方数–LeetCode367

给定一个正整数 num，编写一个函数，如果 num是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16
输出：True

示例 2：

输入：14
输出：False

思路：二分查找。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }
        long left = 2, right = num/2;
        long mid, square;
        while (left <= right) {
            mid = left + (right-left)/2;
            square = mid * mid;
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

11 3的幂–LeetCode326

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 27
输出: true

示例 2:

输入: 0
输出: false

示例 3:

输入: 9
输出: true

示例 4:

输入: 45
输出: false

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        long power = 1;
        while (power < n) {
            power *= 3;
            if (power == n) {
                return true;
            }
        }
        return false;
    }
}

骚操作：3的幂次质因子只有3，而整数范围内的3的幂次最大是1162261467

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

12 除自身以外数组的乘积–LeetCode238（Medium）

给你一个长度为 n的整数数组 nums，其中 n > 1，返回输出数组 output，其中 output[i]等于 nums中除 nums[i]之外其余各元素的乘积。

示例：

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解题思路：将 res 数组列成乘积形式，不同的 n 组成每行内容，形成一个矩阵，可以发现矩阵 主对角线 全部为 1 （当前数字不相乘，等价为乘 1）；因此，我们分别计算矩阵的 下三角 和 上三角，并且在计算过程中储存过程值，最终可以在遍历 2 遍 nums 下完成结果计算。

参考资料：jyd的题解

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int p = 1, q = 1;
        for (int i = 0; i < nums.length; i++) {
            res[i] = p; // res存储的是前缀之积，即nums[0, i-1]的乘积
            p *= nums[i]; 
        }
        for (int i = nums.length - 1; i > 0; i--) {
            q *= nums[i]; // q表示的是后缀之积，即nums[i, nums.length-1]的乘积
            res[i-1] *= q;
        }
        return res;
    }
}

13 三个数的最大乘积–LeetCode628

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1:

输入: [1,2,3]
输出: 6

示例 2:

输入: [1,2,3,4]
输出: 24

注意:

1. 给定的整型数组长度范围是[3, 10⁴]，数组中所有的元素范围是[-1000, 1000]。
2. 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

方法一：排序。
将数组进行升序排序，

• 如果数组中所有的元素都是非负数，那么答案即为最后三个元素的乘积；
• 如果数组中出现了负数，那么我们还需要考虑乘积中包含负数的情况，显然选择最小的两个负数和最大的一个正数是最优的，即为前两个元素与最后一个元素的乘积。

上述两个结果中的较大值就是答案。

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[0]*nums[1]*nums[len-1], nums[len-3]*nums[len-2]*nums[len-1]);
    }
}

方法二：线性扫描。
用线性扫描直接得出数组中最大的三个数以及最小的两个数即可。

public class Solution {
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int n: nums) {
            if (n <= min1) {
                min2 = min1;
                min1 = n;
            } else if (n <= min2) {     // n lies between min1 and min2
                min2 = n;
            }
            if (n >= max1) {            // n is greater than max1, max2 and max3
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n >= max2) {     // n lies betweeen max1 and max2
                max3 = max2;
                max2 = n;
            } else if (n >= max3) {     // n lies betwen max2 and max3
                max3 = n;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}