Leet Code Weekly Contest 273

1. A Number After a Double Reversal

Naive.

c++

class Solution
{
public:
    
    int rev(int x)
    {
        int ret = 0;
        
        while (x > 0)
        {
            int d = x % 10;
            ret = ret * 10 + d;
            x = x / 10;
        }
        
        return ret;
    }
    
    bool isSameAfterReversals(int num)
    {
        return rev(rev(num)) == num;
    }
};

2. Execution of All Suffix Instructions Staying in a Grid

Simulation.

c++

class Solution
{
public:
    
    pair<int, int> get_d(char c)
    {
        if (c == 'L')
        {
            return make_pair(-1, 0);
        }
        
        if (c == 'R')
        {
            return make_pair(+1, 0);
        }
        
        if (c == 'U')
        {
            return make_pair(0, -1);
        }
        
        if (c == 'D')
        {
            return make_pair(0, +1);
        }
        
        return make_pair(0, 0);
    }
    
    
    int solve(int n, int x, int y, string s)
    {
        for (int i = 0; i < s.length(); i++)
        {
            auto p = get_d(s[i]);
            
            int nx = x
            
            if (x < 0 || x >= n || y < 0 || y >= n)
            {
                return i;
            }
            
            
            x += p.first;
            y += p.second;
        }
        
        return s.length();
    }
    
    vector<int> executeInstructions(int n, vector<int>& startPos, string s)
    {
        vector<int> ret;
        
        for (int i = 0; i < s.length(); i++)
        {
            ret.push_back(solve(n, startPos[1], startPos[0], s.substr(i)));
        }
        
        return ret;
    }
};

3. Intervals Between Identical Elements

Take a hash map from values to idexes.
For each value, sort indexes and pre-compute preffix-sums.
Binary search.
Time complexity: $O(n \log(n))$ .

c++

typedef long long ll;

class Solution
{
public:
    
    vector<long long> getDistances(vector<int>& arr)
    {
        map<int, vector<int>> idxes;
        
        for (int i = 0; i < arr.size(); i++)
        {
            int x = arr[i];
            
            if (idxes.find(x) == idxes.end())
            {
                idxes[x] = vector<int>();
            }
            
            idxes[x].push_back(i);
        }
        
        for (auto &p : idxes)
        {
            sort(p.second.begin(), p.second.end());
        }
        
        map<int, vector<ll>> sums;
        
        for (auto &p : idxes)
        {
            int x = p.first;
            
            sums[x].push_back(0);
            
            for (auto &i : p.second)
            {
                sums[x].push_back(sums[x].back() + i);
            }
        }
        
        vector<ll> ret;
        
        for (int i = 0; i < arr.size(); i++)
        {
            int x = arr[i];
            
            ll n = upper_bound(idxes[x].begin(), idxes[x].end(), i) - idxes[x].begin();
            
            ll a = n * i - sums[x][n];
            ll b = (sums[x][idxes[x].size()] - sums[x][n]) - (idxes[x].size() - n) * i;
            
            ret.push_back(a + b);
        }
        
        
        return ret;
    }
};

4. Recover the Original Array

Basically we need to split the array of numbers into two non-increasing sequences $L$ and $H$ .
We know $H_i - L_i$ should always be $2k$ .
If we know $k$ already, we can perform a validation in $O(n\log(n))$ .
We have at most $n - 1$ choices of $k$ .
So overall time complexity is $O(n^2 \log(n))$ .

c++

class Solution {
public:
    
    int low_first(vector<int> &nums)
    {
        int ret = INT_MAX;
        
        for (auto &x : nums)
        {
            ret = min(ret, x);
        }
        
        return ret;
    }
    
    vector<int> possible_ks(int low_first, vector<int> &nums)
    {
        set<int> ret;
        
        for (auto &x : nums)
        {
            if (x > low_first && (x - low_first) % 2 == 0)
            {
                ret.insert((x - low_first) / 2);
            }
        }
        
        return vector<int>(ret.begin(), ret.end());
    }
    
    vector<int> solve(int k, vector<int> nums, bool &succ)
    {
        unordered_map<int, int> cnt;
        
        for (auto x : nums)
        {
            if (cnt.find(x) == cnt.end())
            {
                cnt[x] = 0;
            }
            
            cnt[x]++;
        }
        
        sort(nums.begin(), nums.end());
        
        vector<int> ret;
        
        succ = true;
        
        for (auto x : nums)
        {
            if (cnt[x] == 0)
            {
                continue;
            }

            ret.push_back(x + k);
            
            cnt[x]--;
            
            if (cnt.find(x + 2 * k) == cnt.end() || cnt[x + 2 * k] <= 0)
            {
                succ = false;
                return vector<int>();
            }
            
            cnt[x + 2 * k]--;
        }
        
        return ret;
    }
    
    vector<int> recoverArray(vector<int>& nums)
    {
        vector<int> ks = possible_ks(low_first(nums), nums);
        
        for (auto &k : ks)
        {
            bool succ;
            
            vector<int> ret = solve(k, nums, succ);
            
            if (succ)
            {
                return ret;
            }
        }
        
        return vector<int>();
    }
};

Leet Code Weekly Contest 273

1. A Number After a Double Reversal

2. Execution of All Suffix Instructions Staying in a Grid

3. Intervals Between Identical Elements

4. Recover the Original Array

COMMAND INTERFACE

:help aguang.xyz