本次笔试在赛码网，有选择和编程题，这次来记录一下编程题。
图片压缩
时间限制： 3000MS
内存限制： 589824KB
题目描述：
为了降低APP图片加载内存占用，我们会对图片进行压缩。JPEG是一种十分先进的压缩技术，在编码中，有一个非常重要的步骤，即Z字形编排过程。
请将下列二维数组：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
转换成Z字形排序：
0 1 5 6
2 4 7 12
3 8 11 13
9 10 14 15
输入描述
请将下列二维数组：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输出描述
转换成Z字形排序：
0 1 5 6
2 4 7 12
3 8 11 13
9 10 14 15
样例输入
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
样例输出
0 1 5 6
2 4 7 12
3 8 11 13
9 10 14 15
我的解答
针对这个测试样例我写的没问题，因为最后第一题有一行代码写错了一直没检查出来，所以一直不对所以没交上。
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
| #include<bits/stdc++.h>
using namespace std;
int main() {
int dirs[4][2] = {0, 1, 1, -1, 1, 0, -1, 1};
int a;
vector<vector<int> > vec;
int line = 0, len = 1;
vector<int> temp;
while(cin >> a) {
temp.push_back(a);
if(cin.get() == '\n') {
vec.push_back(temp);
if(line == 0) len = temp.size();
temp.clear();
line ++;
if(line >= len) break;
}
}
cout << len << endl;
int i = 0, j = 0, oi = 0, oj = 0, dir = 0;
vector< vector<int> > ans = vec;
while(oi < len) {
ans[i][j] = vec[oi][oj];
oj ++;
if(oj >= len) {
oj = 0;
oi ++;
if(oi >= len) {
break;
}
}
i += dirs[dir][0];
j += dirs[dir][1];
if(i == 0 and dir != 0) dir = 0;
else if(i == 0 and dir == 0) dir = 1;
else if(j == 0 and dir != 2) dir = 2;
else if(j == 0 and dir == 2) dir = 3;
else if(j == len - 1 and dir != 2) dir = 2;
else if(j == len - 1 and dir == 2) dir = 1;
else if(i == len - 1 and dir != 0) dir = 0;
else if(i == len - 1 and dir == 0) dir = 3;
}
cout << "yes" << endl;
for(int a = 0; a < len; a ++) {
for(int b = 0; b < len; b ++) {
cout << ans[a][b] << " ";
}
cout << 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
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> arr;
int a;
while(cin >> a){
arr.push_back(a);
if(cin.get() == '\n') break;
}
long long depthNode = 1;
long long count = 0;
for(int i: arr) {
if(i != -1)
cout << i << " ";
count ++;
if(count >= depthNode) {
count = 0;
depthNode *= 2;
cout << endl;
}
}
return 0;
}
|
字符串反转
时间限制： 1000MS
内存限制： 65536KB
题目描述：
去哪儿网提供给用户多个目的地的出行选择，比如从“北京”到“上海”再到“武汉”。为了方便用户切换出发地和目的地，请实现一个字符串反转功能：将字符串”北京 上海 武汉”，反转成”武汉 上海 北京”。(注：不借助任何函数库)
输入描述
输入字符串：”北京 上海 武汉”
输出描述
输出字符串：”武汉 上海 北京”
样例输入
北京 上海 武汉
样例输出
武汉 上海 北京
我的解答
这个题感觉很有意思，但是测试样例中用的是中文，我想使用字符串存储，一个中文字符就得占两个char位，并且 题目没有说不能夹杂英文，所以还得考虑中英混合，前后都有空格的情况。一开始我以为只有中文，所以一直只对了一半的测试样例，后来适配中英文的就对了。
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<bits/stdc++.h>
using namespace std;
int main() {
string place = "";
getline(cin, place);
stack<char> tmp;
for(int i = place.length() - 1; i >= 0;) {
if(place[i] == ' ') {
if(i != place.length() - 1) {
while(!tmp.empty()) {
char first = tmp.top();
cout << tmp.top();
tmp.pop();
if(first > 128) {
cout << tmp.top();
tmp.pop();
}
}
cout << " ";
} else i --;
while(place[i] == ' ') i --;
} else {
if(place[i] <= 128) {
tmp.push(place[i]);
i --;
continue;
}
tmp.push(place[i]);
tmp.push(place[i - 1]);
i -= 2;
}
}
while(!tmp.empty()) {
char t = tmp.top();
cout << tmp.top();
tmp.pop();
if(t > 128) {
cout << tmp.top();
tmp.pop();
}
}
return 0;
}
|
Author: o_oyao
License: All articles in this blog are licensed under
CC BY-NC-SA 4.0 unless stating additionally.
