乱七八糟的算法题

未归档的算法题

2019华为-小王的密码

题目描述

小王的保险箱密码是一个升序排列的字符串。但是小王总是记不住他的密码,于是小王将他的密码加密后保存在了一个文本文件里,加密的流程如下:

  1. 用数字的英文单词来代替数字本身。比如1234699变成onethreefoursixninenine
  2. 将上述字符串使用“小王加密算法”进行处理。该算法会按照某种规则来改变原字符串字符的排列顺序,同时还会改变某些字母的大小写。比如onethreefoursixninenine经过加密后就变成了NeNohuiroNNiNeteefersix。

由于“小王加密算法”是小王自己设计的,所以小王认为只有他自己能将加密后的字符串还原。

实际上小王的加密算法存在漏洞。即使不知道“小王加密算法”的具体实现细节,也是可以还原出原始的密码的。请你写一段程序来破解小王的密码。


2019华为春招机试题

示例1

输入

1
oNEthrEEfoursixNiNENiEN

输出

1
134699

我的答案

思路分析

  1. 小王的保险箱密码是升序排列的字符串。
  2. 数字用字母来代替。
  3. 只改变字母的排列顺序,不做替换(即用别的字母代替)。

将所有的数字与对应的字母列出

数字 字母 独有的字符
0 zero z
1 one o-0-2-4
2 two w
3 three h-8
4 four u
5 five f-4
6 six x
7 seven s-6
8 eight g
9 nine i-5-6-8

解释一下:在这10个数字中,对于字母”z“,只在zero中出现。其他的不会出现。

对于字母“h”,只在3和8的英文中出现,其他地方不会出现。

因此对所有的字母进行统计出现的个数,假如z出现3次,则表示数字0出现了3次,同时将“zero”四个字母出现的次数同时减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
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind
/*
0----z zero
2----w two
4----u four
6----x six
8----g eight
3----h-8 three
5----f-4 five
7----s-6 seven
9----i-5-6-8 nine
1----o-0-2-4 one
*/
void solution()
{
string input;
cin >> input;
transform(input.begin(), input.end(), input.begin(), ::tolower);
//cout << input << endl; //变小写
vector<int>res;

map<char, int> m;
for (int i = 0; i < input.length(); i++)
{
if (!m.count(input[i]))
m[input[i]] = 1;
else
m[input[i]] = m[input[i]] + 1;
}

//先处理0
int num[11] = { 0 };
if (m.count('z')) //表示有0
{
num[0] = m['z'];
m['z'] -= num[0];
m['e'] -= num[0];
m['r'] -= num[0];
m['o'] -= num[0];
}
if (m.count('w')) //表示有2
{
num[2] = m['w'];
m['t'] -= num[2];
m['w'] -= num[2];
m['o'] -= num[2];
}
if (m.count('u')) //表示有4
{
num[4] = m['u'];
m['f'] -= num[4];
m['o'] -= num[4];
m['u'] -= num[4];
m['r'] -= num[4];
}

if (m.count('x')) //表示有6
{
num[6] = m['x'];
m['s'] -= num[6];
m['i'] -= num[6];
m['x'] -= num[6];
}

if (m.count('g')) //表示有8
{
num[8] = m['g'];
m['e'] -= num[8];
m['i'] -= num[8];
m['g'] -= num[8];
m['h'] -= num[8];
m['t'] -= num[8];
}

if (m.count('h')) //表示有3
{
num[3] = m['h'];
m['t'] -= num[3];
m['h'] -= num[3];
m['r'] -= num[3];
m['e'] -= num[3];
m['e'] -= num[3];
}

if (m.count('f')) //表示有5
{
num[5] = m['f'];
m['f'] -= num[5];
m['i'] -= num[5];
m['v'] -= num[5];
m['e'] -= num[5];
}

if (m.count('s')) //表示有7
{
num[7] = m['s'];
m['s'] -= num[7];
m['e'] -= num[7];
m['v'] -= num[7];
m['e'] -= num[7];
m['n'] -= num[7];
}

if (m.count('i')) //表示有9
{
num[9] = m['i'];
m['n'] -= num[9];
m['i'] -= num[9];
m['n'] -= num[9];
m['e'] -= num[9];
}

if (m.count('o')) //表示有16
{
num[1] = m['o'];
m['o'] -= num[1];
m['n'] -= num[1];
m['e'] -= num[1];
}

for (int i = 0; i < 11; i++)
{
for (int j = 0; j < num[i]; j++)
{
cout << i;
}
}
cout << endl;
return;
}

int main()
{
#ifdef Wind
freopen("3.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}

2019华为-旋转矩阵

题目大意

给定一个N*N的矩阵,求其向右旋转m次的结果,每次旋转90°。

思路及代码

考察循环。

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind
void solution()
{
ios::sync_with_stdio(false);
int n,m;
cin >> n;
vector<vector<int>>v(n);
for (int i = 0; i < n; i++)
{
v[i].resize(n);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> v[i][j];
}
}
cin >> m;
m = m % 4;
if (m == 1)
{
bool flag = false;
for (int i = 0; i < n; i++)
{
for (int j = n - 1; j >= 0; j--)
{
cout << v[j][i];
flag = true;
if (flag)
cout << ' ';
}
cout << endl;
}

}
if (m == 2)
{
bool flag = false;
for (int i = n-1; i >= 0; i--)
{
for (int j = n-1; j >= 0; j--)
{
cout << v[i][j];
flag = true;
if (flag)
cout << ' ';
}
cout << endl;
}
}
if (m == 3)
{
bool flag = false;
for (int i = n-1; i >= 0; i--)
{
for (int j = 0; j < n ; j++)
{
cout << v[j][i]<<' ';
}
cout << endl;
}
}
if (m == 0)
{
for (int i = 0; i < n; i++)
{
bool flag = false;
for (int j = 0; j < n; j++)
{
cout << v[i][j];
flag = true;
if (flag)
cout << ' ';
}
cout << endl;
}
}
return;
}

int main()
{
#ifdef Wind
freopen("1.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}

2019华为-小朋友的礼物

题目大意

有N个礼物和k个小朋友,请问有多少种分礼物的方式,并把它们全都显示出来,用*表示礼物,用|来分割小朋友。

思路及代码

考察DFS

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind
int n, k;
vector<vector<int>> res;

void display()
{
cout << res.size() << endl;
for (vector<int> temp :res)
{
//cout << res.size() << endl;
for (int i = 0; i < temp[0]; i++)
{
cout << '*';
}
for (int i = 1; i < k; i++)
{
cout << '|';
for (int j = 0; j < temp[i]; j++)
{
cout << '*';
}
}
cout << endl;
}
return;
}

void dfs(int gift, int curChild,vector<int>temp)
{
if (curChild == k - 1) //是最后一个
{
temp[curChild] = gift;
res.push_back(temp);
return;
}
if (gift == 0)
{
res.push_back(temp);
return;
}
for (int i = gift; i >= 0; i--)
{
temp[curChild] = i;
dfs(gift - i, curChild + 1, temp);
}
}

void solution()
{
ios::sync_with_stdio(false);
cin >> n >> k;
vector<int>temp(k, 0);
dfs(n, 0, temp);
display();
return;
}


int main()
{
#ifdef Wind
freopen("1.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}

2019华为-求编辑距离

题目大意

给定一片文章,有n行,对这篇文章按行进行修改,给定一片修改好的文章。

求需要多少次操作(删除、修改、添加)可以得到这篇修改好的文章。

思路及代码

编辑距离,用动态规划去做。

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind
int dp[10010][10010] = { 0 };
int check(string a, string b)
{
for (int i = 0; i <= a.length(); i++)
{
dp[i][0] = i;
}
for (int i = 0; i <= b.length(); i++)
{
dp[0][i] = i;
}
for (int i = 1; i <= a.length(); i++)
{
for (int j = 1; j <= b.length(); j++)
{
if (a[i - 1] == b[j - 1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
int edIns = dp[i][j - 1] + 1;
int edDel = dp[i - 1][j] + 1;
int edRep = dp[i - 1][j - 1] + 1;

dp[i][j] = min(edIns, min(edDel, edRep));
}
}
}
return dp[a.length()][b.length()];
}

void solution()
{
ios::sync_with_stdio(false);
string input;
int n, res = 0;
cin >> n;
vector<string>yuanlai(n), xinde(n);
for (int i = 0; i < n; i++)
{
cin >> yuanlai[i];
}
for (int i = 0; i < n; i++)
{
cin >> xinde[i];
}
for (int i = 0; i < n; i++)
{
//cout << yuanlai[i] << endl;
//cout << xinde[i] << endl;
res += check(yuanlai[i], xinde[i]);

//cout << res;
}
cout << res << endl;
return;
}

int main()
{
#ifdef Wind
freopen("1.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}