LeetCode | Learn for Master - Part 2
• ### Ones and Zeroes

474. Ones and Zeroes

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m0s and n1s respectively. On the other hand, there is an array with strings consisting of only 0sand 1s.

Now your task is to find the maximum number of strings that you can form with given m0s and n1s. Each 0 and 1 can be used at mostonce.

Note:

1. The given numbers of 0s and 1s will both not exceed 100
2. The size of given string array won’t exceed 600.
• ### Leetcode Concatenated Words

472. Concatenated Words

Given a list of words, please write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Note:

1. The number of elements of the given array will not exceed 10,000
2. The length sum of elements in the given array will not exceed 600,000.
3. All the input string will only include lower case letters.
4. The returned elements order does not matter.
• ### leetcode paint fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

There are many solutions online, but the following is the easiest to understand. Thanks the author! https://discuss.leetcode.com/topic/31093/easy-to-understand-java-o-n-runtime-o-1-space

w(n) number of ways to paint n posts

p(n) color of the nth post

w(n) consists of two cases:

1.p(n) == p(n –

• ### Leetcode H-Index

Problem Description

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 5 papers in total and each of them had received 3,

• ### Leetcode Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

整体思路是：整数的32个bits，出现次数mod 3后必余0, 1, 2
其中余1的就是答案

int singleNumber(int A[], int n) {
int n1=0, n2=0; // n1为mod 3余1的bits，n2为mod 3余2的bits
for (int i=0; i<n; ++i) {
int n0 = ~(n1|n2); // 若非余1也非余2，就是余0了
// 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2
n2 = (n2&~A[i]) | (n1&A[i]);
// 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1
n1 = (n1&~A[i]) | (n0&A[i]);
}
return n1;

• ### Leetcode Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Analysis

We can use a hashset to record all the elements in the array. Then for each number in the array, we expand to both left and right and record the length of the expansion.

See the following Java code:

• ### Leetcode Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example:
S = “rabbbit”, T = “rabbit”

Return 3.

Java solution

Here are three solutions to solve this problem.

• ### LeetCode Serialize and Deserialize Binary Tree (Java)

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as “[1,2,3,null,null,4,5]”,

• ### LeetCode Patching Array

Given a sorted positive integer array nums and an integer n, 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 nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1],

• ### Leetcode Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see thek numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.