План курса / Все задачи / Алгоритмы и структуры данных

Инвестор в стране дураков

средне

# решено

В стране дураков вместо сложения используют умножение и богатый инвестор хочет этим воспользоваться, чтобы заработать и выкупить k подряд идущих домов.

Дан массив price и число k. Найдите произведения всех подряд идущих участков длины k. Массив price — цены домов, если price[i] ≤ 0, это должник — он покроет долг и доплатит при необходимости.

Пример 1:

Ввод: price = [-2,0,1,8,-9,0,1,2,3,0], k = 3
Вывод: [0,0,-72,0,0,0,6,0]
Объяснение: 0=-2*0*1, 0=0*1*8, -72=1*8*-9, ...

Пример 2:

Ввод: price = [-100,2], k = 1
Вывод: [-100,2]

Пример 3:

Ввод: price = [1,8,9], k = 5
Вывод: []

Ограничения:

len(price) ≥ 0
k ≥ 1
Значение массива price лежит в диапазоне [-10 000, 10 000] (включительно)

public class Solution {
    public static List<int> KElementsMultiply(List<int> price, int k) {
        if (k > price.Count) {
            return new List<int>();
        }
        // число нулей в плавающем окне
        int zeroCount = 0;
        // произведение всех элементов в плавающем окне за исключением нулевых
        int nonZeroMultiply = 1;
        // заполняем окно
        for (int i = 0; i < k; i++) {
            if (price[i] == 0) {
                zeroCount++;
                continue;
            }
            nonZeroMultiply *= price[i];
        }
        var result = new List<int> { 0 };
        if (zeroCount == 0) {
            result = new List<int> { nonZeroMultiply };
        }
        // переходим от одного окна в другое
        for (int i = k; i < price.Count; i++) {
            // если элемент который выходит из окна == 0
            if (price[i - k] == 0) {
                zeroCount--;
            } else {
                nonZeroMultiply /= price[i - k];
            }
            // если элемент который приходит в окно == 0
            if (price[i] == 0) {
                zeroCount++;
            } else {
                nonZeroMultiply *= price[i];
            }
            int nextMultiply = 0;
            if (zeroCount == 0) {
                nextMultiply = nonZeroMultiply;
            }
            result.Add(nextMultiply);
        }
        return result;
    }
}

#include <vector>

using namespace std;

vector<int> kElementsMultiply(vector<int>& price, int k) {
    if (k > price.size()) {
        return {};
    }
    // число нулей в плавающем окне
    int zeroCount = 0;
    // произведение всех элементов в плавающем окне за исключением нулевых
    int nonZeroMultiply = 1;
    // заполняем окно
    for (int i = 0; i < k; i++) {
        if (price[i] == 0) {
            zeroCount++;
            continue;
        }
        nonZeroMultiply *= price[i];
    }
    vector<int> result = {0};
    if (zeroCount == 0) {
        result = {nonZeroMultiply};
    }
    // переходим от одного окна в другое
    for (int i = k; i < price.size(); i++) {
        // если элемент который выходит из окна == 0
        if (price[i - k] == 0) {
            zeroCount--;
        } else {
            nonZeroMultiply /= price[i - k];
        }
        // если элемент который приходит в окно == 0
        if (price[i] == 0) {
            zeroCount++;
        } else {
            nonZeroMultiply *= price[i];
        }
        int nextMultiply = 0;
        if (zeroCount == 0) {
            nextMultiply = nonZeroMultiply;
        }
        result.push_back(nextMultiply);
    }
    return result;
}

package main

func kElementsMultiply(price []int, k int) []int {
    if k > len(price) {
        return []int{}
    }
    // число нулей в плавающем окне
    zeroCount := 0
    // произведение всех элементов в плавающем окне за исключением нулевых
    nonZeroMultiply := 1
    // заполняем окно
    for i := 0; i < k; i++ {
        if price[i] == 0 {
            zeroCount++
            continue
        }
        nonZeroMultiply *= price[i]
    }
    result := []int{0}
    if zeroCount == 0 {
        result = []int{nonZeroMultiply}
    }
    // переходим от одного окна в другое
    for i := k; i < len(price); i++ {
        // если элемент который выходит из окна == 0
        if price[i-k] == 0 {
            zeroCount--
        } else {
            nonZeroMultiply /= price[i-k]
        }
        // если элемент который приходит в окно == 0
        if price[i] == 0 {
            zeroCount++
        } else {
            nonZeroMultiply *= price[i]
        }
        nextMultiply := 0
        if zeroCount == 0 {
            nextMultiply = nonZeroMultiply
        }
        result = append(result, nextMultiply)
    }
    return result
}

import java.util.*;

public class Solution {
    public static List<Integer> kElementsMultiply(List<Integer> price, int k) {
        if (k > price.size()) {
            return new ArrayList<>();
        }
        // число нулей в плавающем окне
        int zeroCount = 0;
        // произведение всех элементов в плавающем окне за исключением нулевых
        int nonZeroMultiply = 1;
        // заполняем окно
        for (int i = 0; i < k; i++) {
            if (price.get(i) == 0) {
                zeroCount++;
                continue;
            }
            nonZeroMultiply *= price.get(i);
        }
        List<Integer> result = new ArrayList<>();
        result.add(0);
        if (zeroCount == 0) {
            result = new ArrayList<>(Arrays.asList(nonZeroMultiply));
        }
        // переходим от одного окна в другое
        for (int i = k; i < price.size(); i++) {
            // если элемент который выходит из окна == 0
            if (price.get(i - k) == 0) {
                zeroCount--;
            } else {
                nonZeroMultiply /= price.get(i - k);
            }
            // если элемент который приходит в окно == 0
            if (price.get(i) == 0) {
                zeroCount++;
            } else {
                nonZeroMultiply *= price.get(i);
            }
            int nextMultiply = 0;
            if (zeroCount == 0) {
                nextMultiply = nonZeroMultiply;
            }
            result.add(nextMultiply);
        }
        return result;
    }
}

from typing import *

def k_elements_multiply(price: List[int], k: int) -> List[int]:
    if k > len(price):
        return []

    # число нулей в плавающем окне
    zero_count = 0
    # произведение всех элементов в плавающем окне за исключением нулевых
    non_zero_multiply = 1
    # заполняем окно
    for i in range(k):
        if price[i] == 0:
            zero_count += 1
            continue
        non_zero_multiply *= price[i]
    
    result: List[int] = [0]
    if zero_count == 0:
        result = [non_zero_multiply]

    # переходим от одного окна в другое
    for i in range(k, len(price)):
        # если элемент который выходит из окна == 0
        if price[i - k] == 0:
            zero_count -= 1
        else:
            non_zero_multiply //= price[i - k]

        # если элемент который приходит в окно == 0
        if price[i] == 0:
            zero_count += 1
        else:
            non_zero_multiply *= price[i]

        next_multiply = 0
        if zero_count == 0:
            next_multiply = non_zero_multiply
        result.append(next_multiply)
    return result

/**
 * @param {number[]} price
 * @param {number} k
 * @return {number[]}
 */
export function kElementsMultiply(price, k) {
    if (k > price.length) {
        return [];
    }
    // число нулей в плавающем окне
    let zeroCount = 0;
    // произведение всех элементов в плавающем окне за исключением нулевых
    let nonZeroMultiply = 1;
    // заполняем окно
    for (let i = 0; i < k; i++) {
        if (price[i] === 0) {
            zeroCount++;
            continue;
        }
        nonZeroMultiply *= price[i];
    }
    let result = [0];
    if (zeroCount === 0) {
        result = [nonZeroMultiply];
    }
    // переходим от одного окна в другое
    for (let i = k; i < price.length; i++) {
        // если элемент который выходит из окна == 0
        if (price[i - k] === 0) {
            zeroCount--;
        } else {
            nonZeroMultiply /= price[i - k];
        }
        // если элемент который приходит в окно == 0
        if (price[i] === 0) {
            zeroCount++;
        } else {
            nonZeroMultiply *= price[i];
        }
        let nextMultiply = 0;
        if (zeroCount === 0) {
            nextMultiply = nonZeroMultiply;
        }
        result.push(nextMultiply);
    }
    return result;
}

Оценка сложности

Время: O(n), где n - количество элементов в price
Память: O(n-k), где n - длина массива price; k - число подряд идущих домов