PAT乙级第二天记录——反转链表（纯数组解）
第一题
给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
奇奇怪怪的错误
后面发现是我main函数return 1
搜了网友的回答：shell返回值非0是程序退出异常，说明你的代码抛出了异常。
soga！！！
首先这题并没有用到链表结构而是用几个容量大的数组把数据存起来，存起来之后再用一个数组把节点地址线性存起来，节点下一个地址就是下一个位置的值，太妙了😁！！！反转的话直接在地址上反转就行丝毫不影响数据之间的变化。
原本我的代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
int first,N,K,tmp;
int next[100000],data[100000],list[100000];
cin >> first >> N >> K;
for(int i=0;i<N;i++){
cin >> tmp;
cin >> data[tmp] >> next[tmp];
}
int sum = 0; // 不是所有节点都在链上
//用list数组构造链表
for(int i=0;first != -1;i++){
list[sum++] = first;
first = next[first];
}
//反转链表
for(int i=0;i<sum-i*K;i+=K){
reverse(begin(list)+i,begin(list)+i+K);
}
for(int i=0;i<sum-1;i++){
printf("%05d %d %05d\n",list[i],data[list[i]],list[i+1]);
}
printf("%05d %d -1",list[sum-1],data[list[sum-1]]);
return 0;
}
这里的错误主要是【i<sum-i*K】。
我真是脑残，i的值是会变的呀，只能说我写的时候思维好不严谨😢
修改后：
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
int first,N,K,tmp;
int next[100000],data[100000],list[100000];
cin >> first >> N >> K;
for(int i=0;i<N;i++){
cin >> tmp;
cin >> data[tmp] >> next[tmp];
}
int sum = 0; // 不是所有节点都在链上
//用list数组构造链表
for(int i=0;first != -1;i++){
list[sum++] = first;
first = next[first];
}
//反转链表
for(int i=0;i<=sum - sum % K;i+=K){
reverse(begin(list)+i,begin(list)+i+K);
}
for(int i=0;i<sum-1;i++){
printf("%05d %d %05d\n",list[i],data[list[i]],list[i+1]);
}
printf("%05d %d -1",list[sum-1],data[list[sum-1]]);
return 1;
}
第二题
让我们定义dn为：dn=pn+1−pn，其中p*i是第i个素数。显然有d*1=1，且对于n>1有*dn*是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数。
现给定任意正整数N(<105)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
这题显然是素数问题，写个判断素数就行，差为2的话少于5的都是0个，大于5才有素数对；
这里柳神判断素数是
i * i <= n,这样都不用考虑用开平方的函数了
代码：
#include<iostream>
using namespace std;
int isprime(int n){
for(int i=2;i * i <= n;i++){
if(n % i == 0){
return 0;
}
}
return 1;
}
int main(void){
int n,cnt = 0;
cin >> n;
for(int i=5;i<=n;i+=2){
if(isprime(i) && isprime(i-2)) cnt++;
}
cout << cnt;
}
第二题
On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.
Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.
Input Specification:
Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters [A-Z] (case insensitive), digital numbers [0-9], or _ (representing the space). It is guaranteed that both strings are non-empty.
Output Specification:
For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.
Sample Input:
7_This_is_a_test
_hs_s_a_es
Sample Output:
7TI
这是一道甲级题，但是非常简单，题目大意就是找不完整的字母，然后用大写字母输出，但是每个大写字母只输出一次。
用c++中string的find函数即可，
string::npos是没有找到的意思。
#include<iostream>
#include<cctype>
using namespace std;
int main(void){
string s1,s2,ans;
cin >> s1 >> s2;
for(int i=0;i<s1.length();i++){
if(s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos){
ans += toupper(s1[i]);
}
}
cout << ans;
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 jaytp@qq.com
