Huahua’s Tech Road

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

for (int i = 1; i < n; ++i)

for (int j = 0; j < i; ++j)

if (nums[i] > nums[j])

f[i] = max(f[i], f[j] + 1);

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

for (int i = 0; i < n; ++i) {

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems:

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

Example 1:

1 2	Input: [1,3,5,4,7] Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

1 2	Input: [2,2,2,2,2] Output: 1

Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

Idea:

Dynamic Programming

Solution:

// Author: Huahua

class Solution {

public:

int findLengthOfLCIS(vector<int>& nums) {

if (nums.empty()) return 0;

int cur = 1;

int ans = 1;

for (int i = 1; i < nums.size(); ++i) {

if (nums[i] > nums[i-1]) {

++cur;

ans = max(ans, cur);

} else {

cur = 1;

}

return ans;

}

};

花花酱 LeetCode 63. Unique Paths II

By zxi on September 9, 2017

Problem:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

Idea:

Dynamic Programming

Solution:

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int n = obstacleGrid.size();

if (n == 0) return 0;

int m = obstacleGrid[0].size();

// f[i][j] = paths(i, j)

// INT_MIN -> not solved yet, solution unknown

f_ = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MIN));

return paths(m, n, obstacleGrid);

}

private:

vector<vector<int>> f_;

int paths(int x, int y, const vector<vector<int>>& o) {

// Out of bound, return 0.

if (x <= 0 || y <= 0) return 0;

// Reaching the starting point.

// Note, there might be an obstacle here as well.

if (x == 1 && y == 1) return 1 - o[0][0];

// Already solved, return the answer.

if (f_[y][x] != INT_MIN) return f_[y][x];

// There is an obstacle on current block, no path

if (o[y - 1][x - 1] == 1) {

f_[y][x] = 0;

} else {

// Recursively find paths.

f_[y][x] = paths(x - 1, y, o) + paths(x, y - 1, o);

}

// Return the memorized answer.

return f_[y][x];

}

};

Related Problems:

[解题报告] LeetCode 62. Unique Paths

花花酱 LeetCode 62. Unique Paths

By zxi on September 9, 2017

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Idea:

Dynamic Programming

Solution1:

C++

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

if (m < 0 || n < 0) return 0;

if (m == 1 && n == 1) return 1;

if (f_[m][n] > 0) return f_[m][n];

int left_paths = uniquePaths(m - 1, n);

int top_paths = uniquePaths(m, n - 1);

f_[m][n] = left_paths + top_paths;

return f_[m][n];

}

private:

unordered_map<int, unordered_map<int, int>> f_;

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

private int[][] dp;

private int m;

private int n;

public int uniquePaths(int m, int n) {

this.dp = new int[m][n];

this.m = m;

this.n = n;

return dfs(0, 0);

}

private int dfs(int x, int y) {

if (x > m - 1 || y > n - 1)

return 0;

if (x == m - 1 && y == n - 1)

return 1;

if (dp[x][y] == 0)

dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1);

return dp[x][y];

}

Solution2:

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

f[1][1] = 1;

for (int y = 1; y <= n; ++y)

for(int x = 1; x <= m; ++x) {

if (x == 1 && y == 1) {

continue;

} else {

f[y][x] = f[y-1][x] + f[y][x-1];

}

return f[n][m];

}

};

花花酱 LeetCode 268. Missing Number

By zxi on September 9, 2017

Problem:

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Idea:

sum / xor

Solution:

// Author: Huahua

class Solution {

public:

// Solution 1: Sum

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = (0+n)*(n+1)/2 - accumulate(nums.begin(), nums.end(), 0);

return x;

}

// Solution 2: XOR

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = 0;

for(int i=1;i<=n;++i)

x = x ^ i ^ nums[i-1];

return x;

}

};

Huahua's Tech Road

花花酱 LeetCode 300. Longest Increasing Subsequence

C++

Python3

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

花花酱 LeetCode 63. Unique Paths II

花花酱 LeetCode 62. Unique Paths

花花酱 LeetCode 268. Missing Number