## leetcode Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:

Could you do it without using any loop / recursion?

# C++

## leetcode 274 H-Index || 275 H-Index II

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

hifhof his/herNpapers haveat leasthcitations each, and the otherN − hpapers haveno more thanhcitations each.”For example, given

`citations = [3, 0, 6, 1, 5]`

, which means the researcher has`5`

papers in total and each of them had received`3, 0, 6, 1, 5`

citations respectively. Since the researcher has`3`

papers withat least`3`

citations each and the remaining two withno more than`3`

citations each, his h-index is`3`

.

Note: If there are several possible values for`h`

, the maximum one is taken as the h-index.

Hint:

- 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

## leetcode Bulb Switcher

There are

nbulbs 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 thenth round, you only toggle the last bulb. Find how many bulbs are on afternrounds.

Example: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

## 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.

Example 1:Given

`["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]`

Return`16`

The two words can be`"abcw", "xtfn"`

.

Example 2:Given

`["a", "ab", "abc", "d", "cd", "bcd", "abcd"]`

Return`4`

The two words can be`"ab", "cd"`

.

Example 3:Given

`["a", "aa", "aaa", "aaaa"]`

Return`0`

No such pair of words.

Follow up:

Could you do better than O(n^{2}), wherenis the number of words?

## leetcode Peeking Iterator

Given an Iterator class interface with methods:

`next()`

and`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]`

.Call

`next()`

gets you 1, the first element in the list.Now you call

`peek()`

and it returns 2, the next element. Calling`next()`

after thatreturn 2.stillYou call

`next()`

the final time and it returns 3, the last element. Calling`hasNext()`

after that should return false.

Hint:

- 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
`peek()`

before`next()`

vs`next()`

before`peek()`

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

## leetcode Count of Smaller Numbers After Self

You are given an integer array

numsand you have to return a newcountsarray. Thecountsarray has the property where`counts[i]`

is the number of smaller elements to the right of`nums[i]`

.

Example: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 I II

## 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, 8`

are ugly while`14`

is not ugly since it includes another prime factor`7`

.Note that

`1`

is typically treated as an ugly number.

## leetcode Burst Balloons

## leetcode Burst Balloons

Given

`n`

balloons, indexed from`0`

to`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`i`

you will get`nums[left] * nums[i] * nums[right]`

coins. Here`left`

and`right`

are adjacent indices of`i`

. After the burst, the`left`

and`right`

then becomes adjacent.Find the maximum coins you can collect by bursting the balloons wisely.

Note:

(1) You may imagine`nums[-1] = nums[n] = 1`

. They are not real therefore you can not burst them.

(2) 0 ≤`n`

≤ 500, 0 ≤`nums[i]`

≤ 100

Example:Given

`[3, 1, 5, 8]`

Return

`167`

12 nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

## leetcode Count Primes

## leetcode Count Primes

Description:Count the number of prime numbers less than a non-negative number,

.n

## leetcode Perfect Squares

## leetcode Perfect Squares

Given a positive integer

n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`

) which sum ton.For example, given

n=`12`

, return`3`

because`12 = 4 + 4 + 4`

; givenn=`13`

, return`2`

because`13 = 4 + 9`

.