Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 611. Valid Triangle Number

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:

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

Idea:

Greedy

Time Complexity:

O(n^2)

Solution:

 

花花酱 LeetCode 204. Count Primes

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++

Java

Python3

 

 

花花酱 LeetCode 51. N-Queens

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:

Idea:
Search
Solution:
Changes: 12/20/2017
type of sols_ changed from set<vector<string>> to vector<vector<string>>. Thanks to Yun-Ting Lin.

 

花花酱 LeetCode 145. Binary Tree Postorder Traversal

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:

Solution 2:

Solution 3:

 

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

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:

 

Related Problems: