2024 February 3 Problems

[daryl...@gmail.com]

Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

2558 Take Gifts From the Richest Pile66.2%Easy

621Task Scheduler58.1%Medium

2959Number of Possible Sets of Closing Branches 49.5%Hard

Please download and import the following iCalendar (.ics) files to your calendar system.

Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

[Flocela Maldonado]

2558 Take Gifts From the Richest Pile66.2%Easy

Time: O(n + k) Memory: O(n)
class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> pq{};

        for (int gift : gifts)
        {
            pq.push(gift);
        }

        for (int ii=0; ii<k; ++ii)
        {
            int top = pq.top();
            pq.pop();
            double leaveBehind = sqrt(top);
            leaveBehind = floor(leaveBehind);
            pq.push(static_cast<int>(leaveBehind));
        }

        long long sum = 0;
        while (!pq.empty())
        {
            sum += pq.top();
            pq.pop();
        }

        return sum;
    }
};

[Carlos Green]

/**

* @param {number[]} gifts

* @param {number} k

* @return {number}

Time O(n + k) & Space O(1)

Grab the largest value in the array

Find the index of the largest value in the array

Replace the largest value with the square root of it's value

Repeat k times

Return the sum of the array's final values

*/

var pickGifts = function(gifts, k) {

while(k) {

const max = Math.max(...gifts)

const maxIndex = gifts.indexOf(max)

gifts[maxIndex] = Math.floor(Math.sqrt(max))

k--

}

return gifts.reduce((a,c) => a += c, 0)

};

[Andriy T]

2558 Take Gifts From the Richest Pile66.2%Easy

Brute force:

Time O(N^2) Space O(1) (no additional space except input)

  

class Solution {

    public long pickGifts(int[] gifts, int k) {

        Arrays.sort(gifts);

        int i = k;

        while (i > 0) {

            int max = gifts[gifts.length - 1];

            if (max > 1) {

                int left_behind = (int) Math.floor(Math.sqrt(gifts[gifts.length - 1]));

                gifts[gifts.length - 1] = left_behind;

            }

            Arrays.sort(gifts);

            i--;

        }

        long res = 0;

        for (int j = 0; j < gifts.length; j++) {

            res+=gifts[j];

        }

        return res;

    }

}

Priority queue:

Time: O(N log N) Space (O(N))

class Solution {

    public long pickGifts(int[] gifts, int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

        long res = 0;

        for (int g = 0; g < gifts.length; g++) {

            pq.add(gifts[g]);

            res += gifts[g];

        }

        int i = k;

        while (i > 0) {

            int max = pq.poll();

            if (max > 1) {

                int left_behind = (int) Math.floor(Math.sqrt(max));

                pq.add(left_behind);

                res = (res - max) + left_behind;

            }

            else {

                pq.add(max);

            }

            i--;

        }

        return res;

    }

}

[Jagrut]

2558 Take Gifts From the Richest Pile

function pickGifts (gifts, k) {
    const minHeap = new MinHeap();
    for (const gift of gifts) {
        minHeap.push(new HeapItem(gift, -1 * gift));
    }
    for (let i = 1; i <= k; i++) {
        const leave = Math.floor(Math.sqrt(minHeap.pop().item));
        if (leave > 0) {
            minHeap.push(new HeapItem(leave, -1 * leave));
        }
    }
   
    let res = 0;
    while (minHeap.size() > 0) {
        const gift = minHeap.pop().item;
        res += gift;
    }
    return res;
};

621 Task Scheduler

function leastInterval (tasks, n) {
    const pq = new MinHeap();
    const next = [];
    const taskFreq = tasks.reduce((acc, e) => {
        acc.set(e, (acc.get(e) || 0) + 1);
        return acc;
    }, new Map());
    for (const [k, v] of taskFreq.entries()) {
        pq.push(new HeapItem([k, v], -v));
    }
    let time = 0;
    while (pq.size() > 0 || next.length > 0) {
        time++;
        if (pq.size() > 0) {
            const [task, occurrence] = pq.pop().item;
            if (occurrence > 1) {
                next.push([task, occurrence - 1, time + n]);
            }
        }
        let done = false;
        while (!done && next.length > 0) {
            if (next[0][2] <= time) {
                pq.push(new HeapItem([next[0][0], next[0][1]], -1 * next[0][1]));
                next.shift();
            }
            else {
                done = true;
            }
        }
    }
    return time;
};

On Saturday, February 3, 2024 at 9:36:23 AM UTC-8 daryl...@gmail.com wrote:

[Flocela Maldonado]

621Task Scheduler58.1%Medium
Time O(tlogt + t) if t is number of tasks.

Memory O(t)

class Solution {

public:

// Used for making a max priority queue, based on the second number in the pair.

struct myComp {

constexpr bool operator()(

pair<char, int> const& a,

pair<char, int> const& b)

const noexcept

{

return a.second < b.second;

}

};

int leastInterval(vector<char>& tasks, int n) {

// a map of the count per each task

unordered_map<char, int> countPerTask{};

for (char curTask : tasks)

{

if (countPerTask.find(curTask) == countPerTask.end())

{

countPerTask.insert({curTask, 0});

}

++countPerTask[curTask];

}

// vector of pairs of tasks and their counts. Used to make priority queue.

vector<pair<char, int>> tasksAndTheirCounts{};

for (const auto& taskAndCount : countPerTask)

{

tasksAndTheirCounts.push_back(taskAndCount);

}

// Will be putting tasks in this vector.

vector<char> ans{};

// max heap priority queue. pairs are in decreasing order based on the task's count.

priority_queue<pair<char,int>, vector<pair<char, int>>, myComp> pq(tasksAndTheirCounts.begin(), tasksAndTheirCounts.end());

// for each iteration run through n letters.

while(!pq.empty())

{

// keeps the seen tasks and count

unordered_map<char, int> seen{};

// Run through n letters. If number of letters runs out, then add 'i' to indicate idle.

// Or if number of letters runs out, it may be that we've run out of letters, then break!

for (int ii=0; ii<=n; ++ii)

{

if (pq.empty())

{

if (seen.size() == 0)

{

break;

}

else

{

ans.push_back('i');

}

}

else

{

// always use the letter that has the largest count first.

pair<char, int> topPair = pq.top();

pq.pop();

char topChar = topPair.first;

int topCount = topPair.second;

if (topCount > 1)

{

seen.insert({topChar, topCount-1});

}

ans.push_back(topChar);

}

}

// for next iteration add back the used letters in seen. Realize, they're being added back in with

// one lest count.

for (const auto& seenWithCount : seen)

{

pq.push(seenWithCount);

}

}

return ans.size();

}

};

[Flocela Maldonado]

Hi Everybody!

Please think about getting together the first Saturday of the month. It could be a before meeting (9:30am) coffee or it could be an after meeting lunch at noon.

-Flo

[Vivek H]

Sure. after meeting lunch sounds better i guess! 

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/e78e7295-a522-4a69-9d4b-9d8dafa559bfn%40googlegroups.com.

[Vivek H]

*************************************************************

621Task Scheduler58.1%Medium

*************************************************************

class Solution {

public:

    struct comp {

        bool operator()(pair<char, int>& P1, pair<char, int>& P2) {

            return P1.second < P2.second;

        }

    };

    void

    print(priority_queue<pair<char, int>, vector<pair<char, int>>, comp> PQ) {

        while (!PQ.empty()) {

            cout << "[" << PQ.top().first << "," << PQ.top().second << "]"

                 << endl;

            PQ.pop();

        }

    }

    int leastInterval(vector<char>& tasks, int n) {

        map<char, int> M;

        map<char, int> lastSeen;

        for (int i = 0; i < tasks.size(); i++) {

            M[tasks[i]]++;

            lastSeen[tasks[i]] = -(n + 1);

        }

        /*make a priority Q of task and freq */

        priority_queue<pair<char, int>, vector<pair<char, int>>, comp> PQ;

        for (auto& a : M) {

            PQ.push(make_pair(a.first, a.second));

        }

        // print(PQ);

        vector<char> result;

        int i = 0;

        while (!PQ.empty()) {

            bool flag = false;

            priority_queue<pair<char, int>, vector<pair<char, int>>, comp> tempPQ;

            while (!PQ.empty()) {

                if (i - lastSeen[PQ.top().first] > n) {

                    int freq = PQ.top().second;

                    int task = PQ.top().first;

                    lastSeen[task] = i;

                    result.push_back(task);

                    PQ.pop();

                    freq--;

                    if (freq > 0)

                        PQ.push(make_pair(task, freq));

                    i++;

                    flag = true;

                    break;

                } else {

                    tempPQ.push(PQ.top());

                    PQ.pop();

                }

            } // inner while ends

            if(flag){

                //we found a task and breaked;

                while(!PQ.empty()) {

                    tempPQ.push(PQ.top());

                    PQ.pop();

                }

            } else {

                // we did not find any suitable task, add idle task

                result.push_back('0');

                i++;

            }

            PQ = tempPQ;

        } //outer while

 

        //for (auto& a : result)

        //    cout << a;

        return result.size();

    }

};

--

whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/198ce6dc-db90-4117-b3f7-ba55759d0e82n%40googlegroups.com.