By Long Luo

从古到今，人类一直希望机器能够像人一样，代替人们从事各种工作。

机器学习（Machine Learning）是一门引人入胜的领域，通过模拟人脑神经网络，使计算机能够从数据中学习和改进，以完成各种任务。

深度学习(Deep Learning)

神经网络(Neutral Network)

3Blue1Brown 的 深度学习之神经网络的结构 Part 1 。

在当今数字化的时代，机器学习和神经网络成为了引领人工智能发展的核心技术。其中，手写数字识别作为机器学习领域的一个经典问题，为我们深入探索神经网络的原理提供了绝佳的案例。

这篇文章将首先介绍什么是神经网络，神经网络的实现原理，之后以经典的手写数字识别为例来加强对机器学习的理解。

什么是神经网络？

神经系统的工作方式与身体的其他器官完全不同。在身体的许多器官中，同类型的细胞执行同样的功能，单个细胞的工作就代表整个器官的功能，器官的功能也就是其中每个细胞功能的总和。例如肝脏中的每个肝细胞都执行同样的化学合成和解毒功能，小肠上皮细胞都执行同样的吸收营养的功能，每条肌肉中的肌肉细胞都执行同样的收缩功能等。它们的功能状态受整体器官的控制，细胞之间的信息交换比较少。

与此相反，神经系统以网络的方式进行工作，神经细胞之间有频繁和复杂的信息传递，每个神经细胞的状态都根据其在网络中的位置不同而与其它神经细胞不同，单个神经细胞功能也不能代表整个神经系统的功能。

人脑神经网络是由大量的神经元组成，通过突触连接形成复杂的网络。机器学习通过人脑神经网络的启发，构建人工神经网络模型。人工神经网络由节点（神经元）和连接它们的权重组成。权重表示神经元之间的连接强度，信息通过这些连接在网络中传递和处理。

神经网络是如何工作的？

首先，让我们了解一下神经网络的基本结构。神经网络由输入层、隐藏层和输出层组成。输入层接收手写数字的像素值作为输入，隐藏层则负责提取输入特征，输出层给出最终的识别结果。每个神经元都与上一层的所有神经元连接，并带有权重，这些权重决定了每个神经元对信息的贡献程度。

为了训练神经网络，我们需要大量的手写数字样本作为训练数据。训练过程中，神经网络会根据输入数据的真实标签与预测标签之间的误差，通过反向传播算法来更新神经元之间的权重，从而逐渐提高准确性。反向传播算法通过计算每个神经元的梯度，根据梯度的大小来调整权重，使得预测结果与真实标签更加接近。

对于手写数字识别问题，隐藏层的神经元可以学习到不同笔画、曲线等特征，输出层的神经元则对应0到9的数字标签。通过大量的样本和迭代训练，神经网络可以逐渐学习到正确的特征提取和数字分类规则，从而实现准确的手写数字识别。

除了神经网络的结构和训练方法外，还有一些优化技术可以提高手写数字识别的性能。例如，卷积神经网络（Convolutional Neural Networks，CNN）能够有效地利用图像的空间结构特征，提高了识别的准确性和效率。另外，激活函数的选择、正则化技术的应用以及适当的优化算法等都对神经网络的性能起到重要作用。

神经网络是一种受到人脑神经元启发的算法模型，通过多个层次的神经元组成，可以进行复杂的数据处理和模式识别。在手写数字识别中，我们希望机器能够通过训练学习，准确地识别手写的数字。接下来，我们将揭开神经网络的奥秘。

$$S(x) = {\frac {1}{1 + e^{-x}}} = {\frac {e^{x}}{e^{x} + 1}} = 1 - S(-x)$$

By Frank Luo

This is my answers of the MRI Tutorial Videos How MRI Works - Part 2: The Spin Echo and How MRI Works - Part 3：Fourier Transform and K-Space .

Part 2: The Spin Echo

Questions

Answers

Question 1：

1. The Boltzmann Magetization $M_0 = \frac{N {\gamma}^2 \hbar^2 B_0}{4 k T}$, then after elimination the units is $J/T$.
2. The Polarization is $P = \frac{\gamma \hbar B_0}{2kT}$, then after elimination we can get that $P$ is a special number depends on the material, no SI units.

Question 2：

1. The polarization is $P = \frac{51-49}{100} = 0.02$ .
2. The magnet field strength should be $B_0 = \frac{0.02}{0.0000034} \approx 5882T$ .
3. The temperature should be $T = \frac{300 \times 0.0000034}{0.02} = 0.051K$.

Question 3：

1. Since the Boltzmann Magetization Equation is $M = M_0(1- e^{-\frac{t}{T_1}}) e^{-\frac{t}{T_2}}$ , so we can calculate the signal.

The signal of Tissue $A$ : $M_A = M_0(1- e^{-\frac{150}{300}}) e^{-\frac{12.5}{20}} = 0.21$ .
The signal of Tissue $B$ : $M_B = M_0(1- e^{-\frac{150}{200}}) e^{-\frac{12.5}{40}} = 0.38$ .

Surely Tissue $B$ will deliver more signal.

2. We have calculated that Tissue $B$ will deliver more signal if both Tissue $A$ and $B$ has the same Boltzmann Magetization.

If Tissue $A$ is $85\%$ of Tissue $B$, then the Tissue $A$ signal will become lesser, so Tissue $B$ deliver more signal.

3. Let function $f(t) = M_{0A}(1- e^{-\frac{TR}{T_{1A}}})e^{-\frac{t}{T_{2A}}} - M_{0B}(1- e^{-\frac{TR}{T_{1B}}})e^{-\frac{t}{T_{2B}}}$ reprent the signal of time $t$.

Consider the function: $f(t) = (1 - e^{-\frac{150}{200}}) e^{-\frac{t}{40}} - (1- e^{-\frac{150}{300}}) e^{-\frac{t}{20}}$ reaches its PEAK at about $t = 16$, so the $TE$ should be $TE = 32ms$.

By Long Luo

最近在 YouTube 上看了 Freya Holmér 的 贝塞尔曲线之美 的视频，这个视频做的非常好，通俗易懂地解释了贝塞尔曲线的实现原理，通过结合代码，大致了解了 Bezier Curve^[1] 的数学原理。

之前用过 TI 的一个开发板，里面有个屏保的程序，可以在开发板的屏幕上 屏保 ，用的是 Bresneham^[2] 算法，源码如下 。Bresneham 算法先挖个坑，后续会填上，今天这篇文章主要还是分析贝塞尔曲线(Bezier Curve)。

贝塞尔曲线是什么？

贝塞尔曲线是由法国工程师 Pierre Bézier^[3] 在 1962 年提出的数学概念，它以其优雅的曲线特性和广泛的应用领域而闻名。

我写了一个贝塞尔(Bezier Curve) 曲线的在线交互式动画，传送门如下：

http://www.longluo.me/projects/bezier/

贝塞尔曲线的数学原理

这一章节待完善！！！

贝塞尔曲线通过控制点来定义曲线的形状，这些控制点决定了曲线在起始点和结束点之间的路径。通过调整控制点的位置，可以改变曲线的形状、弯曲度和方向。贝塞尔曲线的绘制基于插值的概念，它通过在控制点之间进行插值计算，得到平滑的曲线。

$P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$ ，

$$\begin{cases} x = x_1 + t (x_2 - x_1) \\ y = y_1 + t (y_2 - y_1) \end{cases}$$

贝塞尔曲线的数学表达方式是通过多项式来定义的。在一维空间中，$n$ 次贝塞尔曲线的公式为：

$$B(t) = P_0 + (P_1 - P_0)t= (1-t)P_0 + tP_1, t\in [0,1]$$

$$B(t) = \sum_{i=0}^{n} \binom{n}{i}P_i(1 - t)^{n-i}t^i = \binom{n}{0}P_0(1-t)^{n}t^0 + \binom{n}{1}P_1(1-t)^{n-1}t^1 + \cdots + \binom{n}{n-1}P_{n-1}(1-t)^{n-1}t^{n-1} + \binom{n}{n}P_{n}(1-t)^{n}t^{n}, t\in[0,1]$$

一般地， n 个控制点的贝塞尔曲线的递归版本为：

$$P_0^{n} = (1 - t)P_0^{n-1} + tP_1^{n-1}, t\in [0,1]$$

贝塞尔曲线的应用场合

计算机图形学：贝塞尔曲线被广泛应用于计算机图形学中的曲线绘制和造型。它可以用来绘制平滑的曲线、实现曲线的动画效果，以及创建复杂的几何形状。

平面设计和艺术：贝塞尔曲线在平面设计和艺术创作中也有广泛应用。设计师可以利用贝塞尔曲线的灵活性和精确性，绘制出符合设计要求的曲线和形状。

工程和建筑设计：贝塞尔曲线在工程和建筑设计中用于绘制道路、河流、管道等具有曲线特征的结构。它可以帮助工程师和建筑师准确地描述和模拟复杂的曲线路径。

贝塞尔曲线的缺点

尽管贝塞尔曲线在许多场合下都有广泛应用，但也存在一些不适用的情况。以下是一些例子：

1. 高度精确的曲线：贝塞尔曲线是由有限个控制点所定义的，当需要绘制极其精确的曲线时，可能无法满足需求；
2. 曲率变化较大的曲线：贝塞尔曲线的控制点数量决定了曲线的平滑程度。在曲率变化较大的情况下，可能需要增加更多的控制点来准确描述曲线的形状；
3. 特殊曲线类型：某些特殊曲线类型，如圆或椭圆等，可能有更适合的数学表示方法，而不是使用贝塞尔曲线。

总结

贝塞尔曲线能够帮助我们创建平滑、灵活的曲线，适用于计算机图形学、平面设计、工程和建筑设计等领域。

参考文献

By Long Luo

This article is the solution Data Structures: Thought Process from HashMap to HashMap + Array of Problem 380. Insert Delete GetRandom O(1).

Intuition

It’s easy to think of using a Hash Table to achieve $O(1)$ time complexity for $\texttt{insert}$ and $\texttt{remove}$ operations. However, we need $O(1)$ time complexity to complete the $\texttt{getRandom}$ operation.

The Array structure can complete the operation of obtaining random elements in $O(1)$ time complexity, but it can’t completed the $\texttt{insert}$ and $\texttt{remove}$ operations in $O(1)$ time complexity.

So How?

Aha!!!

By Long Luo

今天 LeetCode 第320场周赛 中第一题是 2475. 数组中不等三元组的数目 ，本文是该题的题解，同时发表在 这里 。

参考了 @灵茶山艾府 的题解 非暴力做法 ，实际上我们可以不用先排序，而是先用 $\texttt{HashMap}$ 统计数组 $\textit{num}$ 元素频率。

之后遍历 $\texttt{HashMap}$ ，结果为：$\sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1])$ ，其中 $n$ 为 $\textit{nums}$ 的长度。

证明如下：

对于数组中的元素 $x$ ，可以得到：

• 小于 $x$ 的数有 $a$ 个；
• 等于 $x$ 的数有 $b$ 个；
• 大于 $x$ 的数有 $c$ 个。

那么 $x$ 对最终答案的贡献是 $abc$ 。

即使 $x$ 是三元组中的最大或最小值，由于 $i, j, k$ 的对称性，很明显其实和 $x$ 是中间值都是同一个答案。

证毕！

By Long Luo

This article is the solution It is Literally a Graph: DFS and Union Find of Problem 947. Most Stones Removed with Same Row or Column.

Intuition

We can find that this is a graph theory problem with analysis.

Imagine the stone on the 2D coordinate plane as the vertex of the graph, If the x-coord or the y-coord of two stones are the same, there is an edge between them.

This can be show as follows:

According to the rule that stones can be removed, we should remove those points that are in the same row or column with other points as late as possible. That is, the more points in the same row or column with point A, the later point A should be removed. In this way, we can delete as many points as possible through point A.

It can be found that all vertices in a connected graph can be deleted to only one vertex.

Since these vertices are in a connected graph, all vertices of the connected graph can be traversed by DFS or BFS.

Therefore: the maximum number of stones that can be removed = the number of all stones - the number of connected components.

By Long Luo

This article is the solution Two Heaps with the Follow Up’s Solution of Problem 295. Find Median from Data Stream.

Intuition

We can simply use a $\texttt{ArrayList}$ to record the number and sort the list, then we can easily get the median element of the list. However, the Time Complexity will be $O(n^2logn)$ and the Space Complexity is $O(n)$.

It surely will be TLE and we have to find a better solution.

Heap

We can use Two Priority Queues (Heaps) to maintain the data of the entire data stream.

The min Heap denoted as $\textit{queueMin}$ is used to maintain the number $\textit{num} \leq \textit{median}$. The max Heap denoted as $\textit{queueMax}$ is used to maintain the number $\textit{num} \gt \textit{median}$.

• When the total number of data stream elements is Even: $\texttt{queueMax.size()} = \texttt{queueMin.size()}$, the dynamic median is $\frac{\texttt{queueMax.peek()} + \texttt{queueMin.peek()}}{2}$;

• When the total number of data stream elements is Odd: $\texttt{queueMin.size()} = \texttt{queueMin.size()} + 1$, the dynamic median is $\texttt{queueMin.peek()}$.

By Long Luo

今天 LeetCode CN 的每日一题是 1668. 最大重复子字符串 ，本文是该题的题解，同时发表在 这里 。

思路

这道题有好几个方法：

1. API：使用 $String$ $API$ $\texttt{contains(CharSequence s)}$ 来判断 $\textit{sequence}$ 中是否存在拼接的 $N$ 个 $\textit{word}$ 字符串；
2. KMP: 使用 KMP 算法判断 $\textit{sequence}$ 中是否存在拼接的 $N$ 个 $\textit{word}$ 字符串；
3. 暴力：判断是否存在拼接的 $N$ 个 $\textit{word}$ ，虽然很简单，但代码要写的优雅简洁有难度。

API 方法最简单，但 KMP 算法比较复杂。看了一些题解里的暴力解法，大多数人的暴力解法写的太复杂。我自己写该题暴力解法也写了 $3$ 个版本，前 $2$ 个版本也很复杂，逐渐优化为目前的简洁优雅版本。

暴力解法使用 $2$ 个循环，第 $1$ 个循环，遍历 $\textit{sequence}$ 中的每个字符，判断是否和 $\texttt{word.charAt(0)}$ 相同，相同的话的进入下一步；

使用一个索引 $j$ ，$0 \le j \le len - i$ ，而这里 $\textit{word}$ 字符索引可以使用 $j \mod wLen$ 来获取，这是暴力解法中最优雅的地方。如果遇到不相同的字符，跳出循环。

最后更新最大重复子字符串，就是 $\textit{ans}$ 和 $j / wLen$ 的更大值。

中间其实还可以剪枝，但由于数据量比较小，就不加了。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int maxRepeating(String sequence, String word) {
        int sLen = sequence.length();
        int wLen = word.length();

        int ans = 0;

        for (int i = 0; i < sLen; i++) {
            if (sequence.charAt(i) != word.charAt(0)) {
                continue;
            }
            
            int j = 0;
            while (i + j < sLen && sequence.charAt(i + j) == word.charAt(j % wLen)) {
                j++;
            }

            ans = Math.max(ans, j / wLen);
        }

        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$ ，其中 $n$ 是字符串 $\textit{sequence}$ 长度，存在 $2$ 个循环，所以总时间复杂度为 $O(n^2)$ 。
• 空间复杂度：$O(1)$ 。

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

This article is the solution Why Greedy Works? of Problem 334. Increasing Triplet Subsequence.

Intution

We can easily find that whether there exists a triple of indices $(i, j, k)$ such that $i < j < k$ and $nums[i] < \textit{nums}[j] < \textit{nums}[k]$ only traversing the array once, but the problem is how to make our mind into algorithms.

Brute Force

It’s easy to use Brute Force way to solve this problem, but the time complexity is $O(n^3)$, it will TLE, so we need to find a better way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static boolean increasingTriplet(int[] nums) {
    if (nums == null || nums.length < 3) {
        return false;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            for (int k = j + 1; k < len; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: $O(n^3)$
• Space Complexity: $O(1)$

Dynamic Programming

We can also use DP method to solve it.

Let $dp[i]$ represents the maximum length of a increasing sequence.

$$dp[i] = \begin{cases} 1 & dp[i] \le dp[j], 0 < j < i \\ dp[j] + 1 & dp[i] > dp[j], 0 < j < i \end{cases}$$

By Long Luo

490. 迷宫 Medium
505. 迷宫 II Medium
499. 迷宫 III Hard

490. The Maze

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

        int m = maze.length;
        int n = maze[0].length;

        if (m * n <= 2) {
            return true;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);

        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();

            int x = curPos[0];
            int y = curPos[1];

            if (x == destination[0] && y == destination[1]) {
                return true;
            }

            for (int[] dir : dirs) {
                int nextX = x + dir[0];
                int nextY = y + dir[1];

                while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                }

                if (!visited[nextX - dir[0]][nextY - dir[1]]) {
                    visited[nextX - dir[0]][nextY - dir[1]] = true;
                    queue.offer(new int[]{nextX - dir[0], nextY - dir[1]});
                }
            }
        }

        return false;
    }
}