《数学》专题

Posted on Edited on In , Views:

数学相关的算法。

1. 进制转换

1.1 任意进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int titleToNumber(string s) {
        int length = s.size();
        long long result = 0;
        for(int i = 0; i<length; i++)
        {
            result = result*s的进制数 + s[i]的数字形式;;
        }
        return result;
    }
};

比如26进制转10进制

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int titleToNumber(string s) {
        int length = s.size();
        long long result = 0;
        for(int i = 0; i<length; i++)
        {
            //【s[i]-'A'+1】将A、B、C... 映射到 1、2、3...
            result = result*26 + s[i]-'A'+1;
        }
        return result;
    }
};

再比如2进制转10进制

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int titleToNumber(string s) {
        int length = s.size();
        long long result = 0;
        for(int i = 0; i<length; i++)
        {
            //【s[i]-'0'】将字符'0'、'1'、'2'...映射到数字1、2、3....
            result = result*2 + s[i]-'0';
        }
        return result;
    }
};

1.2 十进制转任意进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char get(int x)//将x转换为字符形式
{
    if (x <= 9) return x + '0';
    return x - 10 + 'A';
}

string change_base(int n, int b)//【短除法】将十进制整数n转换为b进制，返回对应字符串
{
    string res;
    while (n)
    {
        res += get(n % b);
        n /= b;
    }
    reverse(res.begin(), res.end());//翻转回高位在左
    return res;
}

1.3 任意进制转任意进制（TODO）

一种方法利用10进制作为跳板，但是这样可能会溢出。

2. 大数运算

大数运算的本质就是把每一位数字提取到数组中，然后在数组中模拟运算。考虑到进位的情况，数字应该被倒序存储到数组中，否则产生进位时要移动整个数组。

2.1 大数加法

t的作用是把两数对应位上的数字相加，判断它是否大于10，如果true，则它变成1并参与下一轮运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*both a and b are in reversed order*/
vector<int> add(vector<int>& a, vector<int>& b)
{
    vector<int> re;
    int t = 0;  //accumulator
    for (int i = 0; i < a.size() || i < b.size(); i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        re.push_back(t % 10);       
        t /= 10;      //if t>10, t/10 = 1
    }
    if (t) re.push_back(1);  //t产生进位
    return re;
}

2.2 大数减法

还是用t表示是否借位了。该模板默认a大于b，若可能出现a小于b，则把它们顺序调换一下传入，再添上负号即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*1. both a and b are in reversed order
  2. a is bigger than b
*/
vector<int> subtract(vector<int>& a, vector<int>& b)
{
    vector<int> re;
    int t = 0; //accumulator
    for (int i = 0; i < a.size(); i++)
    {
        t  = a[i]-t;
        if (i < b.size()) t -= b[i];
        re.push_back((t + 10) % 10);//if t<0, t+=10
        if (t < 0) t = 1; //如果t<0, 下一次计算a[i]要被减去1（借位）
        else t = 0;
    }
    /*消除前导零/
    while (re.size() > 1 && re.back() == 0) re.pop_back();
   
    return re;
}

2.3 大数乘法

大数与普通整型数相乘。
不像我们手算乘法，b逐位与arr逐位相乘，该方法是arr逐位与b整体相乘。其中t表示每次进位的数

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> mul(vector<int>& arr, int b)
{
    vector<int> re;
    int t = 0;
    for (int i = 0; i <arr.size()||t; i++) //“||t”表示如果进位没处理完，则循环还要继续
    {
        if( i<arr.size() )  t = arr[i] * b + t;
        re.push_back(t % 10);
        t /= 10;
    }
    return re;
}

2.4 大数除法

被除数的每一位与除数比较，如果除数较大，则把当前位的被除数与后一个合并，继续与除数比较。如果除数较小或者相等，则把这次的商存入结果数组，继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*r为余数，b为除数。
为了与其他模板统一，这里传入的arr也是in reverse order
*/
vector<int> div(vector<int>& arr, int b, int& r)
{
    vector<int> re;
    int t = 0;
    for (int i = arr.size()-1; i >= 0; i--)
    {
        t = t * 10 + arr[i];
        re.push_back(t / b);
        t %= b;
    }
    /*因为该方法是从结果的最高位push进arr的（这样就是正序了），
    为了与其他模板统一，将arr变为倒序。*/
    reverse(arr.begin(), arr.end());  
    while (arr.size() > 1 && arr.back() == 0) arr.pop_back();
    return re;
}

3. 找众数

投票算法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}
//时间复杂度O(n), 空间复杂度O(1)

例题

1. 到数轴上其他点距离之和最小的点

【题目】

数轴上有许多点，找到一个位置x，使得x到所有点的距离之和最小，并求出这个距离。

https://www.acwing.com/problem/content/106/

【解析】

x到区间(a, b)两端点的距离之和为$|a-x|+|b-x|$，根据绝对值不等式
$$
|a-x|+|b-x| \ge |(a-x)- (b-x)| = |b-a|
$$
可以想象，如果x小于a或者大于b，都不可能使得它到a和b的距离之和最小。但是只要x取到a和b之间，上述不等式的等号就成立，即这时x到a和b的距离之和取到最小值 b-a。拓展到n个点的情况，只要把x放在所有点的中心位置（当n为偶数时放在中间两个点的中间，为奇数时放在最中间那个点上），这时它与所有其他点的距离之和即为最短。

简而言之，当数轴上点的总数为奇数时，x的位置就是数轴上最中间那个点的位置；当数轴上点的总数为偶数时，x的位置就在数轴上最中间那两个点的中间。

【ac代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int q[N];

int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++) cin>>q[i];
    
    sort(q, q+n);
    
    //当n为偶数时x取到中间两个点的中间，为奇数时x直接取到最中间那个点上
    int x = n%2==0?q[n/2]+q[n/2-1]>>1:q[n/2];
    int re = 0;
    for(int i = 0;i<n;i++) re += abs(q[i]-x);
    
    cout<<re<<endl;
    return 0;
}