## leetcode Patching Array

Given a sorted positive integer array

numsand an integern, add/patch elements to the array such that any number in range`[1, n]`

inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

nums=`[1, 3]`

,n=`6`

Return`1`

.Combinations of

numsare`[1], [3], [1,3]`

, which form possible sums of:`1, 3, 4`

.

Now if we add/patch`2`

tonums, the combinations are:`[1], [2], [3], [1,3], [2,3], [1,2,3]`

.

Possible sums are`1, 2, 3, 4, 5, 6`

, which now covers the range`[1, 6]`

.

So we only need`1`

patch.

# java

## leetcode Longest Increasing Path in a Matrix

## leetcode Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

Return

`4`

The longest increasing path is`[1, 2, 6, 9]`

.

## leetcode Odd Even Linked List

## leetcode Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

Given`1->2->3->4->5->NULL`

,

return`1->3->5->2->4->NULL`

.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …

## leetcode Wiggle Sort II

## leetcode Wiggle Sort II

Given an unsorted array

`nums`

, reorder it such that`nums[0] < nums[1] > nums[2] < nums[3]...`

.

Example:

(1) Given`nums = [1, 5, 1, 1, 6, 4]`

, one possible answer is`[1, 4, 1, 5, 1, 6]`

.

(2) Given`nums = [1, 3, 2, 2, 3, 1]`

, one possible answer is`[2, 3, 1, 3, 1, 2]`

.

Note:

You may assume all input has valid answer.

Follow Up:

Can you do it in O(n) time and/or in-place with O(1) extra space?

## leetcode Create Maximum Number

## leetcode Create Maximum Number

Given two arrays of length

`m`

and`n`

with digits`0-9`

representing two numbers. Create the maximum number of length`k <= m + n`

from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the`k`

digits. You should try to optimize your time and space complexity.

Example 1:nums1 =

`[3, 4, 6, 5]`

nums2 =`[9, 1, 2, 5, 8, 3]`

k =`5`

return`[9, 8, 6, 5, 3]`

Example 2:nums1 =

`[6, 7]`

nums2 =`[6, 0, 4]`

k =`5`

return`[6, 7, 6, 0, 4]`

Example 3:nums1 =

`[3, 9]`

nums2 =`[8, 9]`

k =`3`

return`[9, 8, 9]`

## 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 Super Ugly Number

## leetcode Super Ugly Number

Write a program to find the n

^{th}super ugly number.Super ugly numbers are positive numbers whose all prime factors are in the given prime list

`primes`

of size`k`

. For example,`[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]`

is the sequence of the first 12 super ugly numbers given`primes`

=`[2, 7, 13, 19]`

of size 4.

Note:

(1)`1`

is a super ugly number for any given`primes`

.

(2) The given numbers in`primes`

are in ascending order.

(3) 0 <`k`

≤ 100, 0 <`n`

≤ 10^{6}, 0 <`primes[i]`

< 1000.

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