LeetCode Weekly Contest 151

a.cpp

class Solution 
{
public:
    vector<string> invalidTransactions(vector<string>& t) 
    {
        set<string> res;
        map<string, vector<vector<string> > > m;
        int n = t.size();
        for(int i = 0; i < n; i++)
        {
            string d1 = t[i];
            istringstream iss(d1);
            vector<string> parse1;

            string token;

            while(getline(iss, token, ','))
            {
                parse1.push_back(token);
            }
            
            string name1 = parse1[0];
            int time1 = stoi(parse1[1]);
            int money1 = stoi(parse1[2]);
            string city1 = parse1[3];
            vector<string>data;
            
            data = {parse1[1], parse1[2], parse1[3]};
            int sz = m[name1].size();
            for(int j = 0; j < sz; j++)
            {
                if(city1 != m[name1][j][2] && abs(time1 - stoi(m[name1][j][0])) <= 60) // same name with another city 
                {
                    res.insert(name1 + "," + parse1[1] + "," + parse1[2] + "," + parse1[3]);                
                    res.insert(name1 + "," + m[name1][j][0] + "," + m[name1][j][1] + "," + m[name1][j][2]);               
                }
                    
            }
            if(money1 > 1000)
            {
                res.insert(d1);
            }
            m[name1].push_back(data);
        }
        vector<string> final_res(res.begin(), res.end());
        return final_res;
    }
};

b.cpp

class Solution 
{
public:
    vector<int> numSmallerByFrequency(vector<string>& q, vector<string>& w) 
    {
        vector<int> res;
        int n = q.size();
        int m = w.size();
        vector<int> qfq(n, 0);
        vector<int> wfq(m, 0);
        
        int idx = 0;
        for(auto x : q)
        {
            qfq[idx++] = f(x);
        }
        
        idx = 0;
        for(auto x : w)
        {
            wfq[idx++] = f(x);
        }
        
        sort(wfq.begin(), wfq.end());
        for(auto x : qfq)
        {
            res.push_back(wfq.end() - upper_bound(wfq.begin(), wfq.end(), x));
        }
        return res;
    }
    int f(string s)
    {
        int fq[26] = {0};
        for(auto x : s)
        {
            fq[x - 'a']++;
        }
        
        for(int i = 0; i < 26; i++)
        {
            if(fq[i])
            {
                return fq[i];
            }
        }
        return 0;
    }
};

c.cpp

class Solution 
{
public:
    ListNode* removeZeroSumSublists(ListNode* head) 
    {
        ListNode* cur = head;
        
        // collect nodes
        vector<int> v; 
        while(cur != NULL)
        {
            v.push_back(cur -> val);
            cur = cur -> next;
        }
        
        // "turn off" the 0 interval
        int sum = 0;
        for(int i = 0; i < v.size(); i++)
        {
            sum = 0;
            sum += v[i];
            int l = i, r = 0;
            if(sum == 0) // deal with case like [2,0]
            {
                v[i] = -9999;
            }
            for(int j = i + 1; j < v.size(); j++)
            {
                sum += v[j];
                if(sum == 0)
                {
                    i = j;
                    r = j;
                    break;
                }
            }
            if(r)
            {
                fill(v.begin() + l, v.begin() + r + 1, -9999); // turn off the interval that sums up to zero
            }
            
        }
        
        // remove the elements that have been turned off
        while(1)
        {
            auto it = find(v.begin(), v.end(), -9999);
            if(it == v.end())
            {
                break;
            }
            v.erase(it);
        }
        
        // recreate LL
        int n = v.size();
        if(n == 0) // if nothing sum != 0
        {
            return NULL;
        }
        
        head -> val = v[0];
        head -> next = NULL;
        cur = head;
        
        // iterate through the "sanitized" vector and connect the nodes
        for(int i = 1; i < n; i++)
        {
            ListNode* new_node = new ListNode(v[i]);
            cur -> next = new_node;
            cur = cur -> next;
        }
        
        return head;
    }
};

d.cpp

class DinnerPlates 
{
    public:
    unordered_map<int, vector<int> > um; // mapping stack no. to that stack
    
    int element_cnt;
    int max_cap;
    int left, right;
    
    DinnerPlates(int capacity) 
    {
        element_cnt = 0;
        max_cap = capacity;
        left = 0;
        right = 0;
    }

    void push(int val) 
    {
        element_cnt++;
        if(um[left].size() >= max_cap)
        {
            while(um[left].size() >= max_cap)
            {
                left++;
            }
        }
        if(um[right].size() >= max_cap) // increment right by one if rightmost is full
        {
            right++;
        }
        um[left].push_back(val); 
    }

    int pop() 
    {
        if(element_cnt == 0)
        {
            return -1;
        }
        int res = 0;
        res = um[right].back();
        um[right].pop_back();
        if(um[right].size() == 0)
        {
            right--;
        }
        element_cnt--;
        return res;
    }

    int popAtStack(int index) 
    {
        if(element_cnt == 0)
        {
            return -1;
        }
        int res = 0;
        if(um[index].size())
        {
            res = um[index].back();
            um[index].pop_back();
            element_cnt--;
            left = min(index, left);
            return res;
        }
        else
        {
            return -1;
        }
    }
};