网站建立有哪些功能,电子商务平台建设计划书,重庆设计培训机构有哪些,求职前记#xff1a;
做了几日的leetcode每日一题#xff0c;几乎全是十分钟结束战斗的【中等】题#xff0c;今日杀出来个【简单】题#xff0c;反倒开始难以想出很清楚的解题思路#xff0c;反复调试修改才将题目逐渐考虑全面#xff0c;看到了原本思路的漏洞#xff0c…
前记
做了几日的leetcode每日一题几乎全是十分钟结束战斗的【中等】题今日杀出来个【简单】题反倒开始难以想出很清楚的解题思路反复调试修改才将题目逐渐考虑全面看到了原本思路的漏洞于是重新思考方逐渐明了。 Tips for 涉及奇偶数的问题
0. 基本思想奇数 奇数 偶数 此外两数之和均为偶数
1. 由此延伸出要使和为偶数奇数要“一对对”地往上加即至少2个偶数数量上就任意
2. 基于上述讨论我们就得到了涉及奇偶数问题的 “万金油” 式思路转偶数
具体来说 要使结果和为偶数那就先将数的个数本题中cnt转为偶数这样便于后面奇数一对对地往上加简化讨论推荐参考下面本题思路详解食用 ~ 要使结果和为奇数那就转化为 “一个奇数偶数” 的问题从而转化为了和为偶数的问题 思路详解
1. 将奇偶数放到两个数组中并分别排序分开讨论
int maxmiumScore(vectorint cards, int cnt) {vectorintji; vectorintou;for(int i0; icards.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(k0) reou[k--];//最大偶数一定在被抽的卡里面else return 0;
} //保证当前cnt一定是偶数 3. 遍历直到cnt0或出现异常return 0
for循环遍历的内层分解
3.1 特殊情况单独讨论
if(i 0)//特殊情况单独讨论
{if(k1 cnt) return 0;else{re ou[k]; k--; cnt--; continue;}
}
else if(k 0)//特殊情况单独讨论
{if(cnt%2 1 || cnt i1) 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(vectorint cards, int cnt) {vectorintji; vectorintou;for(int i0; icards.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(k0) reou[k--];else return 0;} //保证当前cnt一定是偶数for(; cnt0 ; ){if(i 0)//特殊情况单独讨论{if(k1 cnt) return 0;else{re ou[k]; k--; cnt--; continue;}}else if(k 0)//特殊情况单独讨论{if(cnt%2 1 || cnt i1) 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;}
};~希望对你有启发~
