【LeetCode】每日一题 2023_11_21 美化数组的最少删除数（贪心/模拟）

文章目录

• 刷题前唠嗑
• 题目：美化数组的最少删除数
• 结语

刷题前唠嗑

LeetCode? 启动！！！

原本今天早上要上体育课，没那么早刷每日一题的，本周是体测周，所以体育课取消了，所以马上就启动了 LeetCode 每日一题

题目：美化数组的最少删除数

题目链接：2216. 美化数组的最少删除数

题目描述

代码与解题思路

func minDeletion(nums []int) (cnt int) {
    for i := 0; i < len(nums); i++ {
        for i%2 == 0 && i < len(nums)-1 && nums[i] == nums[i+1] {
            nums = append(nums[:i], nums[i+1:]...)
            cnt++
        }
    }
    if len(nums)%2 != 0 {
        nums = nums[:len(nums)-1]
        cnt++
    }
    return cnt
}

最开始我非常的老实，题目要求把数组转变成美丽数组，我就按照他的步骤直接进行模拟，根据条件将题目给的数组做成了美丽数组，每一步记一次数，然后，就超时了

过了一会儿，我在想怎么让他不超时，我打算用把数组换成 list 降低复杂度，结果发现他的时间复杂度卡的很死，一定要我们一次遍历做出来

然后我就在想，为什么我一定要把这个数组变化成美丽数组呢？我可以通过手动修改一些数值，模拟我对数组进行过的操作，这样不也可以做到计数的效果吗？说干就干，代码如下：

func minDeletion(nums []int) (cnt int) {
    for i := 0; i < len(nums); i++ {
        for (i+cnt)%2 == 0 && i < len(nums)-1 && nums[i] == nums[i+1] {
            cnt++
        }
    }
    if (len(nums)-cnt)%2 != 0 {
        cnt++
    }
    return cnt
}

具体只有两个地方的改动：

1. 计算 i 下标是奇数还是偶数，后面一个数是下标原来是奇数，删除当前位置之后，所有数往前挪一位，他对应的下标就变成偶数了，所以我们想要模拟这个过程，只需要让 i+cnt，就能模拟下标的奇偶变换了
2. 计算删完元素之后，最后数组的长度是奇数还是偶数，只需要 -cnt 就行

结语

想念周末了，呜呜