使用消元法求解方程组

在Lecture 1. The Geometry of Linear Equations中, 提到了使用消元法来求解线性方程组. 事实上消元法就如高中时候所学的, 将方程乘上某个系数使得某个未知数可以被消除. 只不过, 消元法是以线性代数的语言, 使用矩阵来进行运算.

假如有一个线性方程组如下:

用矩阵的形式来表示这个方程组则是如下:

使用消元法, 我们可以知道一个矩阵是”好”(非奇异, 可逆)的, 还是”坏”(奇异, 不可逆)的. 如果是一个性质良好的矩阵, 我们可以使用回代法来求出未知数. 如果是个性质没那么好的矩阵, 我们可以求出其他的一些东西.

首先, 消元的目的是将矩阵每一列只留下一个数, 其他消为0. 为了消元, 我们可以将任意一行乘上某个实数, 然后另一行减去这一行.

以这个矩阵来说:

在第一次消元时, 我们取第一行, 并从第二行减去三倍的第一行. 此时第一列只有第一行有非零数, 其他都为0. 此时, (1, 1)位置的1被称为主元. 而消元法的目标, 就是将矩阵消元到只有

• Leetcode-1-两数之和

• Leetcode-100-相同的树

• Leetcode-101-对称二叉树

• Leetcode-13-罗马文字转整数

• Leetcode-19-删除链表的倒数第N个节点

• Leetcode-191-位1的个数

• Leetcode-20-有效的括号

• Leetcode-202-快乐数

• Leetcode-21-合并两个有序链表

• Leetcode-225-用队列实现栈

• Leetcode-23-合并K个排序链表

• Leetcode-231-2的幂

• Leetcode-232-用栈实现队列

• Leetcode-24-两两交换链表中的节点

• Leetcode-26-删除排序数组中的重复项

• Leetcode-268-缺失数字

• Leetcode-27-移除元素

• Leetcode-278-第一个错误的

• Leetcode-28-实现str-str

• Leetcode-292-Nim游戏

• Leetcode-338-比特位计数

• Leetcode-35-搜索插入位置

• Leetcode-389-找不同

• Leetcode-412-FizzBuzz

• Leetcode-537-复数乘法

• Leetcode-62-不同路径

• Leetcode-657-机器人能否返回原点

• Leetcode-66-加一

• Leetcode-71-简化路径

• Leetcode-796-到达终点

• Leetcode-8-字符串转换整数-atoi

• Leetcode-896-单调数列

• Leetcode-897-递增顺序查找树

• Leetcode-9-回文数

线性方程式

线性方程式组由一组线性方程组合而成. 比如:

而上述的线性方程组以矩阵的语言来描述, 则是:

其中, $A$是方程组的系数矩阵, $x$为未知变量组成的(列)向量, $b$为常量向量.
而后, 有了矩阵我们便可以做出矩阵的图像.

二阶矩阵的行向量图像

而求解这个线性方程组的一个几个方法则是, 将$2x-y=0$与$-x+-2y=3$的图像画出来, 找到两个线的交点. 这一交点就是满足两个线性方程的解.

二阶矩阵的列向量图像

而另一种矩阵的向量图像是列向量的图像, 而列向量的图像更能体现线性代数的本质.

在用列向量描述时, 原方程组变形为以下形式:

则求解向量
$\begin{bmatrix}
2 \\ -1\end{bmatrix}$
与向量
$\begin{bmatrix}
-1 \\ 2
\end{bmatrix}$
的怎样的线性组合可以得到向量
$\begin{bmatrix}
0 \\ 3
\end{bmatrix}$.

如图所示, 我们可以发现$x = 1$, $y=2$.

也就是一个$v_1=(2, -1)^T$ 加上两个$v_2=(-1, 2)^T$.

所有的线性组合

如果我们取两个列向量的所有线性组合, 我们会得到什么呢?

事实上, 如果我们取一对二维的向量, 求这对向量的所有线性组合的集合, 所得到的结果有三种:

1. 这两个向量是不共线的非零向量, 此时会得到一整个二维平面.
2. 这两个向量共线或者其中一个是零向量, 此时只会得到一条与其中一个向量共线的直线.
3. 这两个向量都为零向量, 则此时只会得到原点.

几何上来看, 如果有两个不共线的非零向量 $v_1$ 与 $v_2$, 其中一个向量可以分为两个相互正交的分量 $(v_2 =x_0 + y_0), x_0 \perp y_0$ , 其中有一个分量$(x_0)$是和另一个向量相垂直的. 这样, 那个向量$(v_1)$和与相垂直的的分量$(x_0)$可以取线性组合, 其线性组合的集合是整个$\Bbb{R}^2$空间.

而在两个向量共线或其中一个向量是零向量时, 一个向量无法分出垂直于另一个向量的分量, 所以无法取到整个$\Bbb{R}^2$空间, 其线性组合只能取到与向量共线的直线上的所有点.

在两个向量均为零向量时, 无论如何去线性组合, 都不会离开原点, 则其线性组合只能取到原点.

三阶矩阵的列向量图像

在分析二元一次方程式组后, 我们继续看三元一次方程式组, 如下便是一个”好”的三元一次方程式组:

其中, 每一个方程对应着$\Bbb{R}^3$中的一个平面. 如图:

而求解这三个方程则要找到其中三个平面的交点.

但是没有软件来绘图我们很难去想象一个三维的空间其中有三个平面交于某一点.所以我们使用列向量与矩阵.

其列向量的图像为:

用矩阵来描述则是:

同样的, 我们用线性组合来形容$Ax=b$, 则是如下形式:

事实上, 例子的矩阵$A$与右侧常量$b$选的很好所以很容易就能看出:

也就是第三个向量$v_3$与右侧常量向量$b$共线(事实上此处是相等但是可以将相等看做是共线的一种),
此时只要$x$, $y$取0时, 则可以得到答案.

求解所有Ax=b

那么我们进一步思考, 对于任何右侧常数项$b$, 我们是否可以求出所有$Ax=b$?

也就是, 三个列向量通过线性组合, 是否可以得到$\Bbb{R^3}$ 上面的任何一点?

如果有, 这三个列向量需要满足怎样的条件?

如果没有, 这三个列向量又要满足什么条件?

如果我们求三个向量的线性组合, 其结果则有以下的可能性:

1. 任意两个非共线的向量线性组合后得到一个平面, 第三个向量不与平面相平行, 也就是它可以分出一个垂直于平面的分量, 则三个向量的线性组合可以得到整个$\Bbb{R^3}$
2. 有两个向量非共线, 其线性组合得到一个平面, 但是第三个向量与平面平行(或为零向量), 无法分出一个垂直于平面的分量. 此时, 其线性组合所得到的是$\Bbb{R^3}$中的一个平面.
3. 一个向量与其他两个向量共线(或为零向量), 此时, 只能得到$\Bbb{R^3}$中与向量共线的一条直线
4. 三个向量均为零向量, 得到原点.

事实上, 用消元法, 我们可以检测一个矩阵是否可以求解任何$Ax=b$.

如果三个向量的线性组合可以覆盖整个$\Bbb{R^3}$, 则称这三个向量线性无关.如果其中一个向量是其他两个向量的线性组合, 则称这三个向量线性相关.

当某个方阵中的列向量均线性无关, 则称这个方阵是非奇异的.
如果方阵中某一个列向量可以用其他列向量求线性组合所得到, 则称这个方阵是奇异的.

题目描述

test

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。

由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的.

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。

实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

1
2
3
4
5
6
7

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 `isBadVersion(3)` -> false
调用 `isBadVersion(5)` -> true
调用 `isBadVersion(4)` -> true

所以，4 是第一个错误的版本。

题目分析

简单的二分搜索. 每次找区间[from, to]中间的元素查看是否为badVersion, 如果是, 则查找[from, (to - from) / 2], 否则查找[(to - from) / 2 + 1, to], 直到from == to 或者 from == to - 1, 此时判断如果isBadVersion(from) == isBadVersion(to)则返回from, 否则返回to.

源码(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13

bool isBadVersion(int version);

class Solution {
public:
    int binarySearch(int from, int to) {
        if(from == to || from == to - 1) return isBadVersion(from) ? from : to;
        return isBadVersion(from + (to - from) / 2) ? binarySearch(from, from + (to - from) / 2) : binarySearch(from + (to - from) / 2 + 1, to);
    }

    int firstBadVersion(int n) {
        return binarySearch(1, n);
    }
};

进阶问题

如果isBadVersion()函数只会返回当前位的状态, 并不知道状态true和false哪一个是错误的, 这种情况下要怎么解决呢?

源码(进阶)

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

    bool isBadVersion(int version);

    class Solution {
    public:
        int binarySearch(int from, int to) {
            // 如果**所搜索区间**的第一位和最后一位相同则是**区间**第一位开始出错
            if(isBadVersion(from) == isBadVersion(to)) return from;
            // 如果所搜索区间的起始位置和结束位置相同或者起始位置是结束位置-1
            // 则如果起始位置
            if(from == to || to == from + 1) return isBadVersion(from) == isBadVersion(to) ? from : to;
            return isBadVersion(from) != isBadVersion(from + (to - from) / 2) ? binarySearch(from, from + (to - from) / 2) : binarySearch(from + (to - from) / 2 + 1, to);
        }

        int firstBadVersion(int n) {
            return binarySearch(1, n);
        }
};

梯度下降

公式如下:

$θ_i = θ_i - α \frac{\delta}{\delta θ_i}J(θ)$

$θ_i$ 为第i个特征

$J(\theta)$ 为损失函数

$α$ 为学习率

正规方程

假如训练数据如下:

则第i组训练数据成特征向量$x^{(i)}$

$x^{(i)} = \left[
\begin{matrix}
x^{(i)}_0\\
x^{(i)}_1\\
x^{(i)}_2\\
⋮\\
x^{(i)}_n
\end{matrix}
\right]$

将m组训练数据组成一个矩阵$X$:

$X=\left[\begin{matrix}
{x^{(1)}}^T\\
{x^{(2)}}^T\\
⋮\\
{x^{(m)}}^T
\end{matrix}\right]=\left[\begin{matrix}
x^{(1)}_0&x^{(1)}_1&⋯&x^{(1)}_n\\
x^{(2)}_0&x^{(2)}_1&⋯&x^{(2)}_n\\
⋮\\
x^{(m)}_0&x^{(m)}_1&⋯&x^{(m)}_n
\end{matrix}\right]$ $(x_0 = 1)$

$y = \left[
\begin{matrix}
y^(1)\\
y^(2)\\
\vdots\\
y^(m)
\end{matrix}
\right]$

则$θ = (X^TX)^{-1}X^Ty$

这两种方法的区别

题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1:

1
2
3

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2:

1
2
3

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3:

1
2
3

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4:

1
2

输入："/a/./b/../../c/"
输出："/c"

示例 5:

1
2

输入："/a/../../b/../c//.//"
输出："/c"

示例 6:

1
2

输入："/a//b////c/d//././/.."
输出："/a/b/c"

题目分析

先将字符串以’/‘作为分隔分为子字符串, 再对每一个子字符串判断.

源码

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

class Solution {
public:
    string simplifyPath(string path) {
        stringstream ss(path);
        stack<string> st, res;
        string temp;
        while(getline(ss, temp, '/')) {
            if(temp == "") continue; // 空字符串或"."不操作
            if(temp == ".") continue;
            if(temp == "..") {
                // 子字符串为".."时判断是否有前置目录(栈是否为空)
                // 非空则栈首元素出栈
                if(!st.empty()) st.pop();
                continue;
            }
            st.push(temp);
        }
        temp = "/";
        while(!st.empty()) { // 将元素反序
            res.push(st.top());
            st.pop();
        }
        while(!res.empty()) {
            temp += res.top() + "/";
            res.pop();
        }
        if(temp != "/") temp.pop_back();
        return temp;
    }
};

题目描述

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。
如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
      因此返回 INT_MIN (−231) 。

题目分析

先将字符串头部的空格消去, 之后使用stringstream来读取字符串并将值存至一个int型变量中, 返回此变量.

源码

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int myAtoi(string str) {
        while(*str.begin() == ' ') str.erase(str.begin());
        if(str == "") return 0;
        stringstream ss;
        ss<<str;
        int n;
        ss>>n;
        return n;
    }
};

题目描述

题目分析

源码

1
2

题目描述

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

题目分析

一般方法:

用两个队列来模拟栈.

骚气方法:

先入队列, 然后不停地把队头元素放到队尾(队列长度-1次).

源码(一般方法)

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

class MyStack {
public:
    queue<int> main;
    queue<int> cache;
    /** Initialize your data structure here. */
    MyStack() {

    }

    /*****------------------Main Method------------------*****/

    /** Push element x onto stack. */
    void push(int x) {
        while(!main.empty()) { // 将主队列的元素入缓存队列
            cache.push(main.front());
            main.pop();
        }
        main.push(x); // 入队元素入主队列
        while(!cache.empty()) { // 将缓存队列元素压入主队列
            main.push(cache.front());
            cache.pop();
        }
    }

    /*****------------------Main Method------------------*****/

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int res = main.front();
        main.pop();
        return res;
    }

    /** Get the top element. */
    int top() {
        return main.front();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return main.empty();
    }
};

源码(骚气方法)

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

class MyStack {
public:
    queue<int> main;
    /** Initialize your data structure here. */
    MyStack() {

    }

    /*****------------------Main Method------------------*****/

    /** Push element x onto stack. */
    void push(int x) {
        main.push(x); // 将待入队列元素压入队列
        for(int i=0; i<main.size()-1; ++i) {
            main.push(main.front()); // 将队首元素压入队列
            main.pop(); // 将队首元素弹出队列
        }
    }

    /*****------------------Main Method------------------*****/

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int res = main.front();
        main.pop();
        return res;
    }

    /** Get the top element. */
    int top() {
        return main.front();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return main.empty();
    }
};

题目描述

使用栈实现队列的下列操作：

push(x) — 将一个元素放入队列的尾部。
pop() — 从队列首部移除元素。
peek() — 返回队列首部的元素。
empty() — 返回队列是否为空。

示例:

1
2
3
4
5
6
7

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作,也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。
你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

题目分析

用两个栈模拟一个队列.

源码

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

class MyQueue {
public:
    stack<int> main;
    stack<int> cache;

    /** Initialize your data structure here. */
    MyQueue() {

    }

    /*****------------------Main Method------------------*****/

    /** Push element x to the back of queue. */
    void push(int x) {
        while(!main.empty()) { // 将主栈压入缓存栈
            cache.push(main.top());
            main.pop();
        }
        main.push(x); // 将入栈元素压入主栈
        while(!cache.empty()) { // 将缓存栈元素压回主栈
            main.push(cache.top());
            cache.pop();
        }
    }

    /*****------------------Main Method------------------*****/

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int res = main.top();
        main.pop();
        return res;
    }

    /** Get the front element. */
    int peek() {
        return main.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return main.empty();
    }
};