LeetCode practice: 3075. Maximize Happiness of Selected Children

這個 LeetCode 練習系列可能不會定期發布，但我會盡力在想起來去解題的時候更新。 XD..

我會試著寫下解題的想法或者無法成功解決的思考過程，我對解題這種事情不是很擅長，可能會有些問題，如果你有更好的方法，歡迎隨意留言讓我知道一下

加上用英文寫也是順便練習一下看英文 QQ(儘管都還是靠翻譯工具)，正好順便進行緩慢的學英文進度

The series of LeetCode practice may not be posted periodically, but I will try my best to update it whenever I remember. XD..

I will write down my thought process on how to solve it or if I was unable to solve it successfully.

I'm not very good at this kind of thing, but if you have better ways, please feel free to let me know.

Original problem link : 3075. Maximize Happiness of Selected Children

這個問題被列在 medium 難度，但我覺得他沒有那麼難解，但我還是只打贏 21%的人，所以我知道一定還有更好的方法，而我的解題邏輯也很簡單，就題目來看他有一個陣列代表著幸福值

let happiness = [1,1,2,3,4];

然後我們會從裡面取出 N 個指定在每個位置的小孩，而他所在的位置就是對應的幸福值，而當我們每取出一個後，剩餘的小孩幸福值就會減一，最終我們要試著獲得最大的幸福值數量

例如，我們先取出 4 這個值，剩下的就會變成 [0,0,1,2]，接著我們在拿出 2，那剩下的值就會是[0,0,0] .. 後續以此類推。

基於這個思路，我的第一步是將整個幸福值進行排序。然後，我將遍歷每個值，根據當前提取的數量來扣除幸福值。如果幸福值變得小於 0，則將其視為 0。

以下是範例程式碼： 

  var maximumHappinessSum = function(happiness, k){
    happiness.sort((a, b) =< b - a);
    let maximumSum = 0;
    for (let i = 0; i < k; i++) {
        let happinessV = happiness.shift();
        maximumSum += happinessV - i <= 0 ? happinessV - i : 0;
    }
    return maximumSum;
  };
  

我遇到的問題是，當數量太大時，會發生 TLE（超過時間限制）。

因此，我改變了另一種方法。我不再遍歷整個排序後的內容，而是先在排序後提取所需的數量，然後進行迴圈。這樣一來，迴圈的次數從 N 變為 K，相對來說會小得多。

最後，我改寫了這段程式碼：

var maximumHappinessSum = function (happiness, k) {
    happiness.sort((a, b) => b - a);
    let children = happiness.slice(0, k);
    let maximumSum = 0;
    children.forEach((v, i) => {
        maximumSum += v - i >= 0 ? v - i : 0;
    });
    return maximumSum;
}

恭喜，問題(暫時被)解決了！

------------------------------------------------------------------------

This problem level is medium, I think it's not so hard, but I can still only beat 21% user, so I know it still has many better ways.

My solve logic is very easy, problem show an array means happiness value defined like

let happiness = [1,1,2,3,4];

and we will extract N children locate at each index, and each time we extract one, all the numbers inside will be decreased by 1. In the end, we need to try to obtain the maximum total happiness.

For example, if we take 4 first, ramaining value are [0,0,1,2], and then we take out 2, then happiness set is [0,0,0] ... and so on

Based on that, my first step is to sort the entire happiness values. Then, I will iterate through each value, deducting happiness based on the current quantity extracted.
If the happiness value becomes less than 0, it will be considered as 0.

sample code

  var maximumHappinessSum = function(happiness, k){
    happiness.sort((a, b) =< b - a);
    let maximumSum = 0;
    for (let i = 0; i < k; i++) {
        let happinessV = happiness.shift();
        maximumSum += happinessV - i <= 0 ? happinessV - i : 0;
    }
    return maximumSum;
  };
  

The problem I encountered is that when the quantity is too large, it leads to TLE (time limit exceeded).

So I changed to another approach. Instead of iterating through the entire sorted content, I first extract the required quantity after sorting, and then proceed with the loop. This way, the number of iterations changes from N to K, which could be much smaller in comparison. finally I write the code.

var maximumHappinessSum = function (happiness, k) {
    happiness.sort((a, b) => b - a);
    let children = happiness.slice(0, k);
    let maximumSum = 0;
    children.forEach((v, i) => {
        maximumSum += v - i >= 0 ? v - i : 0;
    });
    return maximumSum;
}

Congratulations! problem solved!

------------------------------------------------------------------------

後記：

其實還有另一個解題思路沒有特別寫出來，但因為還是有排序這個操作所以我想差異不會太大，只是我暫時還不想去搜尋別人的解答，等累積到一定的量之後再來看別人怎麼寫的就好，畢竟如果使用的語言不同解法也不一定能用😬