爱奇艺2018春招Java工程师编程题 C++版题解

字典序最大子序列

题目描述
对于字符串a和b,如果移除字符串a中的一些字母(可以全部移除,也可以一个都不移除)就能够得到字符串b我们就称b是a的子序列。

例如.”heo”是”hello”的子序列,而”xl”不是。
对于给定的一个字符串s,请计算出s的字典序最大的子序列。

输入描述:

输入包括一行,一个字符串s,字符串a长度Length(1 <= 1ength <= 50).s中每个字符都是小写字母
输出描述:

输出一个字符串,即a的字典序最大的子序列。
示例

输入
test

输出
tt

思路

在遍历字符串每个字符的过程中,如果当前字符x大于前面子串str对应最大子序列中的某一个字符y,那么从只保留字符y前的子串nstr(不包括字符y),并且将字符x拼接到新的子串nstr后;否则直接将字符x拼接到子串str后。
以实例分析,比如输入字符串test,处理过程如下:

  • 初始化子串str = “t”
  • 开始从第二个字符’e’到最后一个字符’t’的遍历
    • 到第二个字符’e’,因为’e’不大于’t’,所以直接拼接到str后,此时str = “te”
    • 到第三个字符’s’,因为’s’大于子串”te”对应最大子序列str = “te”中的字符’e’,所以只保留e之前的子串”t”,并把’s’拼接到’t’后,此时str = “ts”
    • 到第四个字符’t’,因为’t’大于子串”tes”对应最大子序列str = “ts”中的字符’s’,所以只保留e之前的子串”t”,并把’t’拼接到’t’后,此时str = “tt”
  • 输出最终结果,”test”字典序最大的子序列为”tt”
实现
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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 55;
string s;
string res;
int len = 0;
int main()
{
while(cin >> s)
{
len = s.length();
res.push_back(s[0]);
for(int i = 1; i < len; i++)
{
int nlen = res.length();
for(int j = 1; j < nlen; j++)
{
if(s[i] > res[j])
{
res = res.substr(0, j);
break;
}
}
res.push_back(s[i]);
}
cout << res << endl;
s.clear();
res.clear();
}
return 0;
}

三个整数

题目描述
牛牛有三个整数X, Y, Z.牛牛现在要使用若干次操作让X, Y, Z变为
相等,每次操作牛牛有两种操作类型可选

操作1:从X, Y, Z中选择两个数,都加1

操作2:从X, Y, Z中选择一个数,加2

牛牛已经证明了使用若干次这两种操作一定可以让三个整数变为
相等,请你帮他计算一下最少需要多少次操作.

输入描述:

输入包括三个整数A, B, C(0 < A , B , C < 100)。
输出描述:

输出一个整数,表示最少需要的操作次数.

示例

输入
2 5 4

输出
2

思路

当时在想,根据输入会有以下几种情况:

  • x、y、z全为偶数
  • x、y、z全为奇数
  • 两偶一奇
  • 一偶两奇
    不如将三个数字排序(num1 < num2 < num3),那么会有以下情况:
  • 三个偶数(情况1)
  • 三个奇数(情况2)
  • 两个偶数一个奇数
    • 奇数排序在第三,两偶在前(情况3)
    • 奇数排序在第一位或者第二位(情况4)
  • 一个偶数两个奇数
    • 偶数排序在第三,两奇在前(情况5)
    • 偶数排序在第一位或者第二位(情况6)

对于情况1、2、3、5,最少操作次数 = (num3-num1+num3-num2)/2
对于情况4、6,讨论情况4中奇数排序在第一的情况,这个时候,需要对第二位和第三位的数字采取第一个操作,即全加1,变成奇数,此时三个数字变成情况2,最少操作次数 = 1+[(num3+1)-num1+(num3+1)-(num2+1)]/2 = (2*num2 - num1-num2)/2+1。其他情况目的也是转换到情况1、2、4、5,但是多了个第一个操作,故而+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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 3;
int a[N];

int main()
{
while(scanf("%d%d%d", &a[0], &a[1], &a[2]) != EOF)
{
sort(a, a+3);
if((a[2] - a[1] + a[2] - a[0]) % 2 == 0)
{
printf("%d\n", (2*a[2] - a[0] - a[1])/2);
}
else
{
printf("%d\n", (2*a[2] - a[0] - a[1] + 1)/2 + 1);
}
}
return 0;
}

牛牛配糖果

题目描述
牛牛有n种糖果,每种糖果都有足够多,现在牛牛想用这些糖果组成一些糖果盒.

每个糖果盒内放m个糖果,对于一个糖果盒牛牛希望第种糖果的数量不能少于li颗,也不能多于ri颗.

满足条件的糖果盒组成方案可能会有很多,牛牛希望你帮他计算一共有多少种糖果盒的拼凄方案.

对于两种方案,当有任意一种糖果个数不同,就视为两种不同方案.

输入描述:

输入包括n+1行。
第一行包括两个正整数(1<=n<= 20, 1<=m<= 100),表示糖果的种数和一盒糖果盒的糖果个数。
接下来的n行,每行两个整数li, ri(0< li< ri <= 10),表示第i种糖果的数量限制上下限。
输出描述:

输出一个整数,表示满足限定条件的方案数。保证答案在64位整数范围内。

示例

输入
3 5
0 3
0 3
0 3

输出
12

思路

开始打算采用dfs写,但是写崩了。这题没有自己做出来,参考了别人的dp写法,想了一下。
这道题意思是问有多少种满足条件的糖果放置方法,每种糖果都有放置数目的上下界,我们只需要考虑在完全满足下界下,有多少种方案就可以了,就像代码里sum = m - least。对于第i种糖果、当前盒子容量为j的情况下,如果第i-1种糖果占用的空间k不比j大,意味着现在可以放入第i种糖果,更新方案个数dp[i][j] += dp[i-1][j-k]。

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

typedef long long ll;

const int N = 20 + 5;
const int M = 100 + 5;
int a[N][2];
int avail[N];
ll res[N][M];
int least = 0, sum = 0, n, m;
int main()
{
//n表示糖果种类,m表示盒子要装多少糖果
while(scanf("%d%d", &n, &m) == 2)
{
//输入两个值,分别表示第i类糖果最少多少个和最多多少个
for(int i = 0; i < n; i++)
{
scanf("%d%d", &a[i][0], &a[i][1]);
least += a[i][0];
avail[i] = a[i][1] - a[i][0];
}
memset(res, 0, sizeof(res));
for(int i = 0; i < n; i++)
{
res[i][0] = 1;
}
sum = m - least;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= sum; j++)
{
for(int k = 0; k <= avail[i-1]; k++)
{
if(k <= j)
res[i][j] += res[i-1][j-k];
}
}
}
printf("%d\n", res[n][sum]);
}
return 0;
}
坚持分享,您的支持将鼓励我继续学习哇~