← 返回目录

算法笔试模拟题精解之“奇偶数列”

第 34 / 74 卷日期：

算法笔试模拟题精解之“奇偶数列”

贡献者 | 猿圈

简介：对于这道题来说，只需要考虑是奇数还是偶数，而不用理会具体的值。

题目描述

等级：中等

知识点：DP

查看题目：奇偶数列

Tom 有一个长度为 n(1<=n<=100) 的数列，数列中只包含 1-n 且不重复的数字。

这个数列是一个不完整的数列，意思是说数列中有几个位置是空的，Tom 想让

你帮他把空的位置填上数字，当然是有要求的，对于一个数列来说，如果相邻两位的

数字奇偶性不同，这个数列的权值就 +1，请你算出来将空位补上以后，权值最小为

多少 ? 对于这个数列，空位用 0 表示。

输入数列长度 n(1<=n<=100) 和 n 个数 ai(0<=ai<=n)

输出填上空位以后的数列的最小权值。

示例 1

输入：

5

[0,5,0,2,3]

输出：

2

注意 :

对于样例解释说明，符合题意的数列可以为 1 5 4 2 3

解题思路一：贪心算法

对于这道题来说，只需要考虑是奇数还是偶数，而不用理会具体的值。

下面用 0 代表偶数，1 代表奇数，-1 表示空位。

这道题对应的空位只有下面 5 种情况（连续空位的不同个数没有影响）：

  1. 空位在左右两侧（以左侧举例）-10 也就是最边上是连续的空位，然后接一

个偶数；

  1. 空位在左右两侧（以左侧举例）-11 也就是最边上是连续的空位，然后接一

个奇数；

  1. 空位在中间，两侧都是奇数 1-11；
  2. 空位在中间，两侧都是偶数 0-10；
  3. 空位在中间，两侧一奇一偶 0-11。

计算在 5 种情况下对应最少可能增加的权值

  1. 可能增加 0( 填偶数 ) 或 1( 偶数不够，要填奇数 )
  2. 可能增加 0 或 1 与上面对应
  3. 可能 0( 填奇数 ) 或 2( 奇数不够填偶数 )
  4. 可能 0 或 2 与上面对应
  5. 只能为 1

给 5 种空位重要性排序（确定贪心策略）

第 5 种，因为不管填什么都增加 1，所以排在最后

第 3，4 种，因为填错了会增加 2，比一二种多，所以排第一（相同情况按照空

位个数排序，越少越靠前）

第 1，2 种，排在 3，4 后面。

计算过程

  1. 遍历一次，从原数组中提取出这 5 种空位，同时计算没有填入的奇数偶数分

别为多少个

  1. 按照 (3，4)(1，2)(5) 分成三组，对前两组按照空位从少到多排序
  2. 按照贪心策略的顺序

先判断 (3，4) 中有多少可以增加 0 的，并消耗掉对应的奇数偶数个数，增加为

2 的直接跳过，不消耗个数。

然后判断 (1，2) 中有多少可以增加 0 的，并消耗掉对应的奇数偶数个数，增加

为 1 的直接跳过，不消耗个数。

最后计算 (3，4) 剩下的个数 *2+(1，2) 中剩下的个数 *1+(5) 中剩下的个数 *1

解题思路二：动态规划

样例是 0 5 0 2 3，那么两个空位只能填 1 或者 4，所以有 1 5 4 2 3 和 4 5 1 2

3 两种情况。

由于前者的权值要小于后者的权值，所以 1 5 4 2 3 是最优解，如果我们考虑贪

心的做法会有很多的情况要讨论，而且也避免不了一些冲突。

我们可以将问题抽象一下，其实就是求对于当前这一个位置之前有多少个奇偶

对，可以进一步转换成求前一位的奇偶性，不妨考虑动态规划。

我们设 dpi[k]，其中 i 表示当前所在第 i 位，j 表示前 i 位一共有 j 个奇数 ( 那么就

有 i-j 个偶数 )，k 只能为 0 或 1，当 k 为 0 表示第 i 位放 0，k 为 1 表示第 i 位放 1，

然后我们同时更新第 i 位放 0 和放 1 的情况的最小值。

那么对于当前的位来说如果填偶数就有 dpi[0] = min(dpi-1[0], dpi-1[1] + 1)，

如果填奇数就有 dpi[1] = min(dpi-1[0] + 1, dpi-1[1])，最终的状态就是 min(dpn[1],

dpn[0])。

图 87-1
图 87-1

时间复杂度：O(2n^2)

空间复杂度：2n^2+n

看完之后是不是有了答题思路了呢，快来练练手吧：奇偶数列

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”