Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2024-01-04 12:41:12
https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/description
2870. Minimum Number of Operations to Make Array Empty
給你一個整數陣列nums我們可以對裡面的數字做兩種操作:
1.刪除兩個相同數字
2.刪除三個相同數字
求出最少需要幾次操作可以讓陣列為空,如果不能則返回-1。
思路:
1.先計算出每個數字的出現次數。
2.對每個數字的最小刪除次數作判斷,如果次數為1表示不可能刪除所以返回-1。
3.因為2和3可以組成任何大於1的數字,且用3去刪除的操作次數一定比用2少,對這一點
做貪婪:
case1 => 若可被3整除,返回 n/3
case2 => 否則若 n-2 可以被3整除,返回 1 + (n-2)/3
case3 => 否則返回2 + (n-4)/3
(n-6) 回到case1
4.把所有結果加總即可。
Java Code:
作者: sustainer123 (caster)   2024-01-04 12:42:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com