【Day 47 】2024-09-30 - Number of Operations to Decrement Target to Zero

[azl397985856]

Number of Operations to Decrement Target to Zero

入选理由

暂无

题目地址

https://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero

前置知识

• 二分法
• 滑动窗口

  题目描述

  本题和 1423. 可获得的最大点数 类似。 因此大家也可以用 1423. 可获得的最大点数。（因为 binarysearch 现在 down 掉了，可能打不了卡）

You are given a list of positive integers nums and an integer target. Consider an operation where we remove a number v from either the front or the back of nums and decrement target by v.

Return the minimum number of operations required to decrement target to zero. If it's not possible, return -1.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [3, 1, 1, 2, 5, 1, 1] target = 7 Output 3 Explanation We can remove 1, 1 and 5 from the back to decrement target to zero.

Example 2 Input nums = [2, 4] target = 7 Output -1 Explanation There's no way to decrement target = 7 to zero.

[huizsh]

class Solution:
    def solve(self, A, target):
        if not A and not target: return 0
        target = sum(A) - target
        ans = len(A) + 1
        i = t = 0

        for j in range(len(A)):
            t += A[j]
            while i <= j and t > target:
                t -= A[i]
                i += 1
            if t == target: ans = min(ans, len(A) - (j - i + 1))
        return -1 if ans == len(A) + 1 else ans

[Fightforcoding]

Leetcode 1423:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        sump = sum(cardPoints)
        n = len(cardPoints)
        if n == k:
            return sump
        maxsum = sump - sum(cardPoints[:n-k])
        cursum = sum(cardPoints[:n-k])
        for i in range(n-k, n):
            cursum = cursum + cardPoints[i] - cardPoints[i -n + k]
            maxsum = max(maxsum, sump -cursum)
        return maxsum