Dell | OAMaster

01Optimizing Resource Allocation

An array of size n represents a set of available resources. Identify a subarray that optimally utilizes these resources under the following constraints: The subarray must have a specific length, denoted as k. All elements in the subarray must be unique, representing distinct resource allocations. The ultimate goal is to find the subarray that maximizes the sum of the allocated resources. Return the sum for that subarray. If it is not possible to allocate resources per the constraints, return -1. Note: A subarray is a contiguous segment of an array. Function Description Complete the function findOptimalResources in the editor.

Example 1

Input:

arr = [1, 2, 3, 7, 3, 5]
k = 3

Output:

Explanation: Following are the subarrays of length k = 3 and all elements are distinct:

[1, 2, 3] and 1 + 2 + 3 = 6
[2, 3, 7] sum = 12
[7, 3, 5] sum = 15 Return the maximum sum, 15.

解法

长度为 k 的滑动窗口，用哈希计数表跟踪窗口内每个元素出现次数；维护当前和 sum 与 dup_count(窗口内出现次数 > 1 的元素数)。当 dup_count == 0 时窗口合法，更新答案。若窗口长度 < k 或无任何合法窗口返回 -1。复杂度 O(n)，空间 O(n)。

from typing import List
from collections import defaultdict

def find_optimal_resources(arr: List[int], k: int) -> int:
    n = len(arr)
    if k > n:
        return -1
    cnt = defaultdict(int)
    s = 0
    dup = 0
    best = -1
    for i, x in enumerate(arr):
        cnt[x] += 1
        if cnt[x] == 2:
            dup += 1
        s += x
        if i >= k:
            old = arr[i - k]
            if cnt[old] == 2:
                dup -= 1
            cnt[old] -= 1
            s -= old
        if i >= k - 1 and dup == 0:
            if s > best:
                best = s
    return best

import java.util.*;

class Solution {
    int findOptimalResources(int[] arr, int k) {
        int n = arr.length;
        if (k > n) return -1;
        Map<Integer, Integer> cnt = new HashMap<>();
        long s = 0;
        int dup = 0;
        long best = -1;
        for (int i = 0; i < n; i++) {
            int c = cnt.merge(arr[i], 1, Integer::sum);
            if (c == 2) dup++;
            s += arr[i];
            if (i >= k) {
                int old = arr[i - k];
                if (cnt.get(old) == 2) dup--;
                cnt.merge(old, -1, Integer::sum);
                s -= old;
            }
            if (i >= k - 1 && dup == 0 && s > best) best = s;
        }
        return (int) best;
    }
}

class Solution {
public:
    int findOptimalResources(vector<int>& arr, int k) {
        int n = arr.size();
        if (k > n) return -1;
        unordered_map<int, int> cnt;
        long long s = 0, best = -1;
        int dup = 0;
        for (int i = 0; i < n; i++) {
            if (++cnt[arr[i]] == 2) dup++;
            s += arr[i];
            if (i >= k) {
                int old = arr[i - k];
                if (cnt[old] == 2) dup--;
                if (--cnt[old] == 0) cnt.erase(old);
                s -= old;
            }
            if (i >= k - 1 && dup == 0 && s > best) best = s;
        }
        return (int) best;
    }
};

02Count Binary Substrings

A binary string is a string consisting only of 0s and 1s. A substring is a contiguous group of characters within a string. Given a binary string, find the number of substrings that contain an equal number of 0s and 1s and all the 0s and 1s are grouped together. Note that duplicate substrings are also counted in the answer. For example, '0011' has two overlapping substrings that meet the criteria: '0011' and '01'. Function Description Complete the function getSubstringCount in the editor. getSubstringCount has the following parameter(s):

s: a binary string Returns int: the number of substrings that meet the criteria

Constraints

The length of s ≤ 10⁵
The string consists of 0s and 1s only.

Example 1

Input:

s = "011001"

Output:

Explanation: The substrings '01', '10', '1100', and '01' have equal numbers of 0s and 1s with all 0s and 1s grouped consecutively. Hence, the answer is 4. Note that the substring '0110' has an equal number of 0s and 1s but is not counted because not all 0s and 1s are grouped together.

解法

等价于 LeetCode 696。把字符串压缩成连续等字符段长度数组 groups，相邻两段贡献 min(groups[i], groups[i+1])。复杂度 O(n)，空间 O(1)。

def get_substring_count(s: str) -> int:
    prev, cur = 0, 1
    ans = 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            cur += 1
        else:
            ans += min(prev, cur)
            prev, cur = cur, 1
    ans += min(prev, cur)
    return ans

class Solution {
    int getSubstringCount(String s) {
        int prev = 0, cur = 1, ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) cur++;
            else { ans += Math.min(prev, cur); prev = cur; cur = 1; }
        }
        ans += Math.min(prev, cur);
        return ans;
    }
}

class Solution {
public:
    int getSubstringCount(string s) {
        int prev = 0, cur = 1, ans = 0;
        for (size_t i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) ++cur;
            else { ans += min(prev, cur); prev = cur; cur = 1; }
        }
        ans += min(prev, cur);
        return ans;
    }
};