528. Random Pick with Weight

https://leetcode.com/problems/random-pick-with-weight?envType=problem-list-v2&envId=rabvlt31

這題我完全是土法煉鋼，因此跑出來的成績不好不意外哈哈哈。

class Solution {
public:

    int sum = 0;
    int w_len = 0;
    vector<int> w_copy;

    Solution(vector<int>& w) {
        getSum(w);
        w_len = w.size();
    }

    void getSum(vector<int>& w) {
        for (auto w_ : w) {
            sum += w_;
            w_copy.push_back(w_);
        }
    }
    
    int getIndex(int target) {
        int temp = 0;
        int i;
        for (i = 0; i < w_copy.size(); i++) {
            temp += w_copy[i];
            if(temp > target) {
                break;
            }
        }
        return i;
    }

    int pickIndex() {
        int x = rand() % sum;
        return getIndex(x);
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

就是一直加到機率符合，沒有什麼技術難度。

Best Solution

翻了一下討論區，竟然有人的想法跟我是一樣的！！還以為我想得很爛的說哈哈。有時間再來討論。

TODO