LeetCode | Learn for Master
• ### [Leetcode] Find Permutation

By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.

On the other hand,

• ### [LeetCode] Android Unlock Patterns

Given an Android 3×3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern.
• ### Leetcode Group Shifted Strings

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”],
Return:

Note: For the return value, each inner list’s elements must follow the lexicographic order.

A better example:

[“eqdf”, “qcpr”]

((‘q’ –

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

• ### LeetCode Recover Binary Search Tree (java)

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Java Solution

We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,