遇到一个奇偶数列问题，求解答。
Tom 有一个长度为 n(1<=n<=100) 的数列，数列中只包含 1-n 且不重复的数字。这个数列是一个不完整的数列，意思是说数列中有几个位置是空的，Tom 想让你帮他把空的位置填上数字，当然是有要求的，对于一个数列来说，如果相邻两位的数字奇偶性不同，这个数列的权值就 +1，请你算出来将空位补上以后，权值最小为多少 ? 对于这个数列，空位用 0 表示。输入数列长度 n(1<=n<=100) 和n个数 ai(0<=ai<=n)输出填上空位以后的数列的最小权值。
展开
收起
1
条回答
写回答
写回答
-
1.遍历一次，从原数组中提取出这 5 种空位,同时计算没有填入的奇数偶数分别为多少个 2.按照 (3，4)(1，2)(5) 分成三组，对前两组按照空位从少到多排序 3.按照贪心策略的顺序先判断 (3，4) 中有多少可以增加 0 的，并消耗掉对应的奇数偶数个数，增加为2 的直接跳过，不消耗个数。然后判断 (1，2) 中有多少可以增加 0 的，并消耗掉对应的奇数偶数个数，增加为 1 的直接跳过，不消耗个数。最后计算 (3，4) 剩下的个数 *2+(1，2) 中剩下的个数 *1+(5) 中剩下的个数 *1 因此输入：5 [0,5,0,2,3] 输出：2 注 :对于样例解释说明，符合题意的数列可以为 1 5 4 2 3
2021-12-23 18:43:07赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
