Code – 第82页

[swift] LeetCode 20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

func isValid(_ s: String) -> Bool {
    var stack = [Character](), b = true

    func compare(_ c: Character) -> Bool {
        guard let t = stack.popLast()  else { return false }
        return (c == ")" && t == "(") || (c == "]" && t == "[" ) || (c == "}" && t == "{")
    }

    loop: for c in s {
        switch c {
        case "(", "[", "{":
            stack.append(c)
        default:
            b = compare(c)
            if !b { break loop }
        }
    }
    
    return b && stack.isEmpty
}

func isValid(_ s: String) -> Bool {

var stack = [Character](), b = true

func compare(_ c: Character) -> Bool {

guard let t = stack.popLast() else { return false }

return (c == ")" && t == "(") || (c == "]" && t == "[" ) || (c == "}" && t == "{")

}

loop: for c in s {

switch c {

case "(", "[", "{":

stack.append(c)

default:

b = compare(c)

if !b { break loop }

}

return b && stack.isEmpty

}

L2-022 重排链表-PAT团体程序设计天梯赛GPLT

给定一个单链表 L~1~→L~2~→…→L~n-1~→L~n~，请编写程序将链表重新排列为 L~n~→L~1~→L~n-1~→L~2~→…。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (<= 10^5^)。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过10^5^的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

分析：用结构体｛id, data, next｝存储节点信息，模拟链表。先遍历一遍链表，把有用数节点存起来（甲级乙级中，姥姥为了加大难度，加了好多不在链表中的干扰数据）然后从后往前交替输出,（先把顺序存在ans中,待会统一输出），l, r代表将要输出的节点位置，当（l-1）-（r+1） == 1时都遍历一遍了，可退出循环~

#include <iostream>
#include <vector>
using namespace std;
struct node{
    int id, data, next;
};
int main() {
    int begin, n;
    cin >> begin >> n;
    node a[100010];
    vector<node> v, ans;
    for(int i = 0; i < n; i++) {
        int tbegin, tdata, tnext;
        cin >> tbegin >> tdata >> tnext;
        a[tbegin] = {tbegin, tdata, tnext};
    }
    while(begin != -1) {
        v.push_back(a[begin]);
        begin = a[begin].next;
    }
    int l = 0, r = v.size() - 1;
    while(1) {
        ans.push_back(v[r]);
        r--;
        if((r + 1) - (l - 1) == 1) break;
        ans.push_back(v[l]);
        l++;
        if((r + 1) - (l - 1) == 1) break;
    }
    for(int i = 0; i < ans.size(); i++) {
        if(i != ans.size() - 1)
            printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i+1].id);
        else
            printf("%05d %d -1\n", ans[i].id, ans[i].data);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node{

int id, data, next;

};

int main() {

int begin, n;

cin >> begin >> n;

node a[100010];

vector<node> v, ans;

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

int tbegin, tdata, tnext;

cin >> tbegin >> tdata >> tnext;

a[tbegin] = {tbegin, tdata, tnext};

}

while(begin != -1) {

v.push_back(a[begin]);

begin = a[begin].next;

}

int l = 0, r = v.size() - 1;

while(1) {

ans.push_back(v[r]);

r--;

if((r + 1) - (l - 1) == 1) break;

ans.push_back(v[l]);

l++;

if((r + 1) - (l - 1) == 1) break;

}

for(int i = 0; i < ans.size(); i++) {

if(i != ans.size() - 1)

printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i+1].id);

else

printf("%05d %d -1\n", ans[i].id, ans[i].data);

}

return 0;

}

L2-027 名人堂与代金券-PAT团体程序设计天梯赛GPLT

对于在中国大学MOOC学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

输入格式：
输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式：
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例：
10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70

输出样例：
360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80

分析：给每个大于60分的学生发20块，如果还有人同时大于G，在发30块。把所有学生生排序后，重新排名。第一个学生为第一名,以后的学生如果分数和前一个学生并列，他的名次和前一个同学名次一样，否则他的名次为下标加一

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct peo{
    string name;
    int sco;
};
bool cmp(peo a, peo b) {
    if(a.sco != b.sco) return a.sco > b.sco;
    return a.name < b.name;
}
int main(){
    int n, g, k, sum = 0, rank[10001] = {0};
    cin >> n >> g >> k;
    vector<peo> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i].name >> v[i].sco;
        if(v[i].sco >= 60) sum += 20;
        if(v[i].sco >= g) sum += 30;
    }
    sort(v.begin(), v.end(), cmp);
    rank[0] = 1;
    for(int i = 1; i < n; i++) {
        if(v[i].sco == v[i-1].sco)
            rank[i] = rank[i-1];
        else
            rank[i] = i + 1;
    }
    cout << sum << endl;
    for(int i = 0; rank[i] <= k && i < n; i++)
        printf("%d %s %d\n", rank[i], v[i].name.c_str(), v[i].sco);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct peo{

string name;

int sco;

};

bool cmp(peo a, peo b) {

if(a.sco != b.sco) return a.sco > b.sco;

return a.name < b.name;

}

int main(){

int n, g, k, sum = 0, rank[10001] = {0};

cin >> n >> g >> k;

vector<peo> v(n);

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

cin >> v[i].name >> v[i].sco;

if(v[i].sco >= 60) sum += 20;

if(v[i].sco >= g) sum += 30;

}

sort(v.begin(), v.end(), cmp);

rank[0] = 1;

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

if(v[i].sco == v[i-1].sco)

rank[i] = rank[i-1];

else

rank[i] = i + 1;

}

cout << sum << endl;

for(int i = 0; rank[i] <= k && i < n; i++)

printf("%d %s %d\n", rank[i], v[i].name.c_str(), v[i].sco);

return 0;

}

L2-026 小字辈-PAT团体程序设计天梯赛GPLT

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：
9
2 6 5 5 -1 5 6 4 7

输出样例：
4
1 9

分析：广度优先搜索最长路径问题（深搜可能会超时），老祖宗的父母即root的id用0表示，队列中的结构体成员分别是，人的编号和所处层数。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct peo{
    int id, level;
};
int main(){
    int n, temp, maxlevel = -1;
    queue<peo> q;
    vector<peo> ans;
    cin >> n;
    vector<vector<int>> v(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> temp;
        if(temp == -1) temp = 0;
        v[temp].push_back(i);
    }
    q.push({0,0});
    while(!q.empty()) {
        peo p  = q.front();
        int id = p.id, level = p.level;
        if(p.level > maxlevel) maxlevel = p.level;
        ans.push_back(p);
        q.pop();
        for(int i = 0; i < v[id].size(); i++)
            q.push({v[id][i], level + 1});
    }
    cout << maxlevel << endl;
    for(int i = 0; i < ans.size(); i++) {
        if(ans[i].level == maxlevel) {
            cout << ans[i].id;
            if(i != ans.size() - 1) cout << " ";
        }
    }
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct peo{

int id, level;

};

int main(){

int n, temp, maxlevel = -1;

queue<peo> q;

vector<peo> ans;

cin >> n;

vector<vector<int>> v(n+1);

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

cin >> temp;

if(temp == -1) temp = 0;

v[temp].push_back(i);

}

q.push({0,0});

while(!q.empty()) {

peo p = q.front();

int id = p.id, level = p.level;

if(p.level > maxlevel) maxlevel = p.level;

ans.push_back(p);

q.pop();

for(int i = 0; i < v[id].size(); i++)

q.push({v[id][i], level + 1});

}

cout << maxlevel << endl;

for(int i = 0; i < ans.size(); i++) {

if(ans[i].level == maxlevel) {

cout << ans[i].id;

if(i != ans.size() - 1) cout << " ";

}

return 0;

}

L2-025 分而治之-PAT团体程序设计天梯赛GPLT

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （<= 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：
对每一套方案，如果可行就输出“YES”，否则输出“NO”。

输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

输出样例：
NO
YES
YES
NO
NO

分析：存图用邻接表存，aa数组表示此城有兄弟城市（即有多少城市与之连接），a组为每次攻城后的次城有多少兄弟城，aa作为原始连接情况，不变，每次用的时候，复制到a上即可。每攻下一座城，次城兄弟成变成0，其兄弟城的兄弟城减少一个。最后检查，如果所有城市的兄弟城都小于零，则输出YES，否则输出NO。

#include <iostream>
#include <vector>
using namespace std;
int n, m, k, aa[10010] = {0}, a[10010];
void check() {
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            cout << "NO\n";
            return ;
        }
    }
    cout << "YES\n";
    return ;
}
int main(){
    cin >> n >> m;
    vector<vector<int>> v(n+1);
    while(m--) {
        int c1, c2;
        cin >> c1 >> c2;
        aa[c1]++;
        aa[c2]++;
        v[c1].push_back(c2);
        v[c2].push_back(c1);
    }
    cin >> k;
    while(k--) {
        int cnt, num;
        cin >> cnt;
        for(int i = 1; i <= n; i++)
            a[i] = aa[i];
        for(int i = 0; i < cnt; i++) {
            cin >> num;
            a[num] = 0;
            for(int j = 0; j < v[num].size(); j++)
                a[v[num][j]]--;
        }
        check();
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n, m, k, aa[10010] = {0}, a[10010];

void check() {

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

if(a[i] > 0) {

cout << "NO\n";

return ;

}

cout << "YES\n";

return ;

}

int main(){

cin >> n >> m;

vector<vector<int>> v(n+1);

while(m--) {

int c1, c2;

cin >> c1 >> c2;

aa[c1]++;

aa[c2]++;

v[c1].push_back(c2);

v[c2].push_back(c1);

}

cin >> k;

while(k--) {

int cnt, num;

cin >> cnt;

for(int i = 1; i <= n; i++)

a[i] = aa[i];

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

cin >> num;

a[num] = 0;

for(int j = 0; j < v[num].size(); j++)

a[v[num][j]]--;

}

check();

}

return 0;

}

L2-023 图着色问题-PAT团体程序设计天梯赛GPLT

图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V（0 < V <= 500）、E（>= 0）和K（0 < K <= V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（<= 20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出“Yes”，否则输出“No”，每句占一行。

输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

输出样例：
Yes
Yes
No
No

分析：给出无向图，和颜色的数量k，求是否给出的颜色数量==k，并且任意两个点之间颜色都不同。
依次判断每一个点是否和周围的点颜色相同，出现一次，就立刻得出结果“No”，如果一次都没出现，结果为“Yes”。
判断给出的颜色个数的时候用set方便（本题数据规模不大，不会对运行时间影响太大）。

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, m, k, num;
vector<vector<int>> v(510);
vector<int> color(510);
bool f(int i) {
    for(int j = 0; j < v[i].size(); j++)
        if(color[i] == color[v[i][j]])
            return false;
    return true;
}
int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        v[t1].push_back(t2);
        v[t2].push_back(t1);
    }
    cin >> num;
    while(num--) {
        int flag = 0;
        set<int> s;
        for(int i = 1; i <= n; i++) {
            cin >> color[i];
            s.insert(color[i]);
        }
        if(s.size() != k ) {
            flag = 1;
            cout << "No\n";
        }else {
            for(int i = 1; i <= n; i++) {
                if(f(i) == false) {
                    cout << "No\n";
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0)  cout << "Yes\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

int n, m, k, num;

vector<vector<int>> v(510);

vector<int> color(510);

bool f(int i) {

for(int j = 0; j < v[i].size(); j++)

if(color[i] == color[v[i][j]])

return false;

return true;

}

int main() {

cin >> n >> m >> k;

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

int t1, t2;

cin >> t1 >> t2;

v[t1].push_back(t2);

v[t2].push_back(t1);

}

cin >> num;

while(num--) {

int flag = 0;

set<int> s;

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

cin >> color[i];

s.insert(color[i]);

}

if(s.size() != k ) {

flag = 1;

cout << "No\n";

}else {

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

if(f(i) == false) {

cout << "No\n";

flag = 1;

break;

}

if(flag == 0) cout << "Yes\n";

}

return 0;

}