花花酱 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;

}

};

花花酱 LeetCode 611. Valid Triangle Number

By zxi on September 9, 2017

Problem:

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

The length of the given array won’t exceed 1000.
The integers in the given array are in the range of [0, 1000].

Idea:

Greedy

Time Complexity:

O(n^2)

Solution:

// Author: Huahua

class Solution {

public:

int triangleNumber(vector<int>& nums) {

if (nums.size() < 3) return 0;

std::sort(nums.rbegin(), nums.rend());

int n = nums.size();

int ans = 0;

for (int c = 0; c < n-2; ++c) {

int b = c + 1;

int a = n - 1;

while (b < a) {

if (nums[a] + nums[b] > nums[c]) {

ans += (a - b);

++b;

} else {

--a;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

花花酱 LeetCode 63. Unique Paths II

花花酱 LeetCode 62. Unique Paths

花花酱 LeetCode 268. Missing Number

花花酱 LeetCode 611. Valid Triangle Number

Problem:

Idea:

Solution: