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);
}
};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;
}
};