Algorithms | Learn for Master - Part 2
• ### Longest Increasing Subsequence

Intro

The algorithms to find the longest increasing subsequence in a sequence are discussed in various places (including Wikipedia), but in my opinion their exposition is not intuitive.

Wikipedia:

M[j] — stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range ki.

Precise and succinct but not easy to parse and grasp.

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

• ### Longest Common Subsequence

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. It is a set of characters that appear in left-to-right order, but not necessarily consecutively.

Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.

Problem definition of Longest Common Subsequence

1. Given the first sequence which contains (m) symbols X = (x1, x2, x3, …, xm)
2. Given the second sequence which contains (n) symbols Y = (y1,
• ### 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 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,

• ### Leetcode Expression Add Operators (Java)

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.

Examples:

Analysis:

This problem can be solved using DFS algorithm. For example, given the input “123456“, suppose we encounter the last digit “6”, at which we already have the result of solve(“12345“). Then there are three cases:

solve(“123456”) = solve(“12345”) + 6

solve(“123456”) = solve(“12345”) – 6

solve(“123456”) = cal( solve(“12345”) ,

• ### Leetcode Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Analysis
This problem can be easily solved using a recursive algorithm.  We defined a method with the following signature:

equal(left, right)

then we recursively call equal(left.left, right.right) and equal(left.right, right.left).

The method returns false as long as only one of the two nodes is null,

• ### Leetcode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

Analysis

To solve this problem, we keep two pointers pre and cur when scanning the LinkedList. Once the current node’s value equals to the target value, we remove the cur node by set pre.next = cur.next;

To make the implementation easier,

• ### Leetcode Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4after calling your function.

Analysis

This problem can be easily solved by replacing the current node’s value with its next node’s value, then delete the next node. If the current node is the last node, just set it as null.

Java Solution:

Reference:

• ### Leetcode Intersection of Two Arrays

Intersection of Two unsorted Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Analysis

Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays