这篇只是个人为了加深对Markov Model的理解而做的学习笔记，基本是以易于理解的目的进行组织，所以可能有很多地方不太严禁。如有错误，还请不吝指出。

Markov Process

• 一个Markov Process是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型，其中n是影响下一个状态选择的（前）n个状态。

  最简单的Markov Process是一阶模型，它的状态选择仅与前一个状态有关。

• Markov Process有两个假设：

  • 系统在时刻t的状态只与时刻t-1处的状态相关（也称为无后效性）。

    用如下公式表示：P(qt=Sj|qt-1=Si,qt-2=Sk,…) = P(qt=Sj|qt-1=Si)，t为大于1的任意数值，Sk为任意状态

Unique Binary Search Trees

Description:

Given n, how many structurally unique BSTs (binary search trees) that store values 1…n?

Example:

Given n = 3, there are a total of 5 unique BST’s.

1           3    3       2      1
 \         /    /       / \      \
  3      2     1       1   3      2
 /      /       \                  \
2     1          2                  3

Permutation Index

Description:

Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

Example:

Given [1,2,4], return 1.

分析：

做过 next permutation 系列题的话自然能想到不断迭代直至最后一个，最后返回计数器的值即可。这种方法理论上自然是可行的，但是最坏情况下时间复杂度为 O(n!)，显然是不能接受的。由于这道题只是列出某给定 permutation 的相对顺序(也就是index)，故我们可从 permutation 的特点出发进行分析。

CS231n课程笔记，记录自己看懂和没看懂的地方。

Lecture 4

1. gradient的计算。

   • 在forward阶段就计算当前unit的local gradient。

   • 在backward阶段：local gradient * gradient from above。

2. add gate, max gate，mul gate

Subtree

Description:

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Notice

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Example:

Count of Smaller Numbers After Self

Description:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

Reverse Pairs

Description:

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.
return total of reverse pairs in A.

Example:

Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3

Interleaving String

Description:

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example:

For s1 = “aabcc”, s2 = “dbbca”

• When s3 = “aadbbcbcac”, return true.
• When s3 = “aadbbbaccc”, return false.

Edit Distance

Description:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Jump Game II

Description:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example: