大家好，又见面了，我是你们的朋友全栈君。
pat试题总结
遍历问题的总结
- dfs中，如果是有环的图，要设置visited数组防止绕圈，同时在dfs函数退出前要将visited数组相应设置为false，否则其他路径就不能遍历该结点；
- 在问题中，如果要求“从一个序列中选取若干个元素来满足条件”，可以考虑dfs，如1103 Integer Factorization (30分)和7-1 Forever (20分)；
- 在写dfs前，罗列需要设置的全部变量，然后在dfs边界上，逐一考虑对这些变量的值的修改，可以避免漏掉某个变量的修改；
- 动手写代码前仔细考虑“什么由什么确定”可以省去debug时的思维定势，如1131 Subway Map (30分)通过两个邻站作为键可以确定一条线路，但是考察“两个邻站都属于哪条线路”却不能确定线路；又如1018 Public Bike Management (30分)，发车数send和收回数back并不满足最优子结构，靠贪心算法选择路径是行不通的。
字符串处理总结
- 字符串处理中，注意利用sscanf，可以按照格式读取字符串中的数字，如
sscanf(s, “The root is %d”, &root)提取int型变量root； - 当不合法情况较多时，不逐个判断不合法的情况，而是只允许合法的情况通过，如判断是否合法数字：只可能有一个小数点、若干位数字、负号只能有一个且出现在头部。
- 熟悉数字和字符串的互相转化。
数学问题总结
- 数学问题中，常用的函数如下：
//辗转相除法求最大公因数
int gcd(int a, int b) {
return b == 0 ? a: gcd(b, a % b);
}
//埃筛对素数进行打表
bool prime[100];
void getPime() {
fill(prime + 2, prime + 100, true);
for(int i = 2; i < 100; i++) {
if(prime[i]) {
int factor = 2;
while(i * factor < 100) {
prime[i * factor] = false;
}
++factor;
}
}
}
//判断素数的函数
bool isPrime(int num) {
int n = sqrt(num);
for(int i = 0; i <= n; i++) {
if(num % i == 0)
return false;
}
return true;
}
- 在一些处理中，可以考虑负号、小数点单独处理，可以有效化简判断条件；
- 进制转换，主要用除基取余法和乘基取整法。
- 没有好方法时，尝试找规律化简解法。
排序问题的总结
- 熟记各种排序代码的编写。
插入排序：每次将无序的子数组中的头部元素插入到有序子数组中；
冒泡排序：游标从前往后扫描，如果前后两个元素逆序，则交换；
选择排序：每次从无序部分选一个最小的，和有序部分的后面的元素交换；
快速排序：选取数组中的一个元素作为pivot，将它藏到最左边，两个游标left, right根据pivot的大小不断交换元素，当两游标相遇时，left指示的就是pivot应该放的位置；
堆排序：先自底向上建堆，每次从堆顶拿出元素，用数组尾的元素顶上，然后将堆顶元素下滤； - 对时间的处理，可以先将时间化成秒为单位，必要时再转换回时分秒。
- 必要时先剔除无效数据，从有效数据中寻找结果；
- 当一个问题有多个查询时，先处理好数据，在处理查询时可以直接返回结果。如果每查询一次就排序一次，可能会超时；
- 仔细阅读排序条件，避免遗漏或出错。
树类问题的总结
- 熟记给出两个序列构造树的代码以及1119 Pre- and Post-order Traversals (30分)前序和后序不唯一地建树；
- 熟记AVL树左旋、右旋的写法，注意旋转后要更新子结点和和父结点的高度，注意更新高度的时机；
- 先写好模版代码，再根据问题需要修改；
- 思考实现的代码和问题的描述逻辑上的不一致，如1135 Is It A Red-Black Tree (30分)要求的是”每个结点到叶结点的黑结点数相同“，而不仅仅是根结点到叶结点。
模拟问题的总结
- 合适地选取数据结构，如1129 Recommendation System 数据出现的次数不断变化，同时又要求根据出现次数有序，所以考虑红黑树实现的
set； - 充分考虑、化简模拟的事件要满足的条件，如1128 N Queens Puzzle (20分)中，”两个皇后不能在同一对角线“，说明两个皇后连线的斜率不能为1；
- 当模拟的事件有时间轴时，考虑设置一个变量模拟时间的流逝。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/128736.html原文链接：https://javaforall.net
