# 机考-数学类

gcd求最大公约数『模板』
lcm最小公倍数『模板』
数字-找规律题解⭐️
- 1.剑指 Offer 44. 数字序列中某一位的数字
- 数字规律！
大数算法『模板』
约瑟夫环-剑指 Offer 62. 圆圈中最后剩下的数字
STL提取出“全排列”『模板』
汉诺塔-递归模板
格雷码的由来
位运算-规律
- 1.交换
- 2.异或的性质

[toc]

# gcd求最大公约数『模板』

题目传送门：一行代码求两个数的最大公约数 (opens new window)
辗转相除法『迭代写法』

#include<bits/stdc++.h>

using namespace std;

int n, m;

//================================
// 我们希望a>=b
int gcd(int a, int b) {
    // 我们希望a>=b
    if (a < b) {
        swap(a, b);
    }

    while (a % b) {
        int temp = a % b;
        a = b; //大=小的
        b = temp; //小=余数
    }

    return b;
}
//================================

int main() {
    while (~scanf("%d%d", &n, &m)) {
        printf("%d\n", gcd(n, m));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# lcm最小公倍数『模板』

和『最大公约数』关系密切，得到最大公约数后，很简单

int lcm(int a, int b){
    int gcdNum=gcd(a,b);
    return a/gcdNum * b;	//注意，学习这种防止溢出的写法
}

1
2
3
4

# 数字-找规律题解⭐️

# 1.剑指 Offer 44. 数字序列中某一位的数字 (opens new window)

# 数字规律！

class Solution {
public:
    int findNthDigit(int n) {
        if( 0==n ) return 0;
        /*规律
            1-9（总共9-1+1=9）
            10-99（总共99-10+1=90）
            1000-999（总共999-1000+1=900）
            ...
        */
        int Left=1;             //目前，开始的数字位置
        long long count=9;            //至今数位个数
        long long cur_digit_length=1; //当前元素的数位

        int res=0;
        while( n > count )
        {
            n-=count;
            cur_digit_length++; 

            Left*=10; //更新
            count= 9 * Left * cur_digit_length;
        }

        long long num= Left+(n-1)/cur_digit_length;
        return to_string(num)[ (n-1)%cur_digit_length ] - '0';
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 大数算法『模板』

# 1.大数加法

牛客网，两个链表生成相加链表 (opens new window)

1、『逆向思维』去模拟

# 2.大数乘法⭐️

牛客网，大数乘法 (opens new window)（两个正数版本）『我的博客题解』
乘法的坑比加法多！✔️
LeetCode43. 字符串相乘 (opens new window)
- 对『写代码前，测试先行』的理解更深刻

1、注意，两个为0的时候，要特判『不然，会有一个样例过不了』
2、『逆向思维』去模拟
3、用数组的下标0,1,2去模拟，10^0,10^1啥的
4、一定要找到第1个不是0的数字，然后再组装回来
    
样例举例
Len1 Len2   Len		长度
0	 123    0		特判
123  0	    0		特判	
-------------------------    
2    3      6		Len1+Len2-1
2    5      10		Len1+Len2
10   10     100     Len1+Len2-1
20   50     1000	Len1+Len2
规律：我们的结果最大只需开
    Len1+Len2
    然后，自己想办法，获得啥时候-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    string multiply(string num1, string num2) {
        
        //代码健壮性
        if( 0==num1.size() || 0==num2.size() )
        {
            throw "error num1.size()||nums2.size()";
        }
        
        string res;
        //*0的特判
        if( 1==num1.size() && '0'==num1[0] )
        {
            return res+="0";
        }
        if( 1==num2.size() && '0'==num2[0] )
        {
            return res+="0";
        }

        reverse( num1.begin(), num1.end() );
        reverse( num2.begin(), num2.end() );
        //可能是Len1+Len2-1  Len1+Len2 两种
        //vector自动初始化为全0
        vector<int> temp( num1.size()+num2.size() );
        
        for( int one=0; one<num1.size(); ++one )
        {
            for(int two=0; two<num2.size(); ++two )
            {
                int val=(num1[one]-'0')*(num2[two]-'0');
                temp[ one+two ]+=val;
                
                //注意要处理进位！！
                int carry=temp[one+two]/10;
                temp[one+two]%=10;

                int curPos=one+two+1;
                while( carry )
                {
                    temp[ curPos ]+=carry;
                    carry=temp[ curPos ]/10;
                    temp[curPos]%=10;
                    ++curPos;
                }
            }
        }

        int pos=num1.size()+num2.size();
        while( pos-- )
        {
            if( temp[pos] )
            {
                break;
            }
        }
        
        //搞定，10*10=100，temp中显示的0010这样的状况
        while( pos>=0 )
        {
            res+=(temp[pos]+'0');
            --pos;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# 3.大数阶乘-N的阶乘 (opens new window)

方法1: string和int进行

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 计算阶乘
// 减少代码的技巧: 用字符串乘以整数 而不是 字符串*字符串
string factorial(string a, int x) {

    string res;
    // 进位
    int carry = 0;
    int sum;
    for (int i = a.size() - 1; i >= 0; i--) {
        sum = carry + (a[i] - '0') * x;

        int val = sum % 10;
        res += (val + '0');
        carry = sum / 10;
    }

    // 坑: ⭐️多的进位[逐个]插入
    // 因为数字x可能很大, 导致carry其实可能远大于10, 所以要慢慢进位
    while (0 != carry) {
        int val = carry % 10;
        res += (val + '0');
        carry /= 10;
    }

    // 记得翻转
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    while (cin >> n) {
        // 0的阶乘=1
        string res = "1";
        // 计算i>=1的阶乘
        for (int i = 1; i <= n; ++i) {
            res = factorial(res, i);
        }
        cout << res << endl;
    }

    return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

方法2:参考题解：牛客网, 借助2个string来, 只是代码量稍微少点 (opens new window)

用long数组存储阶乘结果，数组中的每个数存储阶乘的4位10进制数，不足的用0补充。

# 约瑟夫环-剑指 Offer 62. 圆圈中最后剩下的数字 (opens new window)

公式:参考原理 (opens new window)

从n个**(多的)中, 每次删除第m(少的)**个数字, 求出这个圆圈里剩下的最后一个数字

class Solution {
public:
    int lastRemaining(int n, int m) {
        //f(n,m)= (f'(n-1,m)+m)%n;
        if (1 == n) {
            return 0;
        }

        //初始化的位置 f(1,m)=0;
        int f = 0;
        for (int new_n = 2; new_n <= n; ++new_n) {
            f = (f + m) % new_n;
        }
        return f;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# STL提取出“全排列”『模板』

46. 全排列 (opens new window)不含重复数字的数组
47. 全排列 II (opens new window)可包含重复数字的序列

1.不含重复数字/可包含重复数字『均可』

next_permutation的源代码实现
iter_swap()函数可以直接用
下一个排列的算法模板：『Left（前边） Right（后边）』
- next_permutation()会取得[Left,Right)所标示之序列的下一个排列组合。
- 如果没有下一个排列组合，便返回false，否则返回true
- 『4步伐』
  - 1.首先，从『最尾端开始往前』寻找两个相邻元素，令靠近左边的第1元素为LeftOne，靠近左边的第二元素为LeftTwo，且满足LeftOne< LeftTwo
  - 2.找到这样一组相邻元素后，再从『最尾端开始往前』检验,找出第1个大于LeftOne（LeftOne<Temp）的元素，令为Temp
  - 3.iter_swap( LeftOne, Temp )
  - 4.再将LeftTwo及其之后的所有元素颠倒排列
上1个排列的算法『区别：见标记黄色背景的位置
- prev_permutation()会取得[Left,Right)所标示之序列的上一个排列组合。
- 如果没有上一个排列组合，便返回false，否则返回true
- 『4步伐』
  - 1.首先，从『最尾端开始往前』寻找两个相邻元素，令靠近左边的第1元素为LeftOne，靠近左边的第二元素为LeftTwo，且满足LeftOne> LeftTwo
  - 2.找到这样一组相邻元素后，再从『最尾端开始往前』检验,找出第1个小于LeftOne（LeftOne>Temp）的元素，令为Temp
  - 3.iter_swap( LeftOne, Temp )
  - 4.再将LeftTwo及其之后的所有元素颠倒排列

# 汉诺塔-递归模板

面试题 08.06. 汉诺塔问题 (opens new window)

//start里面的最上面n个元素，借助helo杆子，移到end杆子上
void recursive( vector<int> & start, int n, vector<int> &help, vector<int> & end)
{
    //1==n, 递归边界
    if( 1==n )
    {
        end.push_back( start.back() );
        start.pop_back();
        return ;
    }

    //2==n，虚拟的n=2的绑定递归

    recursive( start, n-1, end, help);

    end.push_back( start.back() );
    start.pop_back();

    recursive( help, n-1, start, end);
}
class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n=A.size();
        recursive( A, n, B, C);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 格雷码的由来

LeetCode89. 格雷编码 (opens new window)
由来 (opens new window)「数学」

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        int count=1<<n;
        for(int loop=0; loop<count; ++loop){
            res.push_back( loop^( loop>>1 ) );
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11

# 位运算-规律

# 1.交换

int a=1;
int b=2;
a=a^b;
b=a^b;
a=a^b;

1
2
3
4
5

记忆：观察知道，右边都是a^b

# 2.异或的性质

0^x=0

  如果：
      a^b=other;
  那么：
      (a^other==b);
  	(b^other==a);

1
2
3
4
5