Simple C++ Using Recursive Lambda to Generate Data


  • 0
    F

    Not a very fast one, but showing another idea.
    We don't need to store the data and then manipulate them, we can only store the current data retrieving functions and this function is good enough to tell us what the data is at any idx.
    Think it this way: int array[] = {1,2,3}; so array[1] == 2.
    If you have a function int array(int i){return i + 1;}, you can get the same result as using an array but you don't need to store any data.

    The tricky part is the current function "array" must be built upon its last version.
    The total run time is O(nlogN) (N "array" calls with each taking logN time) , space is O(logN) which is used by the recursion.

    class Solution {
        string result;
        void generate(int n, int k, int base, function<int(int)> get)
        {
            if (k == n)
            {
                result += to_string(get(base) + 1);
                return;
            }
            get = [n, k, get](int idx){ //fold the date and get each data alternately.
                int dk = 2*k;           //k is group size at this round
                int group_idx= idx%dk < k ? idx/dk : (n-1)/k - idx/dk; 
                int member_idx = idx%k;
                return get(group_idx * k + member_idx);
            };
            result.push_back('(');
            generate(n, k*2, base, get);
            result.push_back(',');
            generate(n, k*2, base + n/(2*k), get);
            result.push_back(')');
        }
    public:
        string findContestMatch(int n) {
            generate(n, 1, 0, [](int idx) {return idx;});
            return result;
        }
    };
    

Log in to reply
 

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