azl397985856 commented 1 month ago

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.

Martina001 commented 1 month ago

时间复杂度：令 n 和 m 分别为 houses 和 heaters 长度，L=1e9 为最大长度，对其进行排序复杂度为 O(nlogn+mlogm)，在 [0,L] 范围进行二分，单次 check 会使用「双指针」判断是否每个 houses[i] 是否被覆盖，复杂度为 O(max(n,m)∗logL)。整体复杂度为O(max(n,m)∗logL) 空间复杂度：排序所需要消耗的空间。复杂度为O(logn+logm)

 public int findRadius(int[] houses, int[] heaters) {
        // 乍一看的思路就是排序后挨个判断 找第一个最小加热半径 然后看后面的还有没有更大的，时间复杂度应该是大于ON
        // 答案解法是二分法 其实正常应该立马想到的，一个数值问题 又是最值，直接考虑二分
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int m=houses.length;
        // 边界取错了，最大会比hourse的最大值还大 以后直接取题目范围准没错
//        int max = houses[m-1];
        int max =(int)1e9;
        int left =0,right = max;
        while(left < right){
            int mid = left + (right - left)/2;
            if(checkOk(houses,heaters,mid)){
                // 如果check成功 半径缩小
                right = mid;
            }else {
                left = mid+1;
            }
        }
        // 返回此时满足checkOk最小加热半径,此时left=right 返回哪个都可
        return left;
//        return left==max?-1:left;
    }
    // 这里直接判断以x为半径是不是能全部覆盖更容易理解
    private boolean checkOk(int[] houses, int[] heaters,int radius) {
        int m=houses.length;
        int n = heaters.length;
        int j =0;
        for(int i = 0;i<m;i++){
            while(j<n && houses[i]>heaters[j]+radius){
                j++;
            }
            if(j<n && houses[i]<=heaters[j]+radius
                    && houses[i]>=heaters[j]-radius){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
}

Dtjk commented 1 month ago

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;
}

}

maike-hps commented 1 month ago

def min_operations(nums, target):

初始化操作次数和指针

operations = 0
left, right = 0, len(nums) - 1
current_sum = sum(nums[left:right+1])

# 当左指针小于等于右指针时继续循环
while left <= right:
    # 如果当前和等于目标，返回操作次数
    if current_sum == target:
        return operations
    # 如果当前和小于目标，无法通过移动指针来减少目标值
    elif current_sum < target:
        return -1
    # 如果当前和大于目标，尝试从两端减少元素
    else:
        # 尝试从右端减少元素
        if nums[right] >= target:
            return operations + 1
        else:
            current_sum -= nums[right]
            right -= 1
            operations += 1
        # 尝试从左端减少元素
        if nums[left] >= target - current_sum:
            return operations + 1
        else:
            current_sum -= nums[left]
            left += 1
            operations += 1

# 如果循环结束，说明无法通过移动指针来减少目标值
return -1

leetcode-pp / 91alg-13-daily-check