loading...

Daily Coding Challenge #28

wingkwong profile image wkw ・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 - Shuffle the Array

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]
Example 3:

Input: nums = [1,1,2,2], n = 2
Output: [1,2,1,2]


Constraints:

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3
*/

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans;
        for(int i=0;i<n;i++){
            // push x1..xn
            ans.push_back(nums[i]);
            // push y1..yn
            ans.push_back(nums[i+n]);
        }
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

/*
LeetCode - The k Strongest Values in an Array

Given an array of integers arr and an integer k.

A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m| where m is the median of the array.
If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.


Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.
Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].
Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.
Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]
Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]


Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length
*/

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        // sort the array
        sort(arr.begin(),arr.end());
        // find the median
        int m=arr[(arr.size()-1)/2];
        // we dont need to sort all of them, just sort the first k 
        partial_sort(arr.begin(),arr.begin()+k,arr.end(),[m](int a, int b){
            // A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m|
            // If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j]
            return (abs(a-m) > abs(b-m)) || (abs(a-m) == abs(b-m) && a>b);
        } );
        // only show first k
        arr.resize(k);
        return arr;
    }
};

Enter fullscreen mode Exit fullscreen mode

/*
LeetCode - Design Browser History

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.


Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"


Constraints:

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of  '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.
*/

class BrowserHistory {
// approach: use two pointers - one for current index, one for max index
public:
    BrowserHistory(string homepage) {
        // first history
        h[i]=homepage;
        mi=i;
    }

    void visit(string url) {
        // add url to map
        h[++i]=url;
        mi=i;
    }

    string back(int steps) {
        // if the target is out of boundary, show the first one
        // else show the target one
        i-=steps;
        if(i<0) i=0;
        return h[i];
    }

    string forward(int steps) {
        // if the target is out of boundary, show the last one
        // else show the target one
        i+=steps;
        if(i>mi) i=mi;
        return h[i];
    }
private:
    int i=0,mi=0;
    unordered_map<int,string> h;
};
Enter fullscreen mode Exit fullscreen mode

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

GitHub logo wingkwong / leetcode

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / hackerrank

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / codeforces

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / atcoder

Migrated to https://github.com/wingkwong/competitive-programming

Discussion

pic
Editor guide