loading...

Daily Coding Challenge #9

wingkwong profile image Wing-Kam ・5 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.


Example 2:

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
*/

/**
 * 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 {
public:
    int findSecondMinimumValue(TreeNode* root) {
        dfs(root);
        // check if the size is greater than / equal to 2
        // if so, print the second one
        // if not, print -1 (because the value in set must be unique, so 2-2-2 would become [2] whose size is less than 2)
        return s.size()>=2? *next(s.begin(),1) :-1;
    }

private:
    // use ordered set to store the unqiue values
    set<int> s;
    void dfs(TreeNode* root){
        if(!root) return;
        s.insert(root->val);
        dfs(root->left);
        dfs(root->right);
    }
};

/*
LeetCode -  Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].



Example 1:

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.


Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.
*/

class StockSpanner {
public:
    stack<pair<int,int>> s;
    StockSpanner() {}

    int next(int price) {
        int res=1;
        // put the price and the number of prices that are less than the current one into a pair
        while(!s.empty()&&s.top().first<=price){
            // update res and pop it 
            res+=s.top().second;
            s.pop();
        }
        s.push({price,res});
        return res;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

/*
LeetCode - Increasing Decreasing String

Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.
In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.



Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
Example 3:

Input: s = "leetcode"
Output: "cdelotee"
Example 4:

Input: s = "ggggggg"
Output: "ggggggg"
Example 5:

Input: s = "spo"
Output: "ops"


Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.
*/

class Solution {
public:
    string sortString(string s) {
        string ans="";
        vector<int> v(26,0);
        int sz=(int)s.size();
        for(char c:s) v[c-'a']++;
        while(sz!=ans.size()){
            // same idea as Solution2 but more simple 
            // using string init
            for(char c='a';c<='z';c++) ans+=string(--v[c-'a']>=0?1:0,c); 
            for(char c='z';c>='a';c--) ans+=string(--v[c-'a']>=0?1:0,c); 
        }
        return ans;
    }
};

class Solution2 {
public:
    string sortString(string s) {
        string ans="";
        vector<int> v(26,0);
        int sz=(int)s.size();
        // store the occurence of each character to a vector
        for(char c:s) v[c-'a']++;
        // 7. Repeat the steps from 1 to 6 until you pick all characters from s.
        while(sz){
            // 1. Pick the smallest character from s and append it to the result.
            // 2. Pick the smallest character from s which is greater than the last appended character to the result and append it
            // 3. Repeat step 2 until you cannot pick more characters
            for(char c='a';c<='z';c++){
                if(v[c-'a']){
                    ans+=c;
                    v[c-'a']--;
                    sz--;
                }
            }
            // 4. Pick the largest character from s and append it to the result.
            // 5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
            // 6. Repeat step 5 until you cannot pick more characters.
            for(char c='z';c>='a';c--){
                if(v[c-'a']){
                    ans+=c;
                    v[c-'a']--;
                    sz--;
                }
            }
        }

        return ans;
    }
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

πŸ† A Collection of my LeetCode Solutions with Explanations πŸ†

GitHub logo wingkwong / hackerrank

πŸ† A Collection of my HackerRank Solutions with Explanations πŸ†

GitHub logo wingkwong / codeforces

πŸ† A Collection of my Codeforces Solutions with Explanations πŸ†

GitHub logo wingkwong / atcoder

πŸ† A Collection of my AtCoder Solutions with Explanations πŸ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide