【leetcode详解】心算挑战: 一题搞懂涉及奇偶数问题的 “万金油” 思路(思路详解)

前记： 

做了几日的leetcode每日一题，几乎全是十分钟结束战斗的【中等】题，今日杀出来个【简单】题，反倒开始难以想出很清楚的解题思路，反复调试修改才将题目逐渐考虑全面，看到了原本思路的漏洞，于是重新思考，方逐渐明了。

Tips for 涉及奇偶数的问题：

0. 基本思想：奇数 = 奇数 + 偶数； 此外，两数之和均为偶数

1. 由此延伸出：要使和为偶数，奇数要“一对对”地往上加（即至少2个），偶数数量上就任意

2. 基于上述讨论，我们就得到了涉及奇偶数问题的 “万金油” 式思路：转偶数

具体来说：

        要使结果和为偶数，那就先将数的个数（本题中cnt）转为偶数，这样便于后面奇数一对对地往上加，简化讨论（推荐参考下面本题思路详解食用 ~）

        要使结果和为奇数，那就转化为 “一个奇数+偶数” 的问题（从而转化为了和为偶数的问题）

思路详解：

1. 将奇偶数放到两个数组中并分别排序，分开讨论：

int maxmiumScore(vector<int>& cards, int cnt) {vector<int>ji; vector<int>ou;for(int i=0; i<cards.size(); i++){if(cards[i]%2 == 0){ou.push_back(cards[i]);}else{ji.push_back(cards[i]);}}sort(ou.begin(), ou.end());sort(ji.begin(), ji.end());
}

2. 若cnt初始为奇数，则转化为偶数

int k = ou.size()-1;
if(cnt%2 == 1)//若cnt初始为奇数
{cnt--;if(k>=0) re+=ou[k--];//最大偶数一定在被抽的卡里面else return 0;
} //保证当前cnt一定是偶数

 3. 遍历直到cnt=0或出现异常（return 0）

for循环遍历的内层分解：

3.1 特殊情况单独讨论

if(i < 0)//特殊情况单独讨论
{if(k+1 < cnt) return 0;else{re += ou[k]; k--; cnt--; continue;}
}
else if(k < 0)//特殊情况单独讨论
{if(cnt%2 == 1 || cnt > i+1) return 0;else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2; continue;}
}

3.2 因为抽卡数目(cnt)有限，且奇数牌只能一对一对抽，所以需要判断抽一对奇数牌和抽一对偶数牌谁的增值大

if(i >= 1)//奇数数组至少剩余两个元素
{if(k >= 1)//偶数数组至少剩余两个元素{if(ou[k]+ou[k-1] <= ji[i]+ji[i-1]){re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}else{re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}}else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}
}
else if(k >= 1){//奇数数组剩余元素个数<1re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;
}
else{//i,k == 1return 0;
}

 AC代码见下 ~

class Solution {
public:int maxmiumScore(vector<int>& cards, int cnt) {vector<int>ji; vector<int>ou;for(int i=0; i<cards.size(); i++){if(cards[i]%2 == 0){ou.push_back(cards[i]);}else{ji.push_back(cards[i]);}}sort(ou.begin(), ou.end());sort(ji.begin(), ji.end());//保证从小到大排列int re = 0;int i = ji.size()-1;int k = ou.size()-1;if(cnt%2 == 1)//若cnt初始为奇数{cnt--;if(k>=0) re+=ou[k--];else return 0;} //保证当前cnt一定是偶数for(; cnt>0 ; ){if(i < 0)//特殊情况单独讨论{if(k+1 < cnt) return 0;else{re += ou[k]; k--; cnt--; continue;}}else if(k < 0)//特殊情况单独讨论{if(cnt%2 == 1 || cnt > i+1) return 0;else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2; continue;}}if(i >= 1)//奇数数组至少剩余两个元素{if(k >= 1)//偶数数组至少剩余两个元素{if(ou[k]+ou[k-1] <= ji[i]+ji[i-1]){re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}else{re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}}else{re+=(ji[i]+ji[i-1]);cnt-=2; i-=2;}}else if(k >= 1){//奇数数组剩余元素个数<1re+=(ou[k]+ou[k-1]);cnt-=2; k-=2;}else{//i,k == 1return 0;}}return re;}
};

~希望对你有启发~