loading...

Daily Coding Challenge #7

wingkwong profile image Wing-Kam ・4 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 - Consecutive Characters

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.

Return the power of the string.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.
Example 2:

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.
Example 3:

Input: s = "triplepillooooow"
Output: 5
Example 4:

Input: s = "hooraaaaaaaaaaay"
Output: 11
Example 5:

Input: s = "tourist"
Output: 1
*/

class Solution {
public:
    int maxPower(string s) {
        int ans=1,cnt=1;
        char cur=s[0];
        // traverse each character
        for(int i=1;i<s.size();i++){
            if(s[i]==cur){
                // if it is consecutive, add 1 to the counter
                // and check if it s greater than max length
                cnt++;
                ans=max(ans,cnt);
            } else {
                // if not, update cur and reset the counter
                cur=s[i];
                cnt=1;
            }
        }
        return ans;
    }
};

/*
LeetCode - Simplified Fractions

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]
Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
Example 4:

Input: n = 1
Output: []

Constraints: 1 <= n <= 100
*/

class Solution {
public:
    // int helper(int x, int y){
    //     int d,xx,yy;
    //     d=__gcd(x,y);
    //     xx=x/d;
    //     yy=y/d;
    //     return (xx==x&&yy==y);
    // }

    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        // brute-force approach to find out all answers
        for(int i=2;i<=n;i++) {
            for(int j=1;j<n;j++){
                if(
                    (i%j==0&&j!=1) ||
                    (j/i)>=1 ||
                    !__gcd(i,j)
                ) continue;
                // 20200518: I think it can be further simplified 
                // check if __gcd(i,j) is 1, if so, j/i would be one of the answers
                ans.push_back(to_string(j)+"/"+to_string(i));
            }
        }
        return ans;
    }
};



/*
LeetCode - Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.
*/

/**
 * 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:
    void dsf(TreeNode* root, int val){
        // if root is NULL, return
        if(!root) return;
        // if the node value is greater than / equal to the max value, increase ans by 1
        if(root->val>=val) ans++;
        int mx=max(root->val,val);
        // pass the max value to left node
        dsf(root->left, mx);
        // pass the max value to right node
        dsf(root->right, mx);
    }

    int goodNodes(TreeNode* root) {
        // simple dsf approach
        // record the maximum value along the path from the root to the node
        dsf(root, root->val); 
        return ans;
    }
private:
    int ans=0;
};

/*
LeetCode - Form Largest Integer With Digits That Add up to Target

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
The total cost used must be equal to target.
Integer does not have digits 0.
Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return "0".

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "997", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5
Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.
Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.
Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"


Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000
*/


class Solution {
public:
    // top-down dp approach
    string largestNumber(vector<int>& cost, int target) {
        if(target==0) return "";
        if(target<0) return "0";
        if(dp[target].empty()){
             dp[target]="0";
             // 9 digits
             for(int i=1;i<=9;i++){
                 // build the result string 
                 string res=largestNumber(cost,target-cost[i-1]);
                 // if res is "0", that means cost[n]>=target, hence we can't take this digit
                 // if res size plus 1 is greater than the dp[target] size, 
                 if(res!="0"&&res.size()+1>=dp[target].size()){
                     dp[target]=to_string(i)+res;
                 }
             }
        }
        return dp[target];
    }
private:
    string dp[5001] = {};
};

class Solution2 {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<string> dp(target+1,"0");
        int n=(int)cost.size();
        dp[0]="";
        for(int i=0;i<n;i++){
            for(int j=1;j<=target;j++){
                if(
                    j<cost[i] || 
                    dp[j-cost[i]]=="0"
                ) continue;
                string s = string(1,'1'+i)+dp[j-cost[i]];
                if(
                    s.size() != dp[j].size() ?
                        s.size() > dp[j].size() :
                            s > dp[j]
                ) dp[j]=s;
            }
        }
        return dp[target];
    }
};

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