Random Pick with Weight

 

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

• For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

 

Example 1:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

 

Constraints:

• 1 <= w.length <= 104
• 1 <= w[i] <= 105
• pickIndex will be called at most 104 times.

 

class Solution {
private:
    vector<int> sum;
public:
    Solution(vector<int>& w) {
        sum = w;
        for (int i = 1; i < w.size(); i++) {
            sum[i] = sum[i - 1] + w[i];
        }
    }
    
    int pickIndex() {
        int size = sum.size();
        int random = rand() % sum.back() + 1;  // range: 1 to sum[last]
        
        int st = 0, end = size - 1;
        while (st <= end) {
            int mid = st + (end - st)/2;
            if (sum[mid] == random) {
                return mid;
            } else if (sum[mid] < random) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return st;
    }
};

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

1592. Rearrange Spaces Between Words

 

You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

 

Example 1:

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Example 2:

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

 

Constraints:

• 1 <= text.length <= 100
• text consists of lowercase English letters and ' '.
• text contains at least one word.

 

 

class Solution {
public:
    string reorderSpaces(string text) {
        queue<string> q;
        int count = 0;
        string word;
        for (int i = 0; i < text.size(); i++) {
            if (text[i] == ' ') {
                count++;
                if (!word.empty()) {
                    q.push(word);
                }
                word = "";
            } else {
                word += text[i];
            }
        }
        if (!word.empty()) {
            q.push(word);
        }
       
        int word_size = q.size();
        string ans;
        if (word_size == 1) {
            ans = q.front(); q.pop();
            for (int i = 0; i < count; i++) {
                ans += " ";
            }
            return ans;
        }
       
        int space_count = count / (word_size - 1);
        int remaining_space = count % (word_size - 1);
       
        while (!q.empty()) {
            if (ans.empty()) {
                ans = q.front(); q.pop();
            } else {
                for (int i = 0; i < space_count; i++) {
                    ans += " ";
                }
                ans += q.front(); q.pop();
            }
        }
        for (int i = 0; i < remaining_space; i++) {
            ans += " ";
        }
        return ans;
    }
};

252. Meeting Rooms

 

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

 

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if (intervals.size() < 2) {
            return true;
        }
        sort(intervals.begin(), intervals.end(), [](auto &first, auto &second) {
            return first[0] < second[0];
        });
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

 

245. Shortest Word Distance III

 

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

 

Constraints:

• 1 <= wordsDict.length <= 105
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.

 

 

class Solution {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        if (wordsDict.size() == 0) {
            return 0;
        }
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < wordsDict.size(); i++) {
            mp[wordsDict[i]].push_back(i);
        }
        int ans = INT_MAX;
        if (word1 != word2) {
            int i = 0, j = 0;
            auto dist_vec1 = mp[word1];
            auto dist_vec2 = mp[word2];
            while (i < dist_vec1.size() && j < dist_vec2.size()) {
                ans = min(ans, abs(dist_vec1[i] - dist_vec2[j]));
                if (dist_vec1[i] <= dist_vec2[j]) {
                    i++;
                } else {
                    j++;
                }
            }
        } else {
            auto vec = mp[word1];
            if (vec.size() == 1) {
                return 0;
            }
            int i = 1;
            while (i < vec.size()) {
                ans = min(ans, vec[i] - vec[i - 1]);
                i++;
            }
        }
        return ans;
    }
};

243. Shortest Word Distance

 

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

 

Constraints:

• 2 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2
•  
•  

 

 

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        if (wordsDict.size() == 0) {
            return 0;
        }
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < wordsDict.size(); i++) {
            mp[wordsDict[i]].push_back(i);
        }
       
        int ans = INT_MAX, i = 0, j = 0;
        auto dist_vec1 = mp[word1];
        auto dist_vec2 = mp[word2];
        while (i < dist_vec1.size() && j < dist_vec2.size()) {
            ans = min(ans, abs(dist_vec1[i] - dist_vec2[j]));
            if (dist_vec1[i] <= dist_vec2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};