腾讯2017暑期实习生编程题

构造回文

时间限制:1秒

空间限制:32768K

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?
输出需要删除的字符个数。

输入描述:

输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000.

输出描述:

对于每组数据,输出一个整数,代表最少需要删除的字符个数。

输入例子1:
abcda
google

输出例子1:
2
2

分析
思路1

“最少删除几个字符变成回文串”和“最少增加几个字符变成回文串”本质上一样的,不妨以增加字符的情况进行分析,设$dp[i][j]$表示由$a[i]…a[j]$构成的子串变成回文串需要增加的字符,那么

  • 当$i \geq j$时,显然$dp[i][j] = 0$;
  • 当$i<j$时,如果$a[i] = a[j]$,则$dp[i][j] = dp[i+1][j-1]$,此时$a[i]…a[j]$变成回文串需要增加的字符数和$a[i+1]…a[j-1]$一样。
  • 当$i<j$时,如果$a[i] \neq a[j]$,则$dp[i][j] = min(dp[i+1][j], dp[i][j-1])$。
思路2

最少增加的字符 = 字符串长度 - LCS(字符串,字符串倒序)

实现
实现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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000+10;
int res[N][N];
string s;
int main()
{
while(cin >> s)
{
int len = s.length();
memset(res, 0, sizeof(res));
for(int j = 0; j < len; j++)
{
for(int i = j-1; i >= 0; i--)
{
if(s[i] == s[j])
res[i][j] = res[i+1][j-1];
else
res[i][j] = min(res[i+1][j], res[i][j-1])+1;
}
}
printf("%d\n", res[0][len-1]);
}
return 0;
}
实现2
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 <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1000+10;
string s;
int len;
int res[N][N];
int LCS(string a, string b, int len);

int main()
{
while(cin >> s)
{
string t = s;
len = s.length();
reverse(s.begin(), s.end());
//cout << LCS(s, t, len) << endl;
printf("%d\n", len - LCS(s, t, len));
}
return 0;
}

int LCS(string a, string b, int len)
{
memset(res, 0, sizeof(res));
for(int i = 0; i <= len; i++)
{
for(int j = 0; j <= len; j++)
{
if(i == 0 || j == 0)
{
res[i][j] = 0;
}
else
{
if(a[i-1] == b[j-1])
res[i][j] = res[i-1][j-1]+1;
else
res[i][j] = max(res[i-1][j], res[i][j-1]);
}
}
}
return res[len][len];
}

算法基础-字符移位

时间限制:1秒

空间限制:32768K

小Q最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。
你能帮帮小Q吗?

输入描述:

输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000.

输出描述:

对于每组数据,输出移位后的字符串。

输入例子1:
AkleBiCeilD

输出例子1:
kleieilABCD

分析

注意不申请额外空间

实现
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 <cstdlib>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
string s;

int main()
{
while(cin >> s)
{
int len = s.length();
int add = 0;
for(int i = 0; i < len; i++)
{
if(s[i] >= 'A' && s[i] <= 'Z')
{
s.push_back(s[i]);
add++;
}
else
printf("%c", s[i]);
}
cout << s.substr(len, add) << endl;
}
return 0;
}

有趣的数字

时间限制:1秒

空间限制:32768K

小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢?

输入描述:

输入包含多组测试数据。

对于每组测试数据:

N - 本组测试数据有n个数

a1,a2…an - 需要计算的数据

保证:

1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

对于每组数据,输出两个数,第一个数表示差最小的对数,第二个数表示差最大的对数。

输入例子1:
6
45 12 45 32 5 6

输出例子1:
1 2

分析

对含n个整数的数组进行排序,主要分以下情况:

  • 所有数字都相同,此时差最小对数 = 差最大对数 = $n(n-1)/2$
  • 存在相同数字,假设有m种相同数字,每种数字对应的个数为m->num,则差最小对数为每种数字的(m->num) ((m->num)-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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int N = 100000 + 10;
int a[N], n;
int minres, maxres;

int main()
{
while(scanf("%d", &n) == 1)
{
memset(a, 0, sizeof(a));
minres = maxres = 0;
map<int, int> mp;
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
mp[a[i]]++;
}
sort(a, a+n);
if(a[n-1] - a[0] == 0)
{
minres = maxres = n*(n-1)/2;
printf("%d %d\n", minres, maxres);
continue;
}
maxres = mp[a[n-1]] * mp[a[0]];
map<int, int>::iterator it = mp.begin();
for(; it != mp.end(); it++)
{
int tmp = it -> second;
minres += tmp * (tmp-1) / 2;
}
if(minres == 0)
{
int mini = a[n-1] - a[0];
for(int i = 1; i < n; i++)
{
if(a[i] - a[i-1] < mini)
mini = a[i] - a[i-1];
}
for(int i = 1; i < n; i++)
{
if(a[i] - a[i-1] == mini)
minres += mp[a[i]] * mp[a[i-1]];
}
}
printf("%d %d\n", minres, maxres);
}
return 0;
}

本文地址:http://www.yuhongwa.com/2018/05/22/腾讯2017/
转载请注明出处,谢谢!

坚持分享,您的支持将鼓励我继续学习哇~