Leetcode Solution шешімімен адамдарға кәмпиттер таратыңыз


Күрделілік дәрежесі оңай
Екілік іздеу математика

Проблемалық мәлімдеме

Бұл есепте бізге екі сан беріледі кәмпиттер және адамдар саны. Бірінші санды кәмпиттер - біздегі кәмпиттер саны. num_people кәмпиттер таратылатын адам санын көрсетеді.

Кәмпиттерді тарату ережесі:
Біз сол жақтан оған 1 кәмпит бергеннен бастаймыз, сосын 2 адамға 2 кәмпит, үшінші адамға 3 кәмпит, үшінші адамға n кәмпит береміз. Осыдан кейін біз қайтадан сол жақтан бастадық, оған n + 3 кәмпит береді, содан кейін n + 1, n + 2. Бұл циклдік тарату кәмпиттеріміз біткенше жалғасады, яғни қалған кәмпиттер қазіргі қажеттіліктен аз болғанда, қалған кәмпиттерді қазіргі адамға береміз, содан кейін тоқтаймыз.

мысал

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 тәсіл (қатал күш)

Ең қарапайым тәсіл - кәмпитті бірінші адамға беріп, 2-ден 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 (max (sqrt (кәмпиттер))): Ағымдағы қажеттілік әр циклда бір-бірден артады. Сонымен, кәмпиттер саны алдымен 1-ге азаяды, содан кейін 2-ге азаяды және т.б.
Сонымен, t уақыттан кейін кәмпиттер саны t * (t + 1) / 2 құрайды немесе t уақыттан кейін шамамен t ^ 2 кәмпиттер түсіп кетеді.
Осылайша, кәмпиттерді тастау үшін бізге sqrt (c) уақыт қажет.
Осылайша, уақыттың күрделілігі - sqrt (кәмпиттер).

Ғарыштың күрделілігі 

O (адам саны): Num_people өлшемді жиымы қолданылады. Осылайша, ғарыштық күрделілік O (адамдар_ саны).

2-тәсіл (Екілік іздеу)

Алдыңғы тәсілде біз кәмпиттерді әр адамға жеке-жеке беріп отырдық. Содан кейін қайтадан біз кәмпиттерді басынан бастап бере бастаймыз. Бұл сөзсіз көп уақытты қажет ететін процесс.
Сонымен, осы тәсілмен біз негізінен келесі әрекеттерді орындаймыз.

Біріншіден, біз кәмпиттердің толық орындалуының жалпы санын есептейміз. яғни ережеге сәйкес нақты кәмпиттер алатын адамдардың жалпы санын анықтаймыз.
Тарату 1-ден басталып, 1-ге көбейеді. Осылайша тарату 1 2 3 4 5 сияқты болуы керек. Енді кәмпиттер 6 рет сәтті болды делік. Сонда тұтынылған кәмпиттер саны алғашқы 6 натурал санның қосындысын құрайды.
Сонымен, кез-келген уақытта тұтынылатын кәмпиттер саны n натурал санының қосындысы деп айта аламыз, мұндағы n - осы уақытқа дейін үлестіру.
Енді біз ережеге сәйкес максималды сәтті таратуды қалаймыз. яғни n-тің максималды мәнін n (n + 1) / 2 <= кәмпиттердің жалпы саны болатындай етіп алғымыз келеді.

$ N $ мәнін білу үшін бізде бірнеше тәсілдер бар. Біз n үшін квадраттық функцияны шеше аламыз немесе n = 1 деп бастаймыз және n мәнін n-ді 1-ге көбейтумен алмастыра аламыз. Бірақ ең дұрыс шешім - бұл жерде екілік іздеуді қолдану.

N мәнін табу үшін екілік іздеу.

Мұнда екілік іздеуді қолдану үшін n-дің қандай шекара болатынын білуіміз керек. Н-тің кем дегенде мәні 1-ге тең болады деп айтуға болады, өйткені кәмпиттердің шектеулігі кем дегенде 1-ге тең. Демек, біз ең болмағанда бірінші кәмпитті бірінші адамға бере аламыз, сондықтан бір сәтті үлестіру жасаймыз (Сонымен, төменгі шегі l = 1) . N-нің жоғарғы шекарасын есептеу қиынға соғуы мүмкін, сондықтан біз оған өте үлкен бүтін мән береміз (r = 1 жоғарғы шекарасы болсын).

Енді l мен r арасындағы теңдеуді қанағаттандыратын максималды мән болатын n нүктесін алғымыз келеді.
n (n + 1) / 2 <= кәмпиттердің жалпы саны.
Егер l мен r арасындағы кез-келген нүкте (орта нүкте болсын) жоғарыдағы теңдеуді қанағаттандырса. және келесі нүкте (яғни ортасы + 1) теңдеуді қанағаттандыра алмайды. Сонда ортасы үлестірудің максималды саны болады.

Сәтті орындалу санын тапқаннан кейін (ортасында), біз бөлудің толық циклдарының санын оңай есептей аламыз, бұл k = орта /адамдар саны.

Енді біз кәмпиттерді әр адамға толық циклдан кейін есептейміз.

Leetcode Solution шешімімен адамдарға кәмпиттер таратыңыз

 

Сонымен, біз k толық циклдан кейінгі кәмпиттер санын есептеудің математикалық терминдерін таптық. K + 1-ші толық емес цикл туралы не деуге болады.
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» кәмпиттерін адамдарға тарату үшін күрделілікті талдау

Уақыттың күрделілігі

O (адам саны):  Сәтті орындалу санын табу үшін, біз ең төменгі жағдайда журналдың (10 ^ 6) рет жұмыс істейтін 32 циклін қолданамыз, содан кейін циклды num_people рет сызықтық жүргіздік. Сонымен, уақыт complextiy O (сандық_адам + 32) немесе O (сан_адам) болады.

Ескерту: бұл алгоритм кәмпиттер саны адамдар санынан әлдеқайда көп болған кезде жақсы болады. Бұл алгоритм кәмпиттер санына байланысты емес.

Ғарыштың күрделілігі 

O (адам саны): Num_people өлшемді жиымы қолданылады. Осылайша, ғарыштық күрделілік O (адамдар_ саны).