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

花花酱 LeetCode 51. N-Queens

By zxi on September 8, 2017

Problem:

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[

[".Q..", // Solution 1

"...Q",

"Q...",

"..Q."],

["..Q.", // Solution 2

"Q...",

"...Q",

".Q.."]

]

Idea:

Solution:

Changes: 12/20/2017

type of sols_ changed from set<vector<string>> to vector<vector<string>>. Thanks to Yun-Ting Lin.

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<vector<string>> solveNQueens(int n) {

sols_.clear();

board_ = vector<string>(n, string(n, '.'));

cols_ = vector<int>(n, 0);

diag1_ = vector<int>(2 * n - 1, 0);

diag2_ = vector<int>(2 * n - 1, 0);

nqueens(n, 0);

return sols_;

}

private:

vector<string> board_;

vector<int> cols_;

vector<int> diag1_;

vector<int> diag2_;

vector<vector<string>> sols_;

bool available(int x, int y, int n) {

return !cols_[x]

&& !diag1_[x + y]

&& !diag2_[x - y + n - 1];

}

void updateBoard(int x, int y, int n, bool is_put) {

cols_[x] = is_put;

diag1_[x + y] = is_put;

diag2_[x - y + n - 1] = is_put;

board_[y][x] = is_put ? 'Q' : '.';

}

// Try to put the queen on y-th row

void nqueens(const int n, const int y) {

if (y == n) {

// found one solution, add to the ans set

sols_.push_back(board_);

return;

}

// Try every column

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

if (!available(x, y, n)) continue;

updateBoard(x, y, n, true);

nqueens(n, y + 1);

updateBoard(x, y, n, false);

}

};

Huahua's Tech Road

花花酱 LeetCode 62. Unique Paths

花花酱 LeetCode 268. Missing Number

花花酱 LeetCode 611. Valid Triangle Number

Problem:

Idea:

Solution:

花花酱 LeetCode 204. Count Primes

花花酱 LeetCode 51. N-Queens