904. Fruit Into Baskets

LeetCode medium original: C# #array #csharp #hash-table #leetcode #math #medium #sliding-window #tree #two-pointers

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным mảngом fruits, где fruits[i] - это тип фрукта, который производит i-е cây. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. given số nguyên mảng fruits, return максимальное количество фруктов, которое вы можете собрать.

Ví dụ:

Input: fruits = [1,2,1]

Output: 3

C# lời giải

đã khớp/gốc

using System;
using System.Collections.Generic;
public class Solution {
    public int TotalFruit(int[] fruits) {
        var basket = new Dictionary<int, int>();
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.Length; right++) {
            if (!basket.ContainsKey(fruits[right])) {
                basket[fruits[right]] = 0;
            }
            basket[fruits[right]]++;
            while (basket.Count > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                left++;
            }
            maxFruits = Math.Max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 TotalFruit(vector<int>& fruits) {
        var basket = new unordered_map<int, int>();
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.size(); right++) {
            if (!basket.count(fruits[right])) {
                basket[fruits[right]] = 0;
            }
            basket[fruits[right]]++;
            while (basket.size() > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                left++;
            }
            maxFruits = max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }
}

Java lời giải

đã khớp/gốc

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> basket = new HashMap<>();
        int left = 0;
        int maxFruits = 0;
        
        for (int right = 0; right < fruits.length; right++) {
            basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);
            while (basket.size() > 2) {
                basket.put(fruits[left], basket.get(fruits[left]) - 1);
                if (basket.get(fruits[left]) == 0) {
                    basket.remove(fruits[left]);
                }
                left += 1;
            }
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
}

Python lời giải

đã khớp/gốc

def totalFruit(fruits):
    from collections import defaultdict
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        basket[fruits[right]] += 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

Go lời giải

đã khớp/gốc

package main

func totalFruit(fruits []int) int {
    basket := make(map[int]int)
    left, maxFruits := 0, 0

    for right := 0; right < len(fruits); right++ {
        basket[fruits[right]]++
        for len(basket) > 2 {
            basket[fruits[left]]--
            if basket[fruits[left]] == 0 {
                delete(basket, fruits[left])
            }
            left++
        }
        if right - left + 1 > maxFruits {
            maxFruits = right - left + 1
        }
    }

    return maxFruits
}

Algorithm

Использовать метод скользящего окна для поддержания текущего подmảngа, содержащего не более двух типов фруктов.

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

Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов.

Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.