Some questions

946. Validate Stack Sequences

Jimmy (xiaoke) Shen

·

Follow

3 min read

·

Jul 8, 2020

--

Listen

Share

// 1. time used: 9 minutes 44 second
// time complexity: O(m+n)
// space complexity : O(m+n)class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        vector<int> ret;
        const int m = pushed.size(), n = popped.size();
        int i=0, j=0;
        while(1)
        {
            if (ret.size()>0 && j<n && ret.back()==popped[j])
            {
                ret.pop_back();
                j++;
            }
            else if(i<m)
            {
                ret.push_back(pushed[i]);
                i++;
            }
            else break;
        }
        return ret.size()==0;
    }
};

809. Expressive Words

// It took me more than a hour 
// time complexity : O(n*m)
//     space complexity: O(max(n, m))class Solution {
public:
      vector<pair<int, int>> count(string S){
          vector<pair<int, int>> s;
           for (auto c:S)
           {
               if(s.empty()||(c-'a')!=s.back().first)
               {
                   s.emplace_back(c-'a', 1);
               }
               else
               {
                   s.back().second += 1;
               }
           }
          return s;
      }
    bool good(vector<pair<int, int>>s, vector<pair<int, int>>t){
        if(s.size()!=t.size()) return false;
        for(int i=0; i<s.size();++i)
        {
            if (s[i].first==t[i].first && 
                s[i].second==t[i].second || 
                 (s[i].second>t[i].second && s[i].second>=3) )continue;
            else return false;
        }
        return true;
    }
    
     
    int expressiveWords(string S, vector<string>& words) {
        vector<pair<int, int>> s, w;
        s = count(S);
       
        int ret = 0;
        for (auto word: words)
        {
            if (good(s, count(word))) 
            {
                ret++;
            }
        }
        return ret;
    }
};

1110. Delete Nodes And Return Forest

// I used 24 minutes to finish this problem./**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<TreeNode*> ret;
public:
    void helper(TreeNode* parent, TreeNode* node, unordered_set<int>& to_delete_s,  int level, bool left){
        if (!node) return;
        // a) not delete this node:
        //if this is the root node, put it into the ret
        // if this is not the root node, keep on exploring.
        if (to_delete_s.find(node->val)==to_delete_s.end())
        {
            if(level==0)ret.push_back(node);
            helper(node, node->left, to_delete_s,  level+1, true);
            helper(node, node->right, to_delete_s, level+1, false);  
        }
        // b) delete this node.
        // if this node has a parent node, delete this node from the parent node.
        // keep on exploring.
        else
        {  
            if (parent)
            {
                if (left)parent->left = nullptr;
                else parent->right = nullptr;
            }
            helper(node, node->left, to_delete_s, 0, true);
            helper(node, node->right, to_delete_s, 0, false);
        }   
    }
    
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> to_delete_s(to_delete.begin(), to_delete.end());
        helper(nullptr, root, to_delete_s, 0, true);
        return ret;
    }
};

846. Hand of Straights

// took me 20 minutes
class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        const int n = hand.size();
        if (n%W != 0) return false;
        map<int, int> cnt;
        for (auto x: hand)cnt[x] +=1;
        int card = -1;
        for (int i=0; i < n/W; ++i)
        {
            for (int j = 0; j<W; ++j)
            {
                if(j==0)
                {
                    card = (*cnt.begin()).first;
                    cnt[card]-=1;
                    if(cnt[card]==0)
                    {
                        cnt.erase(card);
                    }
                    card ++;
                }
                else
                {
                    if (cnt.count(card))
                    {
                        cnt[card] -= 1;
                        if (cnt[card]==0) cnt.erase(card);
                        card++;     
                    }
                    else return false;
                }
                
            }
        }
        return true;
        
    }
};

1. Two Sum

// 5 minutes
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> ret;
        for (int i=0;i<nums.size();++i)
        {
            if (m.find(target-nums[i])!=m.end())
            {
                return {i, m[target-nums[i]]};
            }
            m[nums[i]] = i;
        } 
        return ret;
    }
};

359. Logger Rate Limiter

class Logger {
    unordered_map<string, int> timestamps;
public:
    /** Initialize your data structure here. */
    Logger() {
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        bool ret = (!timestamps.count(message) || timestamp - timestamps[message] >= 10);
        if (ret) timestamps[message] =  timestamp;
        return ret;
        
    }
};/**
 * Your Logger object will be instantiated and called as such:
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
 */