Информация об изменениях

Сообщение Leetcode - 3Sum. Не пойму, чего хотят от 05.05.2022 16:02

Изменено 05.05.2022 16:02 Marty

Старый текст
Новый текст
Разница

Leetcode - 3Sum. Не пойму, чего хотят

Здравствуйте!

Моё решение

class Solution {
public:
    
    // Constraints:
    // 0 <= nums.length <= 3000


    struct Index3
    {
        size_t  idx[3];

        static void minmax( size_t &i1, size_t &i2 )
        {
            size_t tmp = max(i1,i2);
            i1 = min(i1,i2);
            i2 = tmp;
        }

        static Index3 makeOrdered( size_t i1, size_t i2, size_t i3 )
        {
            // Если закоментить, то вариантов появляется гораздо больше
            minmax(i2,i3);
            minmax(i1,i2); // минимум провалился в i1
            minmax(i2,i3); // максимум всплыл в i3

            Index3 res;
            res.idx[0] = i1;
            res.idx[1] = i2;
            res.idx[2] = i3;

            return res;
        }

        bool operator==(const Index3& rhs) const
        {
            return idx[0] == rhs.idx[0] && idx[1] == rhs.idx[1] && idx[2] == rhs.idx[2];
        }


    };

    struct Index3Hash
    {
        std::size_t operator()(const Index3 &i) const noexcept
        {
            size_t h0 = std::hash<size_t>{}(i.idx[0]);
            size_t h1 = std::hash<size_t>{}(i.idx[1]);
            size_t h2 = std::hash<size_t>{}(i.idx[2]);

            return h0 ^ (h1 << 1) ^ (h2 << 2); // or use boost::hash_combine
        }
    };

    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, const unordered_set<size_t> &used)
    {
        for(auto v:s)
        {
            if (used.find(v)==used.end())
            {
                foundIdx = v;
                return true;
            }
        }
        
        return false;
    }
    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>());
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1 } );
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1, size_t i2 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1, i2 } );
    }
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        unordered_map<int, unordered_set<size_t> > indices;
        
        for(size_t i=0; i!=nums.size(); ++i)
        {
            indices[nums[i]].insert(i);
        }
        
        vector< vector<int> > res;

        unordered_set< Index3, Index3Hash > usedTriplets;

        for(size_t idxFirst=0; idxFirst!=nums.size(); ++idxFirst )
        {
            for(size_t idxSecond=0; idxSecond!=nums.size(); ++idxSecond )
            {
                if (idxFirst==idxSecond)
                    continue;

                int sum2 = nums[idxFirst] + nums[idxSecond];
                
                // sum2 + _3 = 0
                // _3 = 0 - sum2
                int thirdCandidate = 0 - sum2;

                unordered_map<int, unordered_set<size_t> >::iterator itThird = indices.find(thirdCandidate);
                if (itThird==indices.end())
                {
                    continue; // продолжаем перебирать
                }
                
                size_t idxThird = 0;
                if (!findUnusedIdx( itThird->second, idxThird, idxFirst, idxSecond))
                {    
                    continue; // продолжаем перебирать
                }

                auto idxTriplet = Index3::makeOrdered(idxFirst, idxSecond, idxThird);
                if (usedTriplets.find(idxTriplet)!=usedTriplets.end())
                    continue;

                usedTriplets.insert(idxTriplet);

                res.emplace_back(vector<int>{nums[idxFirst], nums[idxSecond], nums[idxThird]});
            
            }
        
        }

        
        return res;
    }
};

Выдаёт:

Your input                   
[-1,0,1,2,-1,-4]             
Output                       
[[-1,0,1],[-1,2,-1],[0,1,-1]]
Expected                     
[[-1,-1,2],[-1,0,1]]

Окай, у меня было другое решение, которое в данном случае выдавало тоже самое. Но ломалось на этом:

[-1,0,1,2,-1,-4,-2,-3,3,0,4]                                                         
Output                                                                               
[[4,-4,0],[3,-4,1],[-2,3,-1],[1,-3,2],[-3,4,-1],[0,3,-3],[2,-2,0],[-1,1,0]]          
Expected                                                                             
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

Что я не так понял?

ЗЫ Я индексы упорядочиваю в обоих своих варантах, если не упорядочивать, то в первом кейсе вариантов становится еще больше, во втором тоже больше, но не на один, а на много

Leetcode - 3Sum. Не пойму, чего хотят

Здравствуйте!

https://leetcode.com/problems/3sum/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Моё решение

class Solution {
public:
    
    // Constraints:
    // 0 <= nums.length <= 3000


    struct Index3
    {
        size_t  idx[3];

        static void minmax( size_t &i1, size_t &i2 )
        {
            size_t tmp = max(i1,i2);
            i1 = min(i1,i2);
            i2 = tmp;
        }

        static Index3 makeOrdered( size_t i1, size_t i2, size_t i3 )
        {
            // Если закоментить, то вариантов появляется гораздо больше
            minmax(i2,i3);
            minmax(i1,i2); // минимум провалился в i1
            minmax(i2,i3); // максимум всплыл в i3

            Index3 res;
            res.idx[0] = i1;
            res.idx[1] = i2;
            res.idx[2] = i3;

            return res;
        }

        bool operator==(const Index3& rhs) const
        {
            return idx[0] == rhs.idx[0] && idx[1] == rhs.idx[1] && idx[2] == rhs.idx[2];
        }


    };

    struct Index3Hash
    {
        std::size_t operator()(const Index3 &i) const noexcept
        {
            size_t h0 = std::hash<size_t>{}(i.idx[0]);
            size_t h1 = std::hash<size_t>{}(i.idx[1]);
            size_t h2 = std::hash<size_t>{}(i.idx[2]);

            return h0 ^ (h1 << 1) ^ (h2 << 2); // or use boost::hash_combine
        }
    };

    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, const unordered_set<size_t> &used)
    {
        for(auto v:s)
        {
            if (used.find(v)==used.end())
            {
                foundIdx = v;
                return true;
            }
        }
        
        return false;
    }
    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>());
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1 } );
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1, size_t i2 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1, i2 } );
    }
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        unordered_map<int, unordered_set<size_t> > indices;
        
        for(size_t i=0; i!=nums.size(); ++i)
        {
            indices[nums[i]].insert(i);
        }
        
        vector< vector<int> > res;

        unordered_set< Index3, Index3Hash > usedTriplets;

        for(size_t idxFirst=0; idxFirst!=nums.size(); ++idxFirst )
        {
            for(size_t idxSecond=0; idxSecond!=nums.size(); ++idxSecond )
            {
                if (idxFirst==idxSecond)
                    continue;

                int sum2 = nums[idxFirst] + nums[idxSecond];
                
                // sum2 + _3 = 0
                // _3 = 0 - sum2
                int thirdCandidate = 0 - sum2;

                unordered_map<int, unordered_set<size_t> >::iterator itThird = indices.find(thirdCandidate);
                if (itThird==indices.end())
                {
                    continue; // продолжаем перебирать
                }
                
                size_t idxThird = 0;
                if (!findUnusedIdx( itThird->second, idxThird, idxFirst, idxSecond))
                {    
                    continue; // продолжаем перебирать
                }

                auto idxTriplet = Index3::makeOrdered(idxFirst, idxSecond, idxThird);
                if (usedTriplets.find(idxTriplet)!=usedTriplets.end())
                    continue;

                usedTriplets.insert(idxTriplet);

                res.emplace_back(vector<int>{nums[idxFirst], nums[idxSecond], nums[idxThird]});
            
            }
        
        }

        
        return res;
    }
};

Выдаёт:

Your input                   
[-1,0,1,2,-1,-4]             
Output                       
[[-1,0,1],[-1,2,-1],[0,1,-1]]
Expected                     
[[-1,-1,2],[-1,0,1]]

Окай, у меня было другое решение, которое в данном случае выдавало тоже самое. Но ломалось на этом:

[-1,0,1,2,-1,-4,-2,-3,3,0,4]                                                         
Output                                                                               
[[4,-4,0],[3,-4,1],[-2,3,-1],[1,-3,2],[-3,4,-1],[0,3,-3],[2,-2,0],[-1,1,0]]          
Expected                                                                             
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]