【Day 47 】2023-07-26 - 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

前置知识

暂无

题目描述

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.

[GuitarYs]

class Solution:
    def minOperations(self, nums, target):
        memo = {}

        def dp(nums, target):
            if target == 0:
                return 0
            if target < 0 or len(nums) == 0:
                return float('inf')

            if target in memo:
                return memo[target]

            option1 = dp(nums[:-1], target - nums[-1]) + 1
            option2 = dp(nums[1:], target - nums[0]) + 1
            result = min(option1, option2)
            memo[target] = result
            return result

        result = dp(nums, target)

        if result == float('inf'):
            return -1
        else:
            return result

[Diana21170648]

思路

滑动窗口+逆向思维

代码

  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

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Master-guang]

const solve = function(A, target) {
    if (!A.length && !target) return 0;
    target = A.reduce((sum, num) => sum + num, 0) - target;
    let ans = A.length + 1;
    let i = 0;
    let t = 0;

    for (let j = 0; j < A.length; j++) {
      t += A[j];
      while (i <= j && t > target) {
        t -= A[i];
        i++;
      }
      if (t === target) ans = Math.min(ans, A.length - (j - i + 1));
    }
    return ans === A.length + 1 ? -1 : ans;
  }
}

[HuiyingC]

Leetcode同题 - 1658. Minimum Operations to Reduce X to Zero

Intuition

• Sliding window, 同向双指针
• 反向思考，先算总和，再缩减至一边 < target，再两边收缩
• sum([0,..,l) + [r,...,n-1)] = x

Code

def minOperations(self, nums, x):
    currSum, n, ans, l = sum(nums), len(nums), float('inf'), 0

    for r in range(n):
        # 定位r指针，move至sum[r,...,n-1)<x处
        # 答案只能存在r,...,n-1和sum(0,...,l)<x区域
        # 双指针收缩并更新答案
        currSum -= nums[r]
        # if smaller, move `l` to left
        while currSum < x and l <= r:
            currSum += nums[l]
            l += 1
        # check if equal
        if currSum == x:
            ans = min(ans, (n-1-r)+l)

    return ans if ans != float('inf') else -1

Complexity Analysis

• Time complexity : O(n)
• Space complexity: O(1)

[wzbwzt]

/* 思路： 滑动窗口

问题可以转换为求nums中最长的连续字串和=sum(nums)-target

复杂度： 时间复杂度： O(n) 空间复杂度： 1 */

func solve(nums []int, target int) int {
    length := len(nums)
    sum := 0
    for _, v := range nums {
        sum += v
    }

    target = sum - target

    ans := length + 1
    i := 0
    tmp_sum := 0
    for j := 0; j < length; j++ {
        tmp_sum += nums[j]
        for tmp_sum > sum {
            tmp_sum -= nums[i]
            i++
        }

        if tmp_sum == target {
            ans = min(ans, length-(j-i+1))
        }
    }
    if ans == length+1 {
        return -1
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

[SoSo1105]

思路

同向双指针

代码

def minOperations(self, nums, x):
    currSum, n, ans, l = sum(nums), len(nums), float('inf'), 0

    for r in range(n):
        currSum -= nums[r]
        # if smaller, move `l` to left
        while currSum < x and l <= r:
            currSum += nums[l]
            l += 1
        # check if equal
        if currSum == x:
            ans = min(ans, (n-1-r)+l)

    return ans if ans != float('inf') else -1

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[zhaoygcq]

思路

滑动窗口: 把求k个数的最大和 => 连续 len - k个数的最小和

代码

/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function(cardPoints, k) {
    // 求连续 cardPoints.length - k 个元素的最小和
    let len = cardPoints.length;
    let size = len - k;
    let sum = 0;
    for(let i = 0; i < size; i++) {
        sum += cardPoints[i];
    }

    let minSum = sum;
    for(let i = len - k; i < len; i++) {
        sum += cardPoints[i] - cardPoints[i - size];
        minSum = Math.min(minSum, sum);
    }

    return cardPoints.reduce((prev, curr) => prev + curr) - minSum;
};

复杂度分析

• 时间复杂度：O(K)，其中 N 为s的长度， K
• 空间复杂度：O(Math.max(K, N - k))

[Beanza]

class Solution: def minOperations(self, nums, target): memo = {}

    def dp(nums, target):
        if target == 0:
            return 0
        if target < 0 or len(nums) == 0:
            return float('inf')

        if target in memo:
            return memo[target]

        option1 = dp(nums[:-1], target - nums[-1]) + 1
        option2 = dp(nums[1:], target - nums[0]) + 1
        result = min(option1, option2)
        memo[target] = result
        return result

    result = dp(nums, target)

    if result == float('inf'):
        return -1
    else:
        return result

[Alexno1no2]

抄别人的巧妙转换后的题解

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if len(cardPoints) == k: 
            return sum(cardPoints)
        # 逆向思维，按题中意思取左取右的最大值，反过来就是求中间连续子数组的和最小
        # 由于要取 k 张牌，所以反过来就是在中间找连续的长度为 len(carPoints)-k 的子数组使其和最小，这以部分就是滑动窗口
        res_opposite = sum(cardPoints[:len(cardPoints) - k])  # 变量存储滑窗的最小值，这里先按初始位置赋初值
        current_sum = res_opposite  # current_sum记录当前滑窗总和
        left_idx, right_idx = 0, len(cardPoints) - k - 1  # 设定滑窗边界
        for _ in range(k):  # 滑窗将移动 k 次
            left_idx += 1  # 更新滑窗左右边界
            right_idx += 1
            # 计算新位置滑窗内值的总和，减去滑窗原来的左边界，加上滑窗新的右边界
            current_sum = current_sum - cardPoints[left_idx - 1] + cardPoints[right_idx]  
            res_opposite = min(res_opposite, current_sum)  # 更新最小的滑窗范围内的和
        return sum(cardPoints) - res_opposite

[snmyj]

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