Good Problem List Summary -2-


  • 0
    F

    Longest Increasing Continuous Subsequence

    Give an integer array,find the longest increasing continuous subsequence in this array. An increasing continuous subsequence:
    Can be from right to left or from left to right. Indices of the integers in the subsequence should be continuous.

    Example
    For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.
    For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

    Solution:

    class Solution {
    public:
        /**
         * @param A an array of Integer
         * @return  an integer
         */
        int longestIncreasingContinuousSubsequence(vector<int>& A) {
            int max_inc_len = 0, cur_inc_len = 0;
            int max_dec_len = 0, cur_dec_len = 0;
    
            for (int i = 0; i < A.size(); ++i) {
                if (i == 0 || A[i] == A[i - 1]) {
                    max_inc_len = max(max_inc_len, ++cur_inc_len);
                    max_dec_len = max(max_dec_len, ++cur_dec_len);
                } else if (A[i] > A[i - 1]) {
                    max_inc_len = max(max_inc_len, ++cur_inc_len);
                    cur_dec_len = 1;
                } else if (A[i] < A[i - 1]) {
                    max_dec_len = max(max_dec_len, ++cur_dec_len);
                    cur_inc_len = 1;
                }
            }
    
            return max(max_inc_len, max_dec_len);
        }
    };
    

    Post office Problem

    On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

    Example
    Given array a = [1,2,3,4,5], k = 2. return 3.
    Challenge
    Could you solve this problem in O(n^2) time ?

    Solution:

    i : the number of post office
    j : the jth house
    dp[i][j] : the minimal cost of building i post office between 0 and j (inclusive)
    cost[i][j] : the minimal cost of building a post office between i and j

    for k =
    dp[i][j] = min(dp[i][j], dp[i-1][k-1] + cost[k][j])

    Here is solution refered from linkes cnblogs

    class Solution 
    {
    public:
        /**
         * @param A an integer array
         * @param k an integer
         * @return an integer
         */
        int postOffice(vector<int>& A, int k) 
        {
            int n = A.size();
            sort(A.begin(), A.end()); 
            // Cost btw. 2 houses i-j with 1 post-office - built in the mid
            vector<vector<int>> w(n + 1, vector<int>(n + 1));
            for(int i = 1; i <= n; i ++)
            {
                w[i][i] = 0;
                for(int j = i + 1; j <= n; j ++)
                {
                    // Check both odd\even. It holds.
                    w[i][j] = w[i][j-1] + A[j - 1] - A[(i + j) / 2 - 1];
                }
            }
            
            // main DP    
            vector<vector<int>> dp(n + 1, vector<int>(k + 1));
            for(int i = 1; i <= n; i++)
            {
                dp[i][1] = w[1][i];
            }
            for(int i = 2; i <= k; i ++) // post-offices
            {
                for(int j = n; j > i; j --) // houses. Low j sets high j
                {
                    dp[j][i] = INT_MAX;
                    for(int x = i - 1; x < j; x ++)
                    {
                        dp[j][i] = min(dp[j][i], dp[x][i-1] + w[x + 1][j]);
                    }
                }
            }
            
            return dp[n][k];
        }
    };
    

    Find Peak Element in Array & Matrix

    Solution 1

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            int start=0, end=nums.size()-1;
            while(end>start){
                int mid=(start+end)/2;
                if(nums[mid] < nums[mid+1])  start=mid+1;
                else end=mid;
            }
            return start;
        }
    };
    

    Solution 2

    class Solution {
    public:
        /**
         * @param A: An integer matrix
         * @return: The index of the peak
         */
        vector<int> findPeakII(vector<vector<int> > A) {
            // write your code here
            vector<int> res;
            int left = 0, right = A.size() - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                int col = findPeak(A[mid]);
                if (A[mid][col] < A[mid+1][col]) {
                    left = mid + 1;
                } else if (A[mid][col] < A[mid-1][col]) {
                    right = mid - 1;
                } else {
                    return {mid, col};
                }
            }
            return res;
        }
        int findPeak(vector<int> &v) {
            int res = 0;
            for (int i = 1; i < v.size(); ++i) {
                if (v[i] > v[res]) res = i;
            }
            return res;
        }
    };
    

Log in to reply
 

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