Leet Code Weekly Contest 272

1. Find First Palindromic String in the Array

Palindromic string detection, naive :)

c++

class Solution
{
public:
    
    bool valid(string &s)
    {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--)
        {
            if (s[i] != s[j])
            {
                return false;
            }
        }
        
        return true;
    }
    
    string firstPalindrome(vector<string>& words)
    {
        for (auto &s : words)
        {
            if (valid(s))
            {
                return s;
            }
        }
        
        return "";
    }
};

2. Adding Spaces to a String

Use a hash-set for the space positions.
The overall time complexity is $O(n)$ .

c++

class Solution
{
public:

    string addSpaces(string s, vector<int>& spaces)
    {
        unordered_set<int> a(spaces.begin(), spaces.end());
        
        string ret = "";
        
        for (int i = 0; i < s.length(); i++)
        {
            if (a.find(i) != a.end())
            {
                ret.push_back(' ');
            }
            
            ret.push_back(s[i]);
        }
        
        return ret;
    }
};

3. Number of Smooth Descent Periods of a Stock

Given a smooth descent period (where the number of days is $n$ ), there are $\frac{n (n - 1)}{2}$ sub-periods in total.
We can perform a linear scan to find all smooth decent periods (which cannot expand).
The overall time complexity is $O(n)$ .

c++

typedef long long ll;

class Solution
{
public:
    
    long long getDescentPeriods(vector<int>& prices)
    {
        
        ll ret = 0;
        
        int n = prices.size();
        
        for (int i = 0; i < n; )
        {
            int j = i;
            
            while (j + 1 < n && prices[j + 1] == prices[j] - 1)
            {
                j++;
            }
            
            ll l = (j - i + 1);
            
            ret += l * (l + 1) / 2;
            
            i = j + 1;
        }
        
        return ret;
    }
};

4. Minimum Operations to Make the Array K-Increasing

Split the original array into $k$ indenpent arrays (by $i \mod k$ ).
For each array, it is obviously a standard longest non-decreasing sub-sequence problem (DP + Fenwick tree).
The overall time complexity is $O(n \log(n))$

c++

class Solution
{
public:
    
    void re_order(vector<int> &arr)
    {
        vector<int> vals = vector<int>(arr.begin(), arr.end());
        
        sort(vals.begin(), vals.end());
        
        unordered_map<int, int> m;
        
        for (int i = 0; i < vals.size(); i++)
        {
            if (m.find(vals[i]) == m.end())
            {
                m[vals[i]] = i + 1;
            }
        }
        
        for (int i = 0; i < arr.size(); i++)
        {
            arr[i] = m[arr[i]];
        }
    }
    
    int lowbit(int x)
    {
        return x & (-x);
    }
    
    int f[100001];
    
    int query(int x)
    {
        int ret = 0;
        
        while (x > 0)
        {
            ret = max(ret, f[x]);
            x = x - lowbit(x);
        }
        
        return ret;
    }
    
    void update(int n, int x, int c)
    {
        while (x <= n)
        {
            f[x] = max(f[x], c);
            x = x + lowbit(x);
        }
    }
    
    int solve(vector<int> &arr)
    {
        re_order(arr);

        int n = arr.size(), ret = 0;
        
        for (int i = 0; i <= n; i++)
        {
            f[i] = 0;
        }
        
        for (int i = 0; i < n; i++)
        {
            int a = arr[i];
            int c = query(a) + 1;
            ret = max(ret, c);
            update(n, a, c);
        }
        
        return ret;
    }
    
    int kIncreasing(vector<int>& arr, int k)
    {
        int n = arr.size();
        int ret = 0;
        
        for (int i = 0; i < k; i++)
        {
            vector<int> s;
            
            for (int j = i; j < n; j += k)
            {
                s.push_back(arr[j]);
            }
            
            ret += s.size() - solve(s);
        }
        
        return ret;
    }
};

Leet Code Weekly Contest 272

1. Find First Palindromic String in the Array

2. Adding Spaces to a String

3. Number of Smooth Descent Periods of a Stock

4. Minimum Operations to Make the Array K-Increasing

COMMAND INTERFACE

:help aguang.xyz