心算挑战
leetcode
题目描述
从 N 张卡牌中选出 cnt张卡牌，若这cnt张卡牌数字总和为偶数，则选手成绩「有效」且得分为cnt张卡牌数字总和。 给定数组cards和 cnt，其中cards[i]表示第i张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
当我看到这个题目时，第一个想法是记忆化递归，因此开始对题目进行分析。
首先，题目可以看成是在0-n-1这n个数中选择cnt个数，使其和为偶数且最大。因此对第n-1个数有以下两种选择
- 选择第
n-1个数- 如果
cards[n-1]为偶数，则问题就变为在0-n-2这n-1个数中选择cnt-1个数，使其和为偶数且最大。 - 如果
cards[n-1]为奇数，则问题就变为在0-n-2这n-1个数中选择cnt-1个数，使其和为奇数且最大。
- 如果
- 不选择第
n-1个数，则问题就变为在0-n-2这n-1个数中选择cnt个数，使其和为偶数且最大。
因此这个问题就变为了在0-i这i+1个数中选择j个数，使其和为偶数/奇数且最大。然后对这个问题进行递归即可。
因此定义dfs(i,j,k)为递归函数，当k为0时，表示要和为偶数，为1时，表示和要为奇数，返回值为在0-i这i+1个数中选择j个数，使其和为偶数/奇数时的最大值。
递归边界为i<0,返回值为0.
递归关系式为
j>1dfs(i,j,k) = max(dfs(i-1,j,k), dfs(i-1, j-1, (k+cards[i]) % 2) ? dfs(i-1, j-1, (k+cards[i]) % 2)+cards[i] : 0j=1cards[i] % 2 == k ? cards[i] : dfs(i - 1, j, k)(已经对cards进行过排序)
最后返回的结果为dfs(n - 1, cnt, 0).
然后是对递归记忆化，避免多次计算同一入口条件，最开始使用3位数组cache[i][j][k]进行记忆，但这个数组有很多空间是没有被利用的。于是采用unordered_map<long long, int> cache进行记忆，其key为long long key = k | i << 1 | j << 20.
尽管这样，但最后运行结果超时，表明这种做法不可行。
dfs代码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
28function<int(int, int, int)> dfs = [&](int i, int j, int k)->int
{
if (i < 0)
{
return 0;
}
else
{
long long flag = k | i << 1 | j << 20;
if (!cache.count(flag))
{
if (j == 1)
{
cache[flag] = (cards[i] % 2 == k ? cards[i] : dfs(i - 1, j, k));
return cache[flag];
}
else
{
cache[flag] = max(dfs(i - 1, j, k), dfs(i - 1, j - 1, (k + cards[i]) % 2) ? dfs(i - 1, j - 1, (k + cards[i]) % 2) + cards[i] : 0);
return cache[flag];
}
}
else
{
return cache[flag];
}
}
};
虽然使用dp不会成功，但已经写出来记忆化递归了，那顺便把dp也写出来吧。
dp的核心递归公式和dfs一致，只是要把dfs替换成dp数组，然后边界条件是j=1时的情况，然后就是dp要从i=1开始计算所以奇数和偶数情况在每次循环时都要计算。最终结果为dp[0 | (n - 1) << 1 | cnt << 20]
- dp代码
1
2
3
4
5
6
7
8
9
10for (int i = 0; i < n; i++)
{
dp[(cards[i] % 2) | i << 1 | 1 << 20] = max(cards[i], dp[(cards[i] % 2) | (i - 1) << 1 | 1 << 20]);
dp[((cards[i] + 1) % 2) | i << 1 | 1 << 20] = dp[((cards[i] + 1) % 2) | (i - 1) << 1 | 1 << 20];
for (int j = 2; j <= i + 1 && j <= cnt; j++)
{
dp[0 | i << 1 | j << 20] = max(dp[0 | (i - 1) << 1 | j << 20], dp[cards[i] % 2 | (i - 1) << 1 | (j - 1) << 20] ? dp[cards[i] % 2 | (i - 1) << 1 | (j - 1) << 20] + cards[i] : 0);
dp[1 | i << 1 | j << 20] = max(dp[1 | (i - 1) << 1 | j << 20], dp[(cards[i] + 1) % 2 | (i - 1) << 1 | (j - 1) << 20] ? dp[(cards[i] + 1) % 2 | (i - 1) << 1 | (j - 1) << 20] + cards[i] : 0);
}
}
然后查看提示，发现要使用贪心和排序。经过思考后决定先将数组排序，然后将其分为奇偶两个数组。然后在进行判断。
在进行判断时要分为多种情况讨论，s_max,d_max1,d_max2分别为最大两个奇数的和，最大的偶数以及最大两个偶数的和。s_pos,d_pos分别表示还未使用的最大奇数下标以及还未使用的最大偶数下标。
以下是几种需要讨论的情况
cnt为1时，需要判断是否还有偶数- 只剩两个偶数时
- 只剩一个偶数时
- 没有偶数时
- 偶数数量大于2时（这是一般情况，只需要比较
s_max,d_max1,d_max2的大小进行判断即可）
其他特殊情况需要综合还未使用的奇数数量，还未使用的偶数数量以及还有多少的数没有选择。
- 奇偶数组的判断代码
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153while (cnt)
{
int s_max = 0;
int d_max1 = 0;
int d_max2 = 0;
if (cnt == 1)
{
if (d_pos >= 0)
{
ans += d[d_pos];
}
else
{
ans = 0;
}
break;
}
if (s_pos > 0)
{
s_max = s[s_pos] + s[s_pos - 1];
}
if (d_pos > 1)
{
d_max1 = d[d_pos];
d_max2 = d[d_pos] + d[d_pos - 1];
if (d_max1 >= s_max)
{
ans += d_max1;
d_pos--;
cnt--;
}
else if (d_max2 > s_max)
{
ans += d_max2;
d_pos -= 2;
cnt -= 2;
}
else
{
ans += s_max;
s_pos -= 2;
cnt -= 2;
}
}
else if (d_pos == 1)
{
d_max1 = d[d_pos];
d_max2 = d[d_pos] + d[d_pos - 1];
if (s_max > d_max2)
{
ans += s_max;
s_pos -= 2;
cnt -= 2;
}
else if (d_max1 >= s_max)
{
ans += d_max1;
d_pos--;
cnt--;
}
else
{
if ((cnt - 2) % 2)
{
ans += d_max1;
d_pos--;
cnt--;
}
else
{
if (cnt - 2 <= s_pos + 1)
{
for (int i = s_pos; i >= s_pos + 3 - cnt; i--)
{
ans += s[i];
}
ans += d_max2;
break;
}
else
{
ans = 0;
break;
}
}
}
}
else if (d_pos == 0)
{
d_max1 = d[d_pos];
if (s_max > d_max1)
{
ans += s_max;
s_pos -= 2;
cnt -= 2;
}
else
{
if ((cnt - 1) % 2)
{
if (cnt <= s_pos + 1)
{
for (int i = s_pos; i >= s_pos + 1 - cnt; i--)
{
ans += s[i];
}
break;
}
else
{
ans = 0;
break;
}
}
else
{
if (cnt - 1 <= s_pos + 1)
{
for (int i = s_pos; i >= s_pos + 2 - cnt; i--)
{
ans += s[i];
}
ans += d_max1;
break;
}
else
{
ans = 0;
break;
}
}
}
}
else if (d_pos < 0)
{
if (cnt % 2)
{
ans = 0;
break;
}
else
{
if (cnt <= s_pos + 1)
{
for (int i = s_pos; i >= s_pos + 1 - cnt; i--)
{
ans += s[i];
}
break;
}
}
}
}
这个思路比较容易想到，但其特殊情况很多，需要经过很多判断，非常烦人，很容易出现一望一些特殊情况。
查看题解后，发现了一个更加简单的方法，不需要考虑很多特殊情况。
首先将数组进行排序，然后取最大的cnt个数相加得到ans.然后根据ans进行判断
- 如果
ans为偶数，则直接返回 - 如果
ans为奇数，则有以下两种情况ans减去已使用过数中的最小偶数，加上一个未使用过的最大奇数ans减去已使用过数中的最小奇数，加上一个未使用过的最大偶数
将以上两种情况得到的值取最大即为ans，但以上两种不一定都会出现，需要进行判断，如果两种情况都不出现，则没有符合条件的结果，返回0.
以下代码中pos1,pos2分别为已使用过的数中最小奇数和最小偶数的下标，pos3,pos4分别为未使用过的数中最大奇数和最大偶数的下标。如果下标值为n,则表明不存在这样的数。
1 | |
总结
本来是一道简单题，但是想的太多，反而使其变得更加复杂。（ps:这是第二次打完这段文字，第一次没有保存，导致多花了一个小时，真是糟糕的一天）