• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

leetcode1658 将 x 减到 0 的最小操作数

admin

11月 28, 2021

思路1:

前缀和+后缀和。

实现1:

 1 class Solution
 2 {
 3 public:
 4     const int INF = 0x3f3f3f3f;
 5     int minOperations(vector<int>& nums, int x)
 6     {
 7         int n = nums.size(), suffix = 0;
 8         unordered_map<int, int> mp;
 9         mp[0] = n;
10         for (int i = n - 1; i >= 0; i--)
11         {
12             suffix += nums[i];
13             mp[suffix] = i;
14         }
15         int prefix = 0;
16         int res = INF;
17         if (mp.count(x)) res = n - mp[x];
18         for (int i = 0; i < n; i++)
19         {
20             mp.erase(suffix); suffix -= nums[i];
21             prefix += nums[i];
22             if (mp.count(x - prefix))
23             {
24                 res = min(res, i + 1 + n - mp[x - prefix]);
25             }
26         }
27         return res == INF ? -1: res;
28     }
29 };

思路2:

用滑动窗口在数组中找到和等于sum-x的最长的子段(sum是数组所有元素的和)。

实现2:

class Solution
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = nums.size(), sum = 0, slow = 0, res = -1;
        int tot = accumulate(nums.begin(), nums.end(), 0);
        if (tot == x) return n;
        x = tot - x;
        for (int i = 0; i < n; i++)
        {
            sum += nums[i];
            if (sum >= x)
            {
                while (slow <= i and sum >= x)
                {
                    if (sum == x) res = max(res, i - slow + 1);
                    sum -= nums[slow++];
                }
            }
        }
        return res == -1 ? -1: n - res;
    }
};

发表回复

您的电子邮箱地址不会被公开。