loading...

Daily Coding Challenge #22

wingkwong profile image Wing-Kam ・3 min read

Daily Coding Challenge (58 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 56 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58

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 - Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
*/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //  L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
        //  L(i) = 1, if no such j exists.
        int n=nums.size();
        if(n==0) return 0;
        vector<int> dp(n+1,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        // find out the max in dp
        int ans=0;
        for(int k:dp) ans=max(ans,k);
        return ans;
        // or return *max_element(dp.begin(),dp.end());
    }
};

/*
LeetCode - Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
*/

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=(int)triangle.size();
        // starting from the second last row
        // e.g. [6,5,7]
        for(int i=n-2;i>=0;i--){
            // traverse each item
            for(int j=0;j<(int)triangle[i].size();j++){
                // add itself to the min of below 2 numbers
                // e.g j=0: 6 + min(4,1) = 7 
                //     j=1: 5 + min(1,8) = 6 
                //     j=2: 7 + min(8,3) = 10
                triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        // at the end, the value in the top row is the min sum
        return triangle[0][0];
    }
};

/*
LeetCode - Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
*/

class Solution {
public:
    char isValid(char a){
        return a!='0';
    }

    char isValid(char a, char b){
        return (a=='1'||(a=='2'&&b<='6'));
    }

    int numDecodings(string s) {
        int n=(int)s.size();
        if(n==0||s[0]=='0') return 0;
        if(n==1) return 1;
        int m1=1,m2=1,m;
        for(int i=1;i<n;i++){
            m=0;
            // validate the current character and the previous character
            if(!isValid(s[i])&&!isValid(s[i-1],s[i])) return 0;
            if(isValid(s[i])) m=m1;
            if(isValid(s[i-1],s[i])) m+=m2;
            m2=m1;
            m1=m;
        }
        return m;
    }
};

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 🏆

Daily Coding Challenge (58 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 56 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58

Posted on Jun 4 by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide
 

My O(n log n) solution to the first problem: play.rust-lang.org/?version=stable...

fn length_of_lis(numbers: &[isize]) -> usize {
    // This is the longest increasing subsequence that can end with a number:
    let mut chain_length = std::collections::BTreeMap::new();

    // This acts as a reverse index of chain_length. Since we always increase the length by one -
    // it can be a vector:
    let mut best_for_length = Vec::new();

    for &num in numbers {
        // Find the longest subsequence num can continue:
        let continue_from = chain_length.range(..num).next_back();
        let prefix_length = if let Some((_, &prefix_length)) = continue_from {
            prefix_length
        } else {
            0
        };

        if prefix_length < best_for_length.len() {
            // This is where the magic happens. If we already have a subsequence with the same
            // length that ends with a higher number, we don't need that subsequence since any
            // subsequence that can continue it can also continue this new subsequence we just
            // discovered. By removing the old one, we are preventing the `continue_from` search
            // from yielding a higher that represents a shorter subsequence.

            let prev_best = best_for_length[prefix_length];
            assert!(num <= prev_best); // otherwise num would have continued the subsequence
            best_for_length[prefix_length] = num;
            chain_length.remove(&prev_best);
        } else {
            best_for_length.push(num);
        }
        chain_length.insert(num, prefix_length + 1);
    }
    chain_length.values().max().copied().unwrap_or(0)

}