แจกจ่ายขนมให้กับผู้คน Leetcode Solution


ระดับความยาก สะดวกสบาย
การค้นหาแบบไบนารี คณิตศาสตร์

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับตัวเลขสองตัว ลูกอม และ num_people. ลูกอมหมายเลขแรกคือจำนวนลูกอมที่เรามี num_people แสดงจำนวนคนที่เราต้องแจกจ่ายลูกอม

กฎของการแจกลูกอมคือ:
เริ่มจากคนซ้ายสุดให้ลูกกวาด 1 ลูกจากนั้นให้ลูกอม 2 ลูกให้คนที่ 2 ลูก 3 ลูกให้คนที่ 3 จนถึงคนที่ 1 หลังจากนั้นเราเริ่มจากคนซ้ายสุดให้ลูกอม n + 2 เม็ดแก่เขาอีกครั้งจากนั้น n + 3, n + XNUMX การกระจายแบบวัฏจักรนี้จะดำเนินต่อไปจนกว่าลูกอมจะหมดกล่าวคือเมื่อลูกอมที่เหลือของเรามีน้อยกว่าความต้องการในปัจจุบันเราจะให้ลูกอมที่เหลือแก่คนปัจจุบันจากนั้นเราก็หยุด

ตัวอย่าง

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 (Brute Force)

วิธีที่ง่ายที่สุดคือให้ขนมกับคนแรกและให้คนที่ 2 คนที่ 2 ไปเรื่อย ๆ จนถึงคนสุดท้าย จากนั้นให้เริ่มจากคนแรกให้ลูกอมเขาอีกครั้ง
ซึ่งสามารถทำได้โดยใช้ a วนซ้ำโดยที่วงนอกจะวิ่งตามเงื่อนไขว่ามีขนมเหลืออยู่หรือไม่ วงในจะวิ่งจากซ้ายไปขวาซึ่งจะสรุปค่าแต่ละตำแหน่งกับลูกอมปัจจุบันที่จะได้รับ แต่อาจมีสถานการณ์ที่ลูกอมที่เหลืออยู่ในปัจจุบันจะมีขนาดเล็กกว่าความต้องการในปัจจุบัน ดังนั้นจึงมีเงื่อนไข if else ในวงใน

เมื่อลูกอมที่ต้องการในปัจจุบันมีมากกว่าลูกอมที่เหลืออยู่จะมอบลูกอมที่เหลือให้กับคนปัจจุบัน มิฉะนั้นจะมอบลูกอมที่จำเป็นในปัจจุบันให้กับคนปัจจุบัน

การดำเนินการเพื่อแจกจ่ายขนมให้กับผู้คนโซลูชัน Leetcode

โปรแกรม 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

ความซับซ้อนของเวลา

O (สูงสุด (sqrt (ลูกอม))): ความต้องการปัจจุบันเพิ่มขึ้นทีละหนึ่งในทุกๆลูป ดังนั้นจำนวนของลูกอมจะลดลง 1 ครั้งแรกจากนั้นลดลง 2 ไปเรื่อย ๆ
ดังนั้นหลังจากเวลา t จำนวนของลูกอมที่ดรอปคือ t * (t + 1) / 2 หรือประมาณ t ^ 2 ลูกอมจะถูกทิ้งหลังจากเวลา t
ดังนั้นในการวาง c candies เราต้องใช้เวลา sqrt (c)
ดังนั้นความซับซ้อนของเวลาคือ sqrt (ลูกอม)

ความซับซ้อนของอวกาศ 

O (จำนวนคน): ใช้อาร์เรย์ของขนาด num_people ดังนั้นความซับซ้อนของพื้นที่จึงเป็น O (num_people)

แนวทางที่ 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 = mid /num_people.

ตอนนี้เรากำลังคำนวณลูกอมให้แต่ละคนหลังจาก k ครบรอบ

แจกจ่ายขนมให้กับผู้คน Leetcode Solution

 

ดังนั้นเราจึงพบเงื่อนไขทางคณิตศาสตร์เพื่อคำนวณจำนวนลูกอมหลังจาก k ครบรอบ สิ่งที่เกี่ยวกับ k + 1 th รอบที่ไม่สมบูรณ์
ในรอบที่ไม่สมบูรณ์ของ k + 1 เราสามารถพูดได้อย่างง่ายดายว่าการเติมลูกอมที่ประสบความสำเร็จจะไม่ตกอยู่กับคนที่ n ลูกอมของเราจะเสร็จสิ้นในระหว่าง

เราได้คำนวณแล้วว่าความสำเร็จครั้งล่าสุดของเราอยู่ในช่วงกลาง และ% กลางnum_people คน ๆ นั้นจะเอาลูกอมตอนกลาง และคนต่อไปจะได้รับลูกอมที่เหลือทั้งหมด

แจกจ่ายขนมให้กับผู้คน Leetcode Solution
ดังนั้นเราจะเพิ่มการแจกแจงรอบสุดท้ายที่ไม่สมบูรณ์นี้ใน% กลางแรกของเราnum_people และ 1 + กลาง%num_people จะได้รับลูกอมที่เหลือทั้งหมด

การดำเนินการเพื่อแจกจ่ายขนมให้กับผู้คนโซลูชัน Leetcode

โปรแกรม 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

ความซับซ้อนของเวลา

O (จำนวนคน):  ในการหาจำนวนการเติมเต็มความสำเร็จเรากำลังใช้ while loop ซึ่งจะเรียกใช้ log (10 ^ 6) ครั้งในกรณีที่แย่ที่สุดซึ่งอยู่ที่ประมาณ 32 ครั้งจากนั้นเราได้ทำการวนซ้ำแบบเชิงเส้นจำนวนครั้ง ดังนั้นเวลาที่สมบูรณ์คือ O (num_people + 32) หรือ O (num_people)

หมายเหตุ: อัลกอริทึมนี้จะดีที่สุดเมื่อจำนวนลูกอมมากกว่าจำนวนคน เนื่องจากอัลกอริทึมนี้ไม่ได้ขึ้นอยู่กับจำนวนลูกอม

ความซับซ้อนของอวกาศ 

O (จำนวนคน): ใช้อาร์เรย์ของขนาด num_people ดังนั้นความซับซ้อนของพื้นที่จึงเป็น O (num_people)