Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
Have you met this question in a real interview?
Yes
Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4
Challenge
Time complexity O(n^2) or O(nlogn)
Clarification
What's the definition of longest increasing subsequence?
* The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
* https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
O(n^2)
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
// write your code here
if (nums.size() == 0) return 0;
vector<int> dp(nums.size(),1);
int longest = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i]) {
dp[i] = max(dp[i],dp[j] + 1);
}
longest = max(longest,dp[i]);
}
}
return longest;
}
};
geeksforgeeks,O(n lg n)Longest Common Substring Show result
Given two strings, find the longest common substring.
Return the length of it.
Have you met this question in a real interview?
Yes
Example
Given A =
"ABCD", B = "CBCE", return 2.
Note
The characters in substring should occur continuously in original string. This is different with subsequence.
Challenge
---------------------------------------------------
O(n x m) time and memory.
画个2d矩阵就明白了
class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
// write your code here
int m = A.length(), n = B.length();
vector<vector<int> > dp(m + 1,vector<int>(n + 1,0));
int longest = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
longest = max(longest,dp[i][j]);
}
}
}
return longest;
}
};
线性额外空间
class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
// write your code here
int m = A.length(), n = B.length();
vector<int> dp(n + 1,0);
int longest = 0;
for (int i = 1; i <= m; i++) {
for (int j = n; j >= 1; j--) {
if (A[i - 1] == B[j - 1]) {
dp[j] = dp[j - 1] + 1;
longest = max(longest,dp[j]);
}else {
dp[j] = 0;
}
}
}
return longest;
}
};
Longest Increasing Continuous subsequence II
Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).
Have you met this question in a real interview?
Yes
Example
Given a matrix:
[
[1 ,2 ,3 ,4 ,5],
[16,17,24,23,6],
[15,18,25,22,7],
[14,19,20,21,8],
[13,12,11,10,9]
]
return
25
Challenge
--------------------------------------------------
O(nm) time and memory.
以每一点为path的起始，它所得到最长递增数列都是恒定的
所以用memoization即可
class Solution {
public:
/**
* @param A an integer matrix
* @return an integer
*/
int dfs(vector<vector<int>>& A,vector<vector<int>> &dp,int row,int col) {
if (dp[row][col] != 0) return dp[row][col];
if (row + 1 < A.size() && A[row + 1][col] > A[row][col]) {
dp[row][col] = max(dp[row][col],dfs(A,dp,row + 1,col));
}
if (row - 1 >= 0 && A[row - 1][col] > A[row][col]) {
dp[row][col] = max(dp[row][col],dfs(A,dp,row - 1,col));
}
if (col - 1 >= 0 && A[row][col - 1] > A[row][col]) {
dp[row][col] = max(dp[row][col],dfs(A,dp,row,col - 1));
}
if (col + 1 < A[0].size() && A[row][col + 1] > A[row][col]) {
dp[row][col] = max(dp[row][col],dfs(A,dp,row,col + 1));
}
dp[row][col]++;
return dp[row][col];
}
int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
// Write your code here
if (A.size() == 0) return 0;
int m = A.size(), n = A[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
int longest = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == 0) {
dp[i][j] = dfs(A,dp,i,j);
}
longest = max(longest,dp[i][j]);
}
}
return longest;
}
};
遍历，所有点按高度排序struct Dot {
int row;
int col;
int height;
Dot(int x,int y,int h):row(x),col(y),height(h) {
}
};
class Solution {
public:
static bool cmp(const Dot &d1,const Dot &d2) {
return d1.height < d2.height;
}
/**
* @param A an integer matrix
* @return an integer
*/
int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
// Write your code here
if (A.size() == 0) return 0;
int m = A.size(), n = A[0].size();
vector<vector<int>> len(m,vector<int>(n,0));
vector<Dot> dots;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Dot d(i,j,A[i][j]);
dots.push_back(d);
}
}
sort(dots.begin(),dots.end(),cmp);
int longest = 0;
for (int i = 0; i < dots.size(); i++) {
if (dots[i].row + 1 < m && A[dots[i].row + 1][dots[i].col] > dots[i].height
&& len[dots[i].row + 1][dots[i].col] < len[dots[i].row][dots[i].col] + 1) {
len[dots[i].row + 1][dots[i].col] = len[dots[i].row][dots[i].col] + 1;
}
if (dots[i].col + 1 < n && A[dots[i].row][dots[i].col + 1] > dots[i].height
&& len[dots[i].row][dots[i].col + 1] < len[dots[i].row][dots[i].col] + 1) {
len[dots[i].row][dots[i].col + 1] = len[dots[i].row][dots[i].col] + 1;
}
if (dots[i].row - 1 >= 0 && A[dots[i].row - 1][dots[i].col] > dots[i].height
&& len[dots[i].row - 1][dots[i].col] < len[dots[i].row][dots[i].col] + 1) {
len[dots[i].row - 1][dots[i].col] = len[dots[i].row][dots[i].col] + 1;
}
if (dots[i].col - 1 >= 0 && A[dots[i].row][dots[i].col - 1] > dots[i].height
&& len[dots[i].row][dots[i].col - 1] < len[dots[i].row][dots[i].col] + 1) {
len[dots[i].row][dots[i].col - 1] = len[dots[i].row][dots[i].col] + 1;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
longest = max(longest,len[i][j]);
}
}
return longest + 1;
}
};
