410. Split Array Largest Sum

LeetCode easy оригинал: C# #array #bit-manipulation #csharp #easy #leetcode #search #two-pointers

LeetCode Static

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

Пример:

Input: nums = [7,2,5,10,8], k = 2

Output: 18

C# решение

сопоставлено/оригинал

public class Solution {
    public int SplitArray(int[] nums, int k) {
        int left = nums.Max();
        int right = nums.Sum();
        while (left < right) {
            int mid = (left + right) / 2;
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private bool CanSplit(int[] nums, int k, int maxSum) {
        int currentSum = 0;
        int subarrays = 1;
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SplitArray(vector<int>& nums, int k) {
        int left = nums.Max();
        int right = nums.Sum();
        while (left < right) {
            int mid = (left + right) / 2;
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private bool CanSplit(vector<int>& nums, int k, int maxSum) {
        int currentSum = 0;
        int subarrays = 1;
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

Java решение

сопоставлено/оригинал

public class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canSplit(int[] nums, int k, int maxSum) {
        int currentSum = 0, subarrays = 1;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

JavaScript решение

сопоставлено/оригинал

function splitArray(nums, k) {
    function canSplit(nums, k, maxSum) {
        let currentSum = 0;
        let subarrays = 1;
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
    
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canSplit(nums, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Python решение

сопоставлено/оригинал

def splitArray(nums, k):
    def canSplit(nums, k, maxSum):
        currentSum = 0
        subarrays = 1
        for num in nums:
            if currentSum + num > maxSum:
                currentSum = num
                subarrays += 1
                if subarrays > k:
                    return False
            else:
                currentSum += num
        return True
    
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        if canSplit(nums, k, mid):
            right = mid
        else:
            left = mid + 1
    return left

Go решение

сопоставлено/оригинал

package main

func splitArray(nums []int, k int) int {
    left, right := max(nums), sum(nums)
    for left < right {
        mid := (left + right) / 2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(nums []int, k int, maxSum int) bool {
    currentSum, subarrays := 0, 1
    for _, num := range nums {
        if currentSum + num > maxSum {
            currentSum = num
            subarrays++
            if subarrays > k {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}

func max(nums []int) int {
    maxNum := nums[0]
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }
    return maxNum
}

func sum(nums []int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    return total
}

Algorithm

Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

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

Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.