Кенди таркатуу Leetcode Solution  


Кыйынчылык деңгээли жеңил
Алгоритмы Binary Search коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Math

Маселени билдирүү  

Бул маселеде бизге эки сан берилет таттууларды жана num_people. Биринчи саны момпосуйлар бизде бар момпосуйлардын саны. num_people момпосуйларды таратышыбыз керек болгон адамдын санын көрсөтөт.

Момпосуйларды таратуунун эрежеси:
Биз эң сол жактагы адамдан баштайбыз, ага 1 момпосуй беребиз, андан кийин 2 адамга 2 момпосуй, 3 адамга 3 момпосуйду экинчи адамга n момпосуй беребиз. Андан кийин, биз кайрадан сол жактагы адамдан баштайбыз, ага n + 1 момпосуй, андан кийин n + 2, n + 3. Бул цикл бөлүштүрүү бизде конфеттер түгөнгөнгө чейин уланат, башкача айтканда, калган конфеттерибиз учурдагы талаптан аз болуп калганда, калган конфеттерди азыркы адамга беребиз, андан кийин токтойбуз.

мисал

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

Explanation:

Биринчи бурулушта 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]

Explanation:

ошондой эле
Word Break

Биринчи бурулушта 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ге чейин берүү жана ушул сыяктуу акыркы адамга өтүү. Андан кийин биринчи адам ага тиешелүү түрдө момпосуй бергенден баштаңыз.
Муну a уюлдук, анда сырткы илмек конфет калабы же жокпу деген шартта иштейт. Ички цикл солдон оңго карай чуркайт, анда ар бир позиция мааниси берилүүчү учурдагы конфеттер менен жыйынтыкталат. Бирок учурда калган момпосуйлар учурдагы талаптан кичинекей болуп калышы мүмкүн. Ошентип, ички циклда 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 (конфеттер).

ошондой эле
Word Search Leetcode Solution

Космостун татаалдыгы 

O (эл_ саны): Num_people өлчөмүндөгү массив колдонулат. Ошентип, мейкиндиктин татаалдыгы O (эл_ саны).

2 -ыкма (Binary Search 

Мурунку ыкмада ар бир адамга момпосуйларды бир-бирден берип жатканбыз. Андан кийин дагы бир жолу биз башынан эле момпосуйларды бере баштайбыз. Бул, албетте, убакытты талап кылган жараян.
Ошентип, ушул ыкма менен, биз, негизинен, төмөнкү кадамдарды аткарабыз.

Биринчиден, момпосуйлардын толук аткарылышынын жалпы санын эсептейбиз. башкача айтканда, эреже боюнча так момпосуйларды алган адамдардын жалпы санын аныктайбыз.
Бөлүштүрүү 1ден башталып, 1ге көбөйтүлөт. Ошентип бөлүштүрүү 1 2 3 4 5 6. Ушундай болушу керек. Эми биз 6 жолу момпосуйларды ийгиликтүү бердик деп коёлу. Ошондо жалпы колдонулган момпосуйлардын саны биринчи 6 натуралдык сандын суммасына теңелет.
Ошентип, биз каалаган убакытта колдонулган момпосуйлардын саны n натуралдык сандардын суммасынан турат деп айта алабыз, ал жерде n ошол мезгилге чейин бөлүштүрүлөт.
Эми эрежеге ылайык максималдуу ийгиликтүү бөлүштүрүүнү каалайбыз. б.а n (n + 1) / 2 <= момпосуйлардын жалпы саны болушунча максималдуу маанини каалайбыз.

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

N маанисин табуу үчүн экилик издөө.

Бул жерде экилик издөөнү колдонуу үчүн, n чектеринин кандай чекте болушу керектигин билишибиз керек. Эң жок дегенде n мааниси 1 болушу мүмкүн деп айта алабыз, анткени момпосуйлардын чектелиши жок дегенде 1 болот. Демек, биз жок дегенде 1 момпосуйду биринчи адамга берсек болот, ошондуктан бир ийгиликтүү бөлүштүрүү жасайбыз (Демек, төмөнкү чеги l = 1) . Nдин жогорку чегин эсептөө татаалдаштырылышы мүмкүн, ошондуктан биз ага өтө чоң бүтүн санды берип жатабыз (жогорку чек r = 1000000 болсун).

ошондой эле
Студенттердин катышуусун эсепке алуу I Leetcode Solution

Эми биз l менен rдин ортосундагы n чекитин каалайбыз, бул теңдемени канааттандырган максималдуу маани.
n (n + 1) / 2 <= момпосуйлардын жалпы саны.
Эгерде l менен r ортосунда кандайдыр бир чекит (ортодогу чекит болсун) жогорудагы теңдемени канааттандырса. жана кийинки чекит (б.а. орто + 1) теңдемени канааттандыра албайт. Ошондо ортодо ийгиликтүү бөлүштүрүүнүн максималдуу саны болот.

Ийгиликтүү аткаруулардын санын тапкандан кийин (ортодо), бөлүштүрүүнүн толук циклдарынын санын оңой эле эсептей алабыз, ал k = орто /num_people.

Эми момпосуйларды ар бир адамга k толук циклдан кийин эсептеп жатабыз.

Кенди таркатуу Leetcode Solutionтөөнөч

 

Ошентип, биз k толук циклдан кийин момпосуйлардын санын эсептөө үчүн математикалык терминдерди таптык. K + 1 чи толук эмес цикл жөнүндө эмне айтууга болот?
K + 1-толук эмес айлампада биз момпосуйлардын ийгиликтүү аткарылышы үчүнчү адамдарга өтпөйт, биздин момпосуйлар ортосунда бир жерде бүтүп калат деп оңой эле айта алабыз.

Акыркы ийгиликтүү аткарылышыбыздын ортосунда экендигин биз буга чейин эсептеп чыкканбыз. Жана% ортоnum_people Ошол момпосуйларды адам алат. Ал эми кийинки адам калган конфеттердин бардыгын алат.

Кенди таркатуу Leetcode Solution
Ошентип, бул акыркы толук эмес цикл бөлүштүрүүнү биринчи% орто ченге кошобузnum_people жана 1 + ортоңку%num_people калган момпосуйларды алат.

Кенди таркатуу үчүн ишке ашыруу 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 (эл_ саны):  Ийгиликтүү аткаруунун санын табуу үчүн, биз a while цикл ал эң начар учурда 10 (болжол менен 6) журнал үчүн иштейт. Андан кийин биз num_people жолу сызыктуу циклди иштеткенбиз. Ошентип, убакыт комплектиси O (num_people+32) же O (num_people).

ошондой эле
Массив Leetcode чечиминдеги XOR иштеши

Эскертүү: Бул алгоритм момпосуйлардын саны адамдардын санынан көп болгондо жакшы болот. Бул алгоритм момпосуйлардын санына көз каранды эмес.

Космостун татаалдыгы 

O (эл_ саны): Num_people өлчөмүндөгү массив колдонулат. Ошентип, мейкиндиктин татаалдыгы O (эл_ саны).

1