Share My Non-Recursive C++ Solution with Simple Comments


  • 0
    J

    '''

    bool canCross(vector<int>& stones) {
        //f[i] is a set and its elements record how many units we can go at ith stone.
        unordered_map<int, unordered_set<int>> f;
        
        //record max units we can go at ith stone.
        vector<int> mu(stones.size(), 0);
        
        f[0].insert(0);
        int k = 0;
        for (int i = 1; i < stones.size(); i++)
        {
            //at kth stone, we cannot reach ith stone if the max units we can go is not enough.
            while (mu[k] + 1 < stones[i] - stones[k])
            {
                k++;
            }
            
            for (int j = k; j < i; j++)
            {
                int t = stones[i] - stones[j];
                if (f[j].count(t - 1) || f[j].count(t) || f[j].count(t + 1))
                {
                    f[i].insert(t);
                    mu[i] = max(mu[i], t);
                    break;
                }
            }
        }
        
        return f[stones.size() - 1].size();
    }
    

    '''


Log in to reply
 

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