1705.吃苹果的最大数目

链接：1705.吃苹果的最大数目
难度：Medium
标签：贪心、数组、堆（优先队列）
简介：给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

题解 1 - cpp

• 编辑时间：2021-12-24
• 执行用时：16ms
• 内存消耗：15.6MB
• 编程语言：cpp
• 解法介绍：异或得到两个唯一数的值，根据首个不同的位数，分别异或。

class Solution {
   public:
    vector<int> singleNumbers(vector<int> &nums) {
        int val = 0;
        for (auto &num : nums) val ^= num;
        vector<int> ans(2, 0);
        int bit = 0;
        while ((val & 1 << bit) == 0) bit++;
        bit = 1 << bit;
        for (auto &num : nums) {
            if (num & bit)
                ans[0] ^= num;
            else
                ans[1] ^= num;
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2024-12-24
• 执行用时：981ms
• 内存消耗：22.36MB
• 编程语言：python
• 解法介绍：有序数组遍历

from sortedcontainers import SortedDict
class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        res = 0
        day = 1
        expiredDict = SortedDict()
        while day <= len(apples) or len(expiredDict):
            while len(expiredDict) and -expiredDict.peekitem()[0] <= day:
                expiredDict.popitem()
            if day <= len(apples) and days[day - 1] != 0:
                time, cnt = -(days[day - 1] + day), apples[day - 1]
                if not time in expiredDict: expiredDict[time] = 0
                expiredDict[time] += cnt
            if len(expiredDict):
                item = expiredDict.popitem()
                res += 1
                if item[1] != 1:
                    expiredDict[item[0]] = item[1] - 1
            day += 1
        return res