leetcode Power of Three
Given an integer, write a function to determine if it is a power of three.
Could you do it without using any loop / recursion?
leetcode 274 H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.
According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
For example, given
citations = [3, 0, 6, 1, 5], which means the researcher has
5papers in total and each of them had received
3, 0, 6, 1, 5citations respectively. Since the researcher has
3papers with at least
3citations each and the remaining two with no more than
3citations each, his h-index is
Note: If there are several possible values for
h, the maximum one is taken as the h-index.
- An easy approach is to sort the array first.
- What are the possible values of h-index?
- A faster approach is to use extra space.
leetcode Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.
leetcode Maximum Product of Word Lengths
Given a string array
words, find the maximum value of
length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
The two words can be
["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
The two words can be
["a", "aa", "aaa", "aaaa"]
No such pair of words.
Could you do better than O(n2), where n is the number of words?
Given an Iterator class interface with methods:
hasNext(), design and implement a PeekingIterator that support the
peek()operation — it essentially peek() at the element that will be returned by the next call to next()
Here is an example. Assume that the iterator is initialized to the beginning of the list:
[1, 2, 3].
next()gets you 1, the first element in the list.
Now you call
peek()and it returns 2, the next element. Calling
next()after that still return 2.
next()the final time and it returns 3, the last element. Calling
hasNext()after that should return false.
- Think of “looking ahead”. You want to cache the next element.
- Is one variable sufficient? Why or why not?
- Test your design with call order of
- For a clean implementation, check out Google’s guava library source code.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
leetcode Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where
counts[i]is the number of smaller elements to the right of
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array
[2, 1, 1, 0].
leetcode Ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include
2, 3, 5. For example,
6, 8are ugly while
14is not ugly since it includes another prime factor
1is typically treated as an ugly number.
leetcode Burst Balloons
nballoons, indexed from
n-1. Each balloon is painted with a number on it represented by array
nums. You are asked to burst all the balloons. If the you burst balloon
iyou will get
nums[left] * nums[i] * nums[right]coins. Here
rightare adjacent indices of
i. After the burst, the
rightthen becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
(1) You may imagine
nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤
n≤ 500, 0 ≤
[3, 1, 5, 8]
12 nums = [3,1,5,8] --> [3,5,8] --> [3,8] -->  --> coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
leetcode Count Primes
Count the number of prime numbers less than a non-negative number, n.
leetcode Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
For example, given n =
12 = 4 + 4 + 4; given n =
13 = 4 + 9.