Бонкҳоро ба мардум Leetcode Solution тақсим кунед


Сатҳи душворӣ осон
Ҷустуҷӯи бинарӣ Матем

Изҳороти мушкилот

Дар ин масъала, ба мо ду рақам дода мешавад Бонбони ва шумораи_мардум. Бонбони рақами аввал ин миқдори конфетҳое, ки мо дорем. num_people шумораи одамонро нишон медиҳад, ки мо бояд қандҳоро тақсим кунем.

Қоидаи тақсимоти конфетҳо инҳоянд:
Мо аз шахси чапдаст оғоз мекунем, ки ба ӯ 1 конфет диҳад, пас 2 нафар ширинро ба шахси 2, 3 қандро ба шахси 3 то н конфетро ба шахси дуввум медиҳем. Пас аз он, мо боз аз шахси чапдаст сар мекунем, ки ба ӯ қандҳои n + 1 диҳад ва пас n + 2, n + 3. Ин тақсимоти даврӣ то он даме ки конфетҳо тамом мешавад, идома меёбад, яъне вақте ки конфетҳои боқимондаамон аз талаботи ҳозира камтар хоҳанд шуд, мо шириниҳои боқимондаро ба шахси ҳозира медиҳем ва он гоҳ қатъ мешавем.

мисол

candies = 7, num_people = 4
[1,2,3,1]

Шарҳ:

Дар гардиши аввал ans [0] + = 1, ва массив [1,0,0,0] аст.
Дар гардиши дуюм, ans [1] + = 2, ва массив [1,2,0,0] аст.
Гардиши сеюм, ans [2] + = 3, ва массив [1,2,3,0] аст.
Гардиши чорум, ans [3] + = 1 (зеро танҳо як конфет боқӣ мондааст) ва массиви ниҳоӣ [1,2,3,1] аст.

candies = 10, num_people = 3
[5,2,3]

Шарҳ:

Дар гардиши аввал ans [0] + = 1, ва массив [1,0,0] аст.
Дар гардиши дуюм, ans [1] + = 2, ва массив [1,2,0] аст.
Гардиши сеюм, ans [2] + = 3, ва массив [1,2,3] аст.
Гардиши чорум, ans [0] + = 4, ва массиви ниҳоӣ [5,2,3] аст.

Муносибати 1 (Force Brute)

Равиши оддӣ ин додани ширини л ба шахси аввал ва додани 2 ба шахси дуввум ва ғайра ба шахси охирин аст. Сипас дубора аз шахси аввал ба ӯ додани қанду мувофиқан оғоз кунед.
Ин метавонад бо истифода аз ҳалқаи лона, ки дар он ҳалқаи берунӣ барои шарте иҷро мешавад, ки ягон конфет боқӣ мондааст ё не. Доираи дохилӣ аз чап ба рост ҳаракат мекунад, ки ҳар як арзишҳои мавқеъро бо конфетҳои ҳозира ҷамъбаст мекунад. Аммо мумкин аст вазъияте ба амал ояд, ки дар он шириниҳои боқимонда аз талаботи ҳозира хурдтар хоҳанд буд. Ҳамин тариқ, дар ҳалқаи ботинӣ як ҳолати if else мавҷуд аст.

вақте ки Бонбони дар айни замон зарурӣ нисбат ба Бонбони боқимонда калонтаранд, Бонбони боқимонда ба шахси ҳозира дода мешавад. Дар акси ҳол, Бонбони ҳозираи зарурӣ ба шахси ҳозира дода мешавад.

Амалисозии паҳн кардани қандҳо ба мардум Leetcode Solution

Барномаи C ++

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

Барномаи Java

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}
5 2 3

Таҳлили мураккабӣ барои паҳн кардани қандҳо ба мардум Leetcode Solution

Мураккабии вақт

O (макс (sqrt (конфетҳо))): Талаботи ҷорӣ дар ҳар давра як адад зиёд мешавад. Ҳамин тавр, шумораи конфетҳо аввал 1 адад кам мешавад ва баъд 2 адад кам мешавад ва ғайра.
Пас, пас аз вақти t, миқдори конфетҳои афтода t * (t + 1) / 2 ё тақрибан t ^ 2 конфет пас аз вақти t партофта мешавад.
Ҳамин тариқ, барои партофтани қанди c ба мо вақти sqrt (c) лозим аст.
Ҳамин тариқ, мураккабии вақт sqrt (конфетҳо) мебошад.

Мураккабии фазо 

О (шумораи_ одамон): Массиви андозаи num_people истифода мешавад. Ҳамин тариқ, мураккабии фазо O (шумораи_ одамон) мебошад.

Муносибати 2 (Ҷустуҷӯи бинарӣ)

Дар равиши қаблӣ, мо ба ҳар кас як-як конфет медодем. Сипас, боз мо давра ба давра додани шириниро оғоз мекунем. Ин бешубҳа як раванди вақтро талаб мекунад.
Пас, дар ин равиш, мо асосан қадамҳои зеринро иҷро хоҳем кард.

Якум, мо шумораи умумии пурраи конфетҳоро ҳисоб мекунем. яъне шумораи умумии одамоне, ки мувофиқи қоида Бонбони дақиқ мегиранд, муайян хоҳем кард.
Тақсимот аз 1 сар мешавад ва афзоиши он ба 1. Ҳамин тариқ, тақсимот бояд чунин бошад, 1 2 3 4 5 6. Ҳоло фарз кунем, ки мо 6 маротиба бомуваффақият шириниҳо супоридем. Пас миқдори кулли қандҳои истеъмолшуда ҷамъи шумораи 6 ададҳои натуралии аввал мебошад.
Ҳамин тариқ, мо гуфта метавонем, ки дар ҳар як лаҳзаи вақт, миқдори конфетҳои истеъмолшуда ҷамъи n ададҳои натуралӣ мебошад, ки n - тақсимот то он лаҳзаи вақт мебошад.
Ҳоло мо мехоҳем, ки мувофиқи қоида тақсимоти муваффақонаи ҳадди аксар муваффақ шавем. яъне арзиши максималии n -ро мехоҳем, ки n (n + 1) / 2 <= шумораи умумии конфетҳо.

Барои муайян кардани арзиши n, мо якчанд равиш дорем. Мо метавонем функсияи квадратиро барои n ҳал кунем ё барои n = 1 сар карда, иваз кардани арзиши n -ро бо афзоиши арзиши n ба 1 хаттӣ давом диҳем. Аммо роҳи ҳалли мувофиқ истифодаи ҷустуҷӯи бинарӣ дар инҷост.

Ҷустуҷӯи бинарӣ барои ёфтани арзиши n.

Барои истифодаи ҷустуҷӯи дуӣ дар ин ҷо, мо бояд ҳудудеро донем, ки дар он n омада метавонад. Мо гуфта метавонем, ки ҳадди аққал арзиши n метавонад 1 бошад, зеро маҳдудияти конфетҳо ҳадди аққал 1 мебошад. Ҳамин тавр, мо ҳадди аққал 1 конфетро ба шахси аввал дода метавонем, бинобар ин як тақсимоти бомуваффақият ба амал орем (Ҳамин тавр, ҳудуди поёнӣ l = 1) . Сарҳади болоии n -ро ҳисоб кардан душвор буда метавонад, бинобар ин мо ба он танҳо арзиши хеле калони бутунро аз ҷониби худ медиҳем (бигзор ҳудуди болоии r = 1000000).

Ҳоло мо мехоҳем нуқтаи n байни l ва r, ки арзиши максималӣ мебошад, ки муодиларо қонеъ мекунад.
n (n + 1) / 2 <= шумораи умумии конфетҳо.
Агар ягон нуқтае (бигзор нуқтаи миёна) байни l ва r муодилаи дар боло овардашударо қонеъ гардонад. ва нуқтаи навбатӣ (яъне миёнаи + 1) муодиларо қонеъ карда наметавонад. Он гоҳ миқдори максималии тақсимоти муваффақ хоҳад буд.

Пас аз пайдо кардани шумораи иҷрои бомуваффақият (мобайн), мо метавонем миқдори даврҳои пурраи тақсимотро ба осонӣ ҳисоб кунем, ки k = миёна /шумораи_мардум.

Ҳоло мо конфетҳоро барои ҳар як шахс пас аз k давраи пурраи он ҳисоб карда истодаем.

Бонкҳоро ба мардум Leetcode Solution тақсим кунед

 

Ҳамин тавр, мо истилоҳоти математикии пайдо кардани миқдори конфетҳоро пас аз k даврҳои пурраро ёфтем. Дар бораи давраи + н-и нопурра чӣ гуфтан мумкин аст?
Дар сикли нопурраи k + 1, мо ба осонӣ гуфта метавонем, ки иҷрои бомуваффақияти конфетҳо ба одамони дуввум нахоҳад рафт, конфетҳои мо дар ҷое ба итмом мерасанд.

Мо аллакай ҳисоб карда баромадем, ки иҷрои бомуваффақияти охирини мо дар миёна аст. Ва нимаи%шумораи_мардум шахс он конфетҳои миенаро мегирад. Ва шахси дигар ҳамаи конфетҳои боқимондаро мегирад.

Бонкҳоро ба мардум Leetcode Solution тақсим кунед
Ҳамин тариқ, мо ин тақсимоти охирини давраи нопурраро ба нимаи аввали мо илова хоҳем кард%шумораи_мардум ва 1 + миёнаи%шумораи_мардум ҳамаи конфетҳои боқимондаро мегирад.

Амалисозии паҳн кардани қандҳо ба мардум Leetcode Solution

Барномаи C ++

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long ans[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person 
        vector<int> ans1;
        for(i=0;i<num_people;i++){
            ans1.push_back((int)(ans[i]));
        }
        return ans1;
        
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

Барномаи Java

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
       
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long[]ans=new long[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person
        int[]ans1=new int[num_people];
        for(i=0;i<ans1.length;i++){
            ans1[i]=(int)(ans[i]);
        }
        return ans1;
    }
}
5 2 3

Таҳлили мураккабӣ барои паҳн кардани қандҳо ба мардум Leetcode Solution

Мураккабии вақт

О (шумораи_ одамон):  Барои пайдо кардани шумораи муваффақонаи иҷро, мо ҳалқаи while -ро истифода мебарем, ки дар бадтарин ҳолат барои log (10 ^ 6) маротиба кор мекунад, тақрибан дар ҳудуди 32. Он гоҳ давраро num_people маротиба ба таври хаттӣ иҷро кардем. Ҳамин тавр, вақти complextiy O (num_people + 32) ё O (num_people) мебошад.

Эзоҳ: Ин алгоритм вақте беҳтар хоҳад буд, ки шумораи қандҳо аз шумораи одамон зиёдтар бошад. Зеро, ин алгоритм аз шумораи қандҳо вобаста нест.

Мураккабии фазо 

О (шумораи_ одамон): Массиви андозаи num_people истифода мешавад. Ҳамин тариқ, мураккабии фазо O (шумораи_ одамон) мебошад.