loading...

Daily Coding Challenge #74

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 - Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
*/


/**
 * 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) {}
 * };
 */
/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        // if null, return {}
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            // travese each level
            int n = q.size();
            vector<int> cur(n);
            for(int i=0;i<n;i++){
                // traverse each element at the current level
                TreeNode* tmp = q.front();
                q.pop();
                cur[i] = tmp->val;
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ans.emplace_back(cur);
        }
        return ans;
    }
};

/*
LeetCode - Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
*/

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        int l2r=1;
        while(!q.empty()){
            int n = q.size();
            vector<int> cur(n);
            for(int i=0;i<n;i++){
                TreeNode* tmp = q.front();
                q.pop();
                // similar to 102, just add l2r to check if it is left to right or right to left
                if(l2r) cur[i]=tmp->val;
                else cur[n-1-i]=tmp->val;
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right); 
            }
            ans.emplace_back(cur);
            l2r=!l2r;
        }
        return ans;
    }
};

/*
LeetCode - Find a Value of a Mysterious Function Closest to Target

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.



Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.
Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0


Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7
*/

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int n = arr.size(), ans=INT_MAX;
        for(int i=0;i<n;i++){
            int sum = arr[i];
            for(int j=i;j<n;j++){
                sum &= arr[j];
                ans = min(ans, abs(sum-target));
                // best case
                if(ans==0) return ans;
                // a1 = arr[1], 
                // a2 = arr[1]&arr[2], 
                // a3 = arr[1]&arr[2]&arr[3]
                // a1 >= a2 >= a3
                // hence, if sum <= target, we can break the loop 
                if(sum <= target) break;
            }
            // the future sum won't be smaller than sum
            // ans won't be smaller 
            if(sum>target) break;
        }
        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

markdown guide