算法刷题小技巧总结

最后一个空格问题：

删除元素可使用标记法。（链表删除元素。）

数组过大超过限制，可定义为全局变量。开一个20000大小的数组，用memset函数赋初值。

给出范围的一定要对范围左右端点进行大小排序，不然可能会吃亏（训练赛A题）

数据处理的问题，要注意边界值，比如0 -1 最大值N等的特殊性，写代码要严谨，确保输入数据在所给范围之内。（判断素数，“1”）

保留小数的问题

#include<iostream>
#include<iomanip>
using namespace std;
cout<<setiosflags(ios::fixed)<<setprecision(2)<<小数;

• c++输入多个字符串，利用cin.getline(char数组,字符数);//利用cin.get(数组,字符数)莫名其妙有问题，无法再次输入。关于输入与输出，多用C++的特性。 如果前面用过cin了，在使用 getline时，记得先cin.ignore()

#include<string>
string a;
getline(cin,a);

• 要是忽略一行 cin.ignore(10000,'n');忽略单个字符cin.ignore();
• 输入输出较为复杂的情况下，要时刻想到用C和C++结合的方式，可使输入输出变简单。
• 注意题目中给的大小空间限制有可能是幌子，可通过其他条件得到限制的上下限，不要懒于计算。（小背包——背包最大体积2000000，最多装载16个物品，每个物品体积2400）
• 判断组合数的奇偶性，二进制n&m==m为奇数，反之为偶数。
• 求最大公因数：辗转相余，a=16，b=12；a%b=4；b%4==0，4即为最大公因数。
• 如果不确定输入数据是否为整形还是浮点型，为保险起见，定义变量为浮点型，从而保证数据的规范性。
• 控制循环结束。

while((scanf("%s",s[count++]))!=EOF) 或者
while(scanf("%s",s[count])!=EOF&&source[n][count]) 或者
while(gets(s[count])&&s[count][0])

• 可以使用strstr()函数查找字串所在位置。

    char *s="GoldenGlobalView";
    char *l="lob";
    char *p;   p=strstr(s,l);
    if(p)     printf("%s",p);
    else      printf("NotFound!");

• 注意字符串和字符数组的区别：字符串最后会有一个’\0’
• 斐波那契数列通常用递归来求，如果不用递归式的定义，斐波那契数列的通项公式为：

• 判重思想，已经使用过的数据或者变量可以进行标记，则在下次遍历或者取相邻的数据或变量时，可减少查找的次数。
• scanf函数读取数据时候会自动跳过空格和换行。
• 数据类型范围：

unsigned int    ： 0～4294967295   
int             ： 2147483648～2147483647 
unsigned long     ： 0～4294967295
long            ： 2147483648～2147483647
long long的最大值 ：9223372036854775807
long long的最小值 ：-9223372036854775808
unsigned long long的最大值：18446744073709551615
__int64的最大值   ：9223372036854775807
__int64的最小值   ：-9223372036854775808
unsigned __int64的最大值：18446744073709551615

• 提高速度的优化方案多个：if ->数组实现
• 打印沙漏问题：

等差数列*2-1 ，即每一组的字符总数为 2Sn-1

• scanf、printf比cin、cout快，做题的时候尽量使用scanf printf。在数据量比较大的情况下cin cout比scanf printf慢挺多。一旦遇到大数据量，光是读入就有可能跪掉。你或许可以使用std::ios::sync_with_stdio(false); 这条语句关掉scanf和cin的同步，加快效率。但是即使这样cin还要慢，而且一旦使用了这条语句，scanf和cin混用可能就会造成一些奇怪的错误
• 语言的灵活运用：大数处理可以用python和java，java需要引包：即BigIntegr类 和 BigDecimal类

1. Java：大数的加减运算不同于普通整数的加减乘除运算

加—— a+b: a=a.add(b);
减—— a-b: a=a.subtract(b);
乘—— a*b: a=a.multiply(b);
除—— a/b: a=a.divide(b);
求余—a%b: a=a.mod(b);
转换—a=b: b=BigInteger.valueOf(a);
比较 if (ans.compareTo(x) == 0)//比较
System.out.println("相等");
System.out.println("a + b = "+ans_add); // 这里的‘+’ （第二个） 是连接的意思

2. Python处理大数可以直接进行加减乘除，不过要注意时间问题，可作为验证来使用。

• 当使用STL容器时，若处在多个用例内，每次循环一定要记得把容器清空。

列举STL常用的函数：

STL常用算法：https://blog.csdn.net/qq_41823684/article/details/98938988

（1）sort
（2）unique
（3）string相关的操作
（4）remove和erase移除元素
（5）序列反转reverse
（6）序列交换swap
（7）统计等于某值的容器元素个数count
（8）条件统计count_if
（9）查找容器元素find
（10）条件查找容器元素find_if
（11）子序列搜索search
（12）最后一个子序列搜索find_end
（13）元素复制copy
（14）元素变换transform
（15）替换replace
（16）条件替换replace_if
（17）n次填充fill_n
（18）随机生成n个元素generate
（19）操作容器中的每一个元素for_each
（20）条件移除remove_if

• 并不是所有迭代器都有加减法。能进行算术运算的迭代器只有随机访问迭代器，要求容器元素存储在连续内存空间里，vector，string，deque的迭代器是有加减法的，但是map，set，multimap,multiset的迭代器是没有加减法的，list也不可以 。
• string之unique(),erase(),remove()

// 去除连续的元素
s.erase(unique(s.begin(), s.end()), s.end());
// 去除指定的元素（字符串中所有该元素）
s.erase(remove(s.begin(), s.end(), '0'),s.end());
// 去除首元素
s.erase(0, 1);

• vector二维数组初始化：

   vector<vector<int>> v;
   v.resize(r, vector<int>(c, 0));

• runtime error可能的原因

①除以零；

②数组越界：int a[3]; a[10000000]=10;

③指针越界：int * p; p=(int *)malloc(5 * sizeof(int)); *(p+1000000)=10;

④使用已经释放的空间：int * p; p=(int *)malloc(5 *sizeof(int));free(p); *p=10;

⑤数组开得太大，超出了栈的范围，造成栈溢出。

• 堆栈溢出的几个问题

（1）vector如果要随机访问进行赋值，则必须先分配空间；

（2）局部数组不能太太，否则会产生堆栈溢出；可以使用全局数组或者动态分配。

（3）可以使用long long int防止数据太小导致的问题；