Leetcode 第 110 场双周赛题解

Leetcode 第 110 场双周赛题解

题目1：2806. 取整购买后的账户余额

思路

题目要求为将 purchaseAmount 四舍五入到最近的 10 的倍数作为 roundedAmount，计算 100−roundedAmount 的值并返回。

分类讨论即可。

代码

/*
 * @lc app=leetcode.cn id=2806 lang=cpp
 *
 * [2806] 取整购买后的账户余额
 */

// @lc code=start
class Solution
{
   
public:
    int accountBalanceAfterPurchase(int purchaseAmount)
    {
   
        int roundedAmount;

        if (purchaseAmount % 10 < 5)
            roundedAmount = purchaseAmount - purchaseAmount % 10;
        else if (purchaseAmount % 10 > 5)
            roundedAmount = purchaseAmount + 10 - purchaseAmount % 10;
        else
            roundedAmount = purchaseAmount + 5;
            
        return 100 - roundedAmount;
    }
};
// @lc code=end

one-line code：

// one-line code

class Solution
{
   
public:
    int accountBalanceAfterPurchase(int purchaseAmount)
    {
   
        return 100 - (purchaseAmount + 5) / 10 * 10;
    }
};

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)。

题目2：2807. 在链表中插入最大公约数

思路

遍历链表，在当前节点 cur 后面插入 gcdNode 节点，同时 gcdNode 节点指向 cur 的下一个节点。

插入后，cur 更新为 cur.next.next，也就是 cur 原来的下一个节点，开始下一轮循环。

循环直到 cur 没有下一个节点为止。

代码

/*
 * @lc app=leetcode.cn id=2807 lang=cpp
 *
 * [2807] 在链表中插入最大公约数
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
   
public:
    ListNode *insertGreatestCommonDivisors(ListNode *head)
    {
   
        // 特判
        if (head == nullptr)
            return nullptr;

        for (ListNode *cur = head; cur->next != nullptr; cur = cur->next->next)
        {
   
            ListNode *gcdNode = new ListNode(gcd(cur->val, cur->next->val));
            gcdNode->next = cur->next;
            cur->next = gcdNode;
        }
        return head;
    }
    // 辅函数 - 求 x 和 y 的最大公约数
    int gcd(int x, int y)
    {
   
        if (y == 0)
            return x;
        return gcd(y, x % y);
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(nlog⁡U)，其中 n 为链表长度，U 为节点值的最大值。每次计算 gcd 需要 O(log⁡U) 的时间。

空间复杂度：O(1)。

题目3：2808. 使循环数组所有元素相等的最少秒数

思路

哈希 + 枚举。

假设答案是数组 nums 的一个元素 x，因为每个 x 每一秒可以把它旁边的两个数变成 x，所以如果两个 x 之间还有 k 个元素，那么 ⌈k/2⌉ 秒之后这些元素就可以全部变成 x。

因此把答案变成 x 需要的时间，就是两个 x 之间最多有几个元素，把元素数量除以 2 上取整。枚举所有 x，选出最优答案即可。

代码

/*
 * @lc app=leetcode.cn id=2808 lang=cpp
 *
 * [2808] 使循环数组所有元素相等的最少秒数
 */

// @lc code=start
class Solution
{
   
public:
    int minimumSeconds(vector<int> &nums)
    {
   
        // 特判
        if (nums.size() <= 1)
            return 0;

        int n = nums.size();
        // mp[x] 表示所有等于 x 的元素下标
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < n; i++)
            mp[nums[i]].push_back(i);

        int ans = INT_MAX;
        for (auto &[_, vec] : mp)
        {
   
            // 计算最终元素为 x = p.first 的情况下需要的时间
            int max_gap = 0;
            for (int i = 0; i < vec.size(); i++)
            {
   
                // 计算两个 x 之间的元素数量
                int gap = 0;
                // 注意序列是环形的
                if (i + 1 < vec.size())
                    gap = vec[i + 1] - vec[i] - 1;
                else
                    gap = n - 1 - vec[i] + vec[0];
                max_gap = max(max_gap, gap);
            }
            // 需要的时间，就是元素的最大间隔，除以 2 上取整
            ans = min(ans, (max_gap + 1) / 2);
        }
        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

空间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

题目4：2809. 使数组和小于等于 x 的最少时间

思路

贪心 + 动态规划。

题解：教你一步步思考本题！（Python/Java/C++/Go/JS/Rust）

代码

/*
 * @lc app=leetcode.cn id=2809 lang=cpp
 *
 * [2809] 使数组和小于等于 x 的最少时间
 */

// @lc code=start
class Solution
{
   
public:
    int minimumTime(vector<int> &nums1, vector<int> &nums2, int x)
    {
   
        int n = nums1.size();
        vector<pair<int, int>> a;
        for (int i = 0; i < n; i++)
        {
   
            a.push_back({
   nums2[i], nums1[i]});
        }
        sort(a.begin(), a.end());
        vector<int> dp(n + 1);
        for (int i = 0; i < n; i++)
        {
   
            for (int j = n; j > 0; j--)
            {
   
                dp[j] = max(dp[j], dp[j - 1] + a[i].second + a[i].first * j);
            }
        }
        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        for (int i = 0; i <= n; i++)
        {
   
            if (s1 + s2 * i - dp[i] <= x)
                return i;
        }
        return -1;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是数组 nums₁ 的长度。

空间复杂度：O(n)，其中 n 是数组 nums₁ 的长度。