Code – 第209页

已知后序与中序输出前序（先序）

已知后序与中序输出前序（先序）：
后序：3, 4, 2, 6, 5, 1（左右根）
中序：3, 2, 4, 1, 6, 5（左根右）
分析：因为后序的最后一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打印右子树。左子树在后序中的根结点为root – (end – i + 1)，即为当前根结点-(右子树的个数+1)。左子树在中序中的起始点start为start，末尾end点为i – 1.右子树的根结点为当前根结点的前一个结点root – 1，右子树的起始点start为i+1，末尾end点为end。
输出的前序应该为：1, 2, 3, 4, 5, 6（根左右）

#include <cstdio>
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
void pre(int root, int start, int end) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1);
    pre(root - 1, i + 1, end);
}

int main() {
    pre(5, 0, 5);
    return 0;
}

#include <cstdio>

using namespace std;

int post[] = {3, 4, 2, 6, 5, 1};

int in[] = {3, 2, 4, 1, 6, 5};

void pre(int root, int start, int end) {

if(start > end) return ;

int i = start;

while(i < end && in[i] != post[root]) i++;

printf("%d ", post[root]);

pre(root - 1 - end + i, start, i - 1);

pre(root - 1, i + 1, end);

}

int main() {

pre(5, 0, 5);

return 0;

}

已知前序（先序）与中序输出后序（建树）

已知前序（先序）与中序输出后序：
前序：1, 2, 3, 4, 5, 6（根左右）
中序：3, 2, 4, 1, 6, 5（左根右）
分析：因为前序（根左右）最先出现的总是根结点，所以令root为前序中当前的根结点下标（并且同时把一棵树分为左子树和右子树）。start为当前需要打印的子树在中序中的最左边的下标，end为当前需要打印的子树在中序中最右边的下标。递归打印这棵树的后序，递归出口为start > end。i为root所表示的值在中序中的下标，所以i即是分隔中序中对应root结点的左子树和右子树的下标。
先打印左子树，后打印右子树，最后输出当前根结点pre[root]的值。
输出的后序应该为：3, 4, 2, 6, 5, 1（左右根）

#include <cstdio>
using namespace std;
int pre[] = {1, 2, 3, 4, 5, 6};
int in[] = {3, 2, 4, 1, 6, 5};
void post(int root, int start, int end) {
    if(start > end) 
        return ;
    int i = start;
    while(i < end && in[i] != pre[root]) i++;
    post(root + 1, start, i - 1);
    post(root + 1 + i - start, i + 1, end);
    printf("%d ", pre[root]);
}

int main() {
    post(0, 0, 5);
    return 0;
}

#include <cstdio>

using namespace std;

int pre[] = {1, 2, 3, 4, 5, 6};

int in[] = {3, 2, 4, 1, 6, 5};

void post(int root, int start, int end) {

if(start > end)

return ;

int i = start;

while(i < end && in[i] != pre[root]) i++;

post(root + 1, start, i - 1);

post(root + 1 + i - start, i + 1, end);

printf("%d ", pre[root]);

}

int main() {

post(0, 0, 5);

return 0;

}

TreeNode* buildTree(int root, int start, int end) {
    if(start > end) return NULL;
    int i = start;
    while(i < end && in[i] != pre[root]) i++;
    TreeNode* t = new TreeNode();
    t->left = buildTree(root + 1, start, i - 1);
    t->right = buildTree(root + 1 + i - start, i + 1, end);
    t->data = pre[root];
    return t;
}

TreeNode* buildTree(int root, int start, int end) {

if(start > end) return NULL;

int i = start;

while(i < end && in[i] != pre[root]) i++;

TreeNode* t = new TreeNode();

t->left = buildTree(root + 1, start, i - 1);

t->right = buildTree(root + 1 + i - start, i + 1, end);

t->data = pre[root];

return t;

}

L1-009. N个数求和-PAT团体程序设计天梯赛GPLT

输入格式：
输入第一行给出一个正整数N（<=100）。随后一行按格式“a1/b1 a2/b2 …”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：
输出上述数字和的最简形式 —— 即将结果写成“整数部分分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：
5
2/5 4/15 1/30 -2/60 8/3
输出样例1：
3 1/3
输入样例2：
2
4/3 2/3
输出样例2：
2
输入样例3：
3
1/3 -1/6 1/8
输出样例3：
7/24

分析：先根据分数加法的公式累加，后分离出整数部分和分数部分～
分子和分母都在长整型内，所以不能用int存储，否则有一个测试点不通过～
一开始一直是浮点错误，按理来说应该是出现了/0或者%0的情况，找了半天也不知道错在哪里～
后来注意到应该在累加的时候考虑是否会超出long long的范围，所以在累加每一步之前进行分子分母的约分处理，然后就AC了～
应该还要考虑整数和小数部分都为0时候输出0的情况，但是测试用例中不涉及，所以如果没有最后两句也是可以AC的～

#include <cstdio>
#include <cstdlib>
using namespace std;
long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
int main() {
    long long n, a, b, suma = 0, sumb = 1, gcdvalue;
    scanf("%lld", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld/%lld", &a, &b);
        gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));
        sumb = sumb / gcdvalue;
        suma = suma / gcdvalue;
        gcdvalue = (a == 0 || b == 0) ? 1 : gcd(abs(a), abs(b));
        a = a / gcdvalue;
        b = b / gcdvalue;
        suma = a * sumb + suma * b;
        sumb = b * sumb;
    }
    long long integer = suma / sumb;
    suma = suma - (sumb * integer);
    gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));
    suma = suma / gcdvalue;
    sumb = sumb / gcdvalue;
    if(integer != 0) {
        printf("%lld", integer);
        if(suma != 0)
            printf(" ");
    }
    if(suma != 0) {
        printf("%lld/%lld", suma, sumb);
    }
    if(integer == 0 && suma == 0)
        printf("0");
    return 0;
}

#include <cstdio>

#include <cstdlib>

using namespace std;

long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}

int main() {

long long n, a, b, suma = 0, sumb = 1, gcdvalue;

scanf("%lld", &n);

for(int i = 0; i < n; i++) {

scanf("%lld/%lld", &a, &b);

gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));

sumb = sumb / gcdvalue;

suma = suma / gcdvalue;

gcdvalue = (a == 0 || b == 0) ? 1 : gcd(abs(a), abs(b));

a = a / gcdvalue;

b = b / gcdvalue;

suma = a * sumb + suma * b;

sumb = b * sumb;

}

long long integer = suma / sumb;

suma = suma - (sumb * integer);

gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));

suma = suma / gcdvalue;

sumb = sumb / gcdvalue;

if(integer != 0) {

printf("%lld", integer);

if(suma != 0)

printf(" ");

}

if(suma != 0) {

printf("%lld/%lld", suma, sumb);

}

if(integer == 0 && suma == 0)

printf("0");

return 0;

}

浮点错误的意思-PAT 、OJ

浮点错误: 您的程序运行时发生浮点错误，比如遇到了除以 0 的情况

所以发生浮点错误应该考虑程序中：

是否可能出现了一个数除以0的情况
是否可能出现了一个数取余0的情况
是否发生了数据溢出而导致的除以0或者取余0的情况

L2-005. 集合相似度-PAT团体程序设计天梯赛GPLT

给定两个整数集合，它们的相似度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N（<=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（<=104），是集合中元素的个数；然后跟M个[0, 109]区间内的整数。

之后一行给出一个正整数K（<=2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例：
50.00%
33.33%

题目大意：nc是两个集合的公共元素个数，nt是两个集合的所有包含的元素个数（其中元素个数表示各个元素之间互不相同）。

分析：因为给出的集合里面含有重复的元素，而计算nc和nt不需要考虑两个集合里面是否分别有重复的元素，所以可以直接使用set存储每一个集合，然后把set放进一个数组里面存储。当需要计算集合a和集合b的相似度nc和nt的时候，遍历集合a中的每一个元素，寻找集合b中是否有该元素，如果有，说明是两个人公共的集合元素，则nc++，否则nt++（nt的初值为b集合里面本有的元素）。

#include <set>
#include <vector>
#include <cstdio>
using namespace std;
int main() {
    int n, m, k, temp, a, b;
    scanf("%d", &n);
    vector<set<int>> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &m);
        set<int> s;
        for(int j = 0; j < m; j++) {
            scanf("%d", &temp);
            s.insert(temp);
        }
        v[i] = s;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        int nc = 0, nt = v[b-1].size();
        for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) {
            if(v[b-1].find(*it) == v[b-1].end()) 
                nt++;
            else
                nc++;
        }
        double ans = (double)nc / nt * 100;
        printf("%.2f%%\n", ans);
    }
    return 0;
}

#include <set>

#include <vector>

#include <cstdio>

using namespace std;

int main() {

int n, m, k, temp, a, b;

scanf("%d", &n);

vector<set<int>> v(n);

for(int i = 0; i < n; i++) {

scanf("%d", &m);

set<int> s;

for(int j = 0; j < m; j++) {

scanf("%d", &temp);

s.insert(temp);

}

v[i] = s;

}

scanf("%d", &k);

for(int i = 0; i < k; i++) {

scanf("%d %d", &a, &b);

int nc = 0, nt = v[b-1].size();

for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) {

if(v[b-1].find(*it) == v[b-1].end())

nt++;

else

nc++;

}

double ans = (double)nc / nt * 100;

printf("%.2f%%\n", ans);

}

return 0;

}

1112. Stucked Keyboard (20)-PAT甲级真题

On a broken keyboard, some of the keys are always stucked. So when you type some sentences, the characters corresponding to those keys will appear repeatedly on screen for k times.

Now given a resulting string on screen, you are supposed to list all the possible stucked keys, and the original string.

Notice that there might be some characters that are typed repeatedly. The stucked key will always repeat output for a fixed k times whenever it is pressed. For example, when k=3, from the string “thiiis iiisss a teeeeeest” we know that the keys “i” and “e” might be stucked, but “s” is not even though it appears repeatedly sometimes. The original string could be “this isss a teest”.

Input Specification:

Each input file contains one test case. For each case, the 1st line gives a positive integer k ( 1<k<=100 ) which is the output repeating times of a stucked key. The 2nd line contains the resulting string on screen, which consists of no more than 1000 characters from {a-z}, {0-9} and “_”. It is guaranteed that the string is non-empty.

Output Specification:

For each test case, print in one line the possible stucked keys, in the order of being detected. Make sure that each key is printed once only. Then in the next line print the original string. It is guaranteed that there is at least one stucked key.

Sample Input:
3
caseee1__thiiis_iiisss_a_teeeeeest
Sample Output:
ei
case1__this_isss_a_teest

题目大意：键盘某些键卡住了，按一次重复k次，要求找出可能的键，并且输出正确的字符串顺序。可能的键要求按照被发现的顺序输出。

分析：考察STL的应用～
map<char, bool>存储出现的键是否坏，set<char>存储输出可能坏的键的时候，当前字符是否已经被输出过，输出过的键放在set里面.

寻找坏键：遍历字符串的每个字符的时候，与pre（字符串当前字符s[i]的前一个字符）相比较，如果相等就继续计数cnt++，如果不相等，令cnt = 1表示当前字符出现了一次～如果cnt % k等于0 则令s[i]可能是坏键，置map对应的字符的bool值为true～

输出坏键：由于需要根据坏键发现的顺序输出，所以遍历整个字符串的方式输出～，并且确保不会重复输出～（用set集合确保，输出过了的放在set里面）
输出整个正确的字符串：如果当前s[i]是坏键，在输出一次后，令 i = i + k – 1，再输出，保证坏键出现k次只输出一次～

tips：谢谢在csdn博客的评论里的同学友情提醒，如果出现了先不是坏建后又判断是坏键的情况，这种情况会出现错误，因为前面已经认为它不是坏键了，说明它一定不是坏建，所以要加一个sureNoBroken，把确定不是坏键的键标记出来，在map都设置完成后把确定不是坏键的m标记为false。虽然测试用例里面没有考虑到这种情况，但是如果输入3 aabbaaa，应该输出没有坏键。

#include <iostream>
#include <map>
#include <cstdio>
#include <set>
using namespace std;
bool sureNoBroken[256];
int main() {
    int k, cnt = 1;
    scanf("%d", &k);
    string s;
    cin >> s;
    map<char, bool> m;
    set<char> printed;
    char pre = '#';
    s = s + '#';
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == pre) {
            cnt++;
        } else {
            if(cnt % k != 0) {
                sureNoBroken[pre] = true;
            }
            cnt = 1;
        }
        if(i != s.length() - 1) m[s[i]] = (cnt % k == 0);
        pre = s[i];
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(sureNoBroken[s[i]] == true)
            m[s[i]] = false;
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(m[s[i]] && printed.find(s[i]) == printed.end()) {
            printf("%c", s[i]);
            printed.insert(s[i]);
        }
    }
    printf("\n");
    for(int i = 0; i < s.length() - 1; i++) {
        printf("%c", s[i]);
        if(m[s[i]])
            i = i + k - 1;
    }
    return 0;
}

#include <iostream>

#include <map>

#include <cstdio>

#include <set>

using namespace std;

bool sureNoBroken[256];

int main() {

int k, cnt = 1;

scanf("%d", &k);

string s;

cin >> s;

map<char, bool> m;

set<char> printed;

char pre = '#';

s = s + '#';

for(int i = 0; i < s.length(); i++) {

if(s[i] == pre) {

cnt++;

} else {

if(cnt % k != 0) {

sureNoBroken[pre] = true;

}

cnt = 1;

}

if(i != s.length() - 1) m[s[i]] = (cnt % k == 0);

pre = s[i];

}

for(int i = 0; i < s.length() - 1; i++) {

if(sureNoBroken[s[i]] == true)

m[s[i]] = false;

}

for(int i = 0; i < s.length() - 1; i++) {

if(m[s[i]] && printed.find(s[i]) == printed.end()) {

printf("%c", s[i]);

printed.insert(s[i]);

}

printf("\n");

for(int i = 0; i < s.length() - 1; i++) {

printf("%c", s[i]);

if(m[s[i]])

i = i + k - 1;

}

return 0;

}