HouXingYi's blog

即使跑得再远,也逃不出自己本身


  • 首页

  • 标签

  • 分类

  • 归档

数据结构 中国MOOC笔记(ING)

发表于 2019-03-25 | 分类于 数据结构

背景

参考书: 《数据结构》 陈越主编,《王道数据结构 考研复习指导》

视频课:中国大学MOOC 数据结构 浙江大学

第一周 基本概念

总结

数据结构的定义与内容,算法的定义与内容,一个实例:最大子列和问题。

什么是数据结构

TODO

什么是算法

TODO

应用实例:最大子列和问题

TODO

编程作业

第一周的编程作业:

  1. 最大子列和问题:是本次课最后讲到的4种算法的实验题,属于基本要求,一定要做;
1
TODO
  1. Maximum Subsequence Sum:是2004年浙江大学计算机专业考研复试真题,要求略高,选做。其实也不难,是本次课最后讲到的算法的改造,挑战一下吧~
1
TODO
  1. 二分查找:配合课后讨论题给出这道函数填空题,学有余力、并且会C语言编程的你可以尝试一下。你只需要提交一个函数,而不用交如main函数之类的其他函数。不会C语言的话,就研究一下课后关于二分法的讨论题吧~
1
TODO

第二周 线性结构

总结

线性表,堆栈,队列,一个实例:多项式加法运算

线性表

定义,顺序储存实现,链式储存实现

堆栈

定义,堆栈的实现

队列

定义,队列的实现

应用实例:多项式加法

TODO

编程作业

第二周的编程作业:

  1. 两个有序链表序列的合并 这是一道C语言函数填空题,训练最基本的链表操作。如果会用C编程的话,一定要做;
1
TODO
  1. 一元多项式的乘法与加法运算 在“小白专场”里,我们会详细讨论C语言实现的方法。对于不会C语言而不能做第1题的同学,本题一定要做;
1
TODO
  1. Reversing Linked List 根据某大公司笔试题改编的2014年春季PAT真题,不难,可以尝试;
1
TODO
  1. Pop Sequence 是2013年PAT春季考试真题,考察队堆栈的基本概念的掌握,应可以一试。
1
TODO

第三周 树(上)

总结

树的定义与表示,二叉树及其存储,二叉树的遍历。

树的定义与表示

TODO

二叉树及存储结构

TODO

二叉树的遍历

TODO

编程作业

第三周的编程作业:

  1. 树的同构 小白专场会做详细讲解,基本要求,一定要做;
1
TODO
  1. List Leaves 训练建树和遍历基本功,一定要做;
1
TODO
  1. Tree Traversals Again 是2014年秋季PAT甲级考试真题,稍微要动下脑筋,想通了其实程序很基础,建议尝试。
1
TODO

PAT乙级官方例题练习

发表于 2019-02-07 | 更新于 2019-03-17 | 分类于 PAT

前置条件

甲级考试的分数分布一般为:20、25、25、30;乙考试的分数分布一般为:15、20、20、20、25。

考试时间:2019年3月2日星期六下午1点30分 (北京时间)。

考试地点:福州大学新区数计学院5号楼。

考试环境:福州大学: 张栋, zhangdong@fzu.edu.cn
Dev C++ 5.10;Code::Blocks 16.01;Java SE Development Kit 9.0.1;Eclipse Oxygen.2 4.7.2;Python解释器(3.6.5);PyCharm Community Edition

PAT练习题列表地址(乙级):https://pintia.cn/problem-sets/994805260223102976/problems

开发工具:Dev-C++ 5.11(尽量与考场接近)

参考用书:《算法笔记》 机械工业出版社

注意

  1. C/C++的主函数必须定义为整型,即“int main()”; 程序正常结束必须返回0,即“return 0;”否则将会得到返回非零错误。

1001 害死人不偿命的(3n+1)猜想 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805325918486528

分类:简单模拟

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>

main () {

int n, step = 0;

scanf("%d", &n);

while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = ( 3 * n + 1) / 2;
}
step++;
}

printf("%d", step);

return 0;

}

1002 写出这个数 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805324509200384

注意点:保证n小于10^100,超出 int ,long 的范围,故首先考虑字符串。因n不超过10的100次方, 所以sum小于9乘以100, 即sum一定不会大于三位数。strlen的使用。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<cstring>

using namespace std;

main () {

int sum = 0;
char c[110];

scanf("%s", c);

for(int i = 0; i < strlen(c); i++) {
sum += c[i] - '0'; // 字符转化
}

char pinyins[10][5] = { "ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

if ( sum < 10 ) {
printf("%s", pinyins[sum]);
} else if ( sum >= 10 && sum < 100 ) {
printf("%s ", pinyins[sum / 10]);
printf("%s", pinyins[sum % 10]);
} else if ( sum >= 100 && sum < 1000 ) {
printf("%s ", pinyins[sum / 100]);
printf("%s ", pinyins[sum % 100 / 10]);
printf("%s", pinyins[sum % 10]);
}

return 0;

}

1003 我要通过! (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805323154440192

注意点:理解题目,找出规律,设P之前A的数量为a,P与T之间A的数量为b,T之后A的数量为c,可知c = a * b。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

main () {
int n;
vector<int> passList;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char c[110];
scanf("%s", c);
int len1 = 0, len2 = 0, len3 = 0;
int isPfind = -1, isTfind = -1, isAfind = -1;
int cLen = strlen(c);
int isLetterPass = -1;

for (int j = 0; j < cLen; j++) {
char temp = c[j];
if (temp == 'P') {
isPfind = j;
} else if (temp == 'T') {
isTfind = j;
} else if (temp == 'A') {
isAfind = 1;
} else {
isLetterPass = 1; // 含有其他字母
}
}

bool isPass = false;

if (isTfind != -1 && isPfind != -1 && isAfind != -1 && isLetterPass == -1) {
len1 = isPfind; // P之前A的数量a
len2 = isTfind - isPfind - 1; // P与T之间A的数量b
len3 = cLen - isTfind - 1; // T之后A的数量 c
if ( len1 * len2 == len3 ) { // c = a * b
isPass = true;
}
}

if (isPass) {
passList.push_back(1);
} else {
passList.push_back(0);
}
}

for (vector<int>::iterator it = passList.begin(); it != passList.end(); it++) {
int temp = *it;
if (temp == 1) {
printf("YES\n");
} else {
printf("NO\n");
}
}

return 0;

}

1004 成绩排名 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805321640296448

注意点:结构体使用,排序算法使用。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<algorithm>
using namespace std;

struct Student{
char name[12];
char number[12];
int score;
};

bool cmp (Student A, Student B) {
return A.score > B.score;
}

main () {

Student stuList[10000];
int n;
scanf("%d", &n);

for (int i = 0; i < n; i++) {
scanf("%s %s %d", stuList[i].name, stuList[i].number, &stuList[i].score);
}

sort(stuList, stuList + n, cmp);

printf("%s %s\n", stuList[0].name, stuList[0].number);
printf("%s %s", stuList[n - 1].name, stuList[n - 1].number);

return 0;
}

1005 继续(3n+1)猜想 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805320306507776

注意点:考查hashTable的思想。专门开一个表用于验证是否出现过,表需要开的足够大(10000),否则会出现部分正确的情况。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>

using namespace std;

bool cmp (int a, int b) {
return a > b;
}

main () {
int k;
bool compareArr[10000] = { false };
int numList[10000];
bool isPrint = false;
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d", &numList[i]);
int n = numList[i];
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = ( 3 * n + 1) / 2;
}
compareArr[n] = true;
}
}
sort(numList, numList + k, cmp);
for (int j = 0; j < k; j++) {
if (compareArr[numList[j]] == false) {
if (!isPrint) {
printf("%d", numList[j]);
isPrint = true;
} else {
printf(" %d", numList[j]);
}
}
}
return 0;
}

1006 换个格式输出整数 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805318855278592

注意点:注意边界条件,比如10,100的情况。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>

main () {

int num;

int Bcount = 0, Scount = 0, Gcount = 0;

scanf("%d", &num);

if (num < 10) {
Gcount = num;
} else if ( num >= 10 && num < 100 ) {

Scount = num / 10;
Gcount = num % 10;

} else if (num >= 100) {

Bcount = num / 100;
Scount = num % 100 / 10;
Gcount = num % 10;

}

while (Bcount > 0) {
printf("B");
Bcount--;
}
while (Scount > 0) {
printf("S");
Scount--;
}
if (Gcount > 0) {
for (int i = 0; i < Gcount; i++) {
printf("%d", i + 1);
}
}

return 0;
}

1007 素数对猜想 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

注意点:素数判断,边界条件注意。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<math.h>

bool isPrime (int n) {
if (n <= 1) {
return false;
}
int sqr = (int)sqrt(1.0 * n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

main () {

int N;
int primeList[10000];
int n = 0; // 素数的个数
int count = 0;

scanf("%d", &N);

for (int i = 1; i <= N; i++) {
int flag = isPrime(i);
if (flag) {
primeList[n] = i;
if (n > 0) {
int dis = primeList[n] - primeList[n - 1];
if (dis == 2) {
count++;
}
}
n++;
}
}

printf("%d", count);

return 0;
}

1008 数组元素循环右移问题 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808

注意点:计算输入数组与输出数组基于n,m的位置关系。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>

main () {

int n, m;
int list[110];

scanf("%d", &n);
scanf("%d", &m);

m = m % n;

for(int i = 0; i < n; i++) {
scanf("%d", &list[i]);
}

for (int j = 0; j < n; j++) {
int index = 0;
if (j + n - m < n) {
index = j + n - m;
} else {
index = j - m;
}
if (j > 0) {
printf(" %d", list[index]);
} else {
printf("%d", list[index]);
}

}

return 0;
}

1009 说反话 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805314941992960

注意点:利用stack倒序输出,注意cin与string的用法。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<string> v;
string s;
while(cin >> s) {
v.push(s);
}
cout << v.top();
v.pop();
while(!v.empty()) {
cout << " " << v.top();
v.pop();
}
return 0;
}

1010 一元多项式求导 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805313708867584

注意点:零多项式特殊处理,使用EOF的方式比使用数组存储的方式简洁高效。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>

main () {

int x, n;

bool isZero = true; // 是否是零多项式

while (scanf("%d%d", &x, &n) != EOF) {
if (n > 0) { // 次数大于零
if (isZero == true) { // 第一项
isZero = false;
printf("%d %d", x * n, n - 1);
} else {
printf(" %d %d", x * n, n - 1);
}
}
}

if (isZero == true) {
printf("0 0");
}

return 0;
}

1011 A+B 和 C (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805312417021952

注意点:注意输入输出与取值范围。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>

main () {

long long a, b, c;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld %lld %lld", &a, &b, &c);
if (a + b > c) {
printf("Case #%d: true\n", i + 1);
} else {
printf("Case #%d: false\n", i + 1);
}
}

return 0;

}

1012 数字分类 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805311146147840

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<vector>

using namespace std;

main () {

int n;

int A1 = 0;
vector<int> A2List;
int A3 = 0;
vector<int> A4List;
int A5 = 0;

scanf("%d", &n);

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

int tempNum;

scanf("%d", &tempNum);

int remain = tempNum % 5;

if (remain == 0) {
if (tempNum % 2 == 0) {
A1 += tempNum;
}
}
if (remain == 1) {
A2List.push_back(tempNum);
}
if (remain == 2) {
A3++;
}
if (remain == 3) {
A4List.push_back(tempNum);
}
if (remain == 4) {
if (A5) {
A5 = A5 > tempNum ? A5 : tempNum;
} else {
A5 = tempNum;
}
}

}

// A1
if (A1 == 0) {
printf("N");
} else {
printf("%d", A1);
}

// A2
if (A2List.size() == 0) {
printf(" N");
} else {
int A2sum = 0;
for (int j = 0; j < A2List.size(); j++) {
if (j %2 == 0) {
A2sum += A2List[j];
} else {
A2sum -= A2List[j];
}
}
printf(" %d", A2sum);
}

// A3
if (A3 == 0) {
printf(" N");
} else {
printf(" %d", A3);
}

// A4
if (A4List.size() == 0) {
printf(" N");
} else {
int A4sum = 0;
float average;
for (int k = 0; k < A4List.size(); k++) {
A4sum += A4List[k];
}
printf(" %.1f", A4sum * 1.0 / A4List.size());
}

// A5
if (A5 == 0) {
printf(" N");
} else {
printf(" %d", A5);
}

return 0;
}

1013 数素数 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<vector>
#include<math.h>

using namespace std;

// 判断是否是素数
bool isPrime (int n) {
if (n <= 1) {
return false;
}
int sqr = (int)sqrt(1.0 * n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

main () {

int n, m;
vector<int> primeList;
int temp = 2;

scanf("%d %d", &n, &m);

while (1) {
bool res = isPrime(temp);
if (res) {
primeList.push_back(temp);
}
temp++;
if (primeList.size() >= m) {
break;
}
}

int row = 0;
for (int j = n - 1; j < m; j++) {

if (row == 0) {
printf("%d", primeList[j]);
row++;
} else if (row > 0 && row < 9) {
printf(" %d", primeList[j]);
row++;
} else if (row == 9) {
printf(" %d\n", primeList[j]);
row = 0;
}

}

return 0;
}

1014 福尔摩斯的约会 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805308755394560

注意点:字符串的输入输出,字符范围的边界问题(A-G,A-N,A-Z)。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<map>
#include<string>
#include<iostream>

using namespace std;

main () {

map<int, string> DAY;
DAY[1] = "MON";DAY[2] = "TUE";DAY[3] = "WED";DAY[4] = "THU";DAY[5] = "FRI";DAY[6] = "SAT";DAY[7] = "SUN";

string str1, str2, str3, str4;

cin >> str1 >> str2 >> str3 >> str4;

bool isFindDay = false;

for (int i = 0; i < str1.size(); i++) {
if (str1[i] == str2[i]) {

if (isFindDay) { // 已找到星期几

if (str1[i] >= 'A' && str1[i] <= 'N') { // A到N(1-14)
cout << str1[i] - 'A' + 10 << ':';
break;
} else if (str1[i] >= '0' && str1[i] <= '9') { // 是数字
cout << '0' << str1[i] << ':';
break;
}

} else {

if (str1[i] >= 'A' && str1[i] <= 'G') { // A到G(1-7)
cout << DAY[str1[i] - 'A' + 1] << ' ';// 输出星期几
isFindDay = true;
}

}

}
}

for (int j = 0; j < str3.size(); j++) {
if (str3[j] == str4[j]) {
if (str3[j] >= 'a' && str3[j] <= 'z' || str3[j] >= 'A' && str3[j] <= 'Z') { // 英文字母,大小写均可
if (j < 10) {
cout << '0' << j;
} else {
cout << j;
}
break;
}

}
}

return 0;
}

1015 德才论 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805307551629312

注意点:主要考察sort中的cmp函数,注意审题,注意边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct Stu {
int number; // 学号
int moralNum; // 德分
int talentNum; // 才分
};

bool cmp (Stu a, Stu b) {
if (a.moralNum + a.talentNum == b.moralNum + b.talentNum) {
if (a.moralNum == b.moralNum) {
return a.number < b.number;
} else {
return a.moralNum > b.moralNum;
}
} else {
return (a.moralNum + a.talentNum) > (b.moralNum + b.talentNum);
}
}

void printAll (vector<Stu> list) {
for (int i = 0; i < list.size(); i++) {
printf("%d %d %d\n", list[i].number, list[i].moralNum, list[i].talentNum);
}
}

main () {

int N, // 考生总数
L, // 录取最低分数线
H; // 优先录取线

scanf("%d %d %d", &N, &L, &H);

vector<Stu> group1; // 才德全尽
vector<Stu> group2; // 德胜才
vector<Stu> group3; // 才德兼亡
vector<Stu> group4; // 德胜才

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

int number, moralNum, talentNum;
Stu tempStu;

scanf("%d %d %d", &number, &moralNum, &talentNum);

tempStu.number = number;
tempStu.moralNum = moralNum;
tempStu.talentNum = talentNum;

if (tempStu.moralNum >= L && tempStu.talentNum >= L) {

if (tempStu.moralNum >= H && tempStu.talentNum >= H) {// 才德全尽
group1.push_back(tempStu);
} else if (tempStu.moralNum >= H && tempStu.talentNum < H) {// 德胜才
group2.push_back(tempStu);
} else if (tempStu.moralNum < H && tempStu.talentNum < H && tempStu.moralNum >= tempStu.talentNum) {// 才德兼亡,但德胜才
group3.push_back(tempStu);
} else {// // 才德兼亡,但才胜德
group4.push_back(tempStu);
}

}

}

sort(group1.begin(), group1.end(), cmp);
sort(group2.begin(), group2.end(), cmp);
sort(group3.begin(), group3.end(), cmp);
sort(group4.begin(), group4.end(), cmp);

printf("%d\n", group1.size() + group2.size() + group3.size() + group4.size());

printAll(group1);
printAll(group2);
printAll(group3);
printAll(group4);

return 0;
}

1016 部分A+B (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805306310115328

注意点:考察字符与数字的转化。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<string>
#include<iostream>
#include<math.h>

using namespace std;

long long getP (string A, char Da) {

long long p = 0;
int count = 0;
int tempNum = Da - '0';

for (int i = 0; i < A.size(); i++) {
if (A[i] == Da) {
count++;
}
}

for (int j = 0; j < count; j++) {
p += tempNum * pow(10, j);
}

return p;
}

main () {
string A, B;
char Da, Db;
long long Asum, Bsum;

cin >> A >> Da >> B >> Db;

Asum = getP(A, Da);
Bsum = getP(B, Db);

printf("%lld", Asum + Bsum);

return 0;
}

1017 A除以B (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805305181847552

注意点:考察大整数运算,需掌握大整数的加减乘除。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>

using namespace std;

// 大整数结构
struct bign {
int n[1010];
int len;
bign () {
memset(n, 0, sizeof(n));
len = 0;
}
};

// 将整数转化为大整数

bign convert (string n) {
bign a;
a.len = n.size();
for (int i = 0; i < a.len; i++) {
a.n[i] = n[a.len - 1 - i] - '0'; // 转化为int,并倒序摆放。
}
return a;
}

// 大整数除法

bign divide (bign a, int b, int& r) {
bign c;
c.len = a.len;
// 做除法,结果保留在c
for (int i = a.len -1; i >= 0; i--) {
r = r*10 + a.n[i];
if (r < b) { // 不够除
c.n[i] = 0;
} else {
c.n[i] = r / b;
r = r % b;
}
}
// 处理c,去除高位的0,同时至少保留一位最低位
while (c.len - 1 >= 1 && c.n[c.len - 1] == 0) {
c.len--;
}
return c;
}

// 打印大整数
void printBign(bign a) {
for (int i = a.len -1; i >= 0; i--) {
printf("%d", a.n[i]);
}
}

main () {

int b, r = 0; // 被除数,余数
string number;
bign c; // 商

cin >> number >> b;

bign bigNumber = convert(number);
c = divide(bigNumber, b, r);
printBign(c); // 打印商
printf(" %d", r); // 打印余数

return 0;
}

1018 锤子剪刀布 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805304020025344

注意点:注意最后一个条件,“如果解不唯一,则输出按字母序最小的解”,即当获胜次数最多的手势相同的时候的策略,影响到数据的摆放。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<cstdio>
#include<iostream>

using namespace std;

void compare (char a, char b, int aRes[], int bRes[], int aResCount[], int bResCount[]) {

// 胜、平、负
// J,C,B

// 平局
if (a == b) {
aRes[1]++;
bRes[1]++;
}

// 甲C胜
if (a == 'C' && b == 'J') {
aRes[0]++;
bRes[2]++;
aResCount[1]++;
}
// 乙B胜
if (a == 'C' && b == 'B') {
aRes[2]++;
bRes[0]++;
bResCount[2]++;
}
// 乙C胜
if (a == 'J' && b == 'C') {
aRes[2]++;
bRes[0]++;
bResCount[1]++;
}
// 甲J胜
if (a == 'J' && b == 'B') {
aRes[0]++;
bRes[2]++;
aResCount[0]++;
}
// 乙J胜
if (a == 'B' && b == 'J') {
aRes[2]++;
bRes[0]++;
bResCount[0]++;
}
// 甲B胜
if (a == 'B' && b == 'C') {
aRes[0]++;
bRes[2]++;
aResCount[2]++;
}

}

void printBest (int a[], bool flag) {

int count = 0;
int temp = 0;

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

if (a[i] >= temp) { // 注意,若相同的情况需要按字典顺序优先,即为BCJ顺序,故要">="
count = i;
temp = a[i];
}

}

if (count == 0) {
if (flag) {
printf("J");
} else {
printf(" J");
}
}
if (count == 1) {
if (flag) {
printf("C");
} else {
printf(" C");
}
}
if (count == 2) {
if (flag) {
printf("B");
} else {
printf(" B");
}
}

}

main () {

int n;

char a, b;

// 结果记录
int aRes[3] = {0, 0, 0};
int bRes[3] = {0, 0, 0};

// 获胜次数手势
int aResCount[3] = {0, 0, 0};
int bResCount[3] = {0, 0, 0};

scanf("%d", &n);

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

getchar();

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

compare(a, b, aRes, bRes, aResCount, bResCount);

}

printf("%d %d %d\n", aRes[0], aRes[1], aRes[2]);
printf("%d %d %d\n", bRes[0], bRes[1], bRes[2]);

printBest(aResCount, true);
printBest(bResCount, false);

return 0;
}

1019 数字黑洞 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805302786899968

注意点:主要在于数字与数字的数组的相互转化,注意printf技巧的使用。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<algorithm>

using namespace std;

bool cmp (int a, int b) {
return a > b;
}

void to_array (int n, int num[]) {
for (int i = 0; i < 4; i++) {
num[i] = n % 10;
n = n / 10;
}
}

int to_number (int num[]) {
int n = 0;
for (int i = 0; i < 4; i++) {
n = n * 10 + num[i];
}
return n;
}

main () {
int n;
int MAX, MIN;
int num[4];
scanf("%d", &n);
while (1) {
to_array(n, num);
sort(num, num + 4, cmp);
MAX = to_number(num);
sort(num, num + 4);
MIN = to_number(num);
n = MAX - MIN;
printf("%04d - %04d = %04d\n", MAX, MIN, n);
if (n == 6174 || n == 0) {
break;
}
}
return 0;
}

1020 月饼 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805301562163200

注意点:理解题意,策略为首先卖出单价最高的,最高的卖完了再依次补充。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<algorithm>

using namespace std;

struct Mooncake {
double store; // 库存
double totalSell; // 总售价
double price; // 库存
};

bool cmp (Mooncake a, Mooncake b) {
return a.price > b.price;
}

main () {

int n; // 月饼种类数

double D; // 市场最大需求量

scanf("%d %lf", &n, &D);

Mooncake cakeList[1010];

for (int i = 0; i < n; i++) {
scanf("%lf", &cakeList[i].store);
}

for (int i = 0; i < n; i++) {
scanf("%lf", &cakeList[i].totalSell);
cakeList[i].price = cakeList[i].totalSell / cakeList[i].store;
}

sort(cakeList, cakeList + n, cmp); // 从大到小排列,先买大的

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

if (cakeList[i].store < D) {
D = D - cakeList[i].store; // 当前全部卖掉
allIncome = allIncome + cakeList[i].totalSell;
} else {
allIncome = allIncome + cakeList[i].price * D;
break;
}
}

printf("%.2lf", allIncome);

return 0;
}

1021 个位数统计 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805300404535296

注意点:需要用大整数方式处理数据。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>

using namespace std;

struct bign {
int n[1010];
int len;
bign () {
memset(n, 0, sizeof(n));
len = 0;
}
};

bign change (string str) {
bign a;
a.len = str.size();
for (int i = 0; i < a.len; i++) {
a.n[i] = str[i] - '0';
}
return a;
}

main () {
string str;
int countList[10];
memset(countList, 0, sizeof(countList));
cin >> str;
bign num = change(str);
for (int i = 0; i < num.len; i++) {
countList[num.n[i]]++;
}
for (int i = 0; i < 10; i++) {
if (countList[i] > 0) {
printf("%d:%d\n", i, countList[i]);
}
}
return 0;
}

1022 D进制的A+B (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805299301433344

注意点:进制转换的问题,需要掌握P进制转化为10进制,与10进制转化为P进制,其他可以以十进制作为中介。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>

main () {

int A, B, D;
scanf("%d %d %d", &A, &B, &D);
int sum = A + B;
int ans[100], len = 0;
while (1) {
ans[len++] = sum % D; // 取余
sum = sum / D; // 除基
if (sum == 0) {
break;
}
}

for (int i = len -1; i >= 0; i--) {
printf("%d", ans[i]);
}

return 0;
}

1023 组个最小数 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805298269634560

注意点:策略为最高位打印除0以外最小的,其余的顺序从小到大按数量打印。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>

main () {
int list[10];
for (int i = 0; i < 10; i++) {
scanf("%d", &list[i]);
}
for (int i = 1; i < 10; i++) {
if (list[i] > 0) {
printf("%d", i);
list[i]--;
break;
}
}
int pos = 0;
while (1) {
if (list[pos] > 0 && pos < 10) {
printf("%d", pos);
list[pos]--;
} else {
pos++;
}
if (pos >= 10) {
break;
}
}
return 0;
}

1024 科学计数法 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805297229447168

注意点:以处理字符串作为思路。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<iostream>

using namespace std;

main () {
string str;
cin >> str;
int len = str.size();
int Epos; // E的位置
int exp = 0; // 指数
if (str[0] == '-') {
printf("-");
}
// 找出E的位置
for (int i = 0; i < len; i++) {
if (str[i] == 'E') {
Epos = i;
}
}
// 计算指数
for (int i = Epos + 2; i < len; i++) {
exp = exp * 10 + (str[i] - '0');
}
// 指数为0特判
if (exp == 0) {
for (int i = 1; i < Epos; i++) {
printf("%d", str[i]);
}
}
if (str[Epos + 1] == '-') { // 指数为负
printf("0.");
for(int i = 0; i < exp - 1; i++) {
printf("0");
}
for(int i = 1;i < Epos; i++) {
if (str[i] == '.') continue;
printf("%c", str[i]);
}
} else { // 指数为正
for (int i = 1; i < Epos; i++) {
if (str[i] == '.') continue;
printf("%c", str[i]);
if (i == exp + 2 && exp + 3 != Epos) {
printf(".");
}
}
// 需补零
if (exp + 3 > Epos) {
for (int i = 0; i < exp + 3 - Epos; i++) {
printf("0");
}
}
}
return 0;
}

1025 反转链表 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168

注意点:根据《算法笔记》里的代码,没通过,直接超时了。后面再想办法。改用柳婼的。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>

using namespace std;

int main() {

int first, k, n, sum = 0;

cin >> first >> n >> k; // 第一个结点地址,结点个数,结点反转周期

int temp, data[100005], next[100005], list[100005], result[100005];

for (int i = 0; i < n; i++) {
cin >> temp;
cin >> data[temp] >> next[temp];
}

while (first != -1) {
list[sum++] = first;
first = next[first];
}

for (int i = 0; i < sum; i++) {
result[i] = list[i];
}
for (int i = 0; i < (sum - sum % k); i++) { // 余下的不反转
result[i] = list[i / k * k + k - 1 - i % k]; // 按周期反转
}
for (int i = 0; i < sum - 1; i++) {
printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
}
printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
return 0;
}

1026 程序运行时间 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805295203598336

注意点:注意四舍五入。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<math.h>

main () {
int C1, C2;
scanf("%d %d", &C1, &C2);
int time = (int)round((C2 - C1) / 100.0);
int hh, mm, ss;
int r;
hh = time / 3600;
r = time % 3600;
mm = r / 60;
ss = r % 60;
printf("%02d:%02d:%02d", hh, mm, ss);
return 0;
}

1027 打印沙漏 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805294251491328

注意点:***注意格式问题,沙漏后面的空格不要打印,十分坑。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>

int main () {
int n, prev = 0, i = 0, res;

char tempStr;

scanf("%d %c", &n, &tempStr);

while (1) {
int now;
if (i == 0) {
now = 1;
} else {
now = prev + 2 * ( 2 * i + 1 );
}
if (now > n) {
res = n - prev;
break;
} else {
prev = now;
i++;
}
}

i = i - 1;

int countLine = 0;
for (int k = 0; k < 2 * i + 1; k++) {
int r = k < (2 * i + 1) / 2 ? k : 2 * i - k; // 当前行数打印空白的对半数量
for (int j = 0; j < r; j++) {
countLine++;
printf(" ");
}
for (int j = 0; j < (2 * i + 1) - (2 * r); j++) {
countLine++;
printf("%c", tempStr);
}
countLine = 0;
printf("\n");
}

printf("%d", res);

return 0;
}

1028 人口普查 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805293282607104

注意点:关注下这个读取数据的方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>


struct Birth {

char name[6];
int year;
int month;
int day;

};

bool isValid (Birth a) {
if (a.year < 1814 || ( a.year == 1814 && a.month < 9) || ( a.year == 1814 && a.month == 9 && a.day < 6) ) {
return false;
}
if (a.year > 2014 || ( a.year == 2014 && a.month > 9 ) || ( a.year == 2014 && a.month == 9 && a.day > 6)) {
return false;
}
return true;
}

main () {

int n;

Birth MIN, MAX;
int count = 0;

scanf("%d", &n);

Birth list[n];

MAX.year = 2014;MAX.month = 9;MAX.day = 6;
MIN.year = 1814;MIN.month = 9;MIN.day = 6;

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

scanf("%s %d/%d/%d", list[i].name, &list[i].year, &list[i].month, &list[i].day);

bool valid = isValid(list[i]);
if (valid) {
count++;
if ( (list[i].year > MIN.year) || (list[i].year == MIN.year && list[i].month > MIN.month) || (list[i].year == MIN.year && list[i].month == MIN.month && list[i].day > MIN.day) ) {
MIN = list[i];
}
if ( (list[i].year < MAX.year) || (list[i].year == MAX.year && list[i].month < MAX.month) || (list[i].year == MAX.year && list[i].month == MAX.month && list[i].day < MAX.day) ) {
MAX = list[i];
}
}
}

if (count > 0) {
printf("%d %s %s", count, MAX.name, MIN.name);
} else {
printf("0");
}

return 0;
}

1029 旧键盘 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805292322111488

注意点:字符串处理。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>

using namespace std;

main () {

string str1, str2;
vector<char> list;
cin >> str1 >> str2;
int offset = 0;
for (int i = 0; i < str1.size(); i++) {
if (str1[i] != str2[i - offset]) {
offset++;
}
if (i - offset < 0 && i == 0) { // 第0个特判
if (str1[i] >= 'a' && str1[i] <= 'z') {
str1[i] = str1[i] - 32; // 转化为大写
}
list.push_back(str1[i]);
} else {
if (str1[i] != str2[i - offset]) {
if (str1[i] >= 'a' && str1[i] <= 'z') {
str1[i] = str1[i] - 32; // 转化为大写
}
int isRepeat = false;
for(int j = 0; j < list.size(); j++) {
if (str1[i] == list[j]) {
isRepeat = true;
}
}
if (!isRepeat) {
list.push_back(str1[i]);
}
}
}
}

for (int k = 0; k < list.size(); k++) {
printf("%c", list[k]);
}

return 0;

}

1030 完美数列 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224

注意点:没理解透。采用二分查找防止超时,还有一种two pointers的方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 二分查找解法
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 100010;

int n, p, a[maxn];

main () {
scanf("%d%d", &n, &p);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 递增排序
sort(a, a + n);
int ans = 1;
for (int i = 0; i < n; i++) {
int j = upper_bound(a + i + 1, a + n, (long long)a[i] * p) - a;
ans = max(ans, j - i);
}
printf("%d\n", ans);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// two pointers解法
#include<cstdio>
#include<algorithm>

using namespace std;

main () {
const int maxn = 100010;
int n, p, a[maxn];

scanf("%d%d", &n, &p);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}

sort(a, a + n);

int i = 0, j = 0, count = 1;
while (i < n && j < n) {
// j不断右移,直到恰好不满足条件
while (j < n && a[j] <= (long long)a[i] * p) {
count = max(count, j - i + 1);
j++;
}
i++;
}
printf("%d\n", count);
return 0;
}

1031 查验身份证 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805290334011392

注意点:

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>

using namespace std;

main () {

char m[11] = {'1','0','X','9','8','7','6','5','4','3','2'};

int wList[18] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
int n;
scanf("%d", &n);

char str[20];
bool flag = true;
for (int i = 0; i < n; i++) {
int sum = 0;
bool isAllNum = true;
scanf("%s", str);
for (int j = 0; j < 17; j++) {
if (str[j] >= '0' && str[j] <= '9') {
sum += (str[j] - '0') * wList[j];
} else {
isAllNum = false;
break;
}
}
int r = sum % 11;
char M = m[r]; // 校验码
if (str[17] != M || isAllNum == false) {
flag = false;
printf("%s\n", str);
}
}
if (flag) {
printf("All passed");
}

return 0;

}

1032 挖掘机技术哪家强 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805289432236032

注意点:

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> a(N + 1);
int num, score;
for (int i = 0; i < N; i++) {
cin >> num >> score;
a[num] += score;
}
int max = a[1], t = 1;
for (int i = 2; i <= N; i++) {
if (max < a[i]) {
max = a[i];
t = i;
}
}
cout << t << " " << max;
return 0;
}

1033 旧键盘打字 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805288530460672

注意点:注意这题把字符当做数字使用的方式,以及getline与cin的区别,这题我原来用了cin,死活有一个点过不去,后来改了getline才可以。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

bool hashTable[128]= { 0 };//元素自己做下表

int main() {

string str1, str2;

getline(cin, str1);
getline(cin, str2);
// cin >> str1 >> str2;

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

hashTable[(int)str1[i]] = true;

if (str1[i] >= 'A' && str1[i] <= 'Z') {
hashTable[((int)str1[i]) + 32] = true;
}

if (str1[i] == '+') {

for (int j = 'A'; j <= 'Z'; j++) {
hashTable[(int)j] = true;
}

}

}

int count = 0;

for (int k = 0; k < str2.size(); k++) {
if (!hashTable[(int)str2[k]]) {
printf("%c", str2[k]);
count++;
}
}

if (count == 0) {
printf("\n");
}

return 0;
}

1034 有理数四则运算 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805287624491008

注意点:分数的四则运算,有套路,背下来。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

struct Fraction {
ll up, down;
};

ll gcd (ll a, ll b) {
// 辗转相除法
if (b == 0) { // 被除尽了
return a; // 返回公约数
} else {
return gcd(b, a % b);
}
}

// 化简
Fraction reduction (Fraction result) {
// 若分母为负
if (result.down < 0) {
result.up = - result.up;
result.down = - result.down;
}
// 若分子为0
if (result.up == 0) {
result.down = 1;
} else {
int d = gcd(abs(result.up), abs(result.down)); // 分子分母的最大公约数
result.up /= d;
result.down /= d;
}
return result;

}
// 加法
Fraction add (Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down + f2.up * f1.down;
result.down = f1.down * f2.down;
return reduction(result);
}

// 减法
Fraction minu (Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down - f2.up * f1.down;
result.down = f1.down * f2.down;
return reduction(result);
}

// 乘法
Fraction multi (Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.up;
result.down = f1.down * f2.down;
return reduction(result);
}

//除法
Fraction divide (Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down;
result.down = f1.down * f2.up;
return reduction(result);
}

// 输出
void showResult (Fraction r) {
r = reduction(r);
if (r.up < 0) printf("(");
if (r.down == 1) {
printf("%lld", r.up); // 整数
} else if (abs(r.up) / r.down) {
printf("%lld %lld/%lld", r.up / r.down, abs(r.up) % r.down, r.down);
} else {
printf("%lld/%lld", r.up, r.down);
}
if (r.up < 0) printf(")");
}

int main () {

Fraction a, b;

scanf("%lld/%lld %lld/%lld", &a.up, &a.down, &b.up, &b.down);
// 加法
showResult(a);
printf(" + ");
showResult(b);
printf(" = ");
showResult(add(a, b));
printf("\n");
// 减法
showResult(a);
printf(" - ");
showResult(b);
printf(" = ");
showResult(minu(a, b));
printf("\n");
// 乘法
showResult(a);
printf(" * ");
showResult(b);
printf(" = ");
showResult(multi(a, b));
printf("\n");
// 除法
showResult(a);
printf(" / ");
showResult(b);
printf(" = ");
if (b.up == 0) {
printf("Inf");
} else {
showResult(divide(a, b));
}

return 0;
}

1035 插入与归并 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805287624491008

注意点:插入排序与归并排序的应用。

1
2
3
PAT乙级需要掌握的排序算法:
一、基本排序算法:1. 冒泡排序 2. 选择排序 3. 插入排序
二、高级排序算法:2. 归并排序(two pointer)2. 快速排序(two pointer)

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 111;
int origin[N], tempOri[N], changed[N]; // 原始数组,原始数组备份,目标数组
int n;

// 判断数组是否相同
bool isSame (int A[], int B[]) {
for (int i = 0; i < n; i++) {
if (A[i] != B[i]) return false;
}
return true;
}

// 输出数组
bool showArray(int A[]) {
for (int i = 0; i < n; i++) {
printf("%d", A[i]);
if (i < n - 1) {
printf(" ");
}
}
printf("\n");
}

// 插入排序
bool insertSort () {
bool flag = false; // 是否有与目标数组相同
for (int i = 1; i < n; i++) {
if (i != 1 && isSame(tempOri, changed)) {
flag = true; // 与目标相同且不是初始状态
}
// 插入排序过程
int temp = tempOri[i], j = i;
while (j > 0 && tempOri[j - 1] > temp) {
tempOri[j] = tempOri[j - 1];
j--;
}
tempOri[j] = temp;
if (flag == true) {
return true; // 如果flag为true,则说明已达到目标数组,返回true
}
}
return false; // 无相同目标数组
}

// 归并排序
void mergeSort () {
bool flag = false;
for (int step = 2; step / 2 <= n; step *= 2) {
if (step != 2 && isSame(tempOri, changed)) {
flag = true;
}
for(int i = 0; i < n; i += step) {
sort(tempOri + i, tempOri + min(i + step, n));
}
if (flag == true) {
showArray(tempOri);
return;
}
}
}

main () {
scanf("%d", &n);
// 备份
for (int i = 0; i < n; i++) {
scanf("%d", &origin[i]);
tempOri[i] = origin[i];
}
for (int i = 0; i < n; i++) {
scanf("%d", &changed[i]); // 目标数组
}
if (insertSort()) {
printf("Insertion Sort\n");
showArray(tempOri);
} else {
printf("Merge Sort\n");
for (int i = 0; i < n; i++) {
tempOri[i] = origin[i];
}
mergeSort();
}
return 0;
}

1036 跟奥巴马一起编程 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805285812551680

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<math.h>

main () {
int n;
char str;

scanf("%d %c", &n, &str);
int row = round(n / 2.0);
int column = n;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (i == 0 || i == row - 1) {
if (j == column - 1) {
printf("%c\n", str);
} else {
printf("%c", str);
}
} else {
if (j == column - 1) {
printf("%c\n", str);
} else if (j == 0){
printf("%c", str);
} else {
printf(" ");
}
}
}
}

return 0;
}

1037 在霍格沃茨找零钱 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805284923359232

注意点:进制转换。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<math.h>

main () {

int Galleon1, Sickle2, Knut3;
int Galleon4, Sickle5, Knut6;

scanf("%d.%d.%d", &Galleon1, &Sickle2, &Knut3);
scanf("%d.%d.%d", &Galleon4, &Sickle5, &Knut6);

int sum1;
int sum2;
int sum3;

sum1 = Knut3 + Sickle2 * 29 + Galleon1 * 29 * 17;
sum2 = Knut6 + Sickle5 * 29 + Galleon4 * 29 * 17;

sum3 = sum2 - sum1;

int plus;

if (sum3 < 0) {
plus = -1;
} else {
plus = 1;
}

sum3 = abs(sum3);

printf("%d.%d.%d", plus * (sum3 / 493), sum3 / 29 % 17, sum3 % 29);
return 0;
}

1038 统计同成绩学生 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805284092887040

注意点:利用map的思想,不然会超时。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>

int map[100010] = { 0 };
main () {
int n;
scanf("%d", &n);

for (int i = 0; i < n; i++) {
int temp;
scanf("%d", &temp);
map[temp]++;
}

int m;
scanf("%d", &m);

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

int temp2;
scanf("%d", &temp2);

if (j == 0) {
printf("%d", map[temp2]);
} else {
printf(" %d", map[temp2]);
}

}
return 0;
}

1039 到底买不买 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805283241443328

注意点:利用hashTable的思想,把字符的ASCII码作为hash值。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

main () {

int hashTable1[128] = { 0 };

string str1, str2;

getline(cin, str1);
getline(cin, str2);

int len = str1.size();

for (int i = 0; i < str1.size(); i++) {
hashTable1[str1[i]]++;
}

int lessCount = 0;

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

if (hashTable1[str2[i]] > 0) {
len--;
hashTable1[str2[i]]--;
} else {
lessCount++;
}
}

if (lessCount > 0) {
printf("No %d", lessCount);
} else {
printf("Yes %d", len);
}

return 0;
}

1040 有几个PAT (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616

注意点:原理,累加每个A左边P的个数与右边T的个数的乘积,注意结果取模要在过程中,否则会溢出。B1045的思想类似。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<string>

using namespace std;

const int MAXN = 100010;

int main () {

int leftPNum[MAXN] = { 0 };

string str;

cin >> str;

// 统计每一位从左往右数的P的数量
for (int i = 0; i < str.size(); i++) {
if (i > 0) {
leftPNum[i] = leftPNum[i - 1]; // 继承上一位的数目
}
if (str[i] == 'P') {
leftPNum[i]++;
}
}

int count = 0;
int rightTnum = 0;

for (int i = str.size() - 1; i >= 0; i--) {

if (str[i] == 'T') {
rightTnum++;
} else if (str[i] == 'A') {
count = (count + leftPNum[i] * rightTnum ) % 1000000007; // 必须在这里取模,否则会在还没输出之前溢出
}

}

printf("%d", count);

return 0;
}

1041 考试座位号 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805281567916032

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<vector>

using namespace std;

struct Stu {
char n[15];
int testSeat;
int seat;
};

main () {
int n;
vector<Stu> list;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
Stu stu;
scanf("%s %d %d", &stu.n, &stu.testSeat, &stu.seat);
list.push_back(stu);
}
int m;
scanf("%d", &m);
for (int j = 0; j < m; j++) {
int num;
scanf("%d", &num);
for (int k = 0; k < list.size(); k++) {
if (list[k].testSeat == num) {
printf("%s %d\n", list[k].n, list[k].seat);
}
}
}

return 0;
}

1042 字符统计 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805280817135616

注意点:同样是字符处理问题,注意ASCII字符与数字的转化,还有哈希表的思想。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

main () {

string str;
int hashTable[128] = { 0 };

getline(cin, str);

for (int i = 0; i < str.size(); i++) {
int code;
if (str[i] >= 'A' && str[i] <= 'Z') {
code = str[i] + 32;
hashTable[code]++;
} else if (str[i] >= 'a' && str[i] <= 'z') {
code = str[i];
hashTable[code]++;
}
}

int maxN = 0;
int c;

for(int i = 'a'; i <= 'z'; i++)
{
if(hashTable[i] > maxN) {
maxN = hashTable[i];
c = i;
}
}

printf("%c %d", c, maxN);

return 0;
}

1043 输出PATest (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805280074743808

注意点:直接暴力输出。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <string>

using namespace std;

int main()
{
string s;
cin >> s;
int length = s.length();
int a[6] = { 0 };
for (int i = 0; i < length; i++)
{
if (s[i] == 'P')
{
a[0] ++;
}
else if (s[i] == 'A')
{
a[1] ++;
}
else if (s[i] == 'T')
{
a[2] ++;
}
else if (s[i] == 'e')
{
a[3] ++;
}
else if (s[i] == 's')
{
a[4] ++;
}
else if (s[i] == 't')
{
a[5] ++;
}
}
for (int i = 0; i < length; i++)
{
if (a[0] != 0)
{
cout << "P";
a[0]--;
}
if (a[1] != 0)
{
cout << "A";
a[1]--;
}
if (a[2] != 0)
{
cout << "T";
a[2]--;
}
if (a[3] != 0)
{
cout << "e";
a[3]--;
}
if (a[4] != 0)
{
cout << "s";
a[4]--;
}
if (a[5] != 0)
{
cout << "t";
a[5]--;
}
}

return 0;
}

1044 火星数字 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805279328157696

注意点:本质上是进制转化问题。注意substr的使用,注意getchar获取多余空格技巧。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<string>
#include<iostream>

using namespace std;

string mars1[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; // 低位

string mars2[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; // 高位

// 数字转火星文
void convertToMars (string str) {
int num = 0;
for (int i = 0; i < str.size(); i++) {
num = num * 10 + (str[i] - '0');
}

// 高位
if (num / 13) {
cout << mars2[ num / 13 ];
}

// 空格
if ((num / 13) && (num % 13)) {
cout << " ";
}

// 低位
if (num % 13 || num == 0) {
cout << mars1[num % 13];
}

}

// 火星文转数字
void marsToConvert (string str) {

int t1 = 0, t2 = 0;

string s1, s2;

s1 = str.substr(0, 3);
if (str.size() > 4) {
s2 = str.substr(4, 3);
}

for (int j = 1; j <= 12; j++) {
if (s1 == mars1[j] || s2 == mars1[j]) {
t2 = j; // 低位
}
if (s1 == mars2[j]) {
t1 = j; // 高位
}
}

cout << t1 * 13 + t2;

}

main () {

int n;

cin >> n;
getchar();

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

string str;
getline(cin, str);

if (str[0] >= '0' && str[0] <= '9') {
// 数字转火星文
convertToMars(str);
} else {
// 火星文转数字
marsToConvert(str);
}
cout << endl;
}
return 0;
}

1045 快速排序 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805278589960192

注意点:暴力会超时。思路原理与B1040一样,都是关注一个元素左边所有与右边所有的情况。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<vector>

using namespace std;

const int MAXN = 100010;

main () {

int n;

int a[MAXN], leftMax[MAXN], rightMin[MAXN];

vector<int> ans;

scanf("%d", &n);

for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}

leftMax[0] = 0;

// 找出i之前最大的
for (int i = 1; i < n; i++) {
if (leftMax[i - 1] > a[i - 1]) {
leftMax[i] = leftMax[i - 1];
} else {
leftMax[i] = a[i - 1];
}
}

rightMin[n -1] = 1000000000; // 一个很大的数字
// 找出i之后最小的
for (int i = n - 2; i >= 0; i--) {
if (rightMin[i + 1] < a[i + 1]) {
rightMin[i] = rightMin[i + 1];
} else {
rightMin[i] = a[i + 1];
}
}

for (int i = 0; i < n; i++) {
if (leftMax[i] < a[i] && rightMin[i] > a[i]) { // i之前都比它小,i之后都比它大,即为主元
ans.push_back(a[i]);
}
}

printf("%d\n", ans.size());

for (int i = 0; i < ans.size(); i++) {
if (i == 0) {
printf("%d", ans[i]);
} else {
printf(" %d", ans[i]);
}
}

if (ans.size() == 0) {
printf("\n");
}

return 0;
}

1046 划拳 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805277847568384

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>

main () {

int n;

scanf("%d", &n);

int aCount = 0, bCount = 0;

for (int i = 0; i < n; i++) {
int a1, r1, a2, r2;
scanf("%d %d %d %d", &a1, &r1, &a2, &r2);
if (a1 + a2 == r1 && a1 + a2 != r2) {
bCount++;
} else if (a1 + a2 == r2 && a1 + a2 != r1) {
aCount++;
}
}

printf("%d %d", aCount, bCount);

return 0;
}

1047 编程团体赛 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805277163896832

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>

main () {

int n;

scanf("%d", &n);
int hashTable[10010] = { 0 };

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

int teamNum, playerNum, score;

scanf("%d-%d %d", &teamNum, &playerNum, &score);

hashTable[teamNum] += score;

}

int maxTeam, maxScore = 0;

for (int i = 0; i < 10010; i++) {
if (hashTable[i] > maxScore) {
maxScore = hashTable[i];
maxTeam = i;
}
}

printf("%d %d", maxTeam, maxScore);
return 0;
}

1048 数字加密 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805276438282240

注意点:注意在string类型下,字符串相加的技巧。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<string>
#include<iostream>

using namespace std;

main () {

string str1, str2;

string t = "0123456789JQK";
cin >> str1 >> str2;

int max;
int len1 = str1.size(), len2 = str2.size();

max = len1 > len2 ? len1 : len2;

// 补零
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++) {
str2 = '0' + str2;
}
} else {
for (int i = 0; i < len2 - len1; i++) {
str1 = '0' + str1;
}
}

string s = "";

for (int i = max - 1; i >= 0; i--) {
int loc = max - i;

if (loc % 2 == 0) { // 偶数
s = t[((str2[i] - '0') - (str1[i] - '0') + 10) % 10] + s;
} else { // 奇数
s = t[((str1[i] - '0') + (str2[i] - '0')) % 13] + s;
}
}

cout << s;
return 0;
}

1049 数列的片段和 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805275792359424

注意点:https://www.jianshu.com/p/937a367ae4ea。数学问题。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int main()
{
int N;
double ai, sum = 0;

scanf("%d", &N);
for(int i = 0; i < N; i++)
{
scanf("%lf", &ai);
/* ai is put at the beginning to avoid overflow */
sum += ai * (i + 1) * (N - i);
}
printf("%.2lf", sum);

return 0;
}

1050 螺旋矩阵 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805275146436608

注意点:还需要再理解下。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 用这三个会超时 
//#include<cstdio>
//#include<algorithm>
//#include<math.h>

#include<bits/stdc++.h>

using namespace std;

int a[10000][1000] = { 0 }; // 螺旋矩阵
int s[10000]; // 原数组

bool cmp(int a, int b){
return a > b;
}

int main(){

int n,i,j,x,y,r,c,tot,minn = 9999;

// 输入
scanf("%d",&n);
for(int i = 0; i < n; i++) {
scanf("%d", &s[i]);
}
// 排序
sort(s, s + n, cmp);

// 计算行列
for(i = 1; i <= sqrt(n * 1.0); i++)
{
if(n % i==0)
{
if(n / i - i < minn){
minn = n / i - i;
r = i;
}
}
}
c = n / r; //c>r c行r列

a[1][1] = s[0]; // 初始点
tot = 0; // 总数
x = y = 1; // 初始化位置

while(tot < r * c-1) // 是否排满
{
// 向右走
while(y + 1 <= r && ! a[x][y + 1]) {
a[x][++y] = s[++tot];
}
// 向下走
while(x + 1 <= c && !a[x + 1][y]) {
a[++x][y] = s[++tot];
}
// 向左走
while(y - 1 > 0 && !a[x][y - 1]) {
a[x][--y] = s[++tot];
}
// 向上走
while(x - 1 > 0 && !a[x - 1][y]) {
a[--x][y] = s[++tot];
}
}

// 打印结果
for(i = 1; i <= c; i++) {
printf("%d", a[i][1]);
for(j=2; j <= r; j++) {
printf(" %d", a[i][j]);
}
printf("\n");

}
return 0;
}

1051 复数乘法 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805274496319488

注意点:三角恒等公式,复数的乘法。注意精度小于三位的情况要设为0。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <math.h>

main() {

double r1, r2, p1, p2;
double a, b;

scanf("%lf %lf %lf %lf", &r1, &p1, &r2, &p2);

a = (r1 * r2) * cos(p1 + p2); // r1 * r2 (cosp1cosp2 - sinp1sinp2)
b = (r1 * r2) * sin(p1 + p2); // r1 * r2 (sinp1cosp2 + cosp1sinp2)

if(fabs(a) < 0.01){
a = 0;
}

if(fabs(b) < 0.01){
b = 0;
}

if (b < 0) {
printf("%.2lf-%.2lfi", a, fabs(b));
} else {
printf("%.2lf+%.2lfi", a, b);
}
return 0;
}

1052 卖个萌 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805273883951104

注意点:字符串处理。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<string>
#include<vector>

using namespace std;

main () {

vector<string> hand;
vector<string> eye;
vector<string> mouth;

for (int i = 0; i < 3; i++) {
string str;
getline(cin, str);

vector<string> tempVector;

int j = 0, k = 0;
while (j < str.size()) {

if (str[j] == '[') {
string tempStr = "";
k = j + 1;
while (str[k] != ']') {
tempStr = tempStr + str[k];
k++;
}
tempVector.push_back(tempStr);
}
j++;
}

if (i == 0) {
hand = tempVector;
} else if (i == 1){
eye = tempVector;
} else if (i == 2) {
mouth = tempVector;
}
}

int m;

cin >> m;

for (int i = 0; i < m; i++) {
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
if (a > hand.size() || b > eye.size() || c > mouth.size() || d > eye.size() || e > hand.size() || a < 1 || b < 1 || c < 1 || d < 1 || e < 1) {
cout << "Are you kidding me? @\\/@" << endl;
continue;
}
cout << hand[a - 1] << "(" << eye[b - 1] << mouth[c - 1] << eye[d - 1] << ")" << hand[e - 1] << endl;
}

return 0;
}

1053 住房空置率 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805273284165632

注意点:注意用printf输出%和\的技巧。%%,\\

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>

main () {

int n, D; // D观察期阈值

double e; // e阈值

double ansA = 0, ansB = 0;

scanf("%d %lf %d", &n, &e, &D);

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

int m;
int count = 0;

scanf("%d", &m);

for (int j = 0; j < m; j++) {
double t;
scanf("%lf", &t);
if (t < e) {
count++;
}
}

if (count > m / 2 && m > D) {
ansB++; // 空置
} else if (count > m / 2 && m <= D) {
ansA++; // 可能空置
}

}

printf("%.1lf%% %.1lf%%", (ansA / n) * 100, (ansB / n) * 100);

return 0;
}

1054 求平均值 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805272659214336

注意点:用sscanf和sprintf处理字符串数据。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

int main() {
int n, cnt = 0;

char a[50], b[50];

double temp, sum = 0.0;

cin >> n;

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

scanf("%s", a);

sscanf(a, "%lf", &temp); // 把字符串以double类型赋给temp

// cout << "temp: " << temp << endl;

sprintf(b, "%.2f", temp); // 把temp以.2double赋给b

// cout << "a:" << a << " b:" << b << endl;

int flag = 0;

for(int j = 0; j < strlen(a); j++) {
if(a[j] != b[j]) flag = 1;
}

if(flag || temp < -1000 || temp > 1000) {
printf("ERROR: %s is not a legal number\n", a);
continue;
} else {
sum += temp;
cnt++;
}
}
if(cnt == 1) {
printf("The average of 1 number is %.2f", sum);
} else if(cnt > 1) {
printf("The average of %d numbers is %.2f", cnt, sum / cnt);
} else {
printf("The average of 0 numbers is Undefined");
}

return 0;
}

1055 集体照 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805272021680128

注意点:自己独立做一遍。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct node {
string name;
int height;
};

int cmp (struct node a, struct node b) {
return a.height != b.height ? a.height > b.height : a.name < b.name; // 身高不等,身高大的排前,身高相等,身高小的排前。
}

int main() {

int n, k, m;

cin >> n >> k; // n个人k排

vector<node> stu(n);

for(int i = 0; i < n; i++) {
cin >> stu[i].name >> stu[i].height;
}
// 排序
sort(stu.begin(), stu.end(), cmp);

int t = 0, row = k;

while(row) {

if(row == k) {
m = n - n / k * (k - 1); // 最高一排人数
}
else {
m = n / k; // 其余各排人数
}

vector<string> ans(m);
ans[m / 2] = stu[t].name; // 中间最高的人

// 左边一列
int j = m / 2 - 1;
for(int i = t + 1; i < t + m; i = i + 2) {
ans[j--] = stu[i].name; // 从高到低间隔放入左边
}
// 右边一列
j = m / 2 + 1;
for(int i = t + 2; i < t + m; i = i + 2) {
ans[j++] = stu[i].name; // 从高到低间隔放入右边
}
// 输出当前排
cout << ans[0];
for(int i = 1; i < m; i++)
cout << " " << ans[i];
cout << endl;

// 换下一排
t = t + m;
row--;
}

return 0;
}

1056 组合数的和 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805271455449088

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>

using namespace std;

int main() {

int n;

int sum = 0;

scanf("%d", &n);

int a[10];

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

scanf("%d", &a[i]);

}

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

int temp = a[i];
for (int j = 0; j < n; j++) {
if (j != i) {
sum += a[i]*10 + a[j];
}
}

}

printf("%d", sum);
return 0;
}

1057 数零壹 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805270914383872

注意点:考察进制转换。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>

using namespace std;

main () {

string str;
getline(cin, str);
int sum;

for (int i = 0; i < str.size(); i++) {
char temp = str[i];
int num = 0;
if (temp >= 'a' && temp <= 'z') {
num = temp - 'a' + 1;
sum += num;
}
if (temp >= 'A' && temp <= 'Z') {
num = temp - 'A' + 1;
sum += num;
}
}

int r;
int count1 = 0, count2 = 0;

while (sum > 0) {
r = sum % 2;
if (r == 1) {
count1++;
} else if (r == 0) {
count2++;
}
sum = sum / 2;
}

printf("%d %d", count2, count1);

return 0;
}

1058 选择题 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805270356541440

注意点:不难,但比较麻烦。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>

struct Ques {
int allScore; // 满分值
int selectNum; // 选项个数
int rSelectNum; // 正确选项个数
char select[6];
};

main () {

int N, M; // 学生人数,多选题的个数

scanf("%d %d", &N, &M);

Ques list[M];

int wrongAns[M] = { 0 };

for (int i = 0; i < M; i++) {
scanf("%d %d %d", &list[i].allScore, &list[i].selectNum, &list[i].rSelectNum);
for (int j = 0; j < list[i].rSelectNum; j++) {
getchar(); // 获取空格
scanf("%c", &list[i].select[j]);
}
}

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

getchar();

int score = 0;
for (int j = 0; j < M; j++) {

bool flag = false;

if (j != 0) {
getchar(); // 空格
}

int rNum;
scanf("(%d", &rNum);

char c;
if (rNum == list[j].rSelectNum) {
bool isSame = true;
for (int k = 0; k < rNum; k++) {
scanf(" %c", &c);
if (c != list[j].select[k]) {
isSame = false;
}
}
if (isSame) {
flag = true;
}
} else {
for (int k = 0; k < rNum; k++) {
scanf(" %c", &c);
}
}

scanf(")");

if (flag) {
score += list[j].allScore;
} else {
wrongAns[j]++; // 错误统计
}
}

printf("%d\n", score);

}

int maxWrong = 0;
for (int i = 0; i < M; i++) {
if(wrongAns[i] > maxWrong) {
maxWrong = wrongAns[i];
}
}

if (maxWrong == 0) {
printf("Too simple");
} else {
printf("%d", maxWrong);
for (int i = 0; i < M; i++) {
if(wrongAns[i] == maxWrong) {
printf(" %d", i + 1);
}
}
}
return 0;
}

1059 C语言竞赛 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805269828059136

注意点:注意其中map查询不到的时候的处理方式,以及素数的判断方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<map>
#include<string>
#include<iostream>
#include<math.h>

using namespace std;

map<string, int> m;

// 获取map的值
int getRank (string str) {
map<string, int>::iterator it = m.find(str);
if (it != m.end()) {
return it -> second;
} else {
return 0; // 没找到
}
}

// 是否是素数
bool isPrime (int n) {
if (n <= 1) {
return false;
}
int sqr = (int)sqrt(1.0 * n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

void check (string str) {

int res = getRank(str);

if (res == 0) { // 没找到
cout << str << ": " << "Are you kidding?" << endl;
} else if (res == -1) {
cout << str << ": " << "Checked" << endl;
} else {

if (res == 1) {
cout << str << ": " << "Mystery Award" << endl;
} else if(isPrime(res)) {
cout << str << ": " << "Minion" << endl;
} else {
cout << str << ": " << "Chocolate" << endl;
}

m[str] = -1;

}

}

main () {

int N;

scanf("%d", &N);
getchar(); // 获取空格
string str;

for (int i = 0; i < N; i++) {
getline(cin, str);
m[str] = i + 1;
}

int M;

scanf("%d", &M);
getchar();

string str2;
for (int i = 0; i < M; i++) {
getline(cin, str2);

check(str2);
}

return 0;
}

1060 爱丁顿数 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805269312159744

注意点:从大到小排序。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>

using namespace std;

bool cmp (int a, int b) {
return a > b;
}

main () {

int n;

int list[100010];

scanf("%d", &n);

for (int i = 0; i < n; i++) {
scanf("%d", &list[i]);
}

// 从大到小排列
sort(list, list + n, cmp);

int ans = 0;

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

int r = i + 1;

if (list[i] > r) {
ans = r;
}

}

printf("%d", ans);

return 0;
}

1061 判断题 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805268817231872

注意点:

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>

struct node {

int score;
int flag;

};

main () {

int N, M;

scanf("%d %d", &N, &M);
node list[M];

// 分值
for (int i = 0; i < M; i++) {
scanf("%d", &list[i].score);
}

// 答案
for (int i = 0; i < M; i++) {
scanf("%d", &list[i].flag);
}

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

int sum = 0;

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

int s;

scanf("%d", &s);

if (s == list[j].flag) {
sum += list[j].score;
}
}
printf("%d\n", sum);

}

}

1062 最简分数 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805268334886912

注意点:求最大公约数,与分数的加减乘除并无关系。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>

using namespace std;

// 最大公约数
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}

int main() {

int n1, m1, n2, m2, k;
scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);

// 当n1/m1大于n2/m2
if(n1 * m2 > n2 * m1) {
swap(n1, n2);
swap(m1, m2);
}

int num = 1; // 分子

bool flag = false; // 是否要打印空格

// 直到num/k > n1/m1
while(n1 * k >= m1 * num) {
num++;
}

// 在n1/m1和n2/m2之间,并且不可再约分的num/k
while(n1 * k < m1 * num && m2 * num < n2 * k) {
if(gcd(num, k) == 1) { // 最简(最大公约数是1)
printf("%s%d/%d", flag == true ? " " : "", num, k);
flag = true;
}
num++;
}

return 0;
}

1063 计算谱半径 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805267860930560

注意点:理解题意。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

double f (double a, double b){
return sqrt(( a * a + b * b ));
}

int main () {

int n;
double a, b, ans = 0;

scanf("%d", &n);

for (int i = 0; i < n; i++) {
scanf("%lf%lf", &a, &b);
ans = max(ans, f(a, b));
}

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

return 0;
}

1064 朋友数 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805267416334336

注意点:灵活运用hashTable,sort,vector,string。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

main () {

int n;
scanf("%d", &n);

vector<int> v;
int list[10010] = { 0 }; // 验证用

for (int i = 0; i < n; i++) {
string str;
cin >> str;
int sum = 0;

for (int j = 0; j < str.size(); j++) {
sum += str[j] - '0';
}

if (list[sum] == 0) {
v.push_back(sum);
list[sum] = 1;
}

}

printf("%d\n", v.size());
sort(v.begin(), v.end());

for (int i = 0; i < v.size(); i++) {
if (i == 0) {
printf("%d", v[i]);
} else {
printf(" %d", v[i]);
}
}

return 0;
}

1065 单身狗 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805266942377984

注意点:注意特殊情况00000,所以输出需要%05d,并且数组初始化为-1

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

main () {

int n;

vector<int> ori;
vector<int> ans;

int list1[100000]; // 用于存储couple
int list2[100000]; // 用于查询

// 全部设为-1,因为00000也是ID
memset(list1, -1, sizeof(list1));
memset(list2, -1, sizeof(list2));

scanf("%d", &n);

for (int i = 0; i < n; i++) {
int a, b;
scanf("%d %d", &a, &b);
list1[a] = b;
list1[b] = a;
}

int m;

scanf("%d", &m);

for (int i = 0; i < m; i++) {
int a;
scanf("%d", &a);
list2[a] = 1;
ori.push_back(a);
}

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

int a = -1, b = -1, c = -1;

a = ori[i];
b = list1[a]; // a的对象

if (b == -1) {
ans.push_back(a);
} else {
c = list2[b]; // b是否在list2中

if (c == -1) {
ans.push_back(a);
}

}

}

sort(ans.begin(), ans.end());
printf("%d\n", ans.size());

for (int i = 0; i < ans.size(); i++) {
if (i == 0) {
printf("%05d", ans[i]);
} else {
printf(" %05d", ans[i]);
}
}

return 0;
}

1066 图像过滤 (15 分)。

https://pintia.cn/problem-sets/994805260223102976/problems/994805266514558976

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>

main () {

int M, N, A, B, r;
int arr[510][510];

scanf("%d %d %d %d %d", &M, &N, &A, &B, &r);

for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int t;
scanf("%d", &t);
if (t >= A && t <= B) {
arr[i][j] = r;
} else {
arr[i][j] = t;
}
}
}

for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (j == 0) {
printf("%03d", arr[i][j]);
} else {
printf(" %03d", arr[i][j]);
}
if (j == N - 1) {
printf("\n");
}
}
}

return 0;
}

1067 试密码 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805266007048192

注意点:注意格式问题。注意获取行数的方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

main () {

string ans;
int n;
cin >> ans >> n;
string str;
bool flag = true;
getchar();
int count = 0;

while (getline(cin, str) && str != "#") {

if (flag) {

if (str == ans) {
flag = false;
cout << "Welcome in" << endl;
} else {

cout << "Wrong password: " << str << endl;

count++;

if (count >= n) {
flag = false;
cout << "Account locked" << endl;
}

}

} else {
continue;
}
}

return 0;
}

1068 万绿丛中一点红 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805265579229184

注意点:坑点在于审题,注意是要“独一无二”的颜色。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

main () {

int M, N, TOL;

map<int, int> vis; // 独一无二

scanf("%d %d %d", &M, &N, &TOL);
int arr[N][M];

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &arr[i][j]);
vis[arr[i][j]]++;
}
}

int count = 0;
int x, y, color;

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (vis[arr[i][j]] == 1) {
int c = arr[i][j];

// 上
if (i - 1 >= 0) {
if (abs(arr[i][j] - arr[i - 1][j]) <= TOL) {
continue;
}
}
// 右上
if (i - 1 >= 0 && j + 1 <= M) {
if (abs(arr[i][j] - arr[i - 1][j + 1]) <= TOL) {
continue;
}
}
// 右
if (j + 1 <= M) {
if (abs(arr[i][j] - arr[i][j + 1]) <= TOL) {
continue;
}
}
// 右下
if (i + 1 <= N && j + 1 <= M) {
if (abs(arr[i][j] - arr[i + 1][j + 1]) <= TOL) {
continue;
}
}
// 下
if (i + 1 <= N) {
if (abs(arr[i][j] - arr[i + 1][j]) <= TOL) {
continue;
}
}
// 左下
if (i + 1 <= N && j - 1 >= 0) {
if (abs(arr[i][j] - arr[i + 1][j - 1]) <= TOL) {
continue;
}
}
// 左
if (j - 1 >= 0) {
if (abs(arr[i][j] - arr[i][j - 1]) <= TOL) {
continue;
}
}
// 左上
if (j - 1 >= 0 && i - 1 >= 0) {
if (abs(arr[i][j] - arr[i - 1][j - 1]) <= TOL) {
continue;
}
}

x = i;
y = j;
color = arr[i][j];

count++;
}

}

}

if (count == 0) {
printf("Not Exist");
} else if (count == 1) {
printf("(%d, %d): %d", y + 1, x + 1, color);
} else {
printf("Not Unique");
}

return 0;
}

1069 微博转发抽奖 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805265159798784

注意点:这题网上搜的答案可以看出,在一定情况下,没有搜到key的map返回0也是可以作为判断依据的。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>
#include<string>
#include<map>

using namespace std;

map<string, int> m;

int isRepeat (string str) {
map<string, int>::iterator it = m.find(str);
if (it != m.end()) {
return it -> second;
} else {
return 0; // 没找到
}
}

main () {

int M, N, S;

scanf("%d %d %d", &M, &N, &S);
getchar();
int luck = S;
string str;
int count = 0;

int r = 0;

for (int i = 1; i <= M; i++) {
getline(cin, str);

if (luck <= M && i == luck) {
int res = isRepeat(str);
if (res == 0) {
cout << str << endl;
count++;
m[str] = 1;
luck += N;
} else {
luck++;
}
}

}

if (count == 0) {
cout << "Keep going..." << endl;
}

return 0;
}

另外答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>
using namespace std;
int main() {
int m, n, s;
scanf("%d%d%d", &m, &n, &s);
string str;
map<string, int> mapp;
bool flag = false;
for (int i = 1; i <= m; i++) {
cin >> str;
if (mapp[str] == 1) s = s + 1;
if (i == s && mapp[str] == 0) {
mapp[str] = 1;
cout << str << endl;
flag = true;
s = s + n;
}
}
if (flag == false) cout << "Keep going...";
return 0;
}

1070 结绳 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805264706813952

注意点:越长的绳子对折的次数应该要越少,最后才会最长。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

int n;
scanf("%d", &n);

vector<int> v(n);

for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}

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

int result = v[0];

for (int i = 1; i < n; i++) {
result = (result + v[i]) / 2;
}

printf("%d", result);
return 0;
}

1071 小赌怡情 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805264312549376

注意点:注意格式,total前面是两个空格。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>

using namespace std;

main () {

int T, K; // 赠送筹码,游戏次数

int chip;
scanf("%d %d", &T, &K);
chip = T;

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

int n1, b, t, n2;

int res;
scanf("%d %d %d %d", &n1, &b, &t, &n2);

if (chip == 0) {
printf("Game Over.\n");
break;
}
if (t > chip) {
printf("Not enough tokens. Total = %d.\n", chip);
continue;
}

if (n2 > n1) {
res = 1;
} else if (n2 < n1){
res = 0;
}

if ( res == b ) {
chip += t;
printf("Win %d! Total = %d.\n", t, chip);
} else {
chip -= t;
printf("Lose %d. Total = %d.\n", t, chip);
}
}

return 0;
}

1072 开学寄语 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805263964422144

注意点:注意格式问题,其中四位数字需要尤其注意, %04d。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<vector>

using namespace std;

main () {

int N, M; // 学生人数,需要被查缴的物品编号

char name[5];
int arr[10000] = { 0 };
scanf("%d %d", &N, &M);
int nameCount = 0, itemCount = 0;

for (int i = 0; i < M; i++) {
int n;
scanf("%d", &n);
arr[n] = 1;
}

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

int tempN;
vector<int> v; // 存储当前被缴获的
bool flag = false;

scanf("%s %d", name, &tempN);
for (int j = 0; j < tempN; j++) {
int k;
scanf("%d", &k);
if (arr[k] == 1) {
v.push_back(k);
}
}

if (v.size() != 0) {
nameCount++;
itemCount += v.size();
printf("%s:", name);
for (int h = 0; h < v.size(); h++) {
printf(" %04d", v[h]);
}
printf("\n");

}

}

printf("%d %d", nameCount, itemCount);
return 0;
}

1073 多选题常见计分法 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805263624683520

注意点:可以与B1058联动,我这里采用网上 “柳婼” 的做法。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n, m, optnum, truenum, temp, maxcnt = 0;
int hash[] = {1, 2, 4, 8, 16}, opt[1010][110] = {0};
char c;
scanf("%d %d", &n, &m);
vector<int> fullscore(m), trueopt(m);
vector<vector<int> > cnt(m, vector<int>(5));
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &fullscore[i], &optnum, &truenum);
for (int j = 0; j < truenum; j++) {
scanf(" %c", &c);
trueopt[i] += hash[c-'a'];
}
}
for (int i = 0; i < n; i++) {
double grade = 0;
for (int j = 0; j < m; j++) {
getchar();
scanf("(%d", &temp);
for (int k = 0; k < temp; k++) {
scanf(" %c)", &c);
opt[i][j] += hash[c-'a'];
}
int el = opt[i][j] ^ trueopt[j];
if (el) {
if ((opt[i][j] | trueopt[j]) == trueopt[j]) {
grade += fullscore[j] * 1.0 / 2;
}
if (el) {
for (int k = 0; k < 5; k++)
if (el & hash[k]) cnt[j][k]++;
}
} else {
grade += fullscore[j];
}
}
printf("%.1f\n", grade);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < 5; j++)
maxcnt = maxcnt > cnt[i][j] ? maxcnt : cnt[i][j];

if (maxcnt == 0) {
printf("Too simple\n");
} else {
for (int i = 0; i < m; i++) {
for (int j = 0; j < cnt[i].size(); j++) {
if (maxcnt == cnt[i][j])
printf("%d %d-%c\n", maxcnt, i+1, 'a'+j);
}
}
}
return 0;
}

1074 宇宙无敌加法器 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805263297527808

注意点:注意这里补零的方式,并且理解为什么最后一个进位一定是1。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>

using namespace std;

int main() {

string s, s1, s2, ans; // 进制表,第一个数,第二个数,答案

int carry = 0, flag = 0; // 进位,结果是否为0

cin >> s >> s1 >> s2;

ans = s;

// 将s1和s2变的与s一样长, 前面都是'0'
string ss1(s.length() - s1.length(), '0');
s1 = ss1 + s1;
string ss2(s.length() - s2.length(), '0');
s2 = ss2 + s2;

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

int mod = s[i] == '0' ? 10 : (s[i] - '0'); // 进制

ans[i] = (s1[i] - '0' + s2[i] - '0' + carry) % mod + '0'; // 当前位

carry = (s1[i] - '0' + s2[i] - '0' + carry) / mod; // 进位,进位永远都是1

}

if (carry != 0) ans = '1' + ans;

for(int i = 0; i < ans.size(); i++) {
if (ans[i] != '0' || flag == 1) {
flag = 1;
cout << ans[i];
}
}
if (flag == 0) cout << 0;
return 0;
}

1075 链表元素分类 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805262953594880

注意点:将数据分为3类,最后输出的时候有技巧。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>

using namespace std;

struct node {
int data, next;
}list[100000];

vector<int> v[3];

int main() {

int start, n, k, a;

scanf("%d%d%d", &start, &n, &k); // 第一个结点地址,结点总个数,以及正整数K

for (int i = 0; i < n; i++) {
scanf("%d", &a); // 结点地址作为下标
scanf("%d%d", &list[a].data, &list[a].next);
}

int p = start;

// 分为三类
while(p != -1) {

int data = list[p].data;

if (data < 0) { // 小于0的为一类
v[0].push_back(p);
}
else if (data >= 0 && data <= k) { // [0, k]为一类
v[1].push_back(p);
}
else { // 大于k为一类
v[2].push_back(p);
}
p = list[p].next;
}

int flag = 0;

for (int i = 0; i < 3; i++) {
for (int j = 0; j < v[i].size(); j++) {
if (flag == 0) {
printf("%05d %d ", v[i][j], list[v[i][j]].data); // 第一次,输出当前结点
flag = 1;
} else {
printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data); // 输出上一个结点的next,也就是当前结点v[i][j]。接着输出下一个结点。
}
}
}

printf("-1"); // 最后一个结点的next

return 0;
}

1076 Wifi密码 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805262622244864

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<string>
#include<iostream>

using namespace std;

main () {
int n;

scanf("%d", &n);

for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
string str;
char a, b;
cin >> str;
a = str[0];
b = str[2];
if (b == 'T') {
if (a == 'A') {
printf("1");
}
if (a == 'B') {
printf("2");
}
if (a == 'C') {
printf("3");
}
if (a == 'D') {
printf("4");
}
}
}
}

return 0;
}

1077 互评成绩计算 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805262303477760

注意点:注意其四舍五入的方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m; // 分组数与满分

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

int g2, g1 = 0, cnt = -2, temp, maxn = -1, minn = m + 1; // cnt去除最高分与最低分

cin >> g2;

for (int j = 0; j < n-1; j++) {
cin >> temp;
if (temp >= 0 && temp <= m) {
if (temp > maxn) maxn = temp;
if (temp < minn) minn = temp;
g1 += temp;
cnt++;
}
}

cout << int((((g1 - minn - maxn) * 1.0 / cnt) + g2) / 2 + 0.5) << endl;
}
return 0;
}

1078 字符串压缩与解压 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805262018265088

注意点:dev-c++ 工具-编译选项-编译器-编译 -std=c++11,stoi的用法。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>

using namespace std;

int main() {

char t;
cin >> t;

getchar();
string s, num;
getline(cin, s);

int cnt = 1;

if (t == 'D') { // 解压
for (int i = 0; i < s.length(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
num += s[i];
} else {
if (num.length() > 0) cnt = stoi(num); // string num 转化为 int cnt
while(cnt--) cout << s[i];
cnt = 1;
num = "";
}
}
} else if (t == 'C') { // 压缩
char pre = s[0]; // 前一个
for (int i = 1; i < s.length(); i++) {
if (s[i] == pre) { // 是否等于前一个
cnt++;
} else {
if (cnt >= 2) cout << cnt;
cout << pre;
cnt = 1;
pre = s[i];
}
}
// 结尾扫描存储下来的cnt和pre,记得输出
if (cnt >= 2) cout << cnt;
cout << pre;
}
return 0;
}

1079 延迟的回文数 (20 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805261754023936

注意点:重点在于其中的相加,需要使用大整数相加的想法。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
#include<string>

using namespace std;

// 与大整数相加类似
string add(string a) {
string b = a, ans;
reverse(b.begin(), b.end());
int len = a.length(), carry = 0;
for (int i = 0; i < len; i++) {
int num = (a[i] - '0' + b[i] - '0') + carry;
carry = 0;
if (num >= 10) {
carry = 1;
num = num - 10;
}
ans += char(num + '0');
}
if(carry == 1) ans += '1';
reverse(ans.begin(), ans.end());
return ans;
}

int main() {
string s;
cin >> s;

int cnt = 0;
while (cnt < 10) {

string t = s;
reverse(t.begin(), t.end()); // 将s翻转

if (t == s) {
cout << s << " is a palindromic number.";
break;
} else {
cout << s << " + " << t << " = " << add(s) << endl;
s = add(s);
cnt++;
}

}

if (cnt == 10) cout << "Not found in 10 iterations.";
return 0;
}

1080 MOOC期终成绩 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805261493977088

注意点:

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

struct node {
string name;
int gp, gm, gf, g; // 在线编程成绩,期中考试成绩,期末考试成绩,总评
};

bool cmp(node a, node b) {
return a.g != b.g ? a.g > b.g : a.name < b.name; // 总分递减,总分相同则姓名递增
}

map<string, int> idx; // 名字与在v中顺序的对应关系

int main() {

int p, m, n, score, cnt = 1;
cin >> p >> m >> n; // P(做了在线编程作业的学生数)、M(参加了期中考试的学生数)、N(参加了期末考试的学生数)

vector<node> v, ans;
string s;

// p个在线编程成绩
for (int i = 0; i < p; i++) {
cin >> s >> score;
if (score >= 200) {
v.push_back(node{s, score, -1, -1, 0}); // struct顺序初始化方式
idx[s] = cnt++;
}
}
// m个期中考试成绩
for (int i = 0; i < m; i++) {
cin >> s >> score;
if (idx[s] != 0) v[idx[s] - 1].gm = score;
}
// n个期末考试成绩
for (int i = 0; i < n; i++) {
cin >> s >> score;
if (idx[s] != 0) {
int temp = idx[s] - 1;
v[temp].gf = v[temp].g = score;
if (v[temp].gm > v[temp].gf) v[temp].g = int(v[temp].gm * 0.4 + v[temp].gf * 0.6 + 0.5); // 计算总评
}
}

// 总评超过60的即为答案
for (int i = 0; i < v.size(); i++) {
if (v[i].g >= 60) ans.push_back(v[i]);
}
// 按照cmp规则排序
sort(ans.begin(), ans.end(), cmp);
// 输出
for (int i = 0; i < ans.size(); i++) {
printf("%s %d %d %d %d\n", ans[i].name.c_str(), ans[i].gp, ans[i].gm, ans[i].gf, ans[i].g);
}

return 0;
}

1081 检查密码 (15 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805261217153024

注意点:一定要注意当需要一整行的时候,一行有可能出现空格的情况,需要使用getline,而使用getline,需要注意开头空格的情况。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

string check (string str) {
string ans;
bool a = false, b = false, c = false; // 字母,数字,其他
// 太短
if (str.size() < 6) {
ans = "Your password is tai duan le.";
return ans;
}
for (int i = 0; i < str.size(); i++) {

if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z') { // 字母
a = true;
}
else if (str[i] >= '0' && str[i] <= '9') { // 数字
b = true;
}
else if (str[i] == '.') { // 小数点

} else { // 其他
c = true;
}
}
if (c) {
ans = "Your password is tai luan le.";
}
if (!b && a) {
ans = "Your password needs shu zi.";
}
if (!a && b) {
ans = "Your password needs zi mu.";
}
if (!c && b && a) {
ans = "Your password is wan mei.";
}
return ans;
}

main () {

int n;
scanf("%d", &n);

getchar(); // 空格
for (int i = 0; i < n; i++) {
string str;
getline(cin, str);
string ans = check(str);
cout << ans << endl;
}

return 0;
}

1082 射击比赛 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805260990660608

注意点:只需要平方和就可以了。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

int main() {

int n, id, x, y, maxid, maxdis = -1, minid, mindis = 99999;

cin >> n;

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

cin >> id >> x >> y;

int dis = x * x + y * y;

if (dis > maxdis) maxid = id;
if (dis < mindis) minid = id;

maxdis = max(maxdis, dis);
mindis = min(mindis, dis);

}
printf("%04d %04d", minid, maxid);
return 0;
}

1083 是否存在相等的差 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805260780945408

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int main() {

int n, t, a[10000] = { 0 };

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

cin >> t;

a[abs(t-i)]++;

}
for (int i = 9999; i >= 0; i--) {
if (a[i] >= 2) cout << i << " " << a[i] << endl;
}

return 0;
}

1084 外观数列 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805260583813120

注意点:to_string的用法,for的别样用法。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

using namespace std;

int main() {
string s;
int n, j;

cin >> s >> n; // 求s的第n项

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

string t;

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

// 从i开始到j为相同的s[i]
for (j = i; j < s.length() && s[j] == s[i]; j++);

t += s[i] + to_string(j - i);

}

s = t; // 当前的s
}

cout << s;
return 0;
}

1085 PAT单位排行 (25 分)***

https://pintia.cn/problem-sets/994805260223102976/problems/994805260353126400

注意点:cctype其中一些处理字符串的函数。还有一个很重要的,就是遍历map的方式。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
#include <map>

using namespace std;

struct node {
string school; // 学校
int tws, ns; // 加权总分,考生人数
};

//学校首先按加权总分排行。如有并列,则应对应相同的排名,并按考生人数升序输出。如果仍然并列,则按单位码的字典序输出
bool cmp(node a, node b) {
if (a.tws != b.tws) {
return a.tws > b.tws;
}
else if (a.ns != b.ns) {
return a.ns < b.ns;
}
else {
return a.school < b.school;
}
}

int main() {
int n;
scanf("%d", &n); // 考生总人数

// 学校作为key
map<string, int> cnt; // 学校人数
map<string, double> sum; // 学校分数

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

string id, school; // 准考证,学校

// 输入准考证,分数,学校
cin >> id;
double score;
scanf("%lf", &score);
cin >> school;

// 学校转化为小写
for (int j = 0; j < school.length(); j++) {
school[j] = tolower(school[j]);
}

// 顶级与乙级的分数的处理
if (id[0] == 'B') {
score = score / 1.5;
}
else if (id[0] == 'T') {
score = score * 1.5;
}

sum[school] += score;
cnt[school]++;
}

vector<node> ans;
// 遍历学校
for (auto it = cnt.begin(); it != cnt.end(); it++) {
node temp = node{it->first, (int)sum[it->first], cnt[it->first]}; // 学校,加权总分,考生人数
ans.push_back(temp);
}

// 按规则学校排序
sort(ans.begin(), ans.end(), cmp);

// 输出答案
int rank = 0, pres = -1;
printf("%d\n", (int)ans.size()); // 学校总数
for (int i = 0; i < ans.size(); i++) {
// 如果当前分数与前一个不同,即排名增加,否则排名与前一位相同的保持一致
if (pres != ans[i].tws) {
rank = i + 1;
}
pres = ans[i].tws;
printf("%d ", rank); // 排名
cout << ans[i].school; // 学校名
printf(" %d %d\n", ans[i].tws, ans[i].ns); // 加权总分,考生人数
}
return 0;
}

1086 就不告诉你 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1038429065476579328

注意点:善于利用to_string,reverse等。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

main () {

int a, b, c;

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

c = a * b;

string d = to_string(c);

bool flag = false; // 数字最高位不能为0
for (int i = d.size() - 1; i >= 0; i--) {
if (d[i] != '0' || flag) {
flag = true;
cout << d[i];
}
}

return 0;
}

1087 有多少不同的值 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1038429191091781632

注意点:利用map或者set不重复的特点。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
scanf("%d", &n);
set<int> s;
for (int i = 1; i <= n; i++)
s.insert(i / 2 + i / 3 + i / 5);
printf("%d", s.size());
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<map>
#include<iostream>

using namespace std;

int main()
{
int n;
map<int, int> mp;
cin >> n;
for(int i = 1; i <= n; i++){
mp[i / 2 + i / 3 + i / 5] ++;
}
cout << mp.size() << endl;
return 0;
}

1088 三人行 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1038429286185074688

注意点:理解题意,丙不一定是整数。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>

using namespace std;

int m, x, y;

// 输出
void print(double t) {
if (m == t) printf(" Ping");
else if (m < t) printf(" Cong");
else printf(" Gai");
}

int main() {

scanf("%d %d %d", &m, &x, &y);

// i为甲,为两位数
for (int i = 99; i >= 10; i--) {
int j = i % 10 * 10 + i / 10; // j为乙
double k = abs(j - i) * 1.0 / x; // k为丙,不一定是整数。
if (j == k * y) { // 乙的能力值是丙的y倍
cout << i; // 输出甲
print(i); print(j); print(k); // 与自己做对比
return 0;
}
}
cout << "No Solution";
return 0;
}

1089 狼人杀-简单版 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1038429385296453632

注意点:https://blog.csdn.net/liuchuo/article/details/82560831

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n+1);
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
vector<int> lie, a(n + 1, 1);
a[i] = a[j] = -1;
for (int k = 1; k <= n; k++)
if (v[k] * a[abs(v[k])] < 0) lie.push_back(k);
if (lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0) {
cout << i << " " << j;
return 0;
}
}
}
cout << "No Solution";
return 0;
}

1090 危险品装箱 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1038429484026175488

注意点:https://blog.csdn.net/liuchuo/article/details/82560808

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
int n, k, t1, t2;
map<int,vector<int>> m;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d%d", &t1, &t2);
m[t1].push_back(t2);
m[t2].push_back(t1);
}
while (k--) {
int cnt, flag = 0, a[100000] = {0};
scanf("%d", &cnt);
vector<int> v(cnt);
for (int i = 0; i < cnt; i++) {
scanf("%d", &v[i]);
a[v[i]] = 1;
}
for (int i = 0; i < v.size(); i++)
for (int j = 0; j < m[v[i]].size(); j++)
if (a[m[v[i]][j]] == 1) flag = 1;
printf("%s\n",flag ? "No" :"Yes");
}
return 0;
}

1091 N-自守数 (15 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1071785664454127616

注意点:注意to_string与substr的运用。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>

using namespace std;

int main() {

int m;
cin >> m;

while (m--) {
int k, flag = 0;
cin >> k;

for (int n = 1; n < 10; n++) {
int mul = n * k * k;
string smul = to_string(mul), sk = to_string(k);
string smulend = smul.substr(smul.length() - sk.length());
if (smulend == sk) {
printf("%d %d\n", n, mul);
flag = 1;
break;
}
}
if (flag == 0) printf("No\n");
}
return 0;
}

1092 最好吃的月饼 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1071785779399028736

注意点:

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>

using namespace std;

int sum[1005];

int main() {
int m, n, maxn = 0, total = 0;
vector<int> ans;

cin >> m >> n; // 月饼种类,城市数量

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
sum[j] += a; // 记录第j种月饼的数量
maxn = max(maxn, sum[j]);
}
}

cout << maxn << endl; // 最大销量

// 最大销量并列的情况
for (int i = 1; i <= m; i++) {
if (sum[i] == maxn) ans.push_back(i);
}
// 递增顺序输出并列冠军
for (int i = 0; i < ans.size(); i++) {
if (i != 0) cout << " ";
cout << ans[i];
}
return 0;
}

1093 字符串A+B (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1071785884776722432

注意点:hashTable思想,已经输出过的字符串不输出即可。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

int main() {
string s1, s2, s;
int hash[200] = {0};

getline(cin, s1);
getline(cin, s2);
s = s1 + s2;

for (int i = 0; i < s.size(); i++) {
if (hash[s[i]] == 0) cout << s[i]; // 没有输出过的才输出
hash[s[i]] = 1;
}
return 0;
}

1094 谷歌的招聘 (20 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1071785997033074688

注意点:擅长应用substr,stoi,以及考察素数。

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

bool isPrime (int a) {
if (a <= 1) {
return false;
}
int sqr = (int)sqrt(1.0 * a);
for (int i = 2; i <= sqr; i++) {
if (a % i == 0) {
return false;
}
}
return true;
}

int main () {
int L, K;
string str;
cin >> L >> K >> str;
for (int i = 0; i <= L - K; i++) {
string s = str.substr(i, K);
int num = stoi(s);
if (isPrime(num)) {
cout << s;
return 0;
}
}
cout << "404\n";
return 0;
}

1095 解码PAT准考证 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/1071786104348536832

注意点:https://blog.csdn.net/liuchuo/article/details/84972869

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct node {
string t;
int value;
};
bool cmp(const node &a, const node &b) {
return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main() {
int n, k, num;
string s;
cin >> n >> k;
vector<node> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].t >> v[i].value;
for (int i = 1; i <= k; i++) {
cin >> num >> s;
printf("Case %d: %d %s\n", i, num, s.c_str());
vector<node> ans;
int cnt = 0, sum = 0;
if (num == 1) {
for (int j = 0; j < n; j++)
if (v[j].t[0] == s[0]) ans.push_back(v[j]);
} else if (num == 2) {
for (int j = 0; j < n; j++) {
if (v[j].t.substr(1, 3) == s) {
cnt++;
sum += v[j].value;
}
}
if (cnt != 0) printf("%d %d\n", cnt, sum);
} else if (num == 3) {
unordered_map<string, int> m;
for (int j = 0; j < n; j++)
if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
for (auto it : m) ans.push_back({it.first, it.second});
}
sort(ans.begin(), ans.end(),cmp);
for (int j = 0; j < ans.size(); j++) printf("%s %d\n", ans[j].t.c_str(), ans[j].value);
if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");
}
return 0;
}

分类与总结

分类与题目的对应

分类与题目的对应并不是一对一的关系,而是多对多的关系。分类表示可以用到某种特定的技巧,或者这题能归类到某种有规律的类型。

简单模拟

特点:直接依据题意处理。

  • 1001
  • 1006
  • 1031
  • 1041
  • 1046
  • 1051:数学问题
  • 1061
  • 1066
  • 1071
  • 1076
  • 1077
  • 1081
  • 1082
  • 1091
  • 1092

暂未定义类型

特点:暂时无法归类到某种特殊的类型。

  • 1003: 找规律
  • 1008: 找规律
  • 1010: 当没有给n的时候,使用EOF判断是否到结尾
  • 1011: 数字范围的判断,int 2^31 10^9,long long 2^63 10^18
  • 1012
  • 1014: 字符串处理
  • 1018
  • 1020:找规律
  • 1023:找规律,最高位打印除0以外最小的,其余的顺序从小到大按数量打印
  • 1024:处理字符串
  • 1028
  • 1029:字符串处理
  • 1048:字符串处理
  • 1049:数学问题
  • 1050:找规律
  • 1052:字符串处理
  • 1053
  • 1055
  • 1056
  • 1058
  • 1060
  • 1063
  • 1067
  • 1070:找规律
  • 1073
  • 1088
  • 1089
  • 1090
  • 1095

字符与数字的相互转化

特点:字符转化为数字的方法有

字符串转数字

  1. 确定是数字字符的,比如’9’,’8’等,直接减去字符’0’,ASCII的相差即为所求的数字。
  2. 使用stoi,把string类型的转化为数字。 (dev-c++ 工具-编译选项-编译器-编译 -std=c++11,stoi的用法)
  3. sscanf(str,”%d”,&a);, 将str(char[])赋给a(int)

数字转字符串

  1. 数字转化为字符串:使用标准库函数to_string()。
  2. 数字转化为字符串:使用sprintf(str,”%d”,a);,这意味着将a(int)赋给str(char[])
  • 1002
  • 1016
  • 1018
  • 1078
  • 1084
  • 1086

排序

特点:排序算法sort的使用,能够理解并手写一些排序算法,
比如,
(从小到大排序)
冒泡排序,(交换)(进行n-1趟,每趟n - 1 - i次交换,每趟把最大的交换到最后)
选择排序,(交换)(进行n趟,每趟把最小的换到最前)(想法与冒泡类似)
插入排序,(后移)(进行n-1趟,每趟把加入的数,换到合适的位置)
归并排序,(分治,合并)两两分组,之后重复合并。(非递归写法)
快速排序。

添加:字符串比较strcmp()

  • 1004
  • 1015:考察sort中cmp函数的编写,以及vector排序的方式
  • 1035:插入与归并,需要大部分的排序算法与实现

hashTable思想

特点:hashTable的理解与使用。

  1. 当key是int的时候可以用范围合适的数组作为hashTable,记得数组的初始化可以用{ 0 }全部初始化为0,当不初始化为0的情况,也可以使用memset(a, -1, sizeof(a));,也可以使用fill(a, a + i, -1)。
  2. 当key是字符串的时候,应该使用map,注意map的遍历方式,以及map查询不到的情况的处理,当value为int的时候,可以将返回为0作为未查询到。
  • 1005
  • 1032
  • 1033
  • 1038
  • 1039
  • 1042
  • 1043
  • 1047
  • 1059
  • 1064:包括vector的排序
  • 1065
  • 1068
  • 1069
  • 1072
  • 1080
  • 1083
  • 1085:***这题方法记下,关注map的遍历方式:auto it = cnt.begin(); it != cnt.end(); it++。auto类似于js的var,自动推导其类型。
  • 1087
  • 1093

素数

特点:牢记素数判断的函数,性能比较好的用sqrt开平方的那种。

  • 1007
  • 1013
  • 1059
  • 1094

大整数运算

特点:大整数的存储方式,大整数的加减乘除

  • 1017
  • 1021
  • 1079

分数的四则运算

特点:特意背下。

  • 1034

进制转化

特点:

  1. P进制转化为10进制:多项式累加
  2. 除基取余法:除以进制,留下余数,得到的商再除以进制。
  • 1022
  • 1057
  • 1074

链表

特点:难,单独处理

  • 1025(未完成)
  • 1075

单位转化

特点:比如日期转化之类的

  • 1026
  • 1037
  • 1044

图形输出

特点:找到规律,注意格式

  • 1027
  • 1036

二分查找与two pointer

  • 1030:完美数列

左右两边问题

特点:属于同一种题,体会思想

  • 1040:找规律
  • 1045:找规律

sscanf与sprintf

特点:字符与其他格式做转化,可以利用不符合的情况下不赋值这一特性。

  • 1054

最大公约数与最小公倍数

特点:辗转相除法

  • 1062

stack

特点:需要倒序输出可以尝试用stack

  • 1009

math与algorithm

algorithm

1
2
3
4
5
6
7
max(),min(),abs(),

swap(a, b),reverse(a, a + i),

fill(a, a + i, -1),sort(a, a + i, cmp),

lower_bound(a, a + i, -1), upper_bound(a, a + i, -1)

math

1
2
3
4
5
6
7
8
9
fabs(double x), floor(double x), ceil(double x),

pow(double r, double p), sqrt(double x), log(double x),

sin(double x), cos(double x), tan(double x)

asin(), acos(), atan(),

double r = round(double x)

[译]你不知道的Node

发表于 2018-10-20 | 更新于 2019-02-07 | 分类于 翻译
1
原文:https://webapplog.com/you-dont-know-node/

你不知道的Node:核心特性的快速介绍

dog

这篇文章是由Kyle Simpson的系列书籍You-Dont-Know-JS所启发。它们是很好的JavaScript基础入门书籍。除了一些我将会在文章中强调的不同,Node基本上就是JavaScript。代码在you-dont-know-node github仓库下的code文件夹下。

为什么在意Node?Node是JavaScript而JavaScript几乎要占领世界了。如果更多开发者掌握Node这个世界岂不是变得更好?更好的应用等于更好的人生!

这是一个主观的最有趣核心特性大合集。这篇文章的重点如下:

  1. Event loop(事件循环):温习下使非阻塞I/O成为可能的核心概念
  2. Global(全局变量) 和 process(进程):如何获得更多信息
  3. Event emitters(事件发射器):基于事件模式的速成课
  4. Streams(流) 和 buffers(缓冲区):处理数据的高效方式
  5. Clusters(集群):像一个专家一样fork进程
  6. 处理异步错误:AsyncWrap,Domain和uncaughtException
  7. C++扩展:给核心做贡献并写你自己的C++扩展

Event Loop(事件循环)

我们可以从Node的核心事件循环开始

dog

Node.js Non-Blocking I/O

它允许在处理IO调用的过程中处理其他任务。想想看Nginx vs. Apache。它让Node更快更有效率,因为阻塞式I/O十分昂贵!

看下这个在 java 中基础的延迟 println 函数的例子:

1
2
3
4
System.out.println("Step: 1");
System.out.println("Step: 2");
Thread.sleep(1000);
System.out.println("Step: 3");

和Node代码是可比较的(实际上不可比较):

1
2
3
4
5
console.log('Step: 1')
setTimeout(function () {
console.log('Step: 3')
}, 1000)
console.log('Step: 2')

实际并不太相同。你需要开始用异步的方式思考。Node脚本输出是1,2,3,但如果我们在“Step 2”后放更多语句,它们将会在setTimeout回调之前运行。看看以下片段:

1
2
3
4
5
6
7
console.log('Step: 1')
setTimeout(function () {
console.log('Step: 3')
console.log('Step 5')
}, 1000);
console.log('Step: 2')
console.log('Step 4')

最终产出1,2,4,3,5。这是因为setTimeout把它的回调放入事件循环的未来周期中了。

把事件循环想象成一个永远旋转的循环就像for循环或者while循环。它只有在现在或者未来没有东西去执行的时候才会停止。

dog

Blocking I/O: Multi-Threading Java

事件循环让你的系统更加的有效率,因为现在你可以在你等待你昂贵的输入输出任务结束的时候,你可以做更多事情。

pic4

Non-Blocking I/O: Node.js

这与我们当前的直接使用系统线程的并发模型做对比。基于线程的网络设计相对来说更没有效率更难用。此外,Node的使用者不用担心进程的死锁,因为根本就没有锁。

小边注:那么我们仍然可能在Node中写阻塞代码吗?思考下面这个简单但是阻塞的Node代码:

1
2
3
4
5
6
7
8
console.log('Step: 1')
var start = Date.now()
for (var i = 1; i<1000000000; i++) {
// This will take 100-1000ms depending on your machine
}
var end = Date.now()
console.log('Step: 2')
console.log(end-start)

当然,一般情况下,我们不会在我们的代码中写空循环。指出同步因此当我们使用他人的模块的时候,阻塞式代码可能更难。比如,核心的fs模块就有两组方法。每组执行相同的功能但用不同的方式。阻塞的fsNode方法在名字上带有Sync:

1
2
3
4
5
6
7
8
9
var fs = require('fs')

var contents = fs.readFileSync('accounts.txt','utf8')
console.log(contents)
console.log('Hello Ruby\n')

var contents = fs.readFileSync('ips.txt','utf8')
console.log(contents)
console.log('Hello Node!')

结果即使Node/JavaScript新手来说也很容易猜出

1
data1->Hello Ruby->data2->Hello NODE!

当我们转为异步方法,就不一样了。这是非阻塞的Node代码:

1
2
3
4
5
6
7
8
9
10
11
var fs = require('fs');

var contents = fs.readFile('accounts.txt','utf8', function(err,contents){
console.log(contents);
});
console.log('Hello Python\n');

var contents = fs.readFile('ips.txt','utf8', function(err,contents){
console.log(contents);
});
console.log("Hello Node!");

将会最后打印contents因为需要一段时间去执行,他们在回调中。事件循环将会在文件读取结束的时候调用他们:

1
Hello Python->Hello Node->data1->data2

所以事件循环和非阻塞I/O非常强大,但你需要写异步代码,然而我们大部分在学校都不是学习这种代码。

Global(全局)

当从浏览器JavaScript或者其他编程语言转到Node,会有下面几个问题:

  • 哪里去存储密码?
  • 如何创建全局变量(在Node中没有window)
  • 如何获得命令行输入,操作系统,平台,内存使用,版本等等?

有一个全局对象,它有一些属性。部分如下:

  • global.process: 进程,系统,环境信息(你可以获得命令行输入,环境变量比如密码,内存等)
  • global.__filename: 文件名和当前运行脚本的路径
  • global.__dirname: 当前运行脚本的绝对路径
  • global.module: 对象用于导出代码,使这个文件变为一个模块
  • global.require(): 导入模块,JSON文件,和文件夹的方法

接下来就是我们熟悉的来自浏览器JavaScript的方法:

  • global.console()
  • global.setInterval()
  • global.setTimeout()

每一个全局属性都可以通过大写的GLOBAL或者干脆没有命名空间比如process代替global.process

Process(进程)

Process对象有许多信息,理应做成一个部分。我列出其中的一些属性:

  • process.pid:这个Node实例的进程ID
  • process.versions:Node,V8和其他组件的各种版本
  • process.arch:系统的架构
  • process.argv:命令行参数
  • process.env:环境变量

一些方法如下:

  • process.uptime():获取uptime
  • process.memoryUsage():获取内存使用
  • process.cwd():获取当前工作目录。不要与__dirname混淆,后者不依赖于启动进程的位置。
  • process.exit():退出当前进程。你可以传入1或0。
  • process.on():添加一个事件监听器比如’on(‘uncaughtException’)’

棘手的问题:谁会喜欢并且理解回调??

一些人太喜欢回调了,于是他们创建了http://callbackhell.com。如果你还不熟悉这个术语,以下是展示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fs.readdir(source, function (err, files) {
if (err) {
console.log('Error finding files: ' + err)
} else {
files.forEach(function (filename, fileIndex) {
console.log(filename)
gm(source + filename).size(function (err, values) {
if (err) {
console.log('Error identifying file size: ' + err)
} else {
console.log(filename + ' : ' + values)
aspect = (values.width / values.height)
widths.forEach(function (width, widthIndex) {
height = Math.round(width / aspect)
console.log('resizing ' + filename + 'to ' + height + 'x' + height)
this.resize(width, height).write(dest + 'w' + width + '_' + filename, function(err) {
if (err) console.log('Error writing file: ' + err)
})
}.bind(this))
}
})
})
}
})

回调地狱难以阅读,并且容易出错。除此之外回调并不能很好的扩展,那么我们该如何模块化和管理异步代码?

Event Emitters(事件发射器)

为了解决回调地狱,或者说末日金字塔,我们有了Event Emitters。他们允许你用事件的方式执行异步代码。

简单来说,event Emitters就是你触发了一个事件,所有有监听这个事件的都可以听到。在Node中,一个事件可以描述为一个字符串和一个响应的回调。

Event Emitters为了以下目的:

  • 用观察者模式处理Node中的事件处理
  • 一个事件追溯所有与之相关联的函数
  • 这些相关联的函数,我们称之为观察者,当对应事件被触发的时候执行

为了使用Event Emitters,导入模块并实例化对象:

1
2
var events  = require('events')
var emitter = new events.EventEmitter()

之后,我们添加事件监听器然后触发事件:

1
2
3
4
5
6
7
8
9
emitter.on('knock', function() {
console.log('Who\'s there?')
})

emitter.on('knock', function() {
console.log('Go away!')
})

emitter.emit('knock')

让我们通过继承EventEmitter来实现一些更有用的。想象你的任务是实现一个类来完成每月,每周和每日的邮件工作。这个类需要足够灵活能够让开发者去自定义最终的输出。换句话说,任何人消费这个类需要在工作结束的时候做一些自定义的逻辑。

下面这个图解解释了我们继承events模块去创建Job,然后我们使用done事件监听器去自定义Job类的行为:

pic4

Node.js Event Emitters: Observer Patterns

类Job将会保持它的属性,但也会得到events。我们需要做的只是在结束的时候触发done即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
// job.js
var util = require('util')
var Job = function Job() {
var job = this
// ...
job.process = function() {
// ...
job.emit('done', { completedOn: new Date() })
}
}

util.inherits(Job, require('events').EventEmitter)
module.exports = Job

现在,我们的目标是自定义Job任务结束后的行为:

1
2
3
4
5
6
7
8
9
10
// weekly.js
var Job = require('./job.js')
var job = new Job()

job.on('done', function(details){
console.log('Job was completed at', details.completedOn)
job.removeAllListeners()
})

job.process()

还有一些emitters的其他功能:

  • emitter.listeners(eventName):列出相应事件的对应的所有事件监听器
  • emitter.once(eventName, listener):添加一个只触发一次的事件监听器
  • emitter.removeListener(eventName, listener):移除一个事件监听器

事件模式在Node中广泛应用,特别是在核心模块。所以,掌握事件将会给你一个很大的提升。

Streams(流)

当Node中处理大的数据的时候有一些问题。速度可能会很慢并且buffer的限制是1Gb。并且,如果资源是持续的,没有设置尽头的,你改如何处理?为了解决这些问题,使用streams(流)。

Node流是持续的数据块的抽象。换句话说,不需要等待整个资源被加载。看下下面的图解展示了标准的buffer的处理方式:

pic4

Node.js Buffer Approach

我们必须等到全部的buffer加载之后,才可以处理输出的数据。接下来,对比下一个描绘流的图解。这下,我们可以从收到的第一个数据块开始马上处理数据:

pic4

Node.js Stream Approach

在Node中有四种类型的Streams:

  • Readable:可读
  • Writable:可写
  • Duplex:即可读也可写
  • Transform:你可以转换数据

事实上在Node中Streams到处都是。最常见的stream实现是:

  • HTTP请求和响应
  • 标准输入/输出
  • 文件读取和写入

Streams继承自Event Emitter,使其提供观察者模式,比如events,还记得吗?我们可以用它来实现流。

可读流例子

一个可读流的例子可以是标准输入流process.stdin。它包含了进入应用的数据。典型的输入是从键盘用来开始进程。

为了读取从stdin读取数据,使用data和end事件。data事件的回调将会把数据块作为参数传入:

1
2
3
4
5
6
7
8
9
10
process.stdin.resume()
process.stdin.setEncoding('utf8')

process.stdin.on('data', function (chunk) {
console.log('chunk: ', chunk)
})

process.stdin.on('end', function () {
console.log('--- END ---')
})

然后数据块便输入至程序。根据输入的大小,事件可能会触发多次。end事件是用于输入流最后的信号。

提示:stdin默认是停止的,所以在读数据之前要resume(恢复)。

可读流有一个同步的read()接口。当流结束的时候,它返回数据块或者null。于是我们可以利用这种特性把null !== (chunk = readable.read())放入while的条件中:

1
2
3
4
5
6
7
var readable = getReadableStreamSomehow()
readable.on('readable', () => {
var chunk
while (null !== (chunk = readable.read())) {
console.log('got %d bytes of data', chunk.length)
}
})

理想情况下,我们想尽量在Node中多写异步代码,为了避免阻塞主线程。然而,数据块很小,所以不必担心同步的readable.read()阻塞线程。

Pipe(管道)

Node为开发者提供了一个事件的替代方案。我们可以使用pipe()方法。下面的例子为读一个文件,用GZip压缩,然后把压缩的数据写入文件:

1
2
3
4
var r = fs.createReadStream('file.txt')
var z = zlib.createGzip()
var w = fs.createWriteStream('file.txt.gz')
r.pipe(z).pipe(w)

Readable.pipe()接受一个可写流然后返回一个终点。这样我们就可以把pipe()方法一个一个串联起来。

所以你使用流的时候在events和pipes之间就可以选择了。

HTTP Streams(HTTP流)

我们大部分使用Node构建传统或者RESTful Api的web应用。所以我们可以把HTTP请求变为流吗?答案是一个响亮的yes。

请求和响应都是可读可写的流并且都继承event emitters。我们可以添加一个data事件监听器。在回调中我们接收数据块,我们马上转化数据块而无需等到全部的响应。在下面的例子中,我拼接body并在end事件的回调中解析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const http = require('http')
var server = http.createServer( (req, res) => {
var body = ''
req.setEncoding('utf8')
req.on('data', (chunk) => {
body += chunk
})
req.on('end', () => {
var data = JSON.parse(body)
res.write(typeof data)
res.end()
})
})

server.listen(1337)

接下来我们使用Express.js让我们的服务更加接近真实情况。在下一个例子中,我有一个巨大的图片(~8Mb)并且有两组路由:/stream和/non-stream。

server-stream.js:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
app.get('/non-stream', function(req, res) {
var file = fs.readFile(largeImagePath, function(error, data){
res.end(data)
})
})

app.get('/non-stream2', function(req, res) {
var file = fs.readFileSync(largeImagePath)
res.end(file)
})

app.get('/stream', function(req, res) {
var stream = fs.createReadStream(largeImagePath)
stream.pipe(res)
})


app.get('/stream2', function(req, res) {
var stream = fs.createReadStream(largeImagePath)
stream.on('data', function(data) {
res.write(data)
})
stream.on('end', function() {
res.end()
})
})

我在/stream2中也有一个替代事件的实现并且在/non-stream2中有一个替代同步的实现。他们做的事是一样的,只不过是用了不同的语法和风格。在这个例子中同步方法性能表现会更好,因为我们只发送了一个请求,而不是同时多个。

为了启动例子,在命令行中输入:

1
$ node server-stream

接下来在chrome中打开http://localhost:3000/stream和http://localhost:3000/non-stream。在开发者工具中的Network标签页中将会向你展示headers。对比X-Response-Time。在我的例子中,是数量级的差距, /stream vs. /stream2:300ms vs. 3–5s。

你的结果可能不一样,但我想表达的意思是使用流,用户可以更早的得到数据。Node的流确实很强大。这里有一些好的关于流的资源,掌握了它们然后在你的团队中成为一个流的专家。

Stream Handbook和stream-adventure你可以通过npm安装:

1
2
$ sudo npm install -g stream-adventure
$ stream-adventure

Buffers

对于二进制数据我们使用什么类型?如果你记得的话,浏览器JavaScript没有二进制类型,但是Node有。我们称之为buffer。是一个全局对象,所以我们不用把他当作模块导入。

创建二进制类型,使用下面的声明之一:

  • Buffer.alloc(size)
  • Buffer.from(array)
  • Buffer.from(buffer)
  • Buffer.from(str[, encoding])

官方[Buffer文档]列出所有的方法和编码。最流行的编码是utf8。

一个典型的buffer看起来像是乱码,所以我们必须用toString()把它转化为人类可读的格式。下面的for循环创建一个字母表的buffer:

1
2
3
4
let buf = Buffer.alloc(26)
for (var i = 0 ; i < 26 ; i++) {
buf[i] = i + 97 // 97 is ASCII a
}

如果我们不把它转化为字符串,这个buffer看起来就像一个数字的数组。

1
console.log(buf) // <Buffer 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a>

如果我们用toString把它转化为字符串

1
2
buf.toString('utf8') // outputs: abcdefghijklmnopqrstuvwxyz
buf.toString('ascii') // outputs: abcdefghijklmnopqrstuvwxyz

如果我们只是需要部分的字符串,这个方法接收开始数字和结束位置:

1
2
3
buf.toString('ascii', 0, 5) // outputs: abcde
buf.toString('utf8', 0, 5) // outputs: abcde
buf.toString(undefined, 0, 5) // encoding defaults to 'utf8', outputs abcde

还记得fs吗?默认情况下data的值也是buffer:

1
2
3
4
fs.readFile('/etc/passwd', function (err, data) {
if (err) return console.error(err)
console.log(data)
});

Clusters(集群)

你可能经常从Node怀疑者那听到说Node是单线程的,所以它没法规模化。有一个核心模块cluster(核心模块意味着你不用安装,它是平台的一部分)允许你利用每个机器的所有CPU能力。这允许你垂直的扩展你的Node程序。

代码是很简单的。我们需要引入模块,创建一个master,和多个worker。典型的我们有多少个CPU核心就创建多少个进程。但这不是硬性规定。你可创建任意数量的进程,但到某一个点,收益递减规律介入,你不会有任何性能提高。

master和worker的代码在同一个文件。worker可以监听同一个端口并且发送消息(通过事件)给master。master可以监听事件并且在需要的时候重启cluster。为master写代码的方式是使用cluster.isMaster(),对worker来说就是cluster.isWorker()。大部分服务器代码都放在worker(isWorker())。

1
2
3
4
5
6
7
8
9
// cluster.js
var cluster = require('cluster')
if (cluster.isMaster) {
for (var i = 0; i < numCPUs; i++) {
cluster.fork()
}
} else if (cluster.isWorker) {
// your server code
})

在cluster.js例子中,我的服务器输出进程ID,因此你可以看到不同的worker处理不同的请求。这就像负载均衡,但这不是真正的负载均衡,因为负载没有平均的分散。你可能看到大量的请求在同一个进程中(PID会一样)。

为了看到不同的worker服务不同的请求,使用loadtest,一个基于Node的压力测试工具:

  1. 通过npm安装loadtest:$ npm install -g loadtest
  2. 使用node运行code/cluster.js($ node cluster.js);让server运行
  3. 运行负载测试:$ loadtest http://localhost:3000 -t 20 -c 10在一个新的窗口
  4. 同时在服务终端和loadtest终端分析结果
  5. 当测试结束的时候在终端按下control+c。你应该看到不同的PID。写下请求服务的数字。

-t 20 -c 10负载测试命令意味着将会有10并发请求,最大时间为20秒。

自带的集群唯一的优势就是核心的一部分。当你准备发布到生产,你应该想要更先进的进程管理工具:

  • strong-cluster-control(https://github.com/strongloop/strong-cluster-control)
  • pm2(https://github.com/Unitech/pm2)

pm2

来谈谈pm2,被认为是一种横向扩展你的Node应用的方式(最好的方式之一),并且有着生产级别的性能和特性。

总的来说,pm2有以下几种优势:

  • 负载均衡和其他特性
  • 系统宕机重启
  • 好的测试覆盖

pm2的文档在这 https://github.com/Unitech/pm2 和 http://pm2.keymetrics.io。

看一下下面的这个作为pm2例子的Express服务。这里没有样板代码isMaster(),这样很好,因为你不用改变你的源码,就像我们在cluster中做的那样。我们只需要打印pid并且观察他们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var express = require('express')
var port = 3000
global.stats = {}
console.log('worker (%s) is now listening to http://localhost:%s',
process.pid, port)
var app = express()
app.get('*', function(req, res) {
if (!global.stats[process.pid]) global.stats[process.pid] = 1
else global.stats[process.pid] += 1;
var l ='cluser '
+ process.pid
+ ' responded \n';
console.log(l, global.stats)
res.status(200).send(l)
})
app.listen(port)

使用pm2启动server.js来使用这个pm2例子。你可以传入需要复制的进程数(-i 0 意味着CPU的数量,在我的例子中是4个)并且将日志放入一个文件中(-l log.txt):

1
$ pm2 start server.js -i 0 -l ./log.txt

另一个pm2的优点是前台。想看当前运行,执行:

1
$ pm2 list

接下来,就像我们在cluster例子中做的那样使用loadtest。在一个新窗口,运行命令:

1
$ loadtest  http://localhost:3000 -t 20 -c 10

你的结果也许和我的不一样,但是我在log.txt中差不多得到了平均分散的结果:

1
2
3
4
5
6
7
8
cluser 67415 responded
{ '67415': 4078 }
cluser 67430 responded
{ '67430': 4155 }
cluser 67404 responded
{ '67404': 4075 }
cluser 67403 responded
{ '67403': 4054 }

Spawn vs Fork vs Exec

既然我们在cluster.js的例子中使用fork()来创建Node服务的新实例,那就有必要来提下在Node中的三种方式来启动一个外部的进程。他们是spawn(), fork() 和 exec()并且他们三个都来自核心模块child_process。他们之间的区别总结如下:

  • require('child_process').spawn():用于大的数据,支持流,可以用于任何命令,并且不创建新的V8实例
  • require('child_process').fork():创建一个V8实例,实例化多个worker,只能用于Node.js脚本(node命令)
  • require('child_process').exec():使用buffer,让其不适合大的数据或者流,以异步的方式让你在回调中一下获取全部的数据,并且可以用于所有命令

看下下面这个例子,我们执行node program.js,但我们也可以执行bash,Python,Ruby或任意其他的命令或脚本。如果你需要给命令传入额外的参数,只需要把需要参数作为数组传入spawn()。数据作为流在data事件传入:

1
2
3
4
5
6
var fs = require('fs')
var process = require('child_process')
var p = process.spawn('node', 'program.js')
p.stdout.on('data', function(data)) {
console.log('stdout: ' + data)
})

从node program.js命令的角度来看,data是它的标准输出,比如,node program.js的终端输出。

fork()的语法和spawn()相似,除了没有命令,因为fork()假定所有的进程都是Node.js:

1
2
3
4
5
6
var fs = require('fs')
var process = require('child_process')
var p = process.fork('program.js')
p.stdout.on('data', function(data)) {
console.log('stdout: ' + data)
})

最后一项是exec()。这个有点不同,因为它没有使用事件模式,只是一个简单的回调。在回调中,你有错误,标准输出和标准错误参数:

1
2
3
4
5
var fs = require('fs')
var process = require('child_process')
var p = process.exec('node program.js', function (error, stdout, stderr) {
if (error) console.log(error.code)
})

errorandstderr的不同之处在于前者来自exec(),而后者来自你运行着的命令的错误。

Handling Async Errors

说到报错,在Node.js和其他几乎所有编程语言中,我们使用try/catch处理错误。对于同步错误,try/catch处理的不错:

1
2
3
4
5
try {
throw new Error('Fail!')
} catch (e) {
console.log('Custom Error: ' + e.message)
}

模块或者函数抛出错误,而后我们catch。这种对Java或者同步Node有效果。但是,Node的最佳实践是写异步代码,所以我们不阻塞线程。

事件循环让系统调度,使得昂贵的输入/输出任务结束的时候,执行相应的代码。但是伴随着异步错误,系统丢失了错误的上下文。

比如,setTimeout()异步使得回调在未来被调用。这有点像,HTTP请求,数据库读取或者写文件的异步函数:

1
2
3
4
5
6
7
try {
setTimeout(function () {
throw new Error('Fail!')
}, Math.round(Math.random()*100))
} catch (e) {
console.log('Custom Error: ' + e.message)
}

当回调被执行的时候,没有catch到,接下来应用崩溃。当然如果你在回调中放一个try/catch,会catch到错误,但这不是一个好的解决方案。这些讨厌的异步错误难于调试和处理。try/catch不足以处理异步错误。

那么异步报错无法catch。我们该怎么处理??你已经见过大部分的回调会有一个error参数。开发者需要去检查错误,并在回调中冒泡上去:

1
2
3
if (error) return callback(error)
// or
if (error) return console.error(error)

其他处理异步错误的最佳实践如下:

  • 监听所有“on error”事件
  • 监听uncaughtException
  • 使用domain或者AsyncWrap
  • 打印与跟踪
  • 提示(可选)
  • 退出或重启

on(‘error’)

监听所有on(‘error’)事件,这些事件大部分由核心Node对象特别是http触发的。并且,任何继承http或者Express.js, LoopBack, Sails, Hapi等实例都会触发error事件,因为这些框架继承自http:

1
2
3
4
5
6
// js
server.on('error', function (err) {
console.error(err)
console.error(err)
process.exit(1)
})

uncaughtException

一定要在process对象上监听uncaughtException事件。uncaughtException是一个非常原始的异常处理机制。一个未处理的异常意味着你的应用-包括你的Node本身-是一个异常状态。盲目的恢复意味着什么都有可能发生。

1
2
3
4
5
process.on('uncaughtException', function (err) {
console.error('uncaughtException: ', err.message)
console.error(err.stack)
process.exit(1)
})

或者

1
2
3
4
5
process.addListener('uncaughtException', function (err) {
console.error('uncaughtException: ', err.message)
console.error(err.stack)
process.exit(1)
})

Domain

Domain和浏览器上的web域没有关系。domain是一个Node核心模块,可以通过保存异步代码执行的上下文来处理异步错误。一个domain基本的用法是实例化它然后把你的报错代码放入run()的回调中:

1
2
3
4
5
6
7
var domain = require('domain').create()
domain.on('error', function(error){
console.log(error)
})
domain.run(function(){
throw new Error('Failed!')
})

domain在4.0版本被软弃用了,意味着Node核心团队将会把domain同平台分离,但是现在核心还暂时没有domain的替代品。并且,因为domain有着很好的支持和使用,它会继续独立作为npm模块的一份子,这样你可以轻易的从核心转移到npm模块,意味着domain还生存的很好。

让我们用setTimeout再创建一个异步错误:

1
2
3
4
5
6
7
8
9
10
// domain-async.js:
var d = require('domain').create()
d.on('error', function(e) {
console.log('Custom Error: ' + e)
})
d.run(function() {
setTimeout(function () {
throw new Error('Failed!')
}, Math.round(Math.random()*100))
});

代码不会崩溃!我们将会得到一个很好的错误信息,从domain的错误事件处理函数得到的“Custom Error”错误,而不是典型的Node堆栈跟踪。

C++ Addons(C++扩展)

Node在硬件,IoT和机器人流行的原因是Node可以很好的适应底层的C/C++代码。那么我们该如何为你的IoT,硬件,机器人,智能设备写C/C++ binding代码?

这是这篇文章的最终章节。大部分的Node初学者甚至认为你不能够写自己的C++扩展!事实上,这很简单,我们从头开始来。

首先,创建hello.cc文件,这个文件在开头有着一些样板引用。接下来我们定义一个方法,这个方法返回一个字符串并导出这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <node.h>

namespace demo {

using v8::FunctionCallbackInfo;
using v8::HandleScope;
using v8::Isolate;
using v8::Local;
using v8::Object;
using v8::String;
using v8::Value;

void Method(const FunctionCallbackInfo<Value>& args) {
Isolate* isolate = args.GetIsolate();
args.GetReturnValue().Set(String::NewFromUtf8(isolate, "capital one")); // String
}

void init(Local<Object> exports) {
NODE_SET_METHOD(exports, "hello", Method); // Exporting
}

NODE_MODULE(addon, init)

}

即使你不是C的专家,也很容易看出发生了是吗,因为这和JavaScript的语法也不是天壤之别。字符串是capital one:

1
args.GetReturnValue().Set(String::NewFromUtf8(isolate, "capital one"));`

导出的名字是hello:

1
2
3
void init(Local<Object> exports) {
NODE_SET_METHOD(exports, "hello", Method);
}

一旦hello.cc准备好了,我们还需要做一些事。其中一件是创建binding.gyp,包含着源代码文件名和扩展的名称:

1
2
3
4
5
6
7
8
{
"targets": [
{
"target_name": "addon",
"sources": [ "hello.cc" ]
}
]
}

把binding.gyp保存在hello.cc相同的文件夹下并在安装node-gyp:

1
$ npm install -g node-gyp

安装完node-gyp之后,在hello.cc和binding.gyp的同级文件夹下运行配置和构建命令

1
2
$ node-gyp configure
$ node-gyp build

这些命令将会创建build文件夹。检查下在build/Release/下编译好的.node文件。

最后,创建一个Node脚本hello.js然后将你的C++扩展引入:

1
2
3
4
5
var addon = require('./build/Release/addon')
console.log(addon.hello()) // 'capital one'
```

运行脚本然后将会看见我们的字符串capital one:

$ node hello.js
`

Summary(总结)

上面的实例代码都在github。如果你对Node的模式比如观察者模式,回调和Node惯例感兴趣,看下我的这篇Node Patterns: From Callbacks to Observer。

我知道这是一篇长阅读,所以来个30秒的总结:

  1. 事件循环:Node非阻塞I/O背后的原理
  2. Global和process:全局对象和系统信息
  3. Event Emitters:Node的观察者模式
  4. 流:大体积数据的模式
  5. Buffers:二进制数据类型
  6. Clusters:垂直扩展
  7. Domain:异步错误处理
  8. C++扩展:底层扩展

Node的大部分就是JavaScript,除了一些核心特性大部分用于处理系统访问、全局变量、外部进程和底层代码。如果你理解了这些概念,你就踏上了掌握Node的快车道。

[译]10个编译为JavaScript的语言

发表于 2018-10-09 | 更新于 2018-10-10 | 分类于 翻译
1
原文:https://www.sitepoint.com/10-languages-compile-javascript/

介绍了10种可以编译为JavaScript的语言

翻译连接

《深入理解ES6》笔记之函数

发表于 2017-11-09 | 更新于 2018-07-29 | 分类于 js

函数形参的默认值

在ES6中可以为函数形参指定默认值,如下:

1
2
3
4
5
function makeRequest(url, timeout = 2000,callback = function() {}) {

//函数的其余部分

}

还可以使用非原始值传参,如下面这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
let value = 5;

function() {
return value++;
}

function add(first,second = getValue()){
return first+second;
}

console.log(add(1,1)); //2
console.log(add(1)); //6
console.log(add(1)); //7

getValue在声明的时候不会调用,只有在调用add且不传入第二个参数时才会调用。

不定参数

在函数的命名参数前添加三个点(…)就表明这是一个不定参数,该参数为一个数组,包含着自它之后传入的所有参数,通过这个数组名即可逐一访问里面的参数。

1
2
3
4
5
6
7
8
9
function checkArgs(normalPara,...args){
console.log(normalPara);
console.log(args.length);
console.log(arguments.length);
console.log(args[0],arguments[1]);
console.log(args[1],arguments[2]);
}

checkArgs("a","b","c");

调用checkArgs(),输出以下内容

1
2
3
4
5
a
2
3
b b
c c

箭头函数

箭头函数是一种使用箭头(=>)定义函数的新语法,但是它与传统的JavaScript函数有些许不同,主要集中在以下方面:

  • 没有this、super、arguments和new.target绑定
  • 不能通过new关键字调用
  • 没有原型
  • 不可以改变this的绑定
  • 不支持arguments对象
  • 不支持重复的命名参数

箭头函数语法

语法

箭头函数语法多变,但无论再怎么变化,主要由三部分组成,参数、箭头、函数体。

比如单参数,简单返回

1
value => value

空函数

1
() => {}

多参数,多返回

1
(num1,num2)=> num1 + num2

类传统形式

1
2
3
4
5
(num1,num2)= {
//do something

return num1 + num2;
}

没有this绑定

js中函数内的this经常在调用的过程中发生改变,以前我们只能用蹩脚的bind或者call之类的来解决。现在,我们可以直接使用箭头函数。

箭头函数中的this值取决于改函数外部非箭头函数的this值,且不能通过call()、apply()和bind()方法来改变this的值。

1
2
3
4
5
6
7
8
9
10
11
12
var handler = {
id: '123456',

init: function() {
document.addEventListener('click',
event => this.doSomething(event.type), false);
},

doSomething: function(type) {
console.log('Handling ' + type + ' for ' + this.id);
}
};

上面的例子中使用了箭头函数,于是导致this.dosomething这一行的this总是指向handler对象,这种行为为我们带来了许多方便。

箭头函数缺少正常函数所拥有的prototype属性,它的设计初衷是“即用即弃”。在日常开发中很适合用于回调函数。

[译]理解并使用js回调函数|性感的js

发表于 2017-11-07 | 更新于 2018-07-29 | 分类于 翻译
1
原文:http://javascriptissexy.com/understand-javascript-callback-functions-and-use-them

在 JavaScript 中,函数是第一类对象;这意味着,函数是Object类型并且可以像其他对象一样(比如String,Array,Number)以第一类的方式使用,因为他们本身都是对象。他们可以“被储存进变量中,作为参数传入一个函数,在函数中被创建,并在函数中被返回”。

因为函数是第一类对象,我们可以把函数作为参数传入另外一个函数并且之后可以执行传入的函数或者甚至把函数返回出来以供后面执行。这就是在 JavaScript 中使用回调函数的本质。在余下的文章中我们会学到 JavaScript 回调函数的方方面面。回调函数大概是在 JavaScript 中使用最为广泛的函数式编程技术了,你大概可以在任何JavaScript代码或者jQuery代码中看到它,然而它对许多JavaScript开发者来说还是保持神秘。当你读完这篇文章的时候,它将不再神秘了。

回调函数是由一个叫做函数式编程的编程范式而来的。最基础来说,函数式编程具体规定了把函数作为参数来使用。函数式编程曾经是-当然现在也是,不过程度有所减少-被认为是一种编程大师的特殊技巧。

幸运的是,函数式编程这门技术已经被解释清楚,以至于像你我这样的普通人也可以轻而易举的理解和使用了。函数式编程中一个主要的技巧正好就是回调函数。很快你就会读到,实现一个回调函数就像传入一个普通变量作为参数那样简单。这个技巧如此简单以至于我总是惊奇它经常被放在高级JavaScript主题下。

什么是回调或者高阶函数

回调函数,也被称作高阶函数,就是把一个函数作为参数传入“另一个函数”,然后回调函数在“另一个函数”中调用。回调函数本质上是一种模式(对一种问题的确定解决方案),因此使用回调函数我们也称之为回调模式。

思考下面这个在jQuery中回调函数的常见用法:

1
2
3
4
//注意传入click方法的参数是一个函数,不是一个变量。
$("#btn_1").click(function() {
alert("Btn 1 Clicked");
});

在以上的例子中可以看到,我们把函数当做一个参数传给一个click方法。click方法则会调用我们传的那个回调函数。这个例子展示了一种典型的回调函数的使用,这是种在jQuery中广泛使用的方式。

思考下面另一个典型的回调函数的例子:

1
2
3
4
5
var friends = ["Mike", "Stacy", "Andy", "Rick"];

friends.forEach(function (eachName, index){
console.log(index + 1 + ". " + eachName); // 1\. Mike, 2\. Stacy, 3\. Andy, 4\. Rick
});

和上面一样,注意我们把一个匿名函数作为参数给 forEach 方法的这种方式。

到此为止我们已经把匿名函数做为参数传给了另一个函数或方法。接下来在我们看更多具体的例子之前,让我们先来理解回调是如何工作的并开始创建我们自己的回调函数。

回调函数是怎么工作的

我们可以把函数像变量一样在函数中传递和返回,并在另一个函数中使用。当我们把函数作为参数传递给另一个函数,我们只是传递了函数的定义。我们没有在参数中调用函数。换句话来说,我们没有像执行函数一样带着一对括号那样传递函数。

并且因为包含函数有着作为函数定义的回调函数作为参数,它就可以在任何时候调用。

注意回调函数不是立即就执行。它是在包含的函数体中指定的地方“回头调用”。所以,即使第一个jQuery例子张的像这样:

1
2
3
4
//在参数中匿名函数并没有执行
$("#btn_1").click(function() {
alert("Btn 1 Clicked");
});

那个匿名函数将会过一会在函数体中调用。即使没有命名,它也可以通过arguments对象在函数体中获得。

回调函数是闭包

当我们把一个回调函数作为参数传入另一个函数,回调在包含函数体中某一个位置被调用,就好像回调是在包含函数体中被定义一样。这意味着回调是一个闭包。读我的另一个博文Understand JavaScript Closures With Ease,了解更多关于闭包的事情。众所周知,闭包可以获得包含函数的作用域,这样闭包就可以访问包含函数的内部的变量,甚至也能访问全局的变量。

实现回调函数的基本原则

在不复杂的情况下,回调有一些值得注意的原则在我们实现的时候需要熟悉的。

使用命名过的或匿名函数作为回调

在先前的jQuery和forEach例子,我们使用定义在包含函数的参数中的匿名函数。这是一种经常使用模式之一。另一个流行的模式是声明一个命名函数然后将这个函数的名字作为参数。考虑以下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 全局变量
var allUserData = [];

// 打印用logStuff函数
function logStuff (userData) {
if ( typeof userData === "string")
{
console.log(userData);
}
else if ( typeof userData === "object")
{
for (var item in userData) {
console.log(item + ": " + userData[item]);
}

}

}

// 一个有两个参数的函数,最后一个参数是回调函数
function getInput (options, callback) {
allUserData.push (options);
callback (options);

}

// 当我们调用getInput函数的时候,我们传入logStuff作为参数
// 所以logStuff函数将会在getInput函数内部回头调用(或者说执行)
getInput ({name:"Rich", speciality:"JavaScript"}, logStuff);
// name: Rich
// speciality: JavaScript

传参给回调函数

因为回调函数在执行的时候就是一个正常的函数,那我们自然可以传参给它。我们可以传入任意的包含函数的内容(或者全局内容)作为参数传给回调函数。在之前的例子中,我们传options作为参数给回调函数。下面来传下全局变量和本地变量:

1
2
3
4
5
6
7
8
//全局变量
var generalLastName = "Clinton";

function getInput (options, callback) {
allUserData.push (options);
// 把全局变量generalLastName传给回调函数
callback (generalLastName, options);
}

在执行回调的时候确保它是个函数

在调用传入的回调函数参数之前检查是否确实是一个函数总是明智的。同样,让这个回调函数可选,也是一个好的实践。

让我们来重构下之前的例子中的getInput函数来保证有适当的检查。

1
2
3
4
5
6
7
8
9
function getInput(options, callback) {
allUserData.push(options);

// 确认回调是一个函数
if (typeof callback === "function") {
// 已确认是一个函数,就可以放心的调用了
callback(options);
}
}

如果getInput函数在没有回调函数作为参数或用非函数代替函数传入的情况下调用的话,没有这些适当的检查,我们的代码将会报一个运行时错误。

当使用带有this对象的方法作为回调的问题

当回调是一个使用this对象的方法时,我们要改变下调用回调函数的方式来保持this对象上下文。否则当回调传给一个全局函数的时候,this对象将会指向全局window对象。或者它会指向包含这个方法的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 定义一个有着一些属性和方法的对象
// 过一会会把方法作为回调函数传给另一个函数
var clientData = {
id: 094545,
fullName: "Not Set",
// setUserName是一个在clientData对象上的方法
setUserName: function (firstName, lastName) {
this.fullName = firstName + " " + lastName;
}
}

function getUserInput(firstName, lastName, callback) {
// 在这里可以验证下firstName/lastName

// 在这里保存名字
callback (firstName, lastName);
}

在下面的例子中,当clientData.setUserName执行的时候,this.fullName将会不在clientData对象上设置fullName属性。反而,它会在window对象上设置fullName属性,原因是getUserInput是一个全局函数。而在全局函数中,this对象指向window对象。

1
2
3
4
5
6
getUserInput ("Barack", "Obama", clientData.setUserName);

console.log (clientData.fullName);// Not Set

// fullName属性在window对象上被初始化了
console.log (window.fullName); // Barack Obama

使用Call或者Apply函数来保持this

我们可以通过使用Call或者Apply函数解决之前的问题 (我们将会在之后的一篇博客里讨论着两个方法)。暂时,你只需要知道在JavaScript中,每一个函数都有两个方法:Call和Apply。这两个方法用于设置函数中的this对象并且传入参数。

Call把第一个参数的值用于函数内的this对象,然后剩下的参数独立地传给函数(通过逗号分隔)。Apply函数也是把第一个参数的值用于函数内的this对象,然而最后一个参数是一个传给对象的数组(或者arguments对象)。

这听起来很复杂,但是让我们来看看使用Apply或Call是多么简单。想要解决先前例子中的问题,我们将会使用Apply函数:

1
2
3
4
5
6
//注意这里我们为回调对象多加了个参数,叫做callbackObj
function getUserInput(firstName, lastName, callback, callbackObj) {

// 用apply函数把this指向callbackObj
callback.apply (callbackObj, [firstName, lastName]);
}

随着Apply函数正确地设置this对象,我们现在也在clientData对象上可以正确地执行回调并且正确地设置fullName属性了:

1
2
3
4
5
// 我们传入clientData.setUserName方法和clientData对象作为参数。clientData对象将用apply函数设置this对象
getUserInput ("Barack", "Obama", clientData.setUserName, clientData);

// clientData上的fullName属性被正确地设置。
console.log (clientData.fullName); // Barack Obama

我们也可以使用Call函数,但是在这个例子中我们使用Apply函数。

允许多个回调函数

我们可以传入不止一个回调函数作为函数的参数,就像我们可以传入不止一个参数。下面是一个典型jQuery AJAX函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function successCallback() {
// Do stuff before send
}

function successCallback() {
// Do stuff if success message received
}

function completeCallback() {
// Do stuff upon completion
}

function errorCallback() {
// Do stuff if error received
}

$.ajax({
url:"http://fiddle.jshell.net/favicon.png",
success:successCallback,
complete:completeCallback,
error:errorCallback

});

“回调地狱”问题和解决方案

进行任何顺序的异步代码执行的时候,经常会出现很多层的回调函数,在某种程度下,会像以下的代码这样。以下的这些凌乱的代码我们称之为回调地狱,因为太多层回调以至于难以理解代码。我从node-mongodb-native中找到下面的代码。以下的代码只是用于展示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var p_client = new Db('integration_tests_20', new Server("127.0.0.1", 27017, {}), {'pk':CustomPKFactory});
p_client.open(function(err, p_client) {
p_client.dropDatabase(function(err, done) {
p_client.createCollection('test_custom_key', function(err, collection) {
collection.insert({'a':1}, function(err, docs) {
collection.find({'_id':new ObjectID("aaaaaaaaaaaa")}, function(err, cursor) {
cursor.toArray(function(err, items) {
test.assertEquals(1, items.length);

// Let's close the db
p_client.close();
});
});
});
});
});
});

你可能不会经常在代码里遇到这样的问题,但你总会不时的遇见,这时候你有以下两种解决方案。

  1. 相比于在函数的参数中定义一个匿名函数,你可以显示的声明函数并命名,然后用传递函数名的方法代替回调。
  2. 模块化:把你的代码模块化,你可以导出一部分代码做特定的事情。然后你在你更大的应用中导入这个模块。

创建你自己的回调函数

现在你已经完全掌握了JavaScript回调函数的方方面面了,并且你已知道使用回调函数非常简单而强大,所以现在你现在应该着眼于你自己的代码中使用回调函数的机会,因为它会让你:

  1. 不重复代码
  2. 更多通用的代码,实现更好的抽象
  3. 更好的可维护性
  4. 更好的可读性
  5. 更多专业的函数

创建你自己的回调函数是相当简单的。在下面的例子中,我本可以创建一个函数去做所有的事情:获取用户数据,用数据创建一个通用的诗歌,并且致敬用户。这将会是一个有着众多if/else语句的混乱的函数,并且即使如此它也是非常有局限性,不能够胜任应用需要用用户的数据实现的其他功能。

相反,我把功能的执行交给回调函数,这样获得了数据的主函数就可以通过简单的传用户名和性别的参数给回调函数并执行回调来执行几乎任何任务。

简单来说,getUserInput函数是通用的:它可以执行各种功能的回调:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 首先,创建通用诗歌创作函数;它将会是下面的getUserInput函数的回调函数
function genericPoemMaker(name, gender) {
console.log(name + " is finer than fine wine.");
console.log("Altruistic and noble for the modern time.");
console.log("Always admirably adorned with the latest style.");
console.log("A " + gender + " of unfortunate tragedies who still manages a perpetual smile");
}


//最后一个参数就是回调函数,它将会是我们上面定义的genericPoemMaker
function getUserInput(firstName, lastName, gender, callback) {
var fullName = firstName + " " + lastName;

// 确认回调是函数
if (typeof callback === "function") {
// 执行回调函数并传入参数
callback(fullName, gender);
}
}

调用getUserInput函数并传入genericPoemMaker函数作为回调:

1
2
3
4
5
6
7
getUserInput("Michael", "Fassbender", "Man", genericPoemMaker);
// Output
/* Michael Fassbender is finer than fine wine.
Altruistic and noble for the modern time.
Always admirably adorned with the latest style.
A Man of unfortunate tragedies who still manages a perpetual smile.
*/

因为getUserInput函数只是处理获取数据,我们可传入任何的回调给它。比如,我们可以传入一个greetUser函数像下面这样:

1
2
3
4
5
6
7
8
9
10
function greetUser(customerName, sex)  {
var salutation = sex && sex === "Man" ? "Mr." : "Ms.";
console.log("Hello, " + salutation + " " + customerName);
}

// 将greetUser函数作为回调传入getUserInput
getUserInput("Bill", "Gates", "Man", greetUser);

// 下面是输出
Hello, Mr. Bill Gates

我们像原来那样调用getUserInput函数,但是这次它执行了一个完全不同的任务。

你可以看到,回调函数提供了更多的灵活。虽然先前的例子相对来说比较简单,但是想想看如果你开始使用回调函数你将会节省多少工作量,你代码的抽象程度将会多好。加油,马上用起你的回调函数。

注意以下几种我们经常在JavaScript中使用回调函数的方式,特别是在开发现代web应用程序,库,和框架的时候:

  • 用于异步执行
  • 在事件监听器/处理器中
  • 在setTimeout和setInterval方法中
  • 用于通用化:代码简洁

最后的话

JavaScript回调函数好用而又强大,它为你的web应用和代码带来了很多好处。当你需要的时候你就应该用回调函数;看看能不能用回调函数来提高你的代码的抽象性,可维护性和可读性。

参考

  1. http://c2.com/cgi/wiki?FirstClass
  2. https://github.com/mongodb/node-mongodb-native
  3. http://callbackhell.com/
  4. JavaScript Patterns by Stoyan Stefanov (Sep 28, 2010)

《深入理解ES6》之块级作用域与字符串

发表于 2017-11-05 | 更新于 2018-07-29 | 分类于 js

块级作用域绑定

使用var声明

原来我们在js中声明变量是使用var关键字。

我们都知道,使用var声明变量,会有变量提升,比如下面的代码:

1
2
console.log(value); //undefined
var value = 0;

通知台会打印undefined,实际JavaScript引擎将代码理解成下面这样:

1
2
3
var value;
console.log(value); //undefined
value = 0;

所有的变量的声明都会被提升至函数的顶部。

另一个使用var声明的特点是,var声明的变量作用域是函数作用域。

块级声明

ES6引入了块级声明,具体有let声明和const声明。

let声明的用法与var相同,区别有如下:

  1. 不会变量提升

用let声明变量,在变量声明之前是不可以使用的,若使用则会报错。

1
2
console.log(value); //ReferenceError: value is not defined
let value = 0;
  1. 块级作用域

用let声明的变量,作用的范围在{}之中,执行流离开{}变量就会销毁。

  1. 禁止重声明

var重复声明则后面的会覆盖前面的,let重复声明则会报错。

const声明的行为类似于let,但const定义的为常量,不可在使用过程中修改。

但是,有一点要注意,js中的常量如果是对象,则对象的值可以修改。这一点与其他语言中的常量有所不同。

循环中的块作用域

js编程中的一个经典问题如下:

1
2
3
4
5
6
7
8
9
10
11
var funcs = [];

for(var i = 0; i < 10; i++){
funcs.push(function(){
console.log(i);
});
}

funcs.forEach(function(func){
func(); //输出10次数字10
});

这个问题的原因是js并不像我们想象的那样运行,我们希望每次的i都是独立的i,每次打印当前循环阶段的i。

而实际情况是,所有的i都是共享的,而在循环结束的时候,i的值为10。传入的回调函数作为闭包可以访问i的值,但当调用的时候,i已经变成10了。所以每次调用打印的都是10。

通常解决这个问题我们都是采用立即调用函数表达式(IIFE)。如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
var funcs = [];

for(var i = 0; i < 10; i++){
funcs.push((function(value){
return function(){
console.log(value);
}
}(i)));
}

funcs.forEach(function(func){
func(); //输出0,然后是1、2直到9
});

既丑陋又难以理解。

而使用let在循环中声明变量就简单多了:

1
2
3
4
5
6
7
8
9
10
11
var funcs = [];

for(let i = 0; i < 10; i++){
funcs.push(function(){
console.log(i);
});
}

funcs.forEach(function(func){
func(); //输出0,然后是1、2直到9
});

这种结果符合我们理解的期望。每次循环的时候let声明都会创建一个新变量i,并将其初始化为i的当前值。

需要注意的是,let声明在循环中的这种行为是专门定义的,与let的不提升特性无关。

而const声明可以在for-in和for-of中使用,但是若在for循环中,出现i++等修改常量的行为则会报错。

字符串

模板字面量

模板字面量是ES6中一个重要的新增特性,主要有下面这些能力:

  1. 多行字符串

模板字面量可以轻易的创建多行字符串:

1
2
3
4
5
6
let message = `Multiline
string`;

console.log(message); //"Multiline
// string"
console.log(message.length); //16
  1. 字符串占位符

在一个模板字面量中,你可以把任何合法的JavaScript表达式嵌入到占位符中并将其作为字符串的一部分输出到结果中。

1
2
3
4
let name = "Nicholas",
message = `Hello, ${name}.`;

console.log(message); //"Hello,Nicholas."

还可以嵌入如运算式、函数调用等JavaScript表达式

1
2
3
4
5
let count = 10,
price = 0.25,
message = `${count} items cost $${(count * price).toFixed(2)}.`;

console.log(message); //"10 items cost $2.50."

还可以在一个模板字面量里面嵌入另外一个模板字面量

1
2
3
4
5
6
let name = "Nicholas",
message = `Hello, ${
`my name is ${ name }`
}.`;

console.log(message); //"Hello,my name is Nicholas."
  1. 标签模板

模板标签可以执行模板字面量上的转换并返回最终的字符串值。等于可以自定义字符串组合的方式。标签指的是在模板字面量第一个反撇号(`)前方标注的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function passthru(literals,...substitutions){
let result = "";

//根据substitution的数量来确定循环的执行次数
for(let i = 0; i < substitutions.length; i++){

result += literals[i];
result += substitutions[i];

}

//合并最后一个literal
result += literals[literals.length - 1];

return result;

}

let count = 10,
price = 0.25,
message = passthru`${count} items cost $${(count * price).toFixed(2)}.`

console.log(message); //"10 items cost $2.50."

js异步编程解决方案

发表于 2017-11-02 | 更新于 2018-07-29 | 分类于 js

在JavaScript中,函数作为一等公民,使用上非常自由,无论调用,或者作为参数,或者作为返回值均可。

于是在无论是前端的事件驱动回调函数中,还是在nodejs中的异步IO,我们可以看见大量的回调函数。所谓的回调函数,就是把函数作为参数传入,并在将来的某个时候”回头调用”。

回调函数通常作为异步编程的一个解决方案,但是回调函数有许多问题

回调函数的问题

问题一:回调地狱

1
2
3
4
5
6
7
var fs = require('fs');
fs.readFile('./text1.txt', 'utf8', function(err, data){
console.log("text1 file content: " + data);
fs.readFile('./text2.txt', 'utf8', function(err, data){
console.log("text2 file content: " + data);
});
});

上面是我们在进行nodejs编程的时候经常会遇见的场景。前端进行异步请求的时候也经常会遇见这样的场景。当回调嵌套过深的时候,就会出现以下场景。

1
2
3
4
5
6
7
8
9
10
11
doSomethingAsync1(function(){
doSomethingAsync2(function(){
doSomethingAsync3(function(){
doSomethingAsync4(function(){
doSomethingAsync5(function(){
// code...
});
});
});
});
});

所以这种嵌套过深的情况有时候是不可忍受的,我们称之为“回调地狱”或“回调金字塔”

问题二:异步编程的理解

我们的大脑习惯顺序思考问题,当要做一件事情的时候,我们会思考先做A再做B然后做C…。然而用回调函数写的异步代码则违反了我们天生的思考原则。

你能够很快的说出以下代码的执行顺序吗。

1
2
3
4
5
6
7
8
9
10
11
doA(function(){
doC();

doD(function(){
doF();
})

doE();
})

doB();

对于这样的代码,我们需要很大的努力才可以理解。也就是说,可读性很差。

回调函数的代替解决方案

拆解function

我们可以通过将各部分的任务拆解为单个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function getData(count) {
get(`/sampleget?count=${count}`, data => {
console.log(data);
});
}

function queryDB(kw) {
db.find(`select * from sample where kw = ${kw}`, (err, res) => {
getData(res.length);
});
}

function readFile(filepath) {
fs.readFile(filepath, 'utf-8', (err, content) => {
let keyword = content.substring(0, 5);
queryDB(keyword);
});
}

事件发布/订阅模式

采用发布订阅模式进行解耦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const events = require('events');
const eventEmitter = new events.EventEmitter();

eventEmitter.on('db', (err, kw) => {
db.find(`select * from sample where kw = ${kw}`, (err, res) => {
eventEmitter('get', res.length);
});
});

eventEmitter.on('get', (err, count) => {
get(`/sampleget?count=${count}`, data => {
console.log(data);
});
});

fs.readFile('./sample.txt', 'utf-8', (err, content) => {
let keyword = content.substring(0, 5);
eventEmitter. emit('db', keyword);
});

以上两种解决方案确实可以解决一定问题,但终究没有摆脱回调函数的模式。

Promise

ES 6中原生提供了Promise对象,Promise对象代表了某个未来才会知道结果的事件(一般是一个异步操作),并且这个事件对外提供了统一的API,可供进一步处理。

使用Promise对象可以用同步操作的流程写法来表达异步操作,避免了层层嵌套的异步回调,代码也更加清晰易懂,方便维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var fs = require('fs')
var read = function (filename){
var promise = new Promise(function(resolve, reject){
fs.readFile(filename, 'utf8', function(err, data){
if (err){
reject(err);
}
resolve(data);
})
});
return promise;
}
read('./text1.txt')
.then(function(data){
console.log(data);
return read('./text2.txt');
})
.then(function(data){
console.log(data);
});

Generator

Generator 函数有多种理解角度。语法上,首先可以把它理解成,Generator 函数是一个状态机,封装了多个内部状态。

执行 Generator 函数会返回一个遍历器对象,也就是说,Generator 函数除了状态机,还是一个遍历器对象生成函数。返回的遍历器对象,可以依次遍历 Generator 函数内部的每一个状态。

形式上,Generator 函数是一个普通函数,但是有两个特征。一是,function关键字与函数名之间有一个星号;二是,函数体内部使用yield表达式,定义不同的内部状态(yield在英语里的意思就是“产出”)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function* helloWorldGenerator() {
yield 'hello';
yield 'world';
yield 'end';
return 'ending';
}
hw.next()
// { value: 'hello', done: false }

hw.next()
// { value: 'world', done: false }

hw.next()
// { value: 'end', done: true }

hw.next()
// { value: undefined, done: true }

上面代码定义了一个 Generator 函数helloWorldGenerator,它内部有三个yield表达式(hello和world、end),即该函数有三个状态:hello,world,end 和 return 语句(结束执行)。

然后,Generator 函数的调用方法与普通函数一样,也是在函数名后面加上一对圆括号。不同的是,调用 Generator 函数后,该函数并不执行,返回的也不是函数运行结果,而是一个指向内部状态的指针对象,也就是遍历器对象(Iterator Object)。

下一步,必须调用遍历器对象的next方法,使得指针移向下一个状态。也就是说,每次调用next方法,内部指针就从函数头部或上一次停下来的地方开始执行,直到遇到下一个yield表达式(或return语句)为止。换言之,Generator 函数是分段执行的,yield表达式是暂停执行的标记,而next方法可以恢复执行。

async/await

async/await是ES7中的异步解决方案,可以看我的这篇博文。

[译]在10分钟内解释JavaScript Async/Await

结尾

结合以上,我们可以有五种方法来解决回调地狱的问题

  • 拆解function
  • 事件发布/订阅模式
  • Promise
  • Generator
  • async/await

mongoose之Population

发表于 2017-10-30 | 更新于 2018-07-29 | 分类于 后端

在MongoDB中没有关系型数据库的join特性,所以在document进行相互关联的时候就比较麻烦。

在mongoose中有一个population用于解决这类问题。在定义Schema的时候,如果设置某个field关联另一个Schema,那么在获取document的时候就可以使用Population功能通过关联Schema的field找到关联的另一个document,并且用被关联document的内容替换掉原来关联field的内容。

例子

下面我拿官方的例子来说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var mongoose = require('mongoose');
var Schema = mongoose.Schema;

var personSchema = Schema({
_id: Schema.Types.ObjectId,
name: String,
age: Number,
stories: [{ type: Schema.Types.ObjectId, ref: 'Story' }]
});

var storySchema = Schema({
author: { type: Schema.Types.ObjectId, ref: 'Person' },
title: String,
fans: [{ type: Schema.Types.ObjectId, ref: 'Person' }]
});

var Story = mongoose.model('Story', storySchema);
var Person = mongoose.model('Person', personSchema);

首先先定义两个model,并且这两个model的schema相互引用。可以看到在person的stories字段(field )中我们定义了数组,表示关联的数据解析为数组。其中ref选项告诉mongoose在使用populate的时候使用什么model,并且后续所有的传入的_id都要在这个model之中。

保存数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var author = new Person({
_id: new mongoose.Types.ObjectId(),
name: 'Ian Fleming',
age: 50
});

author.save(function (err) {
if (err) return handleError(err);

var story1 = new Story({
title: 'Casino Royale',
author: author._id // assign the _id from the person
});

story1.save(function (err) {
if (err) return handleError(err);
// thats it!
});
});

保存数据的时候并没有什么不同,只是记得要分配下_id,若是_ids,则把所有需要展现的document的_id做成一个数组传入。

解析出引用

上面做的一些操作并没有什么特别的,但接下来我们可以看到通过populate我们解析除了内嵌的关联document。

1
2
3
4
5
6
7
8
Story.
findOne({ title: 'Casino Royale' }).
populate('author').
exec(function (err, story) {
if (err) return handleError(err);
console.log('The author is %s', story.author.name);
// prints "The author is Ian Fleming"
});

下面我说下populate方法的常用用法

Query#populate

就是查询语句之后可以调用populate

语法

1
**`Query.populate(path, [select], [model], [match], [options])`**

参数

  • path

类型:String或Object。

String类型的时, 指定要填充的关联字段,要填充多个关联字段可以以空格分隔。

Object类型的时,就是把 populate 的参数封装到一个对象里。当然也可以是个数组。下面的例子中将会实现。

  • select

类型:Object或String,可选,指定填充 document 中的哪些字段。

Object类型的时,格式如:{name: 1, _id: 0},为0表示不填充,为1时表示填充。
  
String类型的时,格式如:”name -_id”,用空格分隔字段,在字段名前加上-表示不填充。详细语法介绍 query-select

  • model

类型:Model,可选,指定关联字段的 model,如果没有指定就会使用Schema的ref。

  • match

类型:Object,可选,指定附加的查询条件。

  • options

类型:Object,可选,指定附加的其他查询选项,如排序以及条数限制等等。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//填充所有 users 的 posts
User.find()
.populate('posts', 'title', null, {sort: { title: -1 }})
.exec(function(err, docs) {
console.log(docs[0].posts[0].title); // post-by-aikin
});

//填充 user 'luajin'的 posts
User.findOne({name: 'luajin'})
.populate({path: 'posts', select: { title: 1 }, options: {sort: { title: -1 }}})
.exec(function(err, doc) {
console.log(doc.posts[0].title); // post-by-luajin
});

//这里的 populate 方法传入的参数形式不同,其实实现的功能是一样的,只是表示形式不一样。

Model#populate

model直接调用populate

语法

1
**`Model.populate(docs, options, [cb(err,doc)])`**

参数

  • docs

类型:Document或Array。单个需要被填充的 doucment 或者 document 的数组。

  • options

类型:Object。以键值对的形式表示。

keys:path select match model options,这些键对应值的类型和功能,与上述Query#populate方法的参数相同。

  • [cb(err,doc)]

类型:Function,回调函数,接收两个参数,错误err和填充完的doc(s)。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Post.find({title: 'post-by-aikin'})
.populate('poster comments')
.exec(function(err, docs) {

var opts = [{
path : 'comments.commenter',
select : 'name',
model : 'User'
}];

Post.populate(docs, opts, function(err, populatedDocs) {
console.log(populatedDocs[0].poster.name); // aikin
console.log(populatedDocs[0].comments[0].commenter.name); // luna
});
});

Document#populate

document直接调用populate

语法

1
**`Document.populate([path], [callback])`**

参数

  • path

类型:String或Object。与上述Query#populate`方法的 path 参数相同。

  • callback

类型:Function。回调函数,接收两个参数,错误err和填充完的doc(s)。

例子

1
2
3
4
5
6
7
8
9
10
11
12
User.findOne({name: 'aikin'})
.exec(function(err, doc) {

var opts = [{
path : 'posts',
select : 'title'
}];

doc.populate(opts, function(err, populatedDoc) {
console.log(populatedDoc.posts[0].title); // post-by-aikin
});
});

跨越等级的Populate

populate可以进行多重引用

1
2
3
4
5
6
7
8
9
10
11
12
var userSchema = new Schema({
name: String,
friends: [{ type: ObjectId, ref: 'User' }]
});

User.
findOne({ name: 'Val' }).
populate({
path: 'friends',
// Get friends of friends - populate the 'friends' array for every friend
populate: { path: 'friends' }
});

参考

官方starter

Mongoose 之 Population 使用

用Vuex来做vue应用的状态管理

发表于 2017-10-29 | 更新于 2018-07-29 | 分类于 前端

什么是Vuex

Vuex是一个专为Vue.js应用程序开发的状态管理模式。

当我们的Vue应用越来越大的时候,有一些公用部分的状态不好管理,比如多重组件嵌套等。这时候,我们就可以用Vuex来进行统一的应用状态管理。

核心概念

State (读)

State是唯一的数据源,单一状态树

this.$store.state.count

Mutations (写)

更改Vuex的store中的状态的唯一方法是提交mutation,Mutation 必须是同步函数。

1
2
3
4
5
6
7
8
mutations: {
increment (state, payload) {
state.count += payload.amount
}
}
store.commit('increment', {
amount: 10
})

Actions

Action 类似于 mutation,不同在于:Action提交的是mutation,而不是直接变更状态,Action可以包含任意异步操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const store = new Vuex.Store({
state: {
count: 0
},
mutations: {
increment (state) {
state.count++
}
},
actions: {
increment (context) {
context.commit('increment')
}
}
})

Getters

通过Getters可以派生出一些新的状态(在state的基础上)

1
2
3
4
5
6
7
8
9
10
11
12
13
const store = new Vuex.Store({
state: {
todos: [
{ id: 1, text: '...', done: true },
{ id: 2, text: '...', done: false }
]
},
getters: {
doneTodos: state => {
return state.todos.filter(todo => todo.done)
}
}
})

Modules

面对复杂的应用程序,当管理的状态比较多时,我们需要将Vuex的store对象分割成模块(modules)。

例子

你可以通过 store.state 来获取状态对象,以及通过 store.commit 方法触发状态变更。

最主要的是store是全局的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Vue.use(Vuex);

const store = new Vuex.Store({
state: {
count: 0
},
mutations: {
increment: state => state.count++,
decrement: state => state.count--
}
})

new Vue({
el: '#app',
computed: {
count () {
return store.state.count
}
},
methods: {
increment () {
store.commit('increment')
},
decrement () {
store.commit('decrement')
}
}
})
12
HouXingYi

HouXingYi

18 日志
8 分类
17 标签
© 2019 HouXingYi
由 Hexo 强力驱动 v3.7.1
|
主题 – NexT.Pisces v7.0.1