C++笔试题模版汇总(一)

1、快速排序

 //1、确定分界点x：q[l]     or   q[r]     or  q[(l+r)]    //2、取中间数，也可以取随机数。 调整区间范围:左端所有数<=x,右端所有数>=x //3、递归排序left，递归排序right）  void quick_sort(int q[], int l, int r) {     if (l >= r) return;//判断边界，如果输入只有一个数或者没有数 就直接return       int x = q[(l + r) / 2], i = l - 1, j = r + 1;//取分界点x(中间点)，i和j是指针     while (i < j)//循环迭代，交换，调整区间     {         do i ++; while (q[i] < x);//循环直到q[i]>x         do j --; while (q[j] > x);//循环直到q[i]<=x         //如果循环之后，指针i和j没有相遇，交换两个数         if (i < j) swap(q[i], q[j]);     }       quick_sort(q, l, j);     quick_sort(q , j + 1, r); }

2、归并排序

 //可以对比一下快排 //1、确定分界点：mid = (l + r)/2 取中间数，分成[L,mid]和[mid,R]两个区域。 //2、将l[L,mid]和[mid,R]两个区域进行递归排序。 //3、归并-将左右两个有序的序列合并成一个有序序列。  void merge_sort(int q[], int l, int r) {     if (l >= r) return;     //确定分界点mid     int mid = l + r >> 1;     // mid = (l + r) >> 1;     //左右区间递归排序     merge_sort(q, l, mid),merge_sort(q, mid + 1, r);     //归并-将两个序列合二为一     int  k = 0, i = l, j = mid + 1;//k为temp数组下标，i代表左半边有序序列起点，j代表右半边有序序列起点     //归并过程     while(i <= mid && j <= r)         if (q[i] <= q[j]) temp[k ++] = q[i ++];//把小的方法temp中         else temp[k ++] = q[j ++];     //左右两边将未排序的放进temp中     while(i <= mid) temp[k ++] = q[i ++];     while(j <= r) temp[k ++] = q[j ++];               //循环将temp中排序好的结果存回q[i]     for (i = l,j = 0; i <= r; i ++, j ++) q[i] = temp[j];   }

3、整数二分算法

 //1、在一个区间内部去区分边界，在选择区间中，要选择答案所在区间，每一次都会将答案覆盖掉。 //2、当区间长度是1的时候区间里的数一定是答案 #include <iostream>   using namespace std;   const int N = 100010;   int n,m; int q[N];     int main() {     scanf("%d%d",&n,&m);     for (int i = 0; i < n; i ++) scanf("%d",&q[i]);          while(m --)     {         int x;         scanf("%d", &x);                  int l = 0, r = n - 1; //区间[l, r]被划分成[l, mid]和[mid + 1, r]时         while(l < r)         {             int mid = l + r >> 1;             if (q[mid] >= x) r = mid;             else l = mid + 1;         }         if (q[l] != x) cout << "-1 -1" << endl;         else // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时         {             cout << l << ' ';             int l = 0,r = n - 1;             while(l < r)             {                 int mid = l + r + 1 >> 1;                 if (q[mid] <= x) l = mid;                 else r = mid - 1;             }             cout << l << endl;         }     }     return 0; }

4、高精度加减乘除

 //C = A + B vector<int> add(vector<int> &A,vector<int> &B) {     if(A.size()<B.size()) return add(B,A);//大的在前面     int t=0;//如果两个个位数相加大于10则进一位     vector<int> c;     for(int i=0;i<A.size();i++){         //个位数相加         t+=A[i];         if(i<B.size()) t+=B[i];         //A + B + t         c.push_back(t%10);//将两个个位数之和结果的个位数存入c中         t/=10;//取十位     }     if(t) c.push_back(t);//判断两数相加是否大于十，大于则进位     return c; }  //C = A - B //1、从低位开始AB对位相减，如果不够减则向前借1。 //2、用t来保存借位状态,即：A-B+t //3、(t+10)%10 包含了两种情况：1、如果A[i]-B[i]>=0,则+10取余数还是个位数。2、A[i]-B[i]<0则要借位+10然后取余10，还是回得到个位的数 //4、去掉前导00 //判断都否有 A>=B,返回true或者false bool cmp(vector<int> &A, vector<int> &B) {     //A 长度比 B长度不同则比较大小     if (A.size() != B.size()) return A.size() > B.size();       //如果AB长度相同则从高到低循环遍历对比每位大小     for (int i = A.size() - 1; i >= 0; i --)         if(A[i] != B[i]) return A[i] > B[i];     return true; }   //C = A - B vector<int> sub(vector<int> &A, vector<int> &B) {     vector<int> C;     //核心思想： 从低位开始AB对位相减，如果不够减则向前借1，并用t来保存借位状态,即：A-B+t     for (int i = 0, t = 0; i < A.size(); i ++)     {         t = A[i] - t;//如果上一次接了位则先减去t         if (i < B.size()) t -= B[i];//i没有超出B的长度，则减去B         C.push_back((t + 10) % 10);//(t+10)%10 包含了两种情况：1、如果A[i]-B[i]>=0,则+10取余数还是个位数。2、A[i]-B[i]<0则要借位+10然后取余10，还是回得到个位的数         if (t < 0) t = 1;//如果t<0则上面一步是接了位的，所以t要标注1，表示借位了，下一次A[i]需要减去1         //否则t = 0         else t = 0;     }     //得到的结果C是一串数组，结果减完之后前面存的全是零，假设结果为9，这样取出来的数是 000009（举例），所以我们要去掉前导（去掉9前面的0）     while (C.size() > 1 && C.back() == 0) C.pop_back();//去掉前导00     return C; }   //C = A * B 高精度*低精度 //核心思想：1、将A从个位开始乘以b,结果%10 得到个位值，结果/10 得到进位的值 vector<int> mul(vector<int> &A, int b) {     vector<int> C;          int t = 0;//用于保存进位值     for (int i = 0; i < A.size() || t; i ++)     {         if (i < A.size()) t += A[i] * b;//如果i没有超出A的size         C.push_back(t % 10);//取个位结果         t /= 10;//保存进位值     }          return C;  }  //C = A / B //核心思想：1、从除数最高位开始除以被除数。 //2、将余数加到下一位：数*10 + 下一位数 //3、取出r/b高位，得到商，以及r%b低位，用r来存进位。 //4、最后得到的结果是逆序的，所以需要反转，然后去除前导。 vector<int> div(vector<int> &A, int b, int &r)//r是引用 {     vector<int> C;//商     r = 0;     for (int i = A.size() - 1; i >=0; i --)//从最高位开始做，将余数加到下一位     {         r = r * 10 + A[i];         C.push_back(r / b);         r %= b;     }     //得到的C是逆序的，所以需要反转     reverse(C.begin(), C.end());     //去除前导如果最高位是0则去除     while(C.size() > 1 && C.back() == 0) C.pop_back();          return C; }   

5、前缀和

Si = a1 + a2 + ...+ ai, S0 = 0。

[L, R]区间和 = aL + aL+1 + ... + aR = SR - SL - 1

1. 预处理前缀和数组
2. 用公式求区间和

 #include <iostream> using namespace std; const int N = 100010; int n, m; int a[N], s[N];   int main() {     scanf("%d%d", &n, &m);     for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);          for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];          while(m --)     {         int l, r;         scanf("%d%d", &l, &r);         printf("%dn", s[r] - s[l - 1]);     }      }

6、子矩阵和

求S[i,j]位置前面所有数之和(有颜色块):

公式如下：

 #include <iostream>   using namespace std;   const int N = 1010;   int n,m,q;   int a[N][N], s[N][N];   int main() {     //第一行包含三个整数n，m，q。     scanf("%d%d%d",&n,&m,&q);     //接下来n行，每行包含m个整数，表示整数矩阵。接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。     for (int i = 1; i <= n; i ++)         for (int j = 1; j <= m; j ++)             scanf("%d",&a[i][j]);     //初始化前缀和数组     for (int i = 1; i <= n; i ++)         for (int j = 1; j <= m; j ++)             s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];     //询问     while(q --)     {         int x1, y1, x2, y2;         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);         printf("%dn", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);     }     return 0;      }

7、差分

假设给定原数组是 a1, a2, a3,..., an.

构造b数组 b1,b2,...,bn.使得 ai = b1 + b2 + ... + bi;

则有 b1 = a1;

        b2 = a2 - a1;

        b3 = a3 - a2；

        ...

        an = an - an-1;

b则称为a的差分，a则是b的前缀和。前缀和和差分是逆运算。
 

 #include <iostream>   using namespace std;   const int N = 100010;   int n,m; int a[N], b[N];   void insert(int l, int r, int c) {     b[l] +=c;//第l + c     b[r + 1] -= c;//第r + 1 减去c }   int main() {     scanf("%d%d", &n, &m);     for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);//输入a数组          for (int i = 1; i <=n; i ++) insert(i, i, a[i]);//把n个数组的数进行插入操作          while(m --)     {         int l, r, c;         scanf("%d%d%d", &l, &r, &c);         insert(l, r, c);     }          for (int i = 1; i <=n; i ++) b[i] += b[i - 1];//求原来数组的值，对差分数组求前缀和          for (int i = 1; i <= n; i ++) printf("%d ", b[i]);//输出b }

差分矩阵

公式如下：

b(x1, y1) += C;

b(x2 + 1, y1) -= C;

b(x1, y2 + 1) -= C;

b(x2 + 1, y2 + 1) += C;

 #include <iostream>   using namespace std;   const int N = 1010;   int n, m, q; int a[N][N], b[N][N];   void insert(int x1, int y1, int x2, int y2, int c) {     //公式     b[x1][y1] += c;     b[x2 + 1][y1] -= c;     b[x1][y2 + 1] -= c;     b[x2 + 1][y2 + 1] += c; }   int main() {     scanf("%d%d%d", &n, &m, &q);          for (int i = 1; i <= n; i ++)         for (int j = 1; j <= m; j ++)             scanf("%d", &a[i][j]);          for (int i = 1; i <= n; i ++)         for (int j = 1; j <= m; j ++)             insert(i, j, i, j, a[i][j]);          while (q --)     {         int x1, y1, x2, y2, c;         cin >> x1 >> y1 >> x2 >> y2 >> c;         insert(x1, y1, x2, y2, c);     }          for (int i = 1; i <= n; i ++)         for (int j = 1; j <= m; j ++)             b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];////求原来数组的值，对差分数组求前缀和          for (int i = 1; i <= n; i ++)     {         for (int j = 1; j <= m; j ++) printf("%d ", b[i][j]);         puts("");     }          return 0; }

8、数组元素目标和-双指针解法

问题：给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。请你求出满足A[i] + B[j] = x的数对(i, j)。

经验：做这种类型的题目先使用暴力方法求解，然后分析其规律，再考虑优化解法，比如双指针解法。

 #include <iostream> #include <algorithm>   using namespace std;   const int N = 100010;   int n, m, x; int a[N], b[N];   int main() {     scanf("%d%d%d", &n, &m, &x);//第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x     for (int i = 0; i < n; i ++) scanf("%d", &a[i]);//第二行包含n个整数，表示数组A。     for (int j = 0; j < m; j ++) scanf("%d", &b[j]);//第三行包含m个整数，表示数组B。          for (int i = 0, j = m - 1; i < n; i ++)//i从首位0开始，j从末尾m - 1开始     {         while (j >= 0 && a[i] + b[j] > x) j --;//a[i]和b[i]进行相加，如果大于x,则B数组末尾数j往前移动一位，直到A + B <= x.         if (a[i] + b[j] == x)//满足条件输出i, j的值。         {             printf("%d %dn", i, j);             break;         }     }     return 0; }

9、位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

 #include <iostream>   using namespace std;   int lowbit(int x) {     return x & -x; }   int main() {     int n;     cin >> n;     while (n --)     {         int x;         cin >> x;                  int res = 0;         while (x) x -= lowbit(x), res ++;//每次减去x的最后一位1,然后res++标记                  cout << res << ' ';     }     return 0; }

10、离散化

如果一个数值范围是0-10^9，数值域特别大，个数比较小，比如只有10^5个数（值域跨度很大，数分布很稀疏）。如果开10^9区域特别浪费内存。所以我们需要把他们映射到从0开始的连续的自然数。

例：数组a[] = 1, 3, 100, 2000, 500000.数值很大，但是里面的数很小。我们使用0，1，2，3，4，来分别映射到1，3，100，2000，500000中.这个过程就叫做离散化。

离散化存在问题：1、a[]中可能有重复元素，我们需要去重。2、如何算出x的值在a[]中的下标是什么？即离散化之后的值。

步骤：1、存储所有待离散化的值。2、将所有值排序。3、去掉重复元素。4、二分求出离散化的值。

 vector<int> alls;//存储所有离散化的值 sort(alls.begin(), all.end());//将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end());//去掉重复元素   //二分求出x对应离散化值   int find(int x) {     int l = 0, r = alls.size() - 1;     while(l < r)     {         int mid = l + r >> 1;         if (alls[mid] >= x) r = mid;         else l = mid + 1;     }     return r + 1;//映射到1, 2, ... n }

11、区间合并

概念：给我们很多区间，如果有交集的区间(如果在端点处相交也算)，我们可以将他们合并城一个区间。

 #include <iostream> #include <algorithm> #include <vector>   using namespace std;   typedef pair<int, int> PII;   const int N = 100010;   int n; vector<PII> segs;   void merge(vector<PII> &segs) {     vector<PII> res;//定义答案：合并之后结果          sort(segs.begin(), segs.end());//所有区间排序          int st = -2e9, ed = -2e9;//定义负无穷正无穷边界2*10^9     for (auto seg : segs)//从前往后扫描所有线段                  if (ed < seg.first)//1、当前区间右端点严格小于枚举区间左边         {             //判断不能是初始区间             if (st != -2e9) res.push_back({st, ed});                          st = seg.first, ed = seg.second;         }         //2、当前区间和维护区间有交集，则求并集         else ed = max(ed, seg.second);//求ed与seg.second的max     if (st != -2e9) res.push_back({st, ed});//防止输入数组是空的          segs = res;//把区间更新到res }   int main() {     cin >> n;          for (int i = 0; i < n; i ++)     {         int l, r;         cin >> l >> r;         segs.push_back({l, r});     }          merge(segs);//区间合并          cout << segs.size() << endl;//返回合并序列长度          return 0; }

• 版权声明：文章来源于网络采集，版权归原创者所有，均已注明来源，如未注明可能来源未知，如有侵权请联系管理员删除。

前沿资讯普通

收藏 海报 链接