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

}

};

花花酱 LeetCode 145. Binary Tree Postorder Traversal

By zxi on September 8, 2017

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

花花酱 LeetCode 154. Find Minimum in Rotated Sorted Array II

By zxi on September 7, 2017

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Idea:

Divide and conquer

Time complexity:

Average: O(logn)

Worst: O(n)

Solution:

// Author: Huahua

class Solution {

public:

int findMin(vector<int> &num) {

return findMin(num, 0, num.size()-1);

}

int findMin(const vector<int>& num, int l, int r)

{

// One or two elements, solve it directly

if (l+1 >= r) return

min(num[l], num[r]);

// Sorted

if (num[l] < num[r])

return num[l];

int m = l + (r-l)/2;

// Recursively find the solution

return min(findMin(num, l, m - 1),

findMin(num, m, r));

}

};

Related Problems:

花花酱 LeetCode 637. Average of Levels in Binary Tree

By zxi on September 7, 2017

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

/ \

9 20

/ \

15 7

Output: [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.

Hence return [3, 14.5, 11].

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<double> ans;

vector<TreeNode*> curr, next;

curr.push_back(root);

// process every level one by one

while(!curr.empty()) {

long long sum = 0;

for(const auto& node : curr) {

sum += node->val;

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

ans.push_back(static_cast<double>(sum) / curr.size());

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2:

DFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<pair<long long, int>> sum_count;

vector<double> ans;

preorder(root, 0, sum_count);

for(const auto& p : sum_count)

ans.push_back(static_cast<double>(p.first) / p.second);

return ans;

}

private:

void preorder(TreeNode* root, int depth, vector<pair<long long, int>>& sum_count) {

if(root == nullptr) return;

if(depth>=sum_count.size()) sum_count.push_back({0,0});

sum_count[depth].first += root->val;

++sum_count[depth].second;

preorder(root->left, depth+1, sum_count);

preorder(root->right, depth+1, sum_count);

}

};

Related Problems:

[解题报告] LeetCode 102. Binary Tree Level Order Traversal

Huahua's Tech Road

花花酱 LeetCode 204. Count Primes

花花酱 LeetCode 51. N-Queens

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Solution 1:

Solution 2:

Solution 3:

花花酱 LeetCode 154. Find Minimum in Rotated Sorted Array II

花花酱 LeetCode 637. Average of Levels in Binary Tree