腾讯 2017 暑期实习生编程题

腾讯2017暑期实习生编程题

链接

  1. 构造回文子串

按照 回文字符串的性质 可以知道 此题 就是求 原串与翻转后的字符串的 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;
}
  1. 这题比较奇葩,首先想到的就是冒泡排序的思想,但是看到有人遍历了两遍然后输出的奇淫技巧只能大喊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
    #include <iostream>
    #include <string>
    #include <algorithm>

    using namespace std;

    //AkleBiCeilD
    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;
    }
  2. 这个题咋看简单其实还是很多错误的思路的。比如 当最小差为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
#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)//最小差为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;
}
T B
站点访问量: / , 本页阅读量:
T B