C++算法竞赛踩坑心得

这几天开始继续刷算法了,昨天晚上写了一道大模拟,今天看了半天才知道bug出在哪里,以后每犯一个值得纪念的错误都会列出来,用以自勉。

  • cin,getline的区别
  • scanf(“%d”,&n);scanf(“%s”,str);需要注意中间要加getchar读掉缓冲区
  • string也可以实现切片,需要参考string的构造函数,如string test(src,beginPos,endPos),不可以直接将一个字符赋给一个string
  • C++11及以下不提供split,可以使用vector作为返回结果手写一个,这也是头条面试的一道经典题目
  • 有时候必须采用哈希,比如在遇到TLE的时候,考虑哈希是否能用,或者怎么哈希

    1
    2
    3
    4
    5
    6
    7
    int hashID(char name[]){ //这是一道PAT题目的例子,名字的格式如THU1,PKU2,BNU1这样
    int id=0;
    for(int i=0;i<3;i++)
    id=id*26+(name[i]-'A');
    id=id*10+(name[3]-'0');
    return id;
    }
  • 有时候大数据点string比如char数组,因为容易超时

  • strcmp函数返回值不一定为正负1和0,取决于编译器

    1
    2
    3
    bool cmp(char A[],char B[]){
    return strcmp(A,B)<0;
    }
  • vector的排序:sort(vec.begin(),vec.end(),cmp),略类似于数组

  • 输出格式可能会成为一个坑,比如”%05d”在输出-1就会有问题
  • C语言结构体也可以有构造函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <iostream>
    using namespace std;

    struct Node {
    int x, y, z;
    Node(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
    };

    int main() {
    Node a(1, 2, 3);
    cout << a.x << " , " << a.y << " , " << a.z << endl;
    return 0;
    }
  • 剑指offer第二题:

    1
    2
    3
    //auto ret=s.c_str();      //比较迷的类型转换可以尝试以下auto
    const char* ret=s.c_str(); //C_str()返回的是const char*,不能直接赋值
    strcpy(str,ret);
  • vector的自身反转可以直接用reverse:reverse(A.begin(), A.end());

  • MAP是关联性容器,erase不当容易引发错误
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // 错误的写法
    for (itor = m.begin(); itor != m.end(); ++itor)
    {
    if (itor->second == "def")
    {
    m.erase(itor) ; // map是关联式容器,调用erase后,当前迭代器已经失效
    }
    }

    // 正确的写法
    for (itor = m.begin(); itor != m.end();)
    {
    if (itor->second == "def")
    {
    m.erase(itor++) ; // erase之后,令当前迭代器指向其后继。
    }
    else
    {
    ++itor;
    }
    }