石家庄网站设计制作服务,公司官网源码下载,第一营销网,把别人的图片拿来做网站一、编程语言选择
很多高校在机试中对编程语言都有明确规定#xff0c;像复旦大学计算机学院就说明可选择 C、C 或 Java 语言答题#xff0c;还支持 C11#xff08;gcc5.4#xff09;#xff0c;C14#xff08;g5.4#xff09;#xff0c;Java (openjdk1.8#xff09…
一、编程语言选择
很多高校在机试中对编程语言都有明确规定像复旦大学计算机学院就说明可选择 C、C 或 Java 语言答题还支持 C11gcc5.4C14g5.4Java (openjdk1.8等编译环境。这里强烈建议大家使用 C/C因为几乎所有高校都支持通用性超强。
二、准备好模板是至关重要的
一般来说机试都可以带书和纸质资料进入考场。所以提前把那些函数的用法和算法的模板准备好是很重要的一方面是增加自己的信心万一没记住还可以翻开来看一下。另外说不定考到原题或者类似的题就可以直接秒杀了。 机试模板PDF详细代码自取
常见头文件
#include iostream
#include algorithm
#include vector
#include string
#include cmath
cout abs(a);
memset(a,-1,sizeof(a)); #include string.hint转字符串
string intToString(long long x){string s;while(x){s (x % 10) 0;x x / 10;} reverse(s.begin(),s.end());return s;
}日期模板
int daytab[2][13] {
{0,31,28,31,30,31,30,31,31,30,31,30,31
},
{0,31,29,31,30,31,30,31,31,30,31,30,31,
}
};bool IsLeapYear(int x){return (x % 4 0 x % 100 ! 0) || (x % 400 0);
}
算天数while(cin y m d){int sum 0;for(int i 0;i m ;i ){sum daytab[isLeapYear(y)][i];}sum d;cout sum endl;}
scanf(%04d%02d%02d,y1,m1,d1);// 第n天后是什么日期cin y m d n;n n d;d 0;while(n daytab[IsLeapYear(y)][m]){n - daytab[IsLeapYear(y)][m];if(m 12){y ;m 1;}else{m ;}}d d n;if(d 0 m ! 1){m --;d daytab[IsLeapYear(y)][m];}else if(d 0 m 1){m 12;d daytab[IsLeapYear(y)][m];}printf(%04d-%02d-%02d\n,y,m,d);}
二分查找在已经有序的情况下
bool BinarySearch(int n,int x){int l 0,r n - 1;while(l r){int m (r l) / 2;if(a[m] x){l m 1;}else if(a[m] x){r m - 1;}else{return true;}}return false;
}sort排序重写CMP函数
bool cmp(Student x,Student y){if(x.score y.score){return x.num y.num; }else{return x.score y.score;}
} stable_sort(stu[0],stu[n],cmp); //重点sort是不稳定排序stable_sort才是稳定排序 快速排序
void quick_sort(int q[],int l,int r){if(l r)return ;int x q[(l r) 1], i l - 1,j r 1;while(i j){do i ;while(q[i] x);do j --;while(q[j] x);if(i j)swap(q[i],q[j]);} quick_sort(q,l,j);quick_sort(q,j 1,r);
}归并排序 逆序数对
void merge_sort(int q[],int l,int r){if(l r)return ;int mid (l r) 1;merge_sort(q,l,mid);merge_sort(q,mid 1,r);int i l ,j mid 1,k 0;// 左右指针进行比较 while(i mid j r){if(q[i] q[j])temp[k ] q[i ];else temp[k ] q[j ];}// 没有分完的 while(i mid)temp[k ] q[i ];while(j r)temp[k ] q[j ];for(int i l,j 0;i r;i ,j )q[i] temp[j];
}逆序数
while(i mid j r){if(q[i] q[j]){temp[k ] q[j ];sum mid - i 1;}else temp[k ] q[i ];}
cout sum endl;字符串处理
int index str.find(a);string newstr str.substr(startIndex,count);向量vector map queue stack
vectorint vectore;vectore.push_back(i);
vectore.pop_back();for(int i 0;i vectore.size();i )// map自带对键排序进行迭代
mapint,string::iterator it;
for(it str.begin();it ! str.end();it ){cout it-second endl;
}queueAnimal cats;
dogs.front().numberstackint s;
s.push(i);
s.pop();
s.top();
s.empty();最大公约数、最小公倍数
int gcd(int a,int b){return b ? gcd(b,a % b):a;
}// 最小公倍数
min (a * b) / gcd;最长子序列和问题 最长公共序列
for(int i1;in;i){a[i]max(a[i],a[i-1]a[i]);answermax(answer,a[i]);}coutanswerendl;for (int i 1; i a.size(); i) {for (int j 1; j b.size(); j) {if (a[i - 1] b[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}
}背包问题
const int N 1010;
int n,m;//物品数量和背包容积
int v[N],w[N];
int f[N];int main(){cin n m;for(int i 1;i n;i ){cin v[i] w[i];}for(int i 1;i n;i ){for(int j m;j v[i];j --){//2种情况f[j] max(f[j],f[j - v[i]] w[i]);//背包有空间}}cout f[m] endl;return 0;
}
// 完全
for(int i 1;i n;i ){for(int j v[i];j m;j ){f[j] max(f[j],f[j - v[i]] w[i]);}}进制转化
数比较小
void convert(int n,int b){while(n){a[cnt ] n % b;n n / b;}
}cin n b;convert(n,b);for(int i cnt - 1;i 0;i --)cout a[i];
高精度:s原字符串m是原进制b是转换后的进制
string convert(string s, int m, int b) {string ans; while (!s.empty()) {int k 0; // 余数bool leadingZero true; // 用于去除前导零string temp;for (int i 0; i s.size(); i) {// 如果是字母字符用于大于10的进制则转换为对应的值如A - 10, B - 11int digit (isdigit(s[i]) ? s[i] - 0 : s[i] - A 10);int t (k * m digit) % b;int quotient (k * m digit) / b;k t;if (quotient ! 0 || !leadingZero) {temp (quotient 10 ? quotient 0 : quotient - 10 A);leadingZero false;}}ans (k 10 ? k 0 : k - 10 A);s temp;}reverse(ans.begin(), ans.end());return ans.empty() ? 0 : ans;
}
16进制到10进制
int CharToInt(char c){if(c 0 c 9) return c - 0;else return c - A 10;
}
int main() {string str;while (cin str) {int x 0;for(int i 2; i str.length(); i ){x x * 16 CharToInt(str[i]);}cout x endl;}return 0;
}
单词替换字符串 getline(cin,s);cin a b;for(int i 0;i s.size();i ){int j i;string word;// s[j]不为空格时把他加到单词序列中相当于split while(j s.size() s[j] ! )word s[j ];i j;if(word a)cout b ;else cout word ;}结构体应用
// 定义一个结构体 point用来存储字符的相关信息
struct point {int num; // 记录字符在字符串中出现的次数vectorint AA; // 记录字符在字符串中出现的位置索引bool flag false; // 用来判断是不是该字符第一次被输出
};int main() {string s; // 用来存储输入的字符串mapchar, point mapp; // 定义一个映射用来存储每个字符及其对应的 point 结构体while (cin s) { // 逐行读取输入的字符串// 第一次遍历字符串统计每个字符的出现次数for (int i 0; i s.size(); i) {mapp[s[i]].num;}// 第二次遍历字符串记录每个字符的出现位置如果出现次数大于1for (int i 0; i s.size(); i) {if (mapp[s[i]].num 1) {mapp[s[i]].AA.push_back(i);}}// 第三次遍历字符串输出每个出现次数大于1且还未被输出的字符及其出现的位置for (int i 0; i s.size(); i) {if (mapp[s[i]].num 1 mapp[s[i]].flag false) {for (int j 0; j mapp[s[i]].AA.size(); j) {if (j 0)printf(%c:%d, s[i], mapp[s[i]].AA[j]);elseprintf(,%c:%d, s[i], mapp[s[i]].AA[j]);}cout endl;mapp[s[i]].flag true; // 标记该字符已被输出}}}return 0;
}
约瑟夫环问题
int main() {int n, p, m; // n多少人p从哪里开始m经过多少人淘汰 while (cin n p m (n || p || m)) {queueint children;for (int i 1; i n; i) {children.push(i);}// 将队列旋转到第p个小孩开始for (int i 1; i p; i) {children.push(children.front());children.pop();}while (!children.empty()) {// 报数到第m个for (int i 1; i m; i) {children.push(children.front());children.pop();}// 输出当前出圈的小孩编号cout children.front();children.pop();if (!children.empty()) {cout ,;}}cout endl;}return 0;
}
素数
bool isPrime(int n)
{if(n 1 || n 0 || n 0)return false; for(int i 2; i sqrt(n); i) {if(n % i 0)return false;}return true;
}埃氏筛法
const int maxn 10000000;
int prime[maxn];
bool IsPrime[maxn] {0};//0代表都是素数
void Find_Prime(){IsPrime[1] 1;//1不是素数int pNum 1;for(int i 2; i maxn; i){if(!IsPrime[i])prime[pNum] i;for(int j i * i; j maxn; j i){IsPrime[j] true;}}
}printf(%d\n, prime[k]);质因数约数 int ret 0;// 从 2 开始尝试每个可能的因数直到 sqrt(n)for (int i 2; i sqrt(n); i) {// 如果 i 是 n 的一个因数while (n % i 0) {ret; // 计数器加一n / i; // 用 i 除去 n 的这个因数}// 如果 n 已经被完全分解提前退出循环if (n 1) break;}// 如果存在大于 sqrt(n) 的质因数则它只能是 n 本身if (n 1) ret;return ret;
约数
int Counter(int x){int count 0; int i 1;for(i 1;i * i x;i ){if(x % i 0)count 2;}if(i * i x) count ;return count;
}快速幂
typedef long long LL;
LL a,n;LL ksm(LL a, LL n){LL ans 1;while(n){if(n 1)ans * a;//如果n的最后一位是1 a * a;n 1; //二进制去掉最后一个1*2 }return ans;
} int main(){cin a n;cout ksm(a,n);高精度加减乘除
// C A B, A 0, B 0
vectorint add(vectorint A, vectorint B)
{if (A.size() B.size()) return add(B, A);vectorint C;int t 0;for (int i 0; i A.size(); i ){t A[i];if (i B.size()) t B[i];C.push_back(t % 10);t / 10;}if (t) C.push_back(t);return C;
}// C A - B, 满足A B, A 0, B 0
vectorint sub(vectorint A, vectorint B)
{vectorint C;for (int i 0, t 0; i A.size(); i ){t A[i] - t;if (i B.size()) t - B[i];C.push_back((t 10) % 10);if (t 0) t 1;else t 0;}while (C.size() 1 C.back() 0) C.pop_back();return C;
}// C A * b, A 0, b 0
vectorint mul(vectorint A, int b)
{vectorint C;int t 0;for (int i 0; i A.size() || t; i ){if (i A.size()) t A[i] * b;C.push_back(t % 10);t / 10;}while (C.size() 1 C.back() 0) C.pop_back();return C;
}// A / b C ... r, A 0, b 0
vectorint div(vectorint A, int b, int r)
{vectorint C;r 0;for (int i A.size() - 1; i 0; i -- ){r r * 10 A[i];C.push_back(r / b);r % b;}reverse(C.begin(), C.end());while (C.size() 1 C.back() 0) C.pop_back();return C;
}KMP
// s[]是长文本p[]是模式串n是s的长度m是p的长度
求模式串的Next数组
for (int i 2, j 0; i m; i )
{while (j p[i] ! p[j 1]) j ne[j];if (p[i] p[j 1]) j ;ne[i] j;
}// 匹配
for (int i 1, j 0; i n; i )
{while (j s[i] ! p[j 1]) j ne[j];if (s[i] p[j 1]) j ;if (j m){j ne[j];// 匹配成功后的逻辑}
}BFS走迷宫
#include iostream
#include queue#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N 1e3 10;int n,m;
int g[N][N];
int d[N][N];
int dx[4] {1,-1,0,0},dy[4] {0,0,1,-1};void bfs(int u){queueint q;q.push({1,1});memset(d,-1,sizeof(d));d[1][1] 0;while(q.size()){PII t q.front();q.pop();for(int i 0;i 4;i ){int a t.x dx[i];int b dy[i] t.y;if(a 1 || a n || b 1 || b m)continue;if(g[a][b] 1)continue;if(d[a][b] ! -1)continue;d[a][b] d[t.x][t.y] 1;q.push({a,b});}}
}int main(){cin n m;for(int i 0;i n;i ){for(int j 0;j n;j ){cin g[i][j];}}bfs();cout d[n][m] endl;return 0;
}N皇后问题DFS
#include iostreamusing namespace std;const int N 20; // 对角线元素2n-1取20防止越界
int n;
char g[N][N]; // 存储图
bool col[N],dg[N],udg[N]; // udg副对角线 diagonal
int cnt;void dfs(int x){if(x n){ // 如果找到方案的话 for(int i 0;i n;i ){puts(g[i]); // puts输出二维数组 输出每一行就会自动换行}puts();cnt ;return; // 返回调用函数进行执行 }// x : 行 y : 列for(int y 0;y n;y ){// 按行枚举 因为每一行都需要放皇后 相当于剪枝 // 判断皇后是否放在这格if(!col[y] !dg[x y] !udg[y - x n]){g[x][y] Q;col[y] dg[x y] udg[y - x n] true;dfs(x 1); // 找下一行// 回溯的时候恢复现场col[y] dg[x y] udg[y - x n] false;g[x][y] .; } }
}
int main(){cin n;for(int i 0;i n;i ){for(int j 0;j n;j ){g[i][j] .;}} dfs(0); // 从第一行开始找[0:下标] return 0;
}链表类型
链表反转
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *cur head, *pre nullptr;while(cur ! nullptr) {ListNode* tmp cur-next; // 暂存后继节点 cur.nextcur-next pre; // 修改 next 引用指向pre cur; // pre 暂存 curcur tmp; // cur 访问下一节点}return pre;}
};回文链表
class Solution {
public:bool isPalindrome(ListNode* head) {vectorint vals;while (head ! nullptr) {vals.emplace_back(head-val);head head-next;}for (int i 0, j (int)vals.size() - 1; i j; i, --j) {if (vals[i] ! vals[j]) {return false;}}return true;}
};环形链表
public class Solution {public boolean hasCycle(ListNode head) {SetListNode seen new HashSetListNode();while (head ! null) {if (!seen.add(head)) {return true;}head head.next;}return false;}
}排序链表
class Solution {
public:ListNode* sortList(ListNode* head) { return mergeSort(head);}/*** 对给定的链表进行归并排序*/ListNode* mergeSort(ListNode* head){// 如果链表为空或只有一个节点无需排序直接返回if(!head || !head-next){return head; }// 获取链表的中间节点分别对左右子链表进行排序ListNode* mid getMid(head);ListNode* rightSorted mergeSort(mid-next); // 排序右子链表if(mid)mid-next nullptr; // 断开两段子链表ListNode* leftSorted mergeSort(head); // 排序左子链表return mergeTwoLists(leftSorted, rightSorted); // 两个子链表必然有序合并两个有序的链表}/*** 获取以head为头节点的链表中间节点* 如果链表长度为奇数返回最中间的那个节点* 如果链表长度为偶数返回中间靠左的那个节点*/ListNode* getMid(ListNode* head){if(!head)return head; ListNode* slow head, *fast head-next; // 快慢指针慢指针初始为while(fast ! nullptr fast-next ! nullptr) {fast fast-next-next; // 快指针每次移动两个节点slow slow-next; // 慢指针每次移动一个节点}return slow; // 快指针到达链表尾部时慢指针即指向中间节点}/*** 合并两个有序链表list1和list2*/ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy new ListNode(); // 伪头节点用于定位合并链表的头节点ListNode* node dummy; // 新链表当前的最后一个节点初始为伪头节点// 直到两个链表都遍历完了合并结束while(list1 ! nullptr || list2 ! nullptr){int val1 list1 nullptr ? 50001 : list1 - val; // 如果链表1已经遍历完val1取最大值保证链表2的节点被选择到 int val2 list2 nullptr ? 50001 : list2 - val; // 如果链表2已经遍历完val2取最大值保证链表1的节点被选择到 if(val1 val2){// 链表1的节点值更小加入到合并链表并更新链表1指向的节点node - next list1;list1 list1 - next;}else{// 链表2的节点值更小加入到合并链表并更新链表2指向的节点node - next list2;list2 list2 - next;}node node - next; // 更新合并链表当前的最后一个节点指向}return dummy - next; // 伪头节点的下一个节点即为合并链表的头节点}
};
合并两个有序链表
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 nullptr) {return l2;} else if (l2 nullptr) {return l1;} else if (l1-val l2-val) {l1-next mergeTwoLists(l1-next, l2);return l1;} else {l2-next mergeTwoLists(l1, l2-next);return l2;}}
};是否含有子链表
struct Link {int data;struct Link *next;
};
#include stdio.h
void subList(Link *a,Link *b) {struct Link *la a ,*pA la-next, *pB b-next;while (pApB) {if (pA-datapB-data) {//相等继续对比下一个pA pA-next;pB pB-next;}else {pB b-next;//pb从头开始与pa对比la la-next;//失败一次la往后移动一个节点pA la-next;//pa从下一个节点又开始}}pB NULL ? printf(true) : printf(false);//如果pb为NULL说明已比对完成
}
int main() {struct Link *a, *b;Link *createLink(int);a createLink(0);b createLink(0);subList(a,b);return 0;
}合并链表 /*有两个循环单链表链表头指针分别为h1和h2编写一个函数将链表h2连接到h1之后要求连接后的链表仍保持循环链表形式。*/struct Link {int data;struct Link *next;};void linkTwoLists(Link *h1,Link *h2) {struct Link *p1 h1-next, *p2 h2-next;while (p1-next ! h1) p1 p1-next;//这里要去判断p1-next是否等于h1进而判断出是否到达尾结点p1-next p2;while (p2-next ! h2) p2 p2-next;p2-next h1;free(h2);//释放h2}int main() {struct Link *h1, *h2,*p;Link *createSinLoopLink();h1 createSinLoopLink();h2 createSinLoopLink();linkTwoLists(h1,h2);p h1-next;while (p!h1) {printf(%d ,p-data);p p-next;}return 0;}输出链表倒数第K个结点
ListNode *findKthTail(ListNode *pHead, int K) {ListNode *p1(pHead), *p2(pHead);for(int i0; iK; i){p1 p1- next;if(!p1){return nullptr;}}while(p1){p1 p1- next;p2 p2- next;}return p2;
}
两数相加
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* first new ListNode(0); // 哑结点ListNode* last first;int carry 0;while(l1 or l2 or carry){// 相加int bitsum 0;if(l1){bitsum l1-val;l1 l1-next;}if(l2){bitsum l2-val;l2 l2-next;}if(carry){bitsum carry;}// 结果int digit bitsum % 10;carry bitsum / 10;// 链表存储ListNode* node new ListNode(digit);last-next node;last node;}last first-next;delete first;return last;}
};
计算循环链表中环的长度
int getLoopLength(ListNode *pHead) {ListNode *fast(pHead), *slow(pHead);while (fast fast-next) {fast fast-next-next;slow slow-next;if (fast slow) {break;}}if (!fast || !fast-next) return -1;int length 1; // 从1开始while (slow-next ! fast) {slow slow-next;length;}return length;
}
先序遍历
void preorder(TreeNode *root, vectorint res) {if (root nullptr) {return;}res.push_back(root-val);preorder(root-left, res);preorder(root-right, res);}vectorint preorderTraversal(TreeNode *root) {vectorint res;preorder(root, res);return res;}层序遍历
vectorvectorint levelOrder(TreeNode* root) {vector vector int ret;if (!root) {return ret;}queue TreeNode* q;q.push(root);while (!q.empty()) {int currentLevelSize q.size();ret.push_back(vector int ());for (int i 1; i currentLevelSize; i) {auto node q.front(); q.pop();ret.back().push_back(node-val);if (node-left) q.push(node-left);if (node-right) q.push(node-right);}}return ret;完全二叉树的节点个数
int countNodes(TreeNode* root) {if(!root)return 0;return countNodes(root - left) countNodes(root - right) 1;}每个人戴不同帽子的方案数
using LL long long;class Solution {
private:static constexpr int mod 1000000007;public:int numberWays(vectorvectorint hats) {int n hats.size();// 找到帽子编号的最大值这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案int maxHatId 0;for (int i 0; i n; i) {for (int h: hats[i]) {maxHatId max(maxHatId, h);}}// 对于每一顶帽子 hhatToPerson[h] 中存储了喜欢这顶帽子的所有人方便进行动态规划vectorvectorint hatToPerson(maxHatId 1);for (int i 0; i n; i) {for (int h: hats[i]) {hatToPerson[h].push_back(i);}}vectorvectorint f(maxHatId 1, vectorint(1 n));// 边界条件f[0][0] 1;for (int i 1; i maxHatId; i) {for (int mask 0; mask (1 n); mask) {f[i][mask] f[i - 1][mask];for (int j: hatToPerson[i]) {if (mask (1 j)) {f[i][mask] f[i - 1][mask ^ (1 j)];f[i][mask] % mod;}}}}return f[maxHatId][(1 n) - 1];}
};同构字符串
bool isIsomorphic(string s, string t) {if(s.size() ! t.size())return false;unordered_mapchar,char s1;unordered_mapchar,char s2;for(int i 0;i s.size();i ){char x s[i],y t[i];if((s1.count(x) s1[x] ! y) || (s2.count(y) s2[y] ! x))return false;s1[x] y;s2[y] x;}return true;}因篇幅受限如需查看完整版内容请点击“上述的link”.
