腾讯2017暑期实习生编程题

题目链接：http://www.nowcoder.com/test/1725829/summary

1、构造回文

解法：倒过来存一遍，对这两个字符串做一次lcs。这样lcs就是回文的，把不包含于lcs的字符删掉就行了。记录字符个数那就直接用串总长度减去lcs长度即可。

 1 /* 
 2 ┓┏┓┏┓┃キリキリ♂ mind！
 3 ┛┗┛┗┛┃＼○／
 4 ┓┏┓┏┓┃ /
 5 ┛┗┛┗┛┃ノ)
 6 ┓┏┓┏┓┃
 7 ┛┗┛┗┛┃
 8 ┓┏┓┏┓┃
 9 ┛┗┛┗┛┃
10 ┓┏┓┏┓┃
11 ┛┗┛┗┛┃
12 ┓┏┓┏┓┃
13 ┃┃┃┃┃┃
14 ┻┻┻┻┻┻
15 */
16 #include <algorithm>
17 #include <iostream>
18 #include <iomanip>
19 #include <cstring>
20 #include <climits>
21 #include <complex>
22 #include <fstream>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rlf(a) scanf("%lf", &a);
42 #define Rint(a) scanf("%d", &a)
43 #define Rll(a) scanf("%I64d", &a)
44 #define Rs(a) scanf("%s", a)
45 #define Cin(a) cin >> a
46 #define FRead() freopen("in", "r", stdin)
47 #define FWrite() freopen("out", "w", stdout)
48 #define Rep(i, len) for(int i = 0; i < (len); i++)
49 #define For(i, a, len) for(int i = (a); i < (len); i++)
50 #define Cls(a) memset((a), 0, sizeof(a))
51 #define Clr(a, x) memset((a), (x), sizeof(a))
52 #define Full(a) memset((a), 0x7f7f, sizeof(a))
53 #define lrt rt << 1
54 #define rrt rt << 1 | 1
55 #define pi 3.14159265359
56 #define RT return
57 #define lowbit(x) x & (-x)
58 #define onenum(x) __builtin_popcount(x)
59 typedef long long LL;
60 typedef long double LD;
61 typedef unsigned long long ULL;
62 typedef pair<int, int> pii;
63 typedef pair<string, int> psi;
64 typedef map<string, int> msi;
65 typedef vector<int> vi;
66 typedef vector<LL> vl;
67 typedef vector<vl> vvl;
68 typedef vector<bool> vb;
69 
70 const int maxn = 1010;
71 char s[maxn];
72 char e[maxn];
73 int dp[maxn][maxn];
74 
75 int main() {
76     // FRead();
77     while(~Rs(s+1)) {
78         Cls(dp);
79         int n = strlen(s+1);
80         For(i, 1, n+1) e[i] = s[n-i+1];
81         For(i, 1, n+1) {
82             dp[i][0] = 0;
83             For(j, 1, n+1) {
84                 if(s[i] == e[j]) {
85                     dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
86                 }
87                 dp[i][j] = max(dp[i][j], max(dp[i-1][j], dp[i][j-1]));
88             }
89         }
90         printf("%d
", n-dp[n][n]);
91     }
92     RT 0;
93 }

2、算法基础-字符移位

解法：模拟，n<=1010所以O(n²)可破。从后往前扫，尽量找靠后的大写字符，然后一路交换到最后，注意别和已经确定位置的字符冲突就行。

 1 /* 
 2 ┓┏┓┏┓┃キリキリ♂ mind！
 3 ┛┗┛┗┛┃＼○／
 4 ┓┏┓┏┓┃ /
 5 ┛┗┛┗┛┃ノ)
 6 ┓┏┓┏┓┃
 7 ┛┗┛┗┛┃
 8 ┓┏┓┏┓┃
 9 ┛┗┛┗┛┃
10 ┓┏┓┏┓┃
11 ┛┗┛┗┛┃
12 ┓┏┓┏┓┃
13 ┃┃┃┃┃┃
14 ┻┻┻┻┻┻
15 */
16 #include <algorithm>
17 #include <iostream>
18 #include <iomanip>
19 #include <cstring>
20 #include <climits>
21 #include <complex>
22 #include <fstream>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rlf(a) scanf("%lf", &a);
42 #define Rint(a) scanf("%d", &a)
43 #define Rll(a) scanf("%I64d", &a)
44 #define Rs(a) scanf("%s", a)
45 #define Cin(a) cin >> a
46 #define FRead() freopen("in", "r", stdin)
47 #define FWrite() freopen("out", "w", stdout)
48 #define Rep(i, len) for(int i = 0; i < (len); i++)
49 #define For(i, a, len) for(int i = (a); i < (len); i++)
50 #define Cls(a) memset((a), 0, sizeof(a))
51 #define Clr(a, x) memset((a), (x), sizeof(a))
52 #define Full(a) memset((a), 0x7f7f, sizeof(a))
53 #define lrt rt << 1
54 #define rrt rt << 1 | 1
55 #define pi 3.14159265359
56 #define RT return
57 #define lowbit(x) x & (-x)
58 #define onenum(x) __builtin_popcount(x)
59 typedef long long LL;
60 typedef long double LD;
61 typedef unsigned long long ULL;
62 typedef pair<int, int> pii;
63 typedef pair<string, int> psi;
64 typedef map<string, int> msi;
65 typedef vector<int> vi;
66 typedef vector<LL> vl;
67 typedef vector<vl> vvl;
68 typedef vector<bool> vb;
69 
70 const int maxn = 1010;
71 char s[maxn];
72 int main() {
73     // FRead();
74     while(~Rs(s)) {
75         int n = strlen(s);
76         int cnt = 0;
77         for(int i = n - 1; i >= 0; i--) {
78             if(s[i] >= 'A' && s[i] <= 'Z') {
79                 For(j, i, n-cnt-1) swap(s[j], s[j+1]);
80                 cnt++;
81             }
82         }
83         printf("%s
", s);
84     }
85     RT 0;
86 }

3、有趣的数字

解法：先排序，最大的差的个数好找，就是最头上的相同数字的个数和最末尾的相同数字的个数的乘积。最小的差考虑了一下，因为n<=100000所以只能是O(n)或者O(nlgn)的做，显然线性的是不行的。既然排好序了，我们就有一条性质，那就是存在序列中三个连续的数字a,b,c，有c-b < c-a。所以我们先找到最小的差，这个值一定是序列中相邻两个数字的差。然后枚举每一个数字和它之前的数字，如果差值和最小的差不相等，那后面的数字就没有必要再遍历了。这个复杂度大概是O(n*k)。

  1 /* 
  2 ┓┏┓┏┓┃キリキリ♂ mind！
  3 ┛┗┛┗┛┃＼○／
  4 ┓┏┓┏┓┃ /
  5 ┛┗┛┗┛┃ノ)
  6 ┓┏┓┏┓┃
  7 ┛┗┛┗┛┃
  8 ┓┏┓┏┓┃
  9 ┛┗┛┗┛┃
 10 ┓┏┓┏┓┃
 11 ┛┗┛┗┛┃
 12 ┓┏┓┏┓┃
 13 ┃┃┃┃┃┃
 14 ┻┻┻┻┻┻
 15 */
 16 #include <algorithm>
 17 #include <iostream>
 18 #include <iomanip>
 19 #include <cstring>
 20 #include <climits>
 21 #include <complex>
 22 #include <fstream>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 using namespace std;
 35 #define fr first
 36 #define sc second
 37 #define cl clear
 38 #define BUG puts("here!!!")
 39 #define W(a) while(a--)
 40 #define pb(a) push_back(a)
 41 #define Rlf(a) scanf("%lf", &a);
 42 #define Rint(a) scanf("%d", &a)
 43 #define Rll(a) scanf("%I64d", &a)
 44 #define Rs(a) scanf("%s", a)
 45 #define Cin(a) cin >> a
 46 #define FRead() freopen("in", "r", stdin)
 47 #define FWrite() freopen("out", "w", stdout)
 48 #define Rep(i, len) for(int i = 0; i < (len); i++)
 49 #define For(i, a, len) for(int i = (a); i < (len); i++)
 50 #define Cls(a) memset((a), 0, sizeof(a))
 51 #define Clr(a, x) memset((a), (x), sizeof(a))
 52 #define Full(a) memset((a), 0x7f7f, sizeof(a))
 53 #define lrt rt << 1
 54 #define rrt rt << 1 | 1
 55 #define pi 3.14159265359
 56 #define RT return
 57 #define lowbit(x) x & (-x)
 58 #define onenum(x) __builtin_popcount(x)
 59 typedef long long LL;
 60 typedef long double LD;
 61 typedef unsigned long long ULL;
 62 typedef pair<int, int> pii;
 63 typedef pair<string, int> psi;
 64 typedef map<string, int> msi;
 65 typedef vector<int> vi;
 66 typedef vector<LL> vl;
 67 typedef vector<vl> vvl;
 68 typedef vector<bool> vb;
 69 
 70 const int maxn = 100100;
 71 int n;
 72 int a[maxn];
 73 int sub;
 74 int ret1, ret2;
 75 
 76 int main() {
 77     // FRead();
 78     while(~Rint(n)) {
 79         For(i, 1, n+1) Rint(a[i]);
 80         sort(a+1, a+n+1); sub = 0x7f7f7f; ret1 = 0;
 81         int l = 0, r = 0;
 82         For(i, 1, n) sub = min(a[i+1]-a[i], sub);
 83         For(i, 1, n+1) {
 84             for(int j = i - 1; j >= 1; j--) {
 85                     if(a[i] - a[j] == sub) ret1++;
 86                     else break;
 87             }
 88         }
 89         For(i, 1, n+1) {
 90             if(a[1] == a[i]) l++;
 91             else break;
 92         }
 93         for(int i = n; i >= 1; i--) {
 94             if(a[n] == a[i]) r++;
 95             else break;
 96         }
 97         ret2 = l * r;
 98         printf("%d %d
", ret1, ret2);
 99     }
100     RT 0;
101 }