Good Problem List Summary -1-


  • 0
    F

    Minimum Adjustment Cost

    Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
    Example
    Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

    Solution :

    定义res[i][j] 表示前 i个number with 最后一个number是j,这样的minimum adjusting cost

    如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间,lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),

    这样的话,transfer function可以写成:

    for (int p=lowerRange; p<= upperRange; p++) {

    dp[i][j] = Math.min(res[i][j], dp[i-1][p] + Math.abs(j-A.get(i-1)));

    }

    class Solution {
    public:
        /**
         * @param A: An integer array.
         * @param target: An integer.
         */
        int MinAdjustmentCost(vector<int> A, int target) {
            // write your code here
            int size_A = A.size();
            if(size_A == 0)  return 0;
            vector<vector<int>> dp(size_A + 1, vector<int>(101, 0));
            for(int i = 0; i < 101; i++) {
                dp[0][i] = 0;
            }
            
            for(int i = 1; i < size_A + 1; i++) {
                for(int j = 1; j < 101; j++) {
                    dp[i][j] = INT_MAX;
                    int low = max(1, j - target);
                    int high = min(100, j + target);
                    for(int k = low; k <= high; k++) {
                        dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(A[i-1] - j));
                    }
                }
            }
            
            int result = INT_MAX;
            for (int i = 1; i <= 100; i++) {
                result = min(result, dp[size_A][i]);
            }
            return result;
        }
    };
    
    

    Subtree

    You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

    class Solution {
    public:
        /**
         * @param T1, T2: The roots of binary tree.
         * @return: True if T2 is a subtree of T1, or false.
         */
        bool isSubtree(TreeNode *T1, TreeNode *T2) {
            if (!T2) {
                return true;
            } else if (!T1) {  // !T1 && T2
                return false;
            } else {  // T1 && T2
                return isSameTree(T1, T2) ||
                       isSubtree(T1->left, T2) ||
                       isSubtree(T1->right, T2);
            }
    
        }
    
        bool isSameTree(TreeNode *T1, TreeNode *T2) {
            if (!T1 && !T2) {
                return true;
            }
    
            if (T1 && T2) {
                return T1->val == T2->val &&
                       isSameTree(T1->left, T2->left) &&
                       isSameTree(T1->right, T2->right);
            }
    
            return false;
        }
    };
    

    Print Number by Recursion

    class Solution {
    public:
        /**
         * @param n: An integer.
         * return : An array storing 1 to the largest number with n digits.
         */
        vector<int> numbersByRecursion(int n) {
            vector<int> result;
            numbersByRecursionHelper(0, n, result);
            return result;
        }
    
        // Construct the numbers by the current digit count.
        void numbersByRecursionHelper(int depth, int n, vector<int>& result) {
            if (depth == n) {
                return;
            }
    
            if (depth == 0) {  // Initiate the result.
                for (size_t d = 1; d <= 9; ++d) {
                    result.emplace_back(d);
                }
            } else {  // Construct the numbers by the previous result.
                const size_t count = result.size();
                for (size_t d = 1; d <= 9; ++d) {
                    result.emplace_back(d * pow(10, depth));
                    for (size_t i = 0; i < count; ++i) {
                        result.emplace_back(result[i] + d * pow(10, depth));
                    }
                }
            }
            // Construct the numbers in the next depth.
            numbersByRecursionHelper(depth + 1, n, result);
        }
    };
    

    Sliding Windows Maximum

    Multiset based Solution

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> result;
            /*** use the multiset to get the max-value ***/
            multiset<int> w;
            for(int i=0; i<nums.size(); i++){
                /*** erase the previous top element ***/
                if(i>=k)  w.erase(w.find(nums[i-k]));
                w.insert(nums[i]);
                /*** insert the max-value of the window ***/
                if(i>=k-1) result.push_back(*w.rbegin());
            }
            return result;
        }
    };
    

    Mono-decrease based Solution

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> result;
            deque<int> q;
            for(int i=0; i<nums.size(); i++){
                /*** remove the top element **/
                if(!q.empty() && q.front()==i-k)  q.pop_front();
                /*** keep the element in the queue is monotically-decreasing ***/
                while(!q.empty() && nums[q.back()] < nums[i])  q.pop_back();
                q.push_back(i);
                if(i>=k-1)  result.push_back(nums[q.front()]);
            }
            return result;
        }
    };
    

    Sliding Windows Median

    Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

    Example

    For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

    At first the window is at the start of the array like this

    [ | 1,2,7 | ,8,5 ] , return the median 2;

    then the window move one step forward.

    [1, | 2,7,8 | ,5], return the median 7;

    then the window move one step forward again.

    [1,2, | 7,8,5 | ], return the median 7;

    Solution :

    class Solution {
    public:
        /**
         * @param nums: A list of integers.
         * @return: The median of the element inside the window at each moving
         */
        vector<int> medianSlidingWindow(vector<int> &nums, int k) {
            // min_bst stores the larger half seen so far.
            multiset<int, less<int>> min_bst;
            // max_bst stores the smaller half seen so far.
            multiset<int, greater<int>> max_bst;
    
            vector<int> ans;
            for (int i = 0; i < nums.size(); ++i) {
                if (i >= k) {
                    // Remove the element outside the window.
                    if (max_bst.find(nums[i - k]) != max_bst.cend()) {
                        max_bst.erase(max_bst.find(nums[i - k]));
                    } else {
                        min_bst.erase(min_bst.find(nums[i - k]));
                    }
                }
    
                // Balance smaller half and larger half.
                if (max_bst.empty() || nums[i] > *max_bst.cbegin()) {
                    min_bst.emplace(nums[i]);
                    if (min_bst.size() > max_bst.size() + 1) {
                        max_bst.emplace(*min_bst.cbegin());
                        min_bst.erase(min_bst.cbegin());
                    }
                } else {
                    max_bst.emplace(nums[i]);
                    if (max_bst.size() > min_bst.size()) {
                        min_bst.emplace(*max_bst.cbegin());
                        max_bst.erase(max_bst.cbegin());
                    }
                }
    
                // If window is full, get the median from 2 BST.
                if (i >= k - 1) {
                    ans.emplace_back(min_bst.size() == max_bst.size() ?
                                     *max_bst.cbegin() : *min_bst.cbegin());
                }
            }
    
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.