LIKE CODING

Wednesday, May 29, 2019

LeetCode [896] Monotonic Array

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:

Input: [1,2,2,3]
Output: true

Example 2:

Input: [6,5,4,4]
Output: true

Example 3:

Input: [1,3,2]
Output: false

Example 4:

Input: [1,2,4,5]
Output: true

Example 5:

Input: [1,1,1]
Output: true

Note:

1 <= A.length <= 50000
-100000 <= A[i] <= 100000

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int order = 0;//0 unknown; 1 increasing; 2 decreasing
        for(int i=1; i<A.size(); ++i)
        {
            if(A[i]>A[i-1]){
                if(order==0) order = 1;
                if(order==2) return false;
            }
            if(A[i]<A[i-1]){
                if(order==0) order = 2;
                if(order==1) return false;
            }
        }
        return true;
    }
};

LeetCode [632] Smallest Range

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.
For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

class Solution {
    typedef vector<int>::iterator IT;
    struct comp{
        bool operator()(pair<IT, IT> p1, pair<IT, IT> p2){
            return *p1.first > *p2.first;
        }
    };
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int l = INT_MAX, h = INT_MIN;
        priority_queue<pair<IT, IT>, vector<pair<IT, IT>>, comp> pq;
        for(auto &v:nums){
            l = min(l, v[0]); h = max(h, v[0]);
            pq.push(pair<IT, IT>(v.begin(), v.end()));
        }

        vector<int> ret{l, h};
        while(!pq.empty()){
            auto next = pq.top();
            pq.pop();
            if(++next.first==next.second) break;
            pq.push(next);
            l = *pq.top().first;
            h = max(h, *next.first);
            if(h-l<ret[1]-ret[0]) {ret[0] = l; ret[1] = h;}
        }
        return ret;
    }
};

Tuesday, May 28, 2019

LeetCode [536] Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5

Note:

There will only be '(', ')', '-' and '0' ~ '9' in the input string.
An empty tree is represented by "" instead of "()".

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int pos = 0;
public:
    TreeNode* str2tree(string s) {
        int n = s.size();
        if(n==pos) return NULL;
        
        //compose the number
        int start = pos;
        while(pos<n && (s[pos]=='-'||isdigit(s[pos]))){pos++;}
        string v = s.substr(start, pos-start);
        TreeNode* node = new TreeNode(stoi(v));
        
        //dfs
        if(pos<n && s[pos]=='('){ pos++; node->left = str2tree(s);}
        if(pos<n && s[pos]=='('){ pos++; node->right = str2tree(s);}
        if(pos<n && s[pos]==')') pos++;
        return node;
    }
};

Sunday, May 26, 2019

LeetCode [708] Insert into a Cyclic Sorted List

Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.

If the list is empty (i.e., given node is null), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.

The following example may help you understand the problem better:

In the figure above, there is a cyclic sorted list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list.

The new node should insert between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node *n = new Node(insertVal, NULL);
        n->next = n;
        if(!head) return n;
        Node *p = head, *p1 = p->next;
        while(p1!=head){
            if(p->val<=insertVal && insertVal<=p1->val) break;
            if(p->val > p1->val && (insertVal>=p->val || insertVal<=p1->val)) break;
            p = p1;
            p1 = p1->next;
        }
        
        n->next = p1;
        p->next = n;
        return head;
    }
};

LeetCode [958] Check Completeness of a Binary Tree

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int maxLevel = -1;
    bool foundLast = false;//true if found a NULL at the last level
public:
    bool isCompleteTree(TreeNode* root) {
        if(!root) return true;
        TreeNode* p = root;
        while(p){
            maxLevel++;
            p = p->left;
        }
        return valid(root, 0);
    }
    
    bool valid(TreeNode* node, int level){
        if(node==NULL){
            if(level<maxLevel) return false;
            if(level==maxLevel) foundLast = true;
            return true;
        }else{
            if(level>maxLevel) return false;
            if(level==maxLevel && foundLast) return false;
            return valid(node->left, level+1)&&valid(node->right, level+1);
        }
    }
};

Saturday, May 25, 2019

LeetCode [567] Permutation in String

567. Permutation in String

Medium

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Constraints:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int mp1[256] = {0}, mp2[256] = {0};
        int n1 = s1.size(), n2 = s2.size(), cnt = 0, i = 0, j = 0;
        for(auto c:s1) mp1[c]++;
        
        while(j<n2){
            while(j-i+1>n1){
                if(--mp2[s2[i]]<mp1[s2[i]]) cnt--;
                i++;
            }
            if(++mp2[s2[j]]<=mp1[s2[j]]) cnt++;
            if(cnt==n1) return true;
            j++;
        }
        
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sz1 = s1.size(), sz2 = s2.size();
        if(sz1>sz2) return false;
        vector<int> count(26), zeros(26, 0);
        
        for(int i=0; i<sz1; ++i)
        {
            count[s1[i]-'a']--;
            count[s2[i]-'a']++;
        }
        if(count == zeros) return true;

        for(int i=sz1; i<sz2; ++i){
            count[s2[i-sz1]-'a']--;
            count[s2[i]-'a']++;
            if(count == zeros) return true;
        }      

        return false;
    }
};

//Java
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        int[] cnt1 = new int[256], cnt2 = new int[256];
        for(char c:s1.toCharArray()){
            cnt1[c]++;
        }

        int i = 0, j = 0, len = 0;
        while(j<n2){
            while(j-i+1>n1){
                char c = s2.charAt(i++);
                if(cnt2[c]<=cnt1[c]){
                    len--;
                }
                cnt2[c]--;
            }
            char c = s2.charAt(j++);
            ++cnt2[c];
            if(cnt2[c]<=cnt1[c]){
                len++;
            }
            if(len==n1){
                return true;
            } 
        }
        return false;
    }
}

Friday, May 24, 2019

LeetCode [636] Exclusive Time of Functions

On a single threaded CPU, we execute some functions. Each function has a unique id between 0 and N-1.

We store logs in timestamp order that describe when a function is entered or exited.

Each log is a string with this format: "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means the function with id 0 started at the beginning of timestamp 3. "1:end:2" means the function with id 1 ended at the end of timestamp 2.

A function's exclusive time is the number of units of time spent in this function. Note that this does not include any recursive calls to child functions.

Return the exclusive time of each function, sorted by their function id.

Example 1:

Input:
n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3, 4]
Explanation:
Function 0 starts at the beginning of time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 1 starts at the beginning of time 2, executes 4 units of time and ends at time 5.
Function 0 is running again at the beginning of time 6, and also ends at the end of time 6, thus executing for 1 unit of time. 
So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.

Note:

1 <= n <= 100
Two functions won't start or end at the same time.
Functions will always log when they exit.

class Solution {
public:
    vector<string> splitStr(string s)
    {
        vector<string> ret;
        stringstream ss(s);
        string tmp;
        while(getline(ss, tmp, ':')) ret.push_back(tmp);
        return ret;
    }
    
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> ret(n, 0);
        stack<vector<int>> stk;//id, start time
        
        for(auto l:logs)
        {
            vector<string> r = splitStr(l);
            if(r[1]=="start"){
                stk.push(vector<int>{stoi(r[0]), stoi(r[2])});
            }else{//end
                int id = stoi(r[0]);
                int len = stoi(r[2])-stk.top()[1]+1;
                ret[id] += len;

                stk.pop();
                if(!stk.empty()){
                    ret[stk.top()[0]] -= len;
                }
            }
        }
        return ret;
    }
};

class Solution {
    class Log{
        int id;
        int timeStamp;
        String state;
        Log(int i, int t, String s){
            id = i;
            timeStamp = t;
            state = s;
        }
    }

    Log parse(String log){
        int i1 = log.indexOf(':');
        int i2 = log.indexOf(':', i1+1);
        int id = Integer.parseInt(log.substring(0, i1));
        int ts = Integer.parseInt(log.substring(i2+1));
        String state = log.substring(i1+1, i2);
        return new Log(id, ts, state);
    }

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res = new int[n];
        Stack<Log> stk = new Stack<>();
        for(String log : logs){
            Log newLog = parse(log);
            if(newLog.state.equals("start")){
                stk.push(newLog);
            }else{
                int dur = newLog.timeStamp - stk.pop().timeStamp + 1;
                res[newLog.id] += dur;
                if(!stk.isEmpty()){
                    res[stk.peek().id] -= dur;
                }
            }
        }
        return res;
    }
}