算法错题本

错题本

注意数据的耦合性

bfs求连通块的时候，在进入四个方向搜索时，要注意，每次得到的新的x，y，一定不要与原x y 有任何的瓜葛，要保证每次for循环都是在旧的x y的基础上进行修改的，如果我们将x1 y1改为了x y，那么每次x y都会被更新，这显然是错的

对于无解情况的处理思路

利用反证法：如上代码，可以在有解的时候，将全局变量res，改为true，这样的话，只要有一组有解，那么就不会输出无解，反之，没有任何解的情况下，就会无解。
这里也可以注意到，全局变量使用时，不仅要关注其自动初始化为0，还要关注，他的变量是全局的，他会累计值，所以，何时该用全局，何时该用局部，要进行衡量
同时也要注意，对于一些比例的验证，最好用乘法，实际上，任何除法的计算，如果可以转化为乘法，那是最好的

一组数据以0为结束标记，如何输入到数组中，并计数

输入时，先将nums[0]输入，然后进行循环，循环时，定义ij 两个循环变量 i初始化为0，j初始化为1，之后i j都要递增，结束条件是nums[i]!=0，这样可以确保结束条件的生效，不然如果只用 i 的话，nums[i]还没被赋值就拿去判断是否等于0了。
总结：循环外输入nums[0], i 始终比 j 小一，结束条件用i判断，输入语句用 j

多个数据进行比较

可以先设一个很大的数（超过本题数据范围的数）
在一个循环里，将每个数据依次在一次循环中得出，每次循环得到的结果是x，将x与ans取min，赋值给ans，这样多次循环之后，就是多个数据的最小值

链表删除重复元素的启发

图中 1、对于链表 可能系统会传入空指针进去 所以要考虑到 要加上空指针判断
2、对于while条件的设置 因为p不可以指到空指针 不然出错 所以不可以设置为p！=NULL 但是p必须最终指向最后一个结点来结束循环 所以可以设置为p->next！=NULL;
3、因为执行完if中的内容之后 还要再比较一遍处理过后的当前结点的情况 所以 在if为真时 不设置p后移
而是在else里设置p后移 这样既可以再比较一遍 还符合运行逻辑

循环体里谨慎写类型定义并初始化（一般写上就是错）

上图中 在循环里 不要定义int i = 0 ；
这样的话每次循环都会使其为0；
低级错误 只能在for循环里设置为int i= 0；

队列中读取队尾元素

数组当做形参传递到函数里之后 就不可以进行数组元素的计算了

sizeof（nums）/sizeof（nums【0】） 可以算出数组的元素个数
但是仅限于在定义数组的函数内才可以
注意：sizeof的办法不能求已经定义好的数组的长度 因为这样的话 sizeof（数组）就是你定义的长度的字节数

如果将数组作为形参 传递到函数里 那么就不可以用这种方法 因为一旦当做形参传递数组 数组就变成了指针 就不会传入整个数组的大小 所以不可以在函数里求函数外的数组的元素个数 只能在函数外求出 然后当做形参传递进去

当数组定义好了长度 如何求有效长度

利用for循环 计数器++ 求长度
终止条件（跳出循环条件）：

可以看到定义好了数组之后 不赋值的地方 就是乱码 以此为终止条件

读取字符串越界位置

越界位置为NULL

返回值是一个容器

当返回值是一个容器时 就要返回一个同类型的容器 可以定义一个函数 在函数里进行操作 之后的输出替换成向容器里面加入元素即可

ps 适用于某个算法在递归输出 而没有返回值时 可能会遇到这种情况

持续删除string中某个字符

首先拿到第一个pos = A.find(目标字符)
之后while循环中，如果pos不等于尾后迭代器(这里是string::npos)，就一直循环
A.erase(pos, 1);
之后在循环内更新pos = A.find(还是那个目标字符)

蓝桥真题

遇到简单的组合数问题

遇到如上图所示，cab中，已经给出了a或者b的值，且a或者b的值很小，那么可以直接把组合数的数学公式推出来，计算即可了，不用局限于写上模版，然后代数。

取模和除法、补充前导0

%：a % b
1、a除以b之后的余数
2、a 减去 b的整数倍 之后，在b范围内的数
3、a % b == 0，a 是 b 的整倍数
4、a % 10，小数点左移一维，取右边的数

/ ：a / b
1、a除以b的结果（int数据会缺失精度）
2、a中最多有多少个b
3、a / 10，小数点左移一位，取左边的数

考试的时候细细琢磨
之所以hh、mm、ss后面要%24、60、60，是因为h / （60 * 1000）得到的是一天有多少分钟，而不是一小时的多少分钟，所以要%一小时单位下mm的范围，即%60，ss也要%一分钟下他的范围，%60

同时，该题解还提供了一种补充前导0的办法。printf(“%02d”,x)表示输出两位数字，如果x是个位，就在前面补0，如果x是两位数，则忽略前面那个0

且如果题目没有强调，那么年份和月份都是按照普通情况处理