PAT考试错误总结（一）

た入场券 2021-11-16 16:56 328阅读 0赞

1002：多项式系数不能为0  
**不认识单词**：polynomial多项式 exponent指数 coefficient系数

1003：dijk最短路径算法

1004：level初始化不合适，应该初始化为1  
**不认识单词**：hierarchy层 pedigree tree谱系树

1005：有可能会出现未给变量index1,index2初始化的情况，导致测试点3段错误  
**不认识单词**：subsequence子序列

1009：多项式系数不能为0，一开始想着相乘不可能乘出来是0，后来想到在插入到map中的时候可能会出现负系数项和正系数项相加出现系数为0的情况

1010：二分法，找到上下界范围，要注意的是如果value < res，应该是left = mid + 1,而不是left = mid，因为这样最后有可能会一直在mid死循环，循环限制使用 while (left < right）即可；同时这道题还需要注意溢出的问题，int类型不断相加可能会造成类型溢出  
**不认识单词**：binary number二进制数 demical十进制

1013：利用dfs算法，每次遍历后即将一个连通分量上的点设为已访问，这样遍历完所有的点所需要调用的dfs次数，即为这个图中连通变量的个数  
**不认识单词**：vitally极其地

1014：deque的使用，用popTime表示队列队首出队时间，endTime表示队列队尾出队时间

1015：某进制下的素数应该是，先换成那个进制的数，再倒过来，再转成十进制数，再判断是否是素数，真的好题（keng de yi pi) =!=

1016：消费金额为0的不能算作顾客

1018：dijk + dfs，dijk用来获得最短路径，以及获得最短路径上的点，dfs用来模拟遍历最短路径，当dfs(0)的时候来获取权重，计算need，这里dfs和一般的dfs不同的是，不再是遍历所有的点，而是遍历所有的最短路径

1019：这里应该用int类型容器来存储余数，因为不确定进制数，如果用string存储，会存进去很多符号（因为 n % b + ‘0’）

1020：递归，每次获取到根结点，再用相同的方法遍历左右子树。  
**后序遍历的最后一个为根节点，然后通过中序遍历找到根节点后，就可以得到左右子树的结点数目，再回到后序遍历中可以得到左右子树的根节点，如此一直递归即可**  
不认识单词：preorder前序 inorder中序 postorder后序 sequence层序 traversal遍历

1021：定义maps\[N\]\[N\]造成内存超限，因为N的范围为10000，数组占内存过大，这里用vectot`<int>` maps\[N\]来代替maps\[N\]\[N\]，存储数据的时候把某的点有连接的其他点push到对应的vector中进行处理  
不认识单词：acyclic非循环的

1022：可以用stringstream来分割字符串，下面给出一个例子：

#include<iostream>
    #include<string>
    #include<sstream>
    #include<vector>
    using namespace std;
    
    int main(){
        //用于存放分割后的字符串 
        vector<string> res;
        //待分割的字符串，含有很多空格 
        string word="   Hello, I want   to learn C++!   ";
        //暂存从word中读取的字符串 
        string result;
        //将字符串读到input中 
        stringstream input(word);
        //依次输出到result中，并存入res中 
        while(input>>result)
            res.push_back(result);
        //输出res 
        for(int i=0;i<res.size();i++){
            cout<<res[i]<<endl;
        }
        return 0;
    }

1025：暂时不知道错误原因

1026：有两个问题疏忽了，第一个是如果玩家到达时间就超过了21点也不可以玩，第二个是如果第一次获取到的最短时间的桌子是小于玩家到达时间的，那么需要再重新遍历获取桌子，因为玩家这时候要的就不是最短时间的桌子了，是所有结束时间小于玩家到达时间的桌子中编号最小的那个桌子，同时如果是vip玩家，那么就是最小编号的vip桌子

1028：有进制转换后前面需要补的‘0’不止一个

1029：归并排序 + 二分查找

1030：dijk获取最短路径中每个点能连接的点，dfs遍历这些点来获取最短开销和最短开销的最短路径路过的点，考虑能不能直接就用dfs来遍历，下次写的时候尝试一下

1032：比较链表共同后缀，这道题可以不用把两个链表存放到vector中，可以用map巧妙解决比较问题  
**不认识单词**：sublist子表 suffix后缀

1033：测试点0错误，我觉得给出的测试用例答案不对，应该是747.91才对，749.17是中间 150 \* 7 / 12 全部按照int类型计算，导致了进制强转时数据遗漏的结果，暂时留到以后再解决吧

1035：**不认识单词**：distinguish区分

1038：有几个点可以注意：  
1.字符串比较采用将两个字符串加起来再比较是最好的  
2.输出第一个数必须非0  
3.要注意全是0 的情况

1039: 如果size为0就不要再做排序这些操作了，不然会超时

1040：**不认识单词**：symmetric对称的

1043：二叉搜索树的性质就是左子树的所有值都不大于根节点，右子树的所有值不小于根节点，序遍历之间的转换就在于找到左右子树的根节点的表达式，然后按照指定的顺序递归方法

1047：用printf和scanf解决超时问题

1048：不能使用暴力遍历，可以对每一位进行判断，看是否能取到1，然后不看这一位，看剩下的位数能够排列组合为多少种数，即为这个位数的1的数目，然后依次得到所有位数的可以获得的1的个数，加起来即可

1051：stack的成员函数示例：

size( ) :返回栈中元素个数
    top( ) :返回栈顶的元素
    pop( ) :从栈中取出并删除元素
    push(e) :向栈中添加元素e
    empty( ) :栈为空时返回true

1052：没有正确判断链表为空的情况，这道题不能通过判断容器size为0来判断，因为如果第一个结点就不存在，在放入容器的时候就会出现放未初始化的结构体对象进去的问题，在输出的时候有可能会出现异常

1053：dfs遍历，到指定的路径大小输出即可，排序的问题上稍微纠结了一会儿，看了一篇博客发现居然可以直接用vector比较大小…

bool cmp(vector<int> v1, vector<int> v2){
        return v1 > v2;
    }

1055：这道题第二个测试点会超时，主要有以下问题:  
1.不要滥用algorithm下的sort排序，虽然很方便，但是用的次数多容易超时  
2.使用scanf，scanf接收字符串类型的方法如下：

string a;
    	a.resize(100); //需要预先分配空间 这点很重要，否则报错
    	scanf("%s", &a[0]);

这道题我们分配9即可，因为他说了名字字符串除了空格不超过8个字符，不过要注意的是如果获取到的字符串没有那么长，需要用substr()来判断，因为后面会默认一直填充”/000“

if(a.substr(0,3) == "abc"){...}

1056：定义结构体做吧，实在是麻烦这道题，题意就不好理解，理解了题意也不好模拟

1057：  
1.C++ Stack（堆栈） 是一个容器类的改编，为程序员提供了堆栈的全部功能，  
——也就是说实现了一个先进后出（FILO）的数据结构。  
它不支持遍历，如果非要遍历只能用pop一个一个输出，那么遍历一次以后堆栈  
将为空，如果需要实现相关操作的话，可以选择用双向队列deque来替代stack

2.C++switch不支持使用string类型作为判断条件

3.直接写会超时，需要用树状数组和二分法结合，树状数组在最新考纲里不在PAT甲级的范围内，所以不纠结这道题了

1058：注意数据类型的溢出，这里需要使用long类型

1059：判断开始的数是否为1

1065：要判断溢出的情况，如果都为正但结果为负，以及如果都为负但结果为正的情况