hi | all for cpp

作者: 三金姐姐 | 来源:发表于2021-03-26 15:32 被阅读0次

算法口试也就是用自然语言描述算法，脑海中要有一个流程图。

【目录】
考点一：循环
考点二：递归
考点三：排序
考点四：查找
考点五：动态规划
考点六：数学
考点七：字符串
考点八：数据结构
考点九：统计学习

附录：面试技巧

BEST WISHES TO YOU 💗

考点一：『循环』

题目1：√

输入一个数n，找到其因子里能被完全平方的数，比如12，因子4开根号是2，可以完全平方，所以输出4。

【考点】
for循环
【思路】
用for循环来做，循环变量可以表示最后的结果。进行到某次循环时，如果该循环变量能整除输入的数，并且该循环变量的平方也能整除该数，那么该循环变量的平方就是要找的完全平方因子数。这样做能减少循环次数，降低时间复杂度。
【算法】
step1：输入一个整数n。
step2：由于sqrt这个开方函数它的返回值是一个double类型，因此我们将其强转为整型，然后再赋值给squreRoot这个整形变量。这样避免了在之后for循环中，每次都需要计算根号n的值。

int squreRoot=sqrt(n);

step3：设定一个循环变量i，并且把它设置为2。接下来要执行一个for循环结构。在执行这个循环结构之前，先判断这个循环变量的值i是否<=squreRoot。如果i<=squreRoot，则执行循环体中的内容，即判断n%i是否=0并且n%(i*i)是否=0，如果满足，则输出i*i,其就是完全平方因子数，并且退出程序。如果不满足，接下来改变这个循环变量的值，就是将其增1再回到循环的入口处去判断i是否<=squreRoot。如果i<=squreRoot，继续执行循环体中内容，这样循环了squreRoot-1次后，i的值为squreRoot+1，i不再<=squreRoot了，那么就退出这个循环的执行。
【复杂度分析】
时间复杂度：O(sqrt(n))，n为输出的变量值。

👉补充

【知识点】
1.因子
有一种说法是“因子不限正负”，不过通常情况下只取正因子。1, -1, n 和 -n 这些数叫做 n 的明显因子。

题目2：√

如果n和n+2都是素数，则称它们是孪生素数。输入m，输出两个数均不超过m的最大孪生素数。5≤m≤10000。

【考点】
素数的判断——试商法
【思路】
因为求得是最大孪生素数，找素数的时候从后往前找。写一个判断是否是素数的函数，该函数的返回值是int类型，如果是素数则返回1，不是则返回0。
【算法】
<设计判断是否是素数的Isprime()函数>

bool Isprime(int num)
{
    if (num <= 1) //the particular values 0,1 and negative
        return 0;
    int squreRoot = sqrt(num);
    for (int i = 2; i <= squreRoot; i++)
    {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

这个函数有一个参数，是要判断的数int num。函数返回值定义为int类型，当这个数是素数的时候返回1，不是素数的时候返回0。
step1：首先判断num是否<=1，因为负数和0、1都不是素数，所以当num<=1时，返回0。做这样一个判断还有一个好处，避免之后对一个负数进行开方运算。
step2：由于sqrt这个开方函数它的返回值是一个double类型，因此我们将其强转为整型，然后再赋值给squreRoot这个整形变量。这样避免了在之后for循环中，每次都需要计算根号num的值。
step3：设定一个循环变量i，并且把它设置为2。接下来要执行一个for循环结构。在执行这个循环结构之前，先判断这个循环变量的值是否<=squreRoot。如果i<=squreRoot，则执行循环体中的内容，即判断num%i，num对i求余数是否等于0，如果满足，函数返回0给主函数。若不满足，接下来改变这个循环变量的值，就是将其增1再回到循环的入口处去判断i是否<=squreRoot。如果i<=squreRoot，继续执行循环体中的内容。当这个循环结束时，还没有返回的话，说明num不能被2到根号num之间的所有数整除，因此说明x是素数，此时返回1给主函数。
<设计主函数>

int main()
{
    int m;
    cin >> m;
    for (int i = m - 2; i >= 3; i++)
    {
        if (Isprime(i) == 1 && Isprime(i + 2) == 1)
        {
            cout << i << ' ' << i + 2;
            break;
        }
    }
    return 0;
}

step1：输入一个整数m。
step2：设定一个循环变量i，并且把它设置为m-2。在执行这个循环结构之前，先判断这个循环变量的值是否>=3。（因为3和5是最小的孪生素数）如果满足，则执行循环体中的内容，即调用Isprime()函数判断i+2和i是否是素数。如果满足，则输出i+2和i，并跳出循环，结束主函数。若不满足，接下来改变这个循环变量的值，就是将其减1再回到循环的入口处去判断i是否>=3。如果i<=sqrt(n)，继续执行循环体中的内容，这样循环了m-1次后，i的值不再>=3了，那么就退出这个循环的执行。
【复杂度分析】
时间复杂度：O(m)，m为输出的变量值。

👉补充

【知识点】
1.判断是否是素数时，整数m的因数（如果有的话）只需考察到m的平方根即可。因为如果整数m有一个比它的平方根 $\sqrt{m}$ 还要大的因数的话，即 $m=k_1*k_2$ ，其中 $k_1\geq\sqrt{m}$ ,则其另一个因数 $k_2\leq\sqrt{m}$ 。

题目3：√

打印一个n阶方阵，数字是按顺时针顺序排列。

【考点】
嵌套循环、逗号表达式
【思路】
首先确立按圈打印的思想，先打印最外圈，再打印靠里的那一圈，依次类推。打印时将旋转遍历分解为四个动作：从左到右，从上到下，从右到左，从下到上。每打印一圈，都用对角两个元素标记，引导循环时候的方向走势，打印完一圈，然后再向内收缩打印一圈。
【算法】
step1：创建一个二维数组，定义表示行列的变量

 int n, num = 1;
    cin >> n;
    int a[100][100], i, j; //i,j are used to represent the row and column

step2：设min和max分别指向两个对角，使其向内收缩。最外层的for循环控制min和max。初始条件是min=0和max=n-1，终止条件是min<=max，每次循环完，min++，max--。for循环里是4个打印方式的循环。设立一个打印初值m，每执行一次打印m++，并把结果存储到二维数组a[100][100]中。

 for (int min = 0, max = n - 1; min <= max; min++, max--)
    {
        for (i = j = min; j <= max; j++)
        {
            a[i][j] = num;
            num++;
        }
        for (i = min + 1, j = max; i <= max; i++)
        {
            a[i][j] = num;
            num++;
        }
        for (i = max, j = max - 1; j >= min; j--)
        {
            a[i][j] = num;
            num++;
        }
        for (i = max - 1, j = min; i >= min + 1; i--)
        {
            a[i][j] = num;
            num++;
        }
    }

step3：打印出a[n][n]。

for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            printf("%-3d", a[i][j]);
        cout << endl;
    }

【复杂度分析】
时间复杂度：O(n)，n为要求打印的矩阵阶数。

👉补充

【拓展】
1.如果给出的矩阵不是方针则要要条件，详见面试题29。
2.逗号表达式

题目4：√

猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。

【考点】
循环、（反向）递推法
【思路】
采用逆向思维，用while循环做。
我们的已知条件是每天都吃掉前一天剩下的桃子再多一个。那么假设猴子每天少吃一个，则多剩一个。每天剩下的桃子数加一后，刚好是前一天的一半，把递推过程表达成一个数学表达式， $x_n=(x_{n+1}+1)*2,1≤n＜10$ ，第10天的桃子数可表达为 $x_n=1,n=10$ 。
【算法】

int main()
{
    int x = 1, d = 1;
    while (d < 10)
    {
        x = (x + 1) * 2;
        d++;
    }
    cout << x;
    return 0;
}

step1：首先在这个问题中要使用两个变量，一个变量d用于记录递推的次数，另外一个变量x用于保存递推的结果，也就是桃子的数量。
step2：由于这个问题一共要递推9次，所以d从1开始变化，直到d不小于10为止，所以while循环的控制条件是就是d<10。只要满足d<10，就执行递推过程。每次要更新x的值， $x=(x+1)*2，$ 并且将d的值加1。如果d的值不再小于10了，那么就输出最终的递推结果x。

题目5：√

将所输入的任意位整数，以相反顺序打印出来。

【考点】
整数的分解、while循环
【思路】
如果用四则运算的方法就是依次对10求余，取出最后一位数。然后再依次乘以10，使低位的数依次到高位。
如果用cpp，可以存于字符串中反向输出。
【算法】
step1：在这个循环中要使用两个变量，一个变量int res用于表示最后的结果，初始值是0。另一个变量int digit存放每次取下的最后那位数。
step2：输入n。
step3：while循环的控制条件是n大于0。当n大于0时，取下当前n的最后一位n%10，将其赋值给digit。令res=res*10+digit，这样每循环一次，前一次循环取下的数就升高一位。再令n=n/10。重新判断n是否大于0。当n等于0时，结束循环，输出res的值。

👉补充

【拓展】
上述算法如果输入700，最后结果是7。如果要使输出007，需要在每次循环里输出digit。
在C++中，亦可以用itos()函数将整型变量转化成字符型，再按相应顺序输出。

题目6：√

输出下三角九九乘法表。

【考点】
嵌套循环
【思路】
九九乘法表是按行和列排列的，它有m行，n列，这里m和n都是9。那么第m和n列要输出的值就是 $m*n$ 的值。
【算法】
step1：先令m=1，进入外层循环。
step2：输入行，令n=1，进入内层循环，再判断n的值是否小于等于m（控制下三角），如果是，输出 $m*n$ 的值。否则，表示内层循环循环完，进行第3步。
step3：输入列，输出换行符，再将m加1，判断m是否小于9。如是重复step2。

题目7：√

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

【考点】
循环
【算法】

int n;
    cin >>n;
    vector<int> a(n,1); //this is a group of people
    int k = 0, m = 0, i = 0;

step1：输入圈子人数n。定义一个长度为n的数组，并将该数组从1开始赋值到n，表示给其编号。
step2：定义三个整型变量。一个用来报数int k，初值为0；一个用来记录退出圈子的人数int m，初值为0；一个相当于指针控制数组移动的变量int i，初值是0。
step3：构建while循环开始报数。先判断退出人数m是否小于总人数n-1，如过是进入循环开始报数。

while (m < n - 1)//m=n-1 means that there is only one number in the array
    { 
        if (a[i] != 0)
            k++;
        if (k == 3)
        {
            k = 0;    //means the new round starts
            a[i] = 0; //number 0 means it has been out
            m++;
        }
        i++;
        if (i == n)
            i = 0;
    }

①首先，判断i位置的数是否为0，如果不是，k++，表示报数。
②然后，判断k是否为3，如果是将k令为0，表示要开始新一轮的报数。并且将num[i]令为0，表示退出，再将m++，表示退出人数加1。
③经过上面两步后，i++，表示向数组的下一位移动。
④最后，判断i是否等于n，如果是，表示到了队尾，需要将指针重新指向对头，令i等于0。
这就是while循环的整个流程。如果此时m小于n-1，再进入循环。如果m=n-1，退出循环。
step4：找到数组中不为0的数，输出，即为留下来的人的编号。

题目8：√

n个人围成一桌，从第一个人开始数第w个人离开，又从下一个人开始数第w个人离开，问最后谁留下了。

【考点】
循环
【算法】
step1：输入w。输入圈子人数n。定义一个长度为n的数组，并将该数组从1开始赋值到n，表示给其编号。
step2：定义三个整型变量，一个用来报数int k，初值为0，一个用来记录退出圈子的人数int m，初值为0，一个相当于指针控制数组移动的变量int i，初值是0。
step3：构建while循环开始报数。先判断退出人数m是否小于n-1，如过是进入循环开始报数。
①首先，判断i位置的数是否为0，如果不是，k++，表示报数。
②然后，判断k是否为w，如果是将k令为0，表示要开始新一轮的报数。并且将num[i]令为0，表示退出，再将m++，表示退出人数加1。
④经过上面两步后，i++，表示向数组的下一位移动。
⑤最后，判断i是否等于n，如果是，表示到了队尾，需要将指针重新指向对头，令i等于0。
这就是while循环的整个流程。如果此时m小于n-1，再进入循环。如果m=n-1，退出循环。
step4：找到数组中不为0的数，输出，即为留下来的人的编号。

题目9：√

题目：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？

【考点】
计算、循环
【算法】

#include<stdio.h>
int main() {
    int i;
    float s=100,l=s;
    s=s/2//第1次的反弹高度
    for(i=2;i<=10;i++){//从第2次落地开始计算，因为初始高度不用乘2
        l=l+s*2;
        s=s/2;
    }
    printf("共经过%f米\n",l);
    printf("第10次反弹%f米",s);
    return 0;
}
【运行结果】

共经过299.609375米

考点二：『递归』

通常下面三种情况需要使用递归：
1.数学定义是递归的
如计算阶乘、最大公约数和Fibonacci数列
2.数据结构是递归的
如队列、链表、数和图
3.问题的解法第递归的
如Hanoi塔，骑士游历，八皇后问题

题目1：√

用递归求5！

【考点】
递归
【思路】
编写一个递归函数。这个递归公式是:
$n=0,1时，n!=1。当n≥2时，n!=n*(n-1)!。$
【算法】
<设计返回n!的函数long Fact(int n)>

long Fact(int n){
    if(n==0||n==1)
        return 1;
    return(n*Fact(n-1));
}

这个函数的形参是需要求阶乘的数int n，返回一个long型变量。
step1：首先判断n是否小于0。如果小于0，则返回就返回一个错误的状态信息-1。否则的话，如果n等于0或1（这是基本条件，控制着递归调用结束），则返回1（递归公式的初值）。再否则的话，即n大于等于2，那么计算n的阶乘就利用n-1的阶乘来计算n的阶乘，就是在Fact函数计算n的阶乘的过程中，再去调用Fact函数自己来计算n-1 的阶乘，然后将n-1的阶乘的结果乘以n作为Fact函数计算n的阶乘的返回值。（这是一般条件，控制递归向基本条件转化）
当然，我们可以把这个函数改为无符号整型unsigned long，则可以不用考虑小于0 的情况了。
【复杂度分析】
时间复杂度：O(sqrt(n))，n为输出的变量值。

👉补充

【其它解】
如果不用递归来解，就在主函数中用for循环。

题目2：√

用递归的方法求Fibonacci数列(1，1，2，3，5，8，···）的第n个数。

【考点】
（正向）递推
【思路】
我们把发现的规律用公式表达出来就是：
$f_1=1,n=1$
$f_2=1,n=2$
$f_n=f_{n-1}+f_{n-2},n≥3$
在主函数中输入n，将其作为实参带入返回第n个Fibonacci数列的值的函数中。
【算法】
<设计一个返回Fibonacci数列第n个数的函数int Fib(int n)>
这个函数的形参是要求的位数int n，返回值是int类型，即第n个数。
step1：如果n=1或者n=2，则返回1。这里n=1或者n=2是基本条件，控制着递归调用的结束。
step2：如果n>2，调用Fib函数自己来计算n-2和n-1位置上的值，返回Fib(n-1)+Fib(n-2)。

👉补充

【知识点】
1.一般认为斐波那契数列的提出是基于理想化的兔子的繁殖问题：如果一开始有一对兔子，它们每月生育一对兔子，小兔在出生后一个月又开始生育且繁殖情况与最初的那对兔子一样，那么一年后有多少对兔子？
答案是，每月兔子的总数可以用以下数列表示：1，1，2，3，5，8，13，21，34，55，89，144，233…。
这一数列是意大利数论家列奥纳多·斐波那契（Leonardo Fibonacci）在他13世纪初的著作Liber Abaci中最早提出的。如果取数列前两个元素为1，那么递推关系就是： $F_n=F_{n-1}+F_{n-2}$ 。
关键是要找到一个数前面的两个数，从第3个数开始，这个数就是前面两个数之和。

题目3：💗

一块板上有三根针，A,B,C。A针上套有64个大小不等的圆盘，大的在下，小的在上。要把这n个圆盘从A移到C针上，每次只能移动一个圆盘，移动可以借助B针。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。

【考点】
递归
【思路】
先考虑简单的情形，当n=2时，则分两三步走：
先将A上面的1个（n-1）取下放到B针，再将A下面的1个放到C针，最后将B针上的取下放到C针。
用数学归纳法求解这个问题，假设n-1个圆盘的汉诺塔问题已解决，将上面n-1个圆盘看成一个整体，这样n个圆盘就可以分成两部分，一部分是上面n-1个圆盘，一部分是最下面的圆盘。那么移动n个圆盘就可以转化成移动n-1个圆盘。
这个问题的基本问题是n=1的情形，直接由A移到C。
【算法】
<设计Hanoi函数>
这个函数有4个参数，分别是盘子的个数int n，以及三个柱子，char a,char c,char b。函数不需要返回值，所以函数的返回值类型定义为void。表示将n个盘子，借b从a移到c。
step1：首先考虑基本情况，也就是n=1的时候，此时直接由a移c，调用Move(n,a,c)。
step2：否则，当n大于等于2时.
①第一步，将上面n-1个圆盘作为一个整体由a移动到b上，此时调用这个函数自身来完成这n-1个圆盘的移动，表示为Hanoi(n-1,a,b,c)。
②再调用Move函数由将第n个圆盘由a移到c。
③最后一步将这n-1个圆盘在看成一个整体，由b移到c上，也是调用Hanoi(n-1,c,b,a)。
<设计Move函数>
这个函数将第n个圆盘由a移到b，只需要输出一个提示信息就够了。
<设计主函数>
在主函数里，首先让用户输入n的值，然后调用Hanoi这个函数，实现将n个圆盘借助C，由A移到B上。

题目5：√

有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？

【考点】
递归
【思路】
编写递归函数int age(int n)，返回第n个人的岁数。
【算法】
<设计返回第n个人岁数的函数int age(int n)>
这个函数的形参是第几个人int n，返回一个int型变量，即这个人的岁数。
step1：如果n=1，这是基本条件，控制着递归调用结束，返回10。
step2：否则，当n大于等于2时，这是一般条件，控制递归向基本条件转化，调用age函数自己来计算第n-1个人的岁数，然后将结果加上2作为age函数计算第n个人岁数的返回值。

题目4：√

题目：利用递归函数调用方式，将所输入的5个字符，以相反顺序打印出来。

【考点】
递归
【算法】
<设计打印一个数组s第l号元素的函数 $\text{<void print(char *s,int l)>}$
这个函数由两个形参，一个是字符数组 $\text{char *s}$ ，一个是表示位置的int l。
step1：打印第l个元素，printf("%c",s[l-1])。
step2：用if条件句判断l是否大于1。如果l大于1，调用print自身打印第l-1个元素，print(s,l-1)。
<主函数>
step1：在主函数中输入一个字符串，char ch[20]。定义一个新变量int n，存放该数组的长度。
step2：调用print()函数，print(ch,n)。即可逆序打印。

#include <stdio.h>

void prin(char *s,int l) {
    printf("%c",s[l-1]);
    if(l>1){
       prin(s,l-1);
    }
}

int main()
{
    char ch[]="abc";
    prin(ch,3);
    return 0;
}

考点三：『排序』

1 插入排序：
1.1 直接插入排序 O(n^2) O(1) 稳定
1.2 希尔排序O(nlogn)不稳定

2 交换排序
2.1 冒泡排序O(n^2) O(1) 稳定
2.2 快速排序O(nlogn) O(logn) 不稳定

3 选择排序
3.1 简单选择排序O(n^2) O(1) 稳定
3.2 堆排序O(nlogn) O(1) 不稳定

1 【插入排序】√

1.1 直接插入排序

【思路】
将序列分为有序部分与无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应的位置上。
【算法】
如N个数升序排列:
使0到 $i(i=1,2...N-1)$ 位置有序，排到 $i$ 位置时，前面0到 $i-1$ 位置已经有序。
step1：从 $i$ 位置往前看，前面大就继续向前。
step2：到0位置或前面小停止。
这里的时间复杂度与数据的具体状况有关，这是与前两者排序的区别。

伪代码如下：

insertionsort(data[],n)
  for i=1 到 n-1
    将大于data[i]的所有元素data[j]都向右移动一个位置，将data[i]放在合适的位置上

【复杂度】
时间复杂度： $O(N^{2})$ （算法流程按照最差情况来估计时间复杂度）
额外空间复杂度： $O(1)$ ，需要建立一个数组

1.2 希尔排序

【思路】
步长n、n/2、、、1,分组做直接插入排序。

2 【交换排序】√

2.1 冒泡排序

【思路】
每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。
【算法】
如N个数升序排列:
①从前往后冒泡
round1
step1：0到1位置哪个大，谁跑后面去。
step2：1到2位置哪个大，谁跑后面去。
···
stepN-1：N-2到N-1位置哪个大，谁跑后面去。
round2
step1：0到1位置哪个大，谁跑后面去。
step2：1到2位置哪个大，谁跑后面去。
···
stepN-2：N-3到N-2位置哪个大，谁跑后面去。
······
roundN-1
step1：0到1位置哪个大，谁跑后面去。

伪代码如下：

bubblesort(data[],n)
  for i=0 到 n-2
    for j=0 往上到 n-2-i
      如果两者逆序，则交换位置j和位置j-1的元素

②从后往前冒泡
round1
step1：N-1到N-2位置哪个小，谁跑前面去。
step2：N-2到N-3位置哪个小，谁跑前面去。
···
stepN-1：1到0位置哪个小，谁跑前前去。
round2
step1：N-2到N-3位置哪个小，谁跑前面去。
step2：N-3到N-4位置哪个小，谁跑前面去。
···
stepN-2：1到0位置哪个小，谁跑前面去。
······
roundN-1
step1：1到0位置哪个小，谁跑前面去。

伪代码如下：

bubblesort(data[],n)
  for i=0 到 n-2
    for j=n-1 往下到 j+1
      如果两者逆序，则交换位置j和位置j-1的元素

【复杂度】
时间复杂度： $O(N^{2})$
额外空间复杂度： $O(1)$
【优缺点】
优点：每一趟不仅找到一个最大的元素放到序列后面，而且还把其它元素理顺。如果下一趟排序没有发生交换则可以提前结束排序。
缺点：元素需要一步步地向上冒泡知道数组的顶部，这是非常费时的。

2.2 快速排序（目前已知最高效的算法）

【考点】
分治法
【思路】
在序列中任意选择一个元素为中心/边界（为了程序方便，一般选择第一个元素，如果不是第一个元素，也可以与第一个元素做交换），把比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列。再把子序列按照上述操作进行调整，直到所有的子序列中都只有一个元素时序列有序。
【算法】
step1：设置两个变量i和j，排序开始前将i和j分别初始化为1和n，这里i和j分别相当于序列的左指针和右指针。
step2：随意选取序列中的一个数作为基准，赋值给s，这里基准相当于序列分割的一个参照物。
step3：从j开始从后向前搜索，每向前搜索一步，就将j的值减去1，直到搜索到第一个小于s的数为止，将这个数和基准互换位置。
step4：从i开始从前向后搜索，每向后搜索一步，就将i的值加上1，直到搜索到第1个大于s的数为止，将这个数和基准互换位置。
step5：重复第3、4步，直到i与j相等为止。
【优缺点】
优点：每一趟能确定至少一个元素的位置，时间效率较高。

3 【选择排序】√

3.1 简单选择排序

【思路】
选择排序就是先找到位置不合适的元素，再把它放在其最终的合适位置上，很明确地直接交换数组元素。
把序列分成两部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。
【算法】
如N个数升序排列:
step1：0到N-1位置找最小值（注意是找到最小的再交换，不是找到了小的就交换）和第0位置交换。
step2：1到N-1位置找最小值，和第1位置交换。
···
stepN-1：N-2到N-1位置找最小值，和第N-2位置交换。

伪代码如下：

selectionsort(data[],n)
  for i=0 到 n-2//n-2s是最后一个i值，因为如果除最后一个元素之外的所有元素都放在合适的位置上，那么第n个元素（位于n-1位置上）就一定是最大的
    找出元素data[i],…,data[n-1]中的最小元素;
    将其与data[i]交换;

【复杂度】
时间复杂度： $O(N^{2})$
额外空间复杂度： $O(1)$
【优缺点】
优点：赋值次数少。这是其它算法无法比拟的。实现起来特别简单。
缺点：每一趟只能确定一个元素的位置，时间效率低。

3.2 堆排序

【思路】
设有任意一个序列，k1到kn。当满足下面特点是称之为堆：让此序列排列为完全二叉树，该数具有以下特点，该树中任意结点均大于或小于其左右孩子，此树的根结点为最大值或最小值。
堆的现实结构是一个数组，利用下标的映射关系将其想象成一个完全二叉树的结构。
【算法】
以大根堆来做
<设计将某个值插入堆的函数void heapinsert(int n)>
step1：设定一个表示下标的变量index。
<设计取下堆的最大值并删掉的函数int popmax()>
step1：将堆顶元素与尾部元素交换。
step2：有效区减一。
<设计主函数>
step1：设定一个表示有效区长度的变量size，初始值为0。输入一个数组。
step2：调用heapinsert，使数组变成一个大根堆。
step3：调用popmax函数，取出堆顶元素存放在数组中。
【优缺点】
优点：对大文件效率明显提高，对小文件效率不明显。

考点四：『查找』

【二分查找】

【算法】
<设计二分查找函数BinSearch>
这个函数有3个形参，分别是long num[]，long x，int n，表示在具有n个元素的num数组中去查找x，如果找到就返回x在这个数组中的下标位置，否则返回-1，表示没有找到。
step1：因为查找是在整个数组中查找，所以low初值是0，high的初值是n-1。
step2：构建while循环。当low<=high时，表示要查找的数组区间是存在的，是可以继续查找的，将其作为while语句的循环条件。在while循环中，首先计算区间的终点值mid，就是将low和high的值相加后除以2，得到中间位置元素的下标。（这里如果数组很大，low和high之和大于有符号整数的极限值就会发生数值溢出，使mid变为一个负数。为了防止溢出，可以修改中间值的计算方法，用减法代替加法，mid=low+(high-low)/2）然后再判断x是否大于num[mid]。比较的结果分为三种情况。第一种是x大于num[mid]时，将low设置为mid+1。第二种是x小于num[mid]时，将high设置为mid-1。再否则，就是x=num[mid]则返回mid的值。如果x不等于num[mid]，则继续循环，每次继续循环前都要判断low的值是否小于等于high。一旦发现low小于等于high为假了，就说明待查找的区间不存在了，或者这个数组中间找不到x。这个时候返回-1。表示找不到。
【时间复杂度】
二分查找的时间复杂度是对数阶：O(logn)

应用1：

有一个已经排好序（升序）的数组。现输入一个数，要求按原来的规律将它插入数组中。

【思路】
因为这是一个有序数组，可以用比线性查找更快的算法——二分查找。
找到两个相邻的位置，前一个位置不超过输入的数，后一位置不小于输入的数，将输入的数插到两者之间。
在一个有序数组中，查找>=某个数最左侧的位置。这是二分法查找的应用。

【哈希查找】

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

【思路】
注意本题是有序数组，用双指针法可以将空间复杂度降为最低。
【算法】
<设计一个查找函数vector<int> twoSum(vector<int>& nums, int target)>

vector<int> twoSum(vector<int> &nums, int target)
{
    int i = 0, j = nums.size() - 1; //define two variables, stands for the start and end
    vector<int> res(2);
    while (i < j)
    {
        int s = nums[i] + nums[j];
        if (s < target)
            i++; //means plus
        else if (s > target)
            j--; //means minus
        else
        {
            res[0] = nums[i];
            res[1] = nums[j];
        }
    }
    return res;
}

这个函数的范围值是一个向量，形参是两个参数，一个一维向量vector<int>& nums，另一个是目标值int target。
step1：定义两个整形变量int i、j，一个指向数组的开头，一个指向数组的结尾。再定义一个一维向量，其长度为2，用于返回结果。
step3：构造一个while循环。当i<j时，表示要找的两个数是存在的，是可以继续查找的，将其作为while语句的循环条件。在while循环中，定义一个新变量int s，其值为nums[i]+nums[j]。判断s是否小于tagert。如果是，将i加一（为什么不将j减一）。否则，将j减一。再否则，将nums[i]，nums[j]存放到字符串中。并退出循环，并返回。直到，i=j，退出循环，表示没有找到这样的两个数，其和等于target，返回空字符串。

考点五：『动态规划』

题目1：💗

求出一个数组中的连续子数组的和，而该数组拥有最大的和，例如给的数组[-2,1,-3,4,-1,2,1,-5,4]连续数组[4,-1,2,1]的和为6。

【考点】
动态规划
【思路】
一般思路是用暴力法求解。就是将给定的所有子数组列出来，然后找到子数组和最大的情况。具体来说就是：对数组内每一个数arr[i]进行遍历，然后遍历以它们为起点的子数组，比较各子数组的大小，找打最大连续子数组。这种思路时间复杂度太高，不应使用。
用动态规划的方法来做。
状态表示：用dp[i]来抽象这个问题，dp[i]表示的是从0位置到第i位置拥有的最大连续子数组和，arr[i]表示数组中i位置的元素。
状态方程：max(dp[i])=getMax(max(dp[i-1])+arr[i],arr[i])。即从头开始遍历数组，遍历到数组元素arr[i]时，连续的最大的和可能为max(dp[i-1])+arr[i]，也可能为arr[i]，取后者是当dp[i-1]为负数的时候。
【算法】
step1：如果数组为空则返回0。

    if (arr == NULL || sz < 0)

step2：新建两个整型变量sum和max，初值都是arr[0]，一个表示临时最大值，一个表示比较后的最大值，即最终结果。

  int Sum = arr[0];//the temporary maximum
  int Max = arr[0];//the maximum after a comparison

step3：从1号位置开始遍历数组。令sum=max(sum+arr[i],arr[i])，每次求完临时最大值时比较sum和max，如果sum大于max，则将sum赋值给max。

  for (int i = 1; i < sz; i++)
    {
        Sum = max(Sum + arr[i], arr[i]);
        if (Sum >= Max)
            Max = Sum;
    }
    return Max;
}

【复杂度分析】
时间复杂度：O(n)，n为数组长度。

题目2：

题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意：你不能同时参与多笔交易（你不能在再次购买前出售掉之前买入的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

【分析】
用动态规划做这道题。这题的实质就是找长度为n的数组下最大差值是多少。
【源代码】
01方法一^[1]

#include <iostream>
#include<algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(int prices[], int length) {
        //数组长度为1时的最小值和最大差值
        int MIN = prices[0];
        int D_MAX = 0;
        //数组长度为i+1时的最小值和最大差值
        for (int i = 1; i < length; i++) {
            D_MAX = max(prices[i] - MIN, D_MAX);//如果prices[i]比 MIN还小，那么它绝不可能超过i-1数组下的 D_MAX
            MIN = min(prices[i], MIN);
        }
        return D_MAX;
    }
};

int main()
{
    int a[] = { 0,0,1,2,1,0,0,0 };
    Solution b;
    cout<<"最大收益等于"<<b.maxProfit(a, 8)<<endl;
    return 0;
}

【运行结果】

最大收益等于2

02方法二

#include <iostream>
#include<algorithm>
using namespace std;

int maxProfit(int prices[], int length) {
        //数组长度为1时的最小值和最大差值
        int MIN = prices[0];
        int D_MAX = 0;
        //数组长度为i+1时的最小值和最大差值
        for (int i = 1; i < length; i++) {
            D_MAX = max(prices[i] - MIN, D_MAX);//如果prices[i]比 MIN还小，那么它绝不可能超过i-1数组下的 D_MAX
            MIN = min(prices[i], MIN);//更新最小值，如果卖出点在这个时间之后，D_MAX更新，否则不更新
        }
        return D_MAX;
    }

int main()
{
    int a[] = { 7,1,5,3,6,4 };
    int n= sizeof(a)/sizeof(a[0]);
    cout<<"最大收益等于"<<maxProfit(a, n)<<endl;
    return 0;
}

【运行结果】

最大收益等于5

举一反三

题目：如果允许多次买进卖出，求最大利润。

【源程序】

#include <iostream>
#include<algorithm>
using namespace std;

int maxProfit(int prices[], int length) {
    int max_profit = 0, profit;
    if (length < 2)
        return 0;
    for (int i = 1; i < length; i++) {
        profit = prices[i] - prices[i-1];//比较相邻两项即可，如果后面大则即为利润
        if (profit > 0) {
            max_profit = max_profit + profit;
        }
    }
    return max_profit;
}

    int main()
{
    int a[] = { 7,6,11,10,12};
    int n= sizeof(a)/sizeof(a[0]);
    cout<<"最大收益等于"<<maxProfit(a, n)<<endl;
    return 0;
}

【运行结果】

最大收益等于5

考点六：『数学』

题目1：√

将所输入5位整数，以相反顺序打印出来。

【考点】
整数的分解
【算法】
step1：输入5位数n。
step2：依次分离出个位、十位、百位、千位和万位，分别用a,b,c,d,e表示。其中，e=n/10,d=n/10%10,c=n/100%10,b=m/1000%10,a=n%10。
step3：用式子 $\text{(((a*10+b)*10+c)*10+d)*10+e}$ 构造新的五位整数。
step4：输出新数。

题目2：√

将十进制转化为2进制。@2019复旦复试

【考点】
进制转换
【思路】
在主函数中输入要转换的十进制数，再构造一个将十进制转换为二进制的函数。
【算法】

int DecToBin(int n)
{
    int res, num = 0;
    while (n != 0)
    {
        res = n % 2;
        num = num * 10 + res;//to raise its level
        n = n / 2;
    }
    return num;
}

step1：在主函数中输入一个数n。
step2：构造一个函数int DecToBin(int n)，在主函数中调用它。
step3：函数中主体是一个while循环。循环的条件是这个数为0。这个数依次除以2，得到一系列余数，将最后的余数排在前，最先的余数排在后则得到了十进制数的二进制表示。在编程中实现这个功能需要在每次除2取余的地方再加一个变量j，每次循环j=j*10。

题目3：√

将2进制转化为10进制。

情形一：8位2进制以字符串形式输入
【考点】
进制转换
【算法】
<设计将10进制转化为2进制的函数BinTDec()>

int BinToDec(int n)
{
    int res, num = 0, j = 0; //j stands for the pow
    while (n != 0)
    {
        res = n % 10;
        if (res == 1)
            num = num + pow(2, j);
        j++;
        n = n / 10;
    }
    return num;
}

这个函数有一个函数，形参是是要转化的数2进制数char $*$ str。函数值返回值定义为int类型，为转化后的10进制数。
step1：设定一个放十进制的变量n，设置其初始值为0。
step2：设定以个循环变量i，并且将它设置为0，在执行这个循环之前，先判断这个循环变量的值是否<8，如是，进入循环。判断str[i]是否为'1'，如是，则n=n2+1，即将原有的数2成为高位，当前的位作为个位1。否则n=n*2，将原油为作为高位。接下来改变循环变量的值，就是将其加1后再去判断是否<8。当i=8时，退出循环，返回n。

题目4：❤️

输入两个正整数m和n，求其最大公约数和最小公倍数。

【考点】
辗转相除法
【思路】
目的：求两个整数的最大公约数
最大公约数：能同时被两个整数整除的最大公约数。为什么用这个算法能得到两个数的最大公因数？
利用辗转相除法求最大公因数的步骤如下：
第一步：用较大的数 $a÷b$ 得到一个商 $q_0$ 和一个余数 $r_0$ ；
第二步：若 $r_0＝0$ ，则 $b$ 为 $a,b$ 的最大公因数；若 $r_0≠0$ ，则用除数 $b÷r_0$ 得到一个商 $q_1$ 和一个余数 $r_1$ ；
第三步：若 $r_1＝0$ ，则 $r_0$ 为 $a,b$ 的最大公因数；若 $r_1≠0$ ，则用除数 $r_0÷r_1$ 得到一个商 $q_2$ 和一个余数 $r_2$ ；
……
依次计算直至 $r_n=0$ ，此时所得到的 $r_{n-1}$ 即为所求的最大公因数。
根据结论，两个数的最小公倍数=两数之积/最小公约数。
【算法】

//递归算法
int gcd(int a,int b){
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}

//辗转相除法，直到b为0为止
int gcd(int a,int b){
    int temp;
    while(b)
    {
        temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

step1：设立一个变量表示余数int r，以及一个用于交换的临时变量int temp。
step2：输入两个整数int a、b。
step3：判断a是否大于b。如果a小于b，则交换a和b，否则不变。
step4：构造一个do-while循环。进入循环，令r=a%b。然后将a=b，b=r。之后判断r是否为0。如果r不为0，继续循环，如果r为0，退出循环，输出此时a的值。
//另一种做法step4'：构造一个while循环。控制条件为b!=0。当满足时，进入循环，令r=a%b。然后将a=b，b=r。之后判断b是否为0。如果b不为0，继续循环，如果b为0，退出循环，输出此时a的值。

题目5：√

将一个正整数分解质因数。例如：输入90,打印出 $90=2*3*3*5$ 。

【考点】
循环、质因子
【思路】
当输入1返回不可分解。
输入其它值，采用循环的方式依次输出质因子。
【算法】
对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
step1：如果这个质数恰等于（小于的时候，继续执行循环）n，则说明分解质因数的过程已经结束，打印出即可。
step2：但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数n.重复执行第二步。
step3：如果n不能被k整除，则用k+1作为k的值,重复执行第一步。

题目6：√

打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。

【考点】
提取各个位上的数
【思路】
用一个for循环表示所有三位数字，对于某一个三位数，把其各位数提取出来，如果其各位数字立方和等于该数本身，则输出。
【算法】
step1：构造一个for循环。设立循环变量i的初始值为100。进入循环前先判断i是否小于1000，因题目要求是三位数，如果满足条件，则进入循环。
①提取这个数的百位数放在变量a中，a=i/100。
②提取这个数的十位数放在变量b中，b=i%100/10。
③提取这个数的个位数放在变量c中，c=i%10。
④判断i是否等于a、b、c的立方和，如果是，输出i。
再将循环变量i自增1，回到循环入口再判断i是否小于1000。当不满足此条件，则退出循环。

考点七：『字符串』

题目1：💗√

计算字符串中子串出现的次数。

【考点】
逗号运算符
【算法】
step1：定义一个计数变量int count，初值是0。
step2：输入母串T，输入子串P。

    string T, P; //T is the father while P is the son
    cin >> T >> P;

step3：将母串的长度放在int Tlen变量中，将子串的长度放在int Plen变量中。以免每次循环都要重新计算数组长度。

    int Tlen = T.size(), Plen = P.size(), i, j, k;

step4：接下来要执行一个for循环结构。设定一个循环变量i，并且把它设置为0。在执行这个循环结构之前，先判断i是否小于Tlen-Plen，如果小于，进入循环。

 for (i = 0; i < Tlen - Plen; i++)
    {
        k = i;
        for (j = 0; j < Plen; j++)
            if (P[j] != T[k])
                break;
            else
                k++;
        if (j == Plen)
            count++;
    }

①首先，再执行一个for循环。设定两个循环变量，一个为j，初值为0，另一个为k，初值为i。判断j是否小于Plen并且P[j]是否等于T[k]。如果满足进入循环，这里循环体内为空语句，所以直接改变两个循环变量的值，就是将其增1再回到循环的入口处去判断j是否小于Plen并且P[j]是否等于T[k]。如果是，继续执行循环体中内容。直到不满足位置，那么就退出这个循环的执行。
②然后，判断j是否等于Plen，如果等于，表示在T中找到了一个子串P，count++。
③再改变循环变量j的值，将其增1再回到循环的入口去判断i是否小于Tlen-Plen。如果是，继续执行循环体中内容。直到不满足位置，那么就退出这个循环的执行。
step5：输出count的值。

补充

【知识点】
1.逗号运算符
for(表达式1,表达式2,···,;)

多数情况下，并不使用整个逗号表达式的值
更常见的是分别得到各表达式的值——顺序求值运算符

题目2：❤️

模式匹配，两个字符串最长匹配字符串。@2019复旦复试

【考点】
二维数组
【思路】
把两个字符串分别以行和列组成一个二维矩阵。比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。通过查找出值为1的最长对角线就能找到最长公共子串。
为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。^[2]
【算法】
<设计返回最长子串的函数string getLCS(string str1, string str2)>
这个函数返回一个字符串string，有两个形参，分别是两个字符串string str1，string str2。
step1：定义一个元素为int类型的二维向量vector<vector<int>> record(str1.length(), vector<int>(str2.length()))。这是一个str1的长度行数，str2的长度为列数的二维向量。在c++中，向量vector是一种对象实体，可以广义上认为是数组的增强版，它能够根据需要随时自动调整自身的大小以便容下所要放下的元素。
step2：定义两个变量。一个是int maxLen，用来记录最长的公共子串的长度，一个是int maxEnd，用来记录最长公共子串最后一个元素在str1的下标。
step3：构建一个for循环。设置循环变量为i，初始值为0，进入循环前，判断i的值是否小于字符串str1的长度，如果小于进入循环，即进入一个嵌套循环。设置循环变量为j，初值值为0，进入循环前，判断j的值是否小于字符串str2的长度，如果小于进入循环。
①判断str1[i]是否等于str[j]。如果等于，再判断i、j是否为0，如果是0，令record[i][j]=1，表示匹配字符串的第一个元素。否则令record[i][j]=record[i-1][j-1]+1，表示匹配字符串的第record[i-1][j-1]+1元素。果str1[i]不等于str[j]，令record[i][j]=0。
②判断record[i][j]是否大于maxLen，如果大于，令maxLen等于record[i][j]，并将此时的i记录下来，令maxEnd等于i。
之后将j自增，直到j等字符串str2的长度，退出内层循环。再将i自增，直到i等于字符串str1的长度，退出外层循环。
step3：返回最长字符串，即从str1的maxEnd-maxLen+1的位置截取向后maxLen长度的子串。
<设计主函数>
主函数就是输入两个字符串。

string getLCS(string str1, string str2)
{
    vector<vector<int> > record(str1.length(), vector<int>(str2.length()));
    int maxLen = 0, maxEnd = 0;
    for (int i = 0; i < str1.length(); i++)
        for (int j = 0; j < str2.length(); j++)
        {
            if (str1[i] == str2[j])
            {
                if (i == 0 || j == 0)
                {
                    record[i][j] = 1; //just a new matching
                }
                else
                {
                    record[i][j] = record[i - 1][j - 1] + 1; //the diagonal element
                }
            }
            else
            {
                record[i][j] = 0;
            }
            if (record[i][j] > maxLen)
            {
                maxLen = record[i][j]; //update the maxLen
                maxEnd = i;            //record this i is to subtract the matching string
            }
        }
    return str1.substr(maxEnd - maxLen + 1, maxLen);
}

题目3：√

有 n个整数，使其前面各数顺序向后移 m 个位置，最后m个数变成最前面的 m 个数。

【考点】
滚动
【思路】
编写一个函数void change_back(int *a,int n,int m)，表示在长度为n的数组a中，完成题述任务。
【算法】

void change_back(int *a,int n,int m){
    int temp;
    for(int i=0;i<m;i++){
        temp=a[n-1];
        for(int j=n-1;j>0;j--)
            a[j]=a[j-1];
        a[0]=temp;
    }
}

外层循环是遍历数组前m个元素，循环主体是，先把最后一个数保存，再将第一个位置到倒数第二个位置的元素整体向后移动一位，再将保存的最后一个元素放到第1个位置。

题目4：√

输入行数按规律打印出下图三角形
1
2 3 4
5 6 7 8 9
1 2 3 4 5 6 7
8 9 1 2 3 4 5 6 7
8 9 1 2 3 4 5 6 7 8 9

【考点】
找规律、for循环
【思路】
这个图形是由4组1-9组成的。设行数为m，m=6。第m行一共有2m-1个数字，每行的第一个数字前有m-i个空格，i为所在行数。
【算法】
step1：设立一个变量int p，存放打印的数，初值为1。设立表示行数的变量int m，输入行数m。
step2：构造一个for循环。设立循环变量i，初值为1。进入循环前先判断i是否小于等于m，如果i小于等于m，则进入循环。
①再构造一个for循环，用于打印每行前的空格。设立循环变量为j，初值为1。进入循环前先判断j是否小于等于m-i。如是，则进入循环，即打印空格。之后，j自增，回到循环入口再判断j是否小于m-i。依次进行，当j大于m-i时，退出循环。
②再构造一个for循环，用于打印每行的数。设立循环变量为k，初值为1。进入循环前先判断i是否小于等于2i-1，如果满足，则进入循环。打印k的值。之后将k自增1。再判断k是否是10，如果是10，将k重新赋值为1。之后，k自增，回到循环入口再判断j是否小于等于2i-1。依次进行，当k大于2i-1时，退出循环。
③输入换行符
之后将i自增1，回到循环入口再判断i是否小于等于m。当i大于m时，退出循环。

#include <stdio.h>
int main() {
    int p=1,m=6;
    for(int i=1;i<=m;i++) {
        for (int j = 1; j <= m - i; j++) {
            printf(" ");
        }
        for (int k = 1; k <= 2 * i - 1; k++) {
            printf("%d", p);
            p++;
            if (p==10) {
                p=1;
            }
        }
        printf("\n");
    }
    return 0;
}

运行结果

考点八：『数据结构』

题目1：√

树给定前序遍历和中序遍历是否可以还原出二叉树并给出证明，如果给定前序和后序呢？

二叉树的前序和中序、后序和中序可以唯一地确定一颗二叉树。但只给定前序和后序遍历不能确定一颗二叉树。（也就是一定要有中序遍历才能确定一颗二叉树）
前中后序遍历这个顺序是以根结点的遍历顺序为依据命名的。在先序遍历中，第一个节点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的柚子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这颗二叉树。
特别注意的是，层序遍历是从根结点层到叶结点层，先左子树后右子树。

题目2：√

树和图有什么不同？

数只能表示层次关系，例如父子关系。其他关系只能间接表示，例如同级关系。图是树的推广，可以表示同级关系。直观讲，图是由定点（或节点）及顶点间的关系组成的集合。

题目3：√

用蒙特卡洛方法计算π。

构造一个单位正方形和一个单位圆的1/4，往整个区域内随机投点，根据点到原点的距离判断点是落在1/4的圆内还是圆外，从而根据落在两个不同区域的点的数目，求出两个区域的比值。如此一来，就可以求出1/4单位圆的面积，从而求出圆周率π。假设每个投入的点等概率的分布在这个正方形区域的任何位置。根据随机投点，投在圆内的点的概率既等于圆的面积与单位正方形的面积之比，同时也等于实际投在圆内的点与总共的投点之比。（Pi/4 = total(圆内点)/total(总点数)）。当投的点越多根据上面等式计算的π值就越精确。
Python中的函数random()可返回随机生成的一个实数，它在[0,1)范围内。^[1]

考点九『统计学习』

EM算法
<what>EM算法时一种迭代算法。用于含有隐变量的概率模型参数的MLE，或极大后验概率估计。每次迭代由两步组成。
E=>EXPECTATION求期望
M=>MAXIMIZATION求极大值

logistic算法
<what>该算法处理的是含定性变量的回归模型。当进行logistic回归分析时，将变量转换为k-1个虚拟变量或哑变量，每个虚拟变量都是一个二分类变量，通常用0,1表示。
1、分组数据的logistic回归
2、未分组数据的logistic回归
Logit变换：logit p=ln p/1-p=β0+β1x1+...+βmxm
p/1-p称为优势

主成分分析（无监督学习）
<what>由线性相关变量表示的观测数据正交变换得到少数几个由线性无关变量（主成分）表示的数据。
先对数据做规范化，在做正交变换。
<why>这是一种将为方法，因为主成分的个数通常小于原始变量的个数。
<how>用于发现数据中的基本结构，即数据中变量之间的关系，是数据分析的有力工具，也用于其它机器学习方法的前处理。
回归线是使得各点到该直线的纵向距离平方和达到最小的那条线，第一主成分y是使各点到该直线的垂直距离平方和达到最小的那条线。一般来说y介于两条回归线之间。

附录

面试技巧

当掌握了知识点，具备了应试的能力后，我们还要学习如何在面试中进行表达和沟通。

除了提出正确的解决方案之外，在每次编程面试中，还需要做一些额外的事情。^[1]

要求澄清问题
在开始说解决方案前，好的面试者总会问清面试官提出的问题，这主要有以下目的：
①缩小了问题的范围。Eg：“这个数组中的所有整数都是正的吗？”，如果答案是肯定的，那么你就不必考虑整个负整数空间，这可能使问题更容易解决。
②向面试官表明你正在积极考虑边缘案例。面试是为了证明你有能力进行批判性和周密的思考，同样也是为了证明你的原始代码能力。
③允许你和面试官就问题的理解达成一致。
主动提供算法的时间复杂度和空间复杂度信息
几乎每个面试官都会关心算法的时间复杂度和空间复杂度。主动通过这些信息，而不是等待他们询问。

你可以按照以下步骤：^[2]
1.提问
2.给出粗糙的解决方案
3.给出优化的解决方案

面试官提出一个问题后，先要从审题开始。理清所有你能想到的有歧义的地方，询问边界情况，提几组特定的输入，确保你的输出是正确的。即使你几乎知道答案，你也要问清楚模糊的地方。这很重要，因为这样做给了你想出边界情况以及完全明确问题的机会（你如何处理边界情况是面试官评估面试的侧重点），并且这样做给予了你整理思路开始解决问题的时间。

接下来，你需要提出一个简单粗暴的解决方案。你应该先讲思路，而不是直接动笔写代码，因为讲起来快，而且更能吸引面试官。一旦面试官被吸引了，他们会介入进来，并给出一定的提示。如果你直接动手写代码，你就错失了良机。

求职者通常会跳过上面那个步骤，他们认为简单粗暴的解决方案过于明显，甚至是错的。这种想法并不正确。记住，对于面试官的问题，永远要给出一个方案（即使这种方案需要指数级的运行时间或者一台NSA超级计算机）。当你提出粗暴的解决方案时，询问面试官是否需要实现出来，或者是给出更高效的解决方案。通常他们会选择后者。

给出高效解决方案的步骤更上一步类似。仍然是先讲思路，试探面试官的想法。但愿这个问题你以前见过，并且知道答案。如果没见过的话，回忆最相似的问题，然后把这些问题的答案讲出来。大部分面试题都是经典算法稍微复杂的应用。面试官通常会指点你用这种算法，如果你遵循了上述步骤的话。（PS：复试的问题没有面试那么难，为节约时间，简单的问题可以跳过第二步，直接讲最有的方法。）

此外，当你用一种编程语言作答时，不妨增添另一种编程语言的解答。

参考资料
版权声明：本文为CSDN博主「敬谦」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/xiaxianba/java/article/details/102700483 ↩ ↩ ↩
【参考资料】
https://zhuanlan.zhihu.com/p/26474610 ↩ ↩

hi | all for cpp

考点一：『循环』

题目1：√

👉补充

题目2：√

👉补充

题目3：√

👉补充

题目4：√

题目5：√

👉补充

题目6：√

题目7：√

题目8：√

题目9：√

考点二：『递归』

题目1：√

👉补充

题目2：√

👉补充

题目3：💗

题目5：√

题目4：√

考点三：『排序』

1 【插入排序】√

1.1 直接插入排序

1.2 希尔排序

2 【交换排序】√

2.1 冒泡排序

2.2 快速排序（目前已知最高效的算法）

3 【选择排序】√

3.1 简单选择排序

3.2 堆排序

考点四：『查找』

【二分查找】

应用1：

【哈希查找】

考点五：『动态规划』

题目1：💗

题目2：

举一反三

考点六：『数学』

题目1：√

题目2：√

题目3：√

题目4：❤️

题目5：√

题目6：√

考点七：『字符串』

题目1：💗√

补充

题目2：❤️

题目3：√

题目4：√

考点八：『数据结构』

题目1：√

题目2：√

题目3：√

考点九『统计学习』

附录

面试技巧

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读