【Day 47 】2022-12-17 - 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.

[mayloveless]

1423. 可获得的最大点数

      思路

      根据题意，需要计算左边连续m个数和，和右边k-m个数和，两边再相加的最大值。 先计算从右到左，累加的值。然后从左向右遍历，测试如果m为0～k个时，左边的和，加上右边的和是多少。 记录每次计算的最大值

代码

var maxScore = function(cardPoints, k) {
    // 右边和的累积
    const sum = [];
    for (let i = cardPoints.length-1;i >=0;i--) {
        if (i === cardPoints.length-1) {
            sum[i] = cardPoints[cardPoints.length-1]
        } else {
            sum[i] = sum[i+1] + cardPoints[i];
        }
    }
    // 左边如果个数为0.
    let max = sum[cardPoints.length- k];
    let sumLeft = 0;
    // 左边个数分别为1-k
    for(let i=1;i<=k;i++) {
        sumLeft += cardPoints[i-1];
        const sumRight = i ===k ? 0 : sum[cardPoints.length- k + i];
        max = Math.max(sumLeft+sumRight, max);
    }

    return max;
};

复杂度

时间：O(n) 空间：O(n)

[zjsuper]

class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int:

k = len(cardpoints) is a corner case

    sums = sum(cardPoints)
    print(sums)
    l = 0
    r = l+len(cardPoints)-k-1
    temp_sum = sum(cardPoints[l:r+1])
    temp_ans = sums - temp_sum
    ans = sums - temp_sum
    print(ans)
    while l<=r and r < len(cardPoints)-1: #l<=r l=r is a corner case
        r += 1
        l += 1
        temp_ans = temp_ans-cardPoints[r]+cardPoints[l-1]
        print(l,r,temp_ans)
        ans = max(ans,temp_ans)

    return ans

[jackgaoyuan]

func minOperations(nums []int, x int) int {
    var total int
    longest := 0
    for _, val := range nums {
        total += val
    }
    if x > total {
        return -1
    }
    if x == total {
        return len(nums)
    }
    var subTotal, i, j int
    for ;j < len(nums); j++ {
        subTotal += nums[j]
        for i < j && subTotal > (total - x) {
            subTotal -= nums[i]
            i++
        }
        if subTotal == (total - x) && (j - i + 1) > longest {
            longest = j - i + 1
        }
    }
    if longest == 0 {
        return -1
    }
    return len(nums) - longest
}

[chenming-cao]

解题思路

滑动窗口+前缀和。

代码

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int[] preSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + cardPoints[i - 1];
        }

        int max = 0;
        for (int i = 0; i <= k; i++) {
            int score = preSum[i] + preSum[len] - preSum[len - k + i];
            max = Math.max(score, max);
        }
        return max;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[FlipN9]

/**
    Sliding Window: 
    由于只能从开头和末尾拿 k 张卡牌，所以最后剩下的必然是连续的 n−k 张卡牌
    可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值。

    TC: O(N)    SC: O(1)
*/
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int N = cardPoints.length;
        int windowSize = N - k;
        int sum = 0;
        for (int i = 0; i < windowSize; i++) {
            sum += cardPoints[i];
        }
        int minSum = sum, total = sum;
        for (int i = windowSize; i < N; i++) {
            total += cardPoints[i];
            sum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = Math.min(minSum, sum);
        }
        return total - minSum;
    }
}

[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

[wtdcai]

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

[zywang0]

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

[bookyue]

code

    public int minOperations(int[] nums, int x) {
        int target = 0;
        for (int num : nums) target += num;
        target -= x;

        int sumOfWindow = 0;
        int maxLen = -1;
        for (int right = 0, left = 0; right < nums.length; right++) {
            sumOfWindow += nums[right];
            while (left <= right && sumOfWindow > target) {
                sumOfWindow -= nums[left];
                left++;
            }

            if (sumOfWindow == target)
                maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen != -1 ? nums.length - maxLen : -1;
    }

[A-pricity]

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

[Abby-xu]

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: ans = [[]] for n in nums: new_ans = [] for l in ans: for i in range(len(l)+1): new_ans.append(l[:i]+[n]+l[i:]) if i<len(l) and l[i]==n: break #handles duplication ans = new_ans return ans

[tiandao043]

思路

leetcode 1423 滑动窗口，先统计正着k个，然后开始滚倒数，维护一个最大值。

代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int ans=0,index=0;
        for(int i=0;i<k;i++){
            index+=cardPoints[i];
        }
        ans=max(ans,index);
        int n=cardPoints.size();
        for(int j=0;j<k;j++){
            index=index-cardPoints[k-j-1]+cardPoints[n-1-j];
            ans=max(ans,index);
        }
        return ans;
    }
};

O(n) O(1)

[Dou-Yu-xuan]

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   

[RestlessBreeze]

代码

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int[] preSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + cardPoints[i - 1];
        }

        int max = 0;
        for (int i = 0; i <= k; i++) {
            int score = preSum[i] + preSum[len] - preSum[len - k + i];
            max = Math.max(score, max);
        }
        return max;
    }
}

[Elsa-zhang]

''' 给你一个数组,你只可以移除数组两端的数。求最小移除次数,使得移除的数字和为target
    思路：
    sum(A)-target的最长子序列
'''

class Solution:
    def solve(self, A: list[int], target: int):
        target = sum(A)-target
        ans = len(A)+1

        t = 0
        j = 0

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

        return -1 if ans == len(A) + 1 else ans

[JancerWu]

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int ans = 0, sum = 0;
        for (int i = n - k; i < n; i++) {
            sum += cardPoints[i];
        }
        ans = Math.max(ans, sum);
        for (int l = n - k, r = 0; r < k; r++) {
            sum -= cardPoints[l++];
            sum += cardPoints[r];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

[GG925407590]

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        // 滑动窗口大小为 n-k
        int windowSize = n - k;
        // 选前 n-k 个作为初始值
        int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
        int minSum = sum;
        for (int i = windowSize; i < n; ++i) {
            // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            sum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = min(minSum, sum);
        }
        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
    }
};

[klspta]

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int ans = 0, sum = 0;
        for (int i = n - k; i < n; i++) {
            sum += cardPoints[i];
        }
        ans = Math.max(ans, sum);
        for (int l = n - k, r = 0; r < k; r++) {
            sum -= cardPoints[l++];
            sum += cardPoints[r];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

[buer1121]

class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int:

共n张，移除k张，求n-k的最小值

    #相当于求这个n个数字滑动窗口长度为n-k的最小值
    n=len(cardPoints)
    window_len=n-k
    cnt=sum(cardPoints[:window_len])
    min_sum=cnt
    for i in range(window_len,n):
        cnt=cnt + cardPoints[i]-cardPoints[i-window_len]
        min_sum=min(min_sum,cnt)
    return sum(cardPoints)-min_sum

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
        int curSum = 0;
        for(int i=0;i<n-k;i++){
            curSum += cardPoints[i];
        }
        int res = curSum;
        //滑动窗口求n-k个连续元素的最小值
        for(int i=n-k;i<n;i++){
            curSum += cardPoints[i] - cardPoints[i-n+k];
            res = Math.min(res,curSum);
        }
        int allSum = 0;
        for(int num:cardPoints){
            allSum += num;
        }
        //数组总和减去n-k个连续元素的最小值即为结果
        return allSum - res;

    }
}

[Jetery]

1658. 将 x 减到 0 的最小操作数

思路

记数组里所有元素的和为sum, 要将x减到 0, 等价于sum子串和等于sum - x
题目要求的是最小操作数, 那么就寻找满足条件的最大子串长度

代码 (cpp)

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int target = 0;
        for (int num : nums) target += num;
        target -= x;

        int sum = 0, len = -1;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            sum += nums[r];
            while (l <= r && sum > target) sum -= nums[l++];
            if (sum == target) len = max(len, r - l + 1);
        }

        return len == -1 ? -1 : nums.size() - len;
    }
};

复杂度分析

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

[AtaraxyAdong]

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int[] preSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + cardPoints[i - 1];
        }

        int max = 0;
        for (int i = 0; i <= k; i++) {
            int score = preSum[i] + preSum[len] - preSum[len - k + i];
            max = Math.max(score, max);
        }
        return max;
    }
}

[neado]

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

[Ryanbaiyansong]

class Solution:
    def maxScore(self, a: List[int], k: int) -> int:
        n = len(a)
        拿k张卡, 卡牌总和最大, 窗口的size 就是n - k, 窗口总和最小即可
        res = inf
        j = sum = 0
        tot = 0
        for i, x in enumerate(a):
            tot += x
            sum += x
            while j < n and i - j + 1 > n - k:
                sum -= a[j]
                j += 1
            if i - j + 1 == n - k:
                res = min(res, sum)
        return tot - res

[whoam-challenge]

class Solution(object): def minOperations(self, nums, x): target = sum(nums) - x

    if target == 0:
        return len(nums)

    left, right = 0, 0 
    curr, cnt = 0, 0 

    while right < len(nums):
        curr = curr + nums[right]

        while left < right and curr > target:
            curr = curr - nums[left]
            left = left + 1
        if curr == target:
            cnt = max(cnt, right - left + 1)
        right = right + 1

    if cnt == 0:
        return -1 
    else:
        return len(nums) - cnt