日常学习

• 牛客打新生编程比赛，关注赛事

• 力扣等大二下就可以开始刷每日一题，关注周赛了

  校赛准备

  为了应对明天校赛，下面给一些常见的点，可以看一下自己会不会，不会的赶紧百度去了解。这里相当于快速带你们看一下一些常见的考点。

  语法注意点

• 格式相关

  • 多组样例输入while(cin>>c)
  • 行末不能留有空格字面意思，for循环需要处理一下
• 常见注意点
  • 时间超限：把c++输入输出改成c的scanf，或者使用快速输入模板；或者是算法的问题改算法；或者逻辑出问题死循环。
  • 注意题目数据大的时候使用long long，有时候逻辑没问题用int开变量，太小也会导致WA。

• 必会STL库函数及数据结构

  • 哈希 map book；book[1]=1; int a = book[1]; bool ifEaxit = book.count(1);
  • 自动去重set book; book.insert(1), book.count(1)
  • 队列queue que;que.push(1),int a = que.front(); que.pop();
  • 栈 stack sta;sta.push(1),int a = sta.top(); sta.pop();
  • 比普通数组好用的 vector arr(初始化几个空间，初始化值),可以自动扩容，支持排序，支持二分查找; vector<int> arr(10,0);arr.push_back(1); int a = arr[10]
  • 二分函数(后面一些方法都基于上面arr数组使用)：int pos = lower_bound(arr.begin(),arr,end(),1) - arr.begin();
  • 排序 sort(arr.begin(),arr.end());

    必会基础题目

• 数组

  • 二分查找
  • 倒转数组 reverse(arr.begin(),arr.end())
• 字符串
  • 字符串转数字 sprintf(str,"%d",a);将str字符printf到a数字变量里面
  • 数字转字符串 sscanf(str,”%d”,&a) 读取数字a输入scanf到str字符串变量;
• 哈希表
  • 统计英文字母频率 map<char,int> book; book[letter]++;
• 栈与队列
  • 4. 有效的括号 ()(())((())) 统计有几对括号，stack<char> sta;
• 回溯算法
  • 2. 组合问题 n个数字随机抽k个，输出所有组合方式
• 搜索算法
  • BFS 迷宫走到终点最短几步，手写bfs(queue队列配合while循环)
  • DFS迷宫走到终点有几种方法，手写dfs(递归思想遍历所有)
• 动态规划
  • 走楼梯经典问题： 可以走一步或者两步dp[i] = dp[i-1] +dp[i-2]
  • 导弹拦截问题（最长不上升子序列问题）：3 1 6 7 2 9的序列，最长的升序列长度是4（3 6 7 9 ）；O(N^2)就是dp，简单dp只能得出长度，更快的是LIS算法O(logN)自行百度；进阶问题求输出3679路径就只能用LIS快速得出了
  • 两个字符串的最长公共子序列；很经典又很难记住的一个题目，比如leetcode - leeodeaa输出leede
• 模拟题
  • 回旋打印回旋打印n*m的数组
  • 打印图形
• 其它常见题目
  • 并查集：好朋友，找一共有几个圈子（就是统计father数组里面有几个父节点）
• 压轴题：
  • 最小生成树
  • 城市之间可达性问题
  • 各种图论或者递归回溯剪枝问题