腾讯2017暑期实习生编程题
链接
- 构造回文子串
按照 回文字符串的性质 可以知道 此题 就是求 原串与翻转后的字符串的 lcs 的值。
参考代码
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
| #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int lcs(string &str1, string &str2)
{
const int len = str1.length();
int dp[len+1][len+1];
for(int i = 0; i <= len; ++i)
{
for(int j = 0; j <= len; ++j)
{
dp[i][j] = 0;
}
}
for(int i = 1; i <= len; ++i)
{
for(int j = 1; j <= len; ++j)
{
if(str1[i-1] == str2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[len][len];
}
int minDelStr(string &str)
{
string str1 = str;
reverse(str1.begin(),str1.end());
return str.length()-lcs(str,str1);
}
int main(int argc, char *argv[])
{
string str;
while(cin>>str)
{
cout<<minDelStr(str)<<endl;
}
return 0;
}
|
- 这题比较奇葩，首先想到的就是冒泡排序的思想，但是看到有人遍历了两遍然后输出的奇淫技巧只能大喊666
参考代码
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
| #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
string str;
while(cin>>str)
{
for(int i = str.length()-2; i >= 0; --i)
{
if(str[i] < 'a')
{
for(int j = i; j < str.length() && str[j+1] >= 'a'; ++j)
{
swap(str[j],str[j+1]);
}
}
}
cout<<str<<endl;
}
return 0;
}
|
- 这个题咋看简单其实还是很多错误的思路的。比如 当最小差为0 时 便不能应用最小差不为0的求解方法，因为当前数字可能与之前的之前的数字进行组合
思路
链接：https://www.nowcoder.net/questionTerminal/af709ab9ca57430886632022e543d4c6
来源：牛客网
1.先排序
特殊情况：如果排完序之后发现数组中所有数都相同，直接输出结果
结果为：差最大个数 = 差最小个数 = （n * (n-1))/2;(两两组合)
2.统计数组中每种数字的个数（这里用的map）
3.计算差最小个数
3.1.如果数组中没有重复数字，说明最小差不为0，最小差肯定是数组中相邻两个数的差
因此，遍历一边数组，计算并统计最小差。
3.2.如果数组中有重复数字，说明最小差是0，此时，遍历一边map，数字个数不为0的
数字会产生最小差0，利用公式计算即可
4.计算差最大个数
只有一种情况，最大值与最小值的两两组合，即最大值个数 * 最小值个数
算法复杂度：排序O(nlogn), 统计O(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
90
91
92
93
94
95
96
97
98
| #include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main(int argc, char *argv[])
{
int count;
while (cin>>count)
{
vector<int > arr;
int tmp;
for(int i = 0; i < count; ++i)
{
cin>>tmp;
arr.push_back(tmp);
}
if (count < 2)
{
cout << 0 << ' ' << 0 << endl;
continue;
}
if (count == 2)
{
cout << 1 << ' ' << 1 << endl;
continue;
}
int max = -1,maxCount = 0;
int min = INT_MAX, minCount = 0;
for(int i = 0; i < arr.size(); ++i)
{
if(arr[i] < min)
{
min = arr[i];
minCount = 1;
}
else if(arr[i] == min)
{
minCount++;
}
if(arr[i] > max)
{
max = arr[i];
maxCount = 1;
}
else if(arr[i] == max)
{
maxCount++;
}
}
sort(arr.begin(),arr.end());
int minTmp = arr[1] - arr[0];
int sameCount = 1;
for(int i = 1; i < arr.size()-1; ++i)
{
if(arr[i+1] - arr[i] < minTmp)
{
sameCount = 1;
minTmp = arr[i+1] - arr[i];
}
else if(arr[i+1] - arr[i] == minTmp)
{
sameCount++;
}
}
if(minTmp == 0)
{
int repCount = 0;
for (int i = 1; i < count; ++i)
{
int j = i - 1;
while (j >= 0 && arr[j] == arr[i])
{
++repCount;
--j;
}
}
cout<<repCount<<" "<<maxCount*minCount<<endl;
}
else
{
cout<<sameCount<<" "<<maxCount*minCount<<endl;
}
}
return 0;
}
|
