Could someone explain how the approach to make a key based on needs[i] works and if in C++ any way to use a vector<int> as a hash key?


  • 0
    E

    The DP based solution to this Q in the Contest#40 was solved by some of the winners of the contest using the following approach to make key from the needs[i] vector.

    Rank-1: username kennethsnow solution code:

        int S = 0;
        for (int i = 0; i < n; i++) {
            S = S * 7 + need[i];
        }
    

    Rank-7 username: yabincui solution code:

    int needToKey(const vector<int>& needs) {
        int res = 0;
        for (auto need : needs) {
            res = res * 7 + need;
        }
        return res;
    }
    
    void keyToNeed(int key, vector<int>& needs) {
        for (int i = needs.size() - 1; i >= 0; --i) {
            needs[i] = key % 7;
            key /= 7;
        }
    }
    

    Both these approaches multiply the current index with base 7 as there max 6 value for needs[i]. This seems to be somehow flattening the 6-dim vector.

    1. But how does this work? Can one not reduce the size of this vector by using a dynamic base (that is derived from needs[i]) instead of a constant 7?

    For example, if needs[] = (0, 2, 1), which means 2 items, first item needs are 0, and second item needs are 2. According to the approach used, max index is going to be 7*(70+2)+1. So, the max index is going to be 15 and 16 elements in the vector. But we actually needed only (0+1)(2+1)*(1+1) = 6 elements as that covers all possible combination of needs.

    1. Is there a way to use vector<int> of needs[i] directly as a key in the std::unordered_map in C++?

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.