手撕算法记录

4 月 8 日 华为云

给定一个 n 位的 01 串，提供两种变换方法：00–>10，10–>01

样例：

0010 –> 1101

  1. 0010–>1010
  2. 1010–>1001
  3. 1001–>1101

碰到的难题：10 可能会变到 01；什么情况下回去这么变，是为了让 00 变成 10；

刚开始没思路，面试官给提示：00 变到 10 是没代价的，而 10 变 01 是要看时机的，出现 010 这种情况时可以让 10 变 01；刚开始写的代码如下：

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
 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4
 5 string func(const string& s) {
 6     string ret;
 7     for (int i = 0;i < s.size(); ++i) {
 8         char c = s[i];
 9         if (c == '1') {
10             ret.push_back(c);
11             continue;
12         } else {
13             if (i + 1 < s.size()) {
14                 if (s[i+1] == '0')
15                     ret.push_back('1');
16                 else {
17                     if (i + 2 < s.size() && s[i+2] == '0') {
18                         ret.append("101");
19                         i += 2;
20                     }
21                 }
22             }
23         }
24     }
25     return ret;
26 }
27
28 int main() {
29     string s = "0000";
30     string ret = func(s);
31     cout << ret << "\n";
32     return 0;
33 }

然后面试官提示 18 行和 13 行出错。然后我还想了一会，哎，无语~~~~

如果是 010 的情况下不是无脑把 101 压入 ret，而应该把 1 压入，然后后续再如循环进行处理。 i + 1 < s.size() 不满足时如果直接返回，会导致 0000 这样的测试过不了，即最后一个字符得不到处理。

改正后的代码：

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
1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4
 5 string func(const string& tmp) {
 6     string s = tmp;
 7     string ret;
 8     for (int i = 0;i < s.size(); ++i) {
 9         char c = s[i];
10         if (c == '1') { // 1
11             ret.push_back(c);
12             continue;
13         } else {
14             if (i + 1 < s.size()) {
15                 if (s[i+1] == '0') // 00
16                     ret.push_back('1');
17                 else { // 01
18                     if (i + 2 < s.size()) {
19                         if (s[i + 2] == '0') { // 010
20                             ret.push_back('1');
21                             s[i + 1] = '0';
22                             s[i + 2] = '1';
23                         } else {
24                             // 011
25                             ret.push_back('0');
26                         }
27                     } else ret.push_back('0');
28                 }
29             } else ret.push_back('0');
30         }
31     }
32     return ret;
33 }
34
35 int main() {
36     string s = "0000";
37     string ret = func(s);
38     cout << ret << "\n";
39     return 0;
40 }