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

}

};

花花酱 LeetCode 204. Count Primes

By zxi on September 9, 2017

Problem:

Count the number of prime numbers less than a non-negative number, n.

Idea:

Sieve of Eratosthenes

Time Complexity:

O(nloglogn)

Space Complexity:

O(n)

Solution:

C++

// Author: Huahua

class Solution {

public:

int countPrimes(int n) {

if (n < 3) return 0;

vector<unsigned char> f(n, 1);

f[0] = f[1] = 0;

for(long i=2;i<=sqrt(n);++i) {

if(!f[i]) continue;

for(long j=i*i;j<n;j+=i)

f[j] = 0;

}

int ans = accumulate(f.begin(), f.end(), 0);

return ans;

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int countPrimes(int n) {

int ans = 0;

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true);

isPrime[0] = false;

if (n > 0) isPrime[1] = false;

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

if (!isPrime[i]) continue;

++ans;

for (int j = 2 * i; j < n; j += i)

isPrime[j] = false;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 800 ms

"""

class Solution:

def countPrimes(self, n):

if n < 3: return 0

isPrime = [True] * (n + 1)

isPrime[0] = False

isPrime[1] = False

ans = 0

for i in range(2, n):

if not isPrime[i]: continue

ans += 1

for j in range(2 * i, n, i):

isPrime[j] = False

return ans

Huahua's Tech Road

花花酱 LeetCode 63. Unique Paths II

花花酱 LeetCode 62. Unique Paths

花花酱 LeetCode 268. Missing Number

花花酱 LeetCode 611. Valid Triangle Number

Problem:

Idea:

Solution:

花花酱 LeetCode 204. Count Primes