6.1分解质因数/判断素数/求因子和/求因子数量 对于任意的正整数而言，其因子一定是两两成对的：若p是x的因子，x/p也一定是x的因子。所以以上的问题有个共同的解法：O(√x)遍历所有不大于√x的的因子即可。要注意x的完全平方数的特判。下面给出求因子和的关键代码： int i,sum=0; for(i=1;i*i<x;i++){ if(x%i==0)sum+=i+x/i; //既计算了因子i，也计算了因子x/i } if(i*i==x)sum+=i; //特判完全平方数6.2欧拉筛 如何快速得到1到n的所有素数？可以这样快速筛出来：先将所有2的倍数标记为合数，然后把所有3的倍数标记为合数...

5.1 二分 二分用于在一个已经排好序的数组里查询某个数/查询第一个大于（不小于）某数的数。 5.1.1 非递归实现 int l=1,r=n,x; while(l<r){ int mid=l+r>>1; //l和r的平均数（向下取整），等价于(l+r)/2 if(a[mid]<x)l=mid+1; //这里可以根据需求换成小于等于，或者check(mid)，即任意//写的check函数 else r=mid; } //搜索完l即为寻找的地方5.1.2 递归实现 int bs(int l,int r,int x){ int mid=l+r>>1; if(a[m...

4.1线性dp 还记得斐波那契数列吗？（是的，我又回来了）可以用数组来记录前面斐波那契数列的值，以此推出后面的值。 feb[0]=feb[1]=1; for(int i=2;i<=n;i++){ feb[i]=feb[i-1]+feb[i-2]; }这即是动态规划的思想：利用已有的结果以及递推方程来推出整体结果。 还有一种变种的线性dp，当数组中某个数选或不选对后面的结果都有影响时，那么可以把选或不选作为两种状态：例如：求数组中取一些数要求取的数不能出现相邻，求取的数之和的最大值： int dp[200020][2]; //dp[i][0]代表不取第i个数的最大值，dp[i][1]则代表...

3.1 栈 栈，即后进先出的线性数据结构。笔试题中可以直接调用stl中的stack。可以用栈解决的问题：括号匹配问题、表达式求值问题等。##3.2 队列队列，即先进先出的线性数据结构。笔试题中可以直接调用stl中的queue。队列最典型的应用：广度优先搜索（bfs）##3.3 广度优先搜索类似二叉树的层序遍历。一般用来解决单源或多源最短路问题，也可以解决连通块问题（这点同dfs，但dfs解决不了最短路）图的bfs代码示例： vector<int>g[100010]; //已经存好的图。 int visited[100010]; //标记数组，用来防止重复遍历 queue<in...

2.1深度优先搜索 深度优先搜索，一般指通过递归达成“不撞南墙不回头”的搜索。一般可以用来解决连通块问题、树形dp问题、或者搜索一些状压枚举解决不了的问题。这里介绍两类深度优先搜索遍历图的代码： vector<int>g[100010]; //已经存好的图。图的vector存储方式见stl篇 void dfs(int x,int pr){ //无根树的遍历。x指遍历到的节点，pr指上一个节点。 int i; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ dfs(g[x][i],x); //你要进行的操作。 } } //也可以有返回值...

1.1 贪心 贪心指每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。典型的贪心问题：1.纸币面额有1元、2元、10元、100元。问凑出正好x元最少要多少张纸币。【思路】显然是尽量取面额大的，因为有整除关系，多张面额小的一定可以被一张面额大的代替。（如果没有整除关系怎么办？）2.纸币面额有a[1]元，a[2]元......a[n]元。问至少凑出x元最少需要多少张纸币？（或者问，x张纸币最多可以凑多少元）【思路】显然的贪心算法。每次尽量取面额大的即可。 1.2 枚举 1.2.1 朴素枚举 传统的for循环（嵌套）。一般考察知识点的题目用枚举也可以获得部分分。例如：《夹...

1.pair 二元组。可以看成是如下定义：struct pair{int first,second;};一般pair型变量定义的方式是：pair<int,int>p;pair<double,double>a[222];pair数组默认排序的依据是：优先按first升序进行排序。若first相等则按second升序进行排序。##2.vector可变长度的数组。主要用法如下： vector<int>a; //vector的定义 a.push_back(x); //在a的最后新增一个数x a[i]; //调用a的下标i对应的数 sort(a.begin(),a.e...

1.语句和字符串 在c/c++中，一个语句一般是以分号结尾。语句有以下几种：①表达式语句：作用大多数为给变量赋值。 a=3; b/=2;②函数调用语句作用为调用函数。函数可以是库函数，也可以是自己定义的函数。 printf(“123”); //库函数，作用为打印字符串 dfs(1,-1); //自己定义的函数③控制语句条件：if(a<b)....循环：while(t--)....转向：break;④复合语句 a=1,b=2; //用逗号隔开的语句为复合语句 while(x<3){x++;printf(“%d\n”,&x);} //大括号里为复合语句⑤空语句 for(i=n-...

1. 什么是面试技巧    1.1 带你初识面试技巧   什么是面试技巧？   我们这里说的面试技巧是技巧，是能让你加分的，而不是让你可以作弊。具体什么叫作弊，什么叫技巧，这一点你是要清楚的。      一、什么叫作弊？   ①在线面试的时候查答案。   很多同学可能不知道在线面试系统的强大，比如随意切换页面，或者去手机上查答案等等，这些都是能被面试官发现的，当然，少部分的企业可能用微信进行面试，这种不太能通过系统看出来，但是面试官也是能通过你的状态发现出来，一旦被发现或者被怀疑，你的印象分都会大打折扣，甚至这一轮会直接被挂掉。      ②在线面试的时候让别人输出答案   还有的同学会在在线...

1.面试题 NC103反转字符串   解法一:     开辟一个和str长度大小相同的一个字符串ans，把传入的str倒序赋值到ans字符串上，时间复杂度O(n) ,额外空间复杂度O(n)      c++   class Solution { public:     string solve(string str) {         string ans = str;   ...

7.1快速幂   利用公式，可以直接用底数平方、指数除以2的方式，这样指数降到0只需要log(n)次，因此复杂度仅需O(logn)，比朴素的模拟乘方法的O(n)要优秀很多。   模板如下：       long long power(long long a,long long b,int mod) { //计算a的b次方对mod取模的值   long long res=1;   while(b){   if(b&1)res=res*a%mod;    //判断b为奇数，等价于b%2==1   b>>=1;    &...

6.1 分解质因数/判断素数/求因子和/求因子数量   对于任意的正整数而言，其因子一定是两两成对的：若p是x的因子，x/p也一定是x的因子。   所以以上的问题有个共同的解法：O(√x)遍历所有不大于√x的的因子即可。   要注意x的完全平方数的特判。   下面给出求因子和的关键代码：       int i,sum=0;   for(i=1;i*i<x;i++){   if(x%i==0)sum+=i+x/i;   //既计算了因子i，也计算了因子x/i   }   if(i*i==x)sum+=i;     &n...

5.1二分   二分用于在一个已经排好序的数组里查询某个数/查询第一个大于（不小于）某数的数。   5.1.1非递归实现       int l=1,r=n,x;   while(l<r){   int mid=l+r>>1;    //l和r的平均数（向下取整），等价于(l+r)/2   if(a[mid]<x)l=mid+1;  //这里可以根据需求换成小于等于，或者check(mid)，即任意//写的check函数   else r=mid;   }   //搜索完l即为寻找的地方       5.1.1递归实现      ...

4.1 线性dp   还记得斐波那契数列吗？（是的，我又回来了）   可以用数组来记录前面斐波那契数列的值，以此推出后面的值。       feb[0]=feb[1]=1;   for(int i=2;i<=n;i++){   feb[i]=feb[i-1]+feb[i-2];   }       这即是动态规划的思想：利用已有的结果以及递推方程来推出整体结果。       还有一种变种的线性dp，当数组中某个数选或不选对后面的结果都有影响时，那么可以把选或不选作为两种状态：   例如：求数组中取一些数要求取的数不能出现相邻，求取的数之和的最大值：       int...