# 数学

数学是利用符号语言研究数量、结构、变化以及空间等概念的一门学科，从某种角度看属于形式科学的一种。数学透过抽象化和逻辑推理的使用，由计数、计算、量度和对物体形状及运动的观察而产生。数学家们拓展这些概念，为了公式化新的猜想以及从选定的公理及定义中建立起严谨推导出的定理。

# 1 相遇问题

# 1 最少移动次数使数组元素相等 II

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

例如:

输入:

[1,2,3]

输出:

说明：

只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：

[1,2,3] => [2,2,3] => [2,2,2]

每次可以对一个数组元素加一或者减一，求最小的改变次数。

这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：

设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。
要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，
也就是把这两个数移动到中位数的移动次数。

设数组长度为 N，则可以找到 N/2 对 a 和 b 的组合，使它们都移动到 m 的位置。

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int lo = 0, hi = nums.length-1, move = 0;
        while(hi >= lo){
            move += nums[hi] - nums[lo];
            lo++;;
            hi--;
         }
        return move;
    }
}

//详细分析题目， 找到边界条件及关键步骤。

# 2最小移动次数使数组元素相等

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。

示例:

输入:

[1,2,3]

输出:

解释:

只需要3次移动（注意每次移动会增加两个元素的值）

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

该方法基于以下思路：将除了一个元素之外的全部元素+1，等价于将该元素-1，因为我们只对元素的相对大小感兴趣
因此，该问题简化为需要进行的减法次数。

显然，我们只需要将所有的数都减到最小的数即可。为了找到答案，我们不需要真的操作这些元素。
只需要累加所有的元素与最小元素的差值；

class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE,hi = nums.length, move = 0;
        for(int i = 0; i<hi; i++){
            min  = Math.min(min, nums[i]);
        }
        for(int j = 0; j<hi; j++){
            move += nums[j] - min;
        }
        return move;
    }
}

# 2 进制转换

任何进制转换为10进制， 10进制转换为其他进制。

# 1 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 
27 写做  XXVII, 即为 XX + V + II 。

输入: "IV"
输出: 4

输入: "IX"
输出: 9

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> romaNumber = new HashMap<>();
        romaNumber.put('I', 1);
        romaNumber.put('V', 5);
        romaNumber.put('X', 10);
        romaNumber.put('L', 50);
        romaNumber.put('C', 100);
        romaNumber.put('D', 500);
        romaNumber.put('M', 1000);

        int firstValue = 0;
        int nextValue = 0;
        int sum = 0;
        for(int i = 0; i<s.length(); i++ ){
            firstValue = romaNumber.get(s.charAt(i));
            // 最后一个roma数字不可能是前缀，边界情况
            if( i == s.length()-1)  sum += firstValue;
            else{
                // 比较当前数字与下个数字， 确定加减当前数字， 每次都是最优解， 贪心算法？
                nextValue = romaNumber.get(s.charAt(i+1));
                if(nextValue > firstValue){
                    sum -= firstValue;
                }else{
                    sum += firstValue;
                }
            }
        }
        return sum;
    }
}

# 2 7进制

# （10进制转其他进制）

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

示例 1:

输入: 100
输出: "202"
示例 2:

输入: -7
输出: "-10"
注意: 输入范围是 [-1e7, 1e7]

通用模板，转换成二进制思路相同，
为什么要先求余数？可以减少很多if语句的判断，请记住最后的反转。

public String convertToBase7(int num) {
    if (num == 0) {
        return "0";
    }
    StringBuilder sb = new StringBuilder();
    boolean isNegative = num < 0;
    if (isNegative) {
        num = -num;
    }
    while (num > 0) {
        sb.append(num % 7);
        num /= 7;
    }
    String ret = sb.reverse().toString();
    return isNegative ? "-" + ret : ret;
}

# 3 Excel表列名称(10进制转换成其他进制)

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

例如，

1 -> A

2 -> B

3 -> C

...

26 -> Z

27 -> AA

28 -> AB

...

示例 1:

输入: 1

输出: "A"

示例 2:

输入: 28

输出: "AB"

public String convertToTitle(int n) {
    String AZ = "#ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char[] CZ = AZ.toCharArray();

    StringBuilder sb = new StringBuilder();

    while (n > 0) {
        if (n % 26 == 0) {
            // 
            sb.append('Z');
            n = n / 26 - 1;
        } else {
            sb.append(CZ[n % 26]);
            n = n / 26;
        }
    }

    return sb.reverse().toString();

}

# 4 26进制

给定一个Excel表格中的列名称，返回其相应的列序号。
例如，
    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...
    
输入: "A"
输出: 1

其他进制转换成10进制也是差不多的流程。

class Solution {
    public int titleToNumber(String s) {
        int ans = 0;
        for(int i=0;i<s.length();i++) {
            int num = s.charAt(i) - 'A' + 1;
            ans = ans * 26 + num;
        }
        return ans;
    }
}

# 4 16 进制转换为10进制

给定一个16进制的数，将其转化为10进制

输入: 16
输出: 256

public int convertToBase10(int num) {
    if (num == 0) {
        return 0;
    }
    int sum = 0;
    while(num > 0){
        sum = sum*16 + num%16;
        num 
    } 
}

# 3 字符串加减

# 1 二进制加法

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

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

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0; // 累加器
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            //保证不会越界，
            sum += i >= 0 ? a.charAt(i) - '0' : 0;   // 字符串相减
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");  //检查最前一位的进位情况，
        return ans.reverse().toString();
    }
}

# 2 字符串相加

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

注意：

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

累加器，位运算也有相同的；

class Solution {
    public String addStrings(String num1, String num2) {
       StringBuilder s = new StringBuilder();
        int l1 = num1.length()-1;
        int l2 = num2.length()-1;
        int ca = 0;
        while(ca == 1 || l1 >=0 || l2>=0){
           int  sum = ca;
            sum += l1 < 0 ? 0: num1.charAt(l1--)- '0';
            sum += l2 < 0 ? 0: num2.charAt(l2--)- '0';
            
            s.append(sum%10);
            ca = sum/10;
        }
        return s.reverse().toString();
        
    }
}

# 4投票问题

# 波义尔摩尔投票算法是一种使用线性时间复杂度和常数空间复杂度来找到数组的主要元素（出现超过一半次数的元素）。

遍历数组的时候保存两个值：一个是数组中的数字，另一个是次数。
当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；
如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，那么需要保存下一个数字，并把次数设为1.
由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时的对应数字。

# 1 求众数

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

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

示例 1:

输入: [3,2,3]

输出: 3

示例 2:

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

输出: 2

投票法时间复杂度为线性时间。空间复杂度为常数。

// 投票法
class Solution {
  public int majorityElement(int[] nums) {
    int major = nums[0];
    int cnt =0;
    for(int n  : nums){
        major = (cnt == 0)? n: major;
        cnt = (major == n)? cnt+1: cnt-1;
    }
    return major;

}
}


// 排序， 中间位置

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

# 2 求众数2

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:

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

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

class Solution {
   public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0)
        return res;
    //初始化：定义两个候选人及其对应的票数
    int candidateA = nums[0];
    int candidateB = nums[0];
    int countA = 0;
    int countB = 0;
    //遍历数组
    for (int num : nums) {
        if (num == candidateA) {
            countA++;//投A
            continue;
        }
        if (num == candidateB) {
            countB++;//投B
            continue;
        }

        //此时当前值和AB都不等，检查是否有票数减为0的情况，如果为0，则更新候选人
        if (countA == 0) {
            candidateA = num;
            countA++;
            continue;
        }
        if (countB == 0) {
            candidateB = num;
            countB++;
            continue;
        }
        //若此时两个候选人的票数都不为0，且当前元素不投AB，那么A,B对应的票数都要--;
        countA--;
        countB--;
    }

    //上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数
    countA = 0;
    countB = 0;
    for (int num : nums) {
        if (num == candidateA)
            countA++;
        else if (num == candidateB)
            countB++;
    }
    if (countA > nums.length / 3)
        res.add(candidateA);
    if (countB > nums.length / 3)
        res.add(candidateB);
    return res;
   }
}

# 5 素数分解

每一个数都可以分解成素数的乘积，例如 84 = 22 * 31 * 50 * 71 * 110 * 130 * 170 * …

# 1生成素数序列

Count Primes (Easy)

埃拉托斯特尼筛法在每次找到一个素数时，将能被素数整除的数排除掉。

public 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++;
        // 从 i * i 开始，因为如果 k < i，那么 k * i 在之前就已经被去除过了
        for (long j = (long) (i) * i; j < n; j += i) {
            notPrimes[(int) j] = true;
        }
    }
    return count;
}

# 6 最大公约数与最小公倍数

# 1 最大公约数

// 辗转相除法
// 辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

// 最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

# 2 最小公倍数

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积
最小公倍数为两数的乘积除以最大公约数。

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

← stack-queue 贪心算法与回溯算法 →