Problem Conversion

525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input:
 [0,1]

Output:
 2

Explanation:
 [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Conversion:

Equal number of 0 and 1 can be represent as total sum equals 0, if we change all 0 to -1.

364. Nested List Weight Sum II

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from theprevious questionwhere weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:
Given the list[[1,1],2,[1,1]], return8. (four 1's at depth 1, one 2 at depth 2)

Example 2:
Given the list[1,[4,[6]]], return17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)

Conversion:

Weighted sum can be thought of as repeated sum. Repeated x times means at level x / with weight x.

594. Longest Harmonious Subsequence

We define a harmonious array is an array where the difference between its maximum value and its minimum value isexactly1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possiblesubsequences.

Example 1:

Input:
 [1,3,2,2,5,2,3,7]

Output:
 5

Explanation:
 The longest harmonious subsequence is [3,2,2,2,3].

Note:The length of the input array will not exceed 20,000.

Conversion:

Subsequence in this case means we don't care the ordering of the numbers. As long as the numbers you are considering are of difference by exactly 1 then it is fine. The problem is also ask us to find how many are such numbers not the length of the sub-array.

487. Max Consecutive Ones II

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1:

Input:
 [1,0,1,1,0]

Output:
 4

Explanation:
Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.

Conversion:

It is equivalent to finding the max sub array length, which contains only k zeros. It is then sliding window problem. For streaming, we don't store the numbers, we can instead store the position information of the zeros.