YifanChen's Blog

一个专注技术的新手程序员

0%

发表于 更新于 分类于

链接

链表理论基础
203.移除链表元素
707.设计链表
206.反转链表

知识

链表理论基础

链表是一种通过指针串联在一起的线性结构。每个节点等于数据域+指针域（存放指向下一个节点的指针）。最后一个节点的指针域指向null。头节点head。

img

单链表、双链表：既可以向前查询也可以向后查询。
循环链表：链表首尾相连（解决约瑟夫环问题）

链表在内存中不是连续分布的。其通过指针域的指针链接在内存中的各个节点。

链表的定义：
手写链表：

1
2
3
4
5
6
// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

通过上述构造函数初始化节点：ListNode* head = new ListNode(5);
使用默认构造函数初始化节点：

1
2
ListNode* head = new ListNode();
head->val = 5;

不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

添加节点：见图

数组和链表有不同的适用场景。数组适合数据量固定，频繁查找，较少增删的场景；链表适合数据量不固定，频繁增删，较少查询的场景。

203.移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        
    }
};

结构体中定义了两个变量和三个构造函数。class Solution中的removeElements函数返回的变量类型是ListNode*，即这个函数返回一个指向ListNode对象的指针。

如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点。如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

删除头节点：

  • 直接使用原来的链表来进行删除操作：头节点后移一位
  • 设置一个虚拟头结点在进行删除操作：原链表的所有节点就都可以按照统一的方式进行移除了，最后return dummyNode->next;

707.设计链表

  • void函数可以直接return，表示退出
  • 统一使用虚拟头节点的方式，便于进行增删改的操作
  • 变量名前加_表示是这个类的变量，而非局部变量，这是cpp中的一种约定俗成

206.反转链表

初次尝试

203.移除链表元素

对链表题我一直有点懵，不太熟悉链表题的格式，但是对用数组模拟链表倒是挺熟悉的。我知道算法的思路大致是：先定义一个虚的头节点，然后遍历链表，删去值等于val的节点，然后返回头节点指针指向的节点，就是新的头节点，但我不知道这种代码怎么写。

707.设计链表

这题yxc也教过，但是在他那里似乎是用数组模拟链表，实现链表的各种功能，而这里是调用链表完成函数中的功能，我认为这题不难，只是多个功能需要分别实现，单个功能的代码较为简单。这道题我基本会做，但处理边界条件时要倍加注意！！

206.反转链表

yxc也讲过这个题，但我也给完全忘了

实现

203.移除链表元素

方法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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头节点
        while (head != NULL && head -> val == val)
        {
            ListNode* tmp = head;
            head = head -> next;
            delete tmp;
        }

        // 删除非头节点
        ListNode* cur = head; // cur存储要删去的节点的前一个节点
        // 要删的节点cur->next不可为空, cur != NULL是考虑空链表的情况
        while (cur != NULL && cur -> next != NULL) 
        {
            if (cur -> next -> val == val)
            {
                ListNode* tmp = cur -> next;
                cur -> next = cur -> next -> next;
                delete tmp;
            }
            else cur = cur -> next; // 后移一位
        }
        return head;
    }
};

方法2: 加入虚拟头节点

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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 创建虚拟头节点
        ListNode* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        // 上面的两行代码：创建虚拟头节点可以简写为：
        // ListNode* dummyHead = new ListNode(0, head);
        // 或者ListNode* dummyHead = new ListNode();
        // dummyHead -> next = head;

        // 统一方法删去值为val的节点
        // 从虚拟头节点开始遍历, cur为目标节点的前一个节点
        // 此时因为加入了虚拟头节点，因此链表不可能为空，因此不再需要考虑链表为空的判断条件：cur != NULL
        ListNode* cur = dummyHead;
        while (cur -> next != NULL)
        {
            if (cur -> next -> val == val)
            {
                ListNode* tmp = cur -> next;
                cur -> next = cur -> next -> next;
                delete tmp;
            }
            else cur = cur -> next;
        }

        head = dummyHead -> next;
        delete dummyHead;
        return head;
    }
};

以方法2为主。

707.设计链表

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class MyLinkedList {
public:
    // 记住struct的写法
    struct LinkedList {
        int val;
        LinkedList* next;
        LinkedList(int x): val(x), next(NULL) {};
    };

    // 初始化, 带下划线的变量表示类中的变量，而非局部变量
    MyLinkedList() {
        _dummyHead = new LinkedList(0); // 虚拟头节点
        _size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index > ( _size - 1)) return -1;

        LinkedList* cur = _dummyHead -> next;

        while (index -- ) cur = cur -> next;

        return cur -> val;
    }
    
    void addAtHead(int val) {
        LinkedList* head = new LinkedList(val);
        head -> next = _dummyHead -> next;
        _dummyHead -> next = head;
        _size ++ ;
    }
    
    void addAtTail(int val) {
        LinkedList* tail = new LinkedList(val);

        LinkedList* cur = _dummyHead;
        // while循环中的条件不能是_size -- ，不然会破坏链表长度的准确性
        while(cur -> next != NULL) cur = cur -> next;
        cur -> next = tail;
        _size ++ ;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size || index < 0) return;

        LinkedList* cur = _dummyHead;
        LinkedList* node = new LinkedList(val);

        while(index -- ) cur = cur -> next;

        node -> next = cur -> next;
        cur -> next = node;
        _size ++ ;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= _size) return;
        LinkedList* cur = _dummyHead;
        while (index -- ) cur = cur -> next;
        LinkedList* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;
        _size -- ;
    }

private:
    LinkedList* _dummyHead;
    int _size;
};

206.反转链表（常考）

是考察对基础数据结构操作非常好的一道题目。先掌握双指针解法，再掌握递归的解法。根据双指针代码写出递归代码。

双指针解法

leetcode206.png

具体解法：由于不需要让翻转以后的链表的头节点为空，因此当cur指向NULL时，遍历结束。因此循环为：while(cur)，cur == NULL为遍历的终止条件。

更新cur和pre的方式：用临时节点将cur的下一个节点保存下来。否则一旦反转后cur的写一个节点就会丢失（反转后的链表的下一个节点是pre）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;

        while (cur)
        {
            ListNode* tmp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

递归解法1

按照双指针的思路写递归的代码。递归的代码更简短但更难懂。

具体解法：定义一个reverse函数，其中有两个参数，即reverse(cur, pre)。

在主函数中调用reverse函数，需要传入两个参数cur和pre，前者对应于双指针解法中的head，后者对应于双指针解法中的null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    // 仿照双指针解法，递归函数中需要传入两个参数：cur和pre
    ListNode* reverse(ListNode* cur, ListNode* pre)
    {
        // 先检查递归的终止条件，同双指针解法
        if (cur == NULL) return pre;
        
        // 再执行递归的步骤
        // 同双指针解法中tmp = cur -> next, cur -> next = pre, pre = cur, cur = tmp
        ListNode* tmp = cur -> next;
        cur -> next = pre;
        return reverse(tmp, cur);
    }

    ListNode* reverseList(ListNode* head) {
        // 双指针解法中初始时cur = head, pre = NULL
        return reverse(head, NULL); 
    }
};

递归解法2

另一种递归解法，思路和递归解法1完全不同，我认为相比于递归解法1更好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 先判断终止条件是否成立
        if (head == NULL) return NULL; // 空链表，返回空
        if (head->next == NULL) return head; // 递归结束，返回反转后链表的head

        // 执行递归流程
        ListNode* last = reverseList(head->next); // 从第二个节点开始反转链表
        // 将原来的头节点接到反转后链表的尾节点之后，反转后链表的尾节点是head->next
        head->next->next = head; 
        head->next = NULL; // 尾节点指向空
        return last; // 返回反转后链表的头节点
    }
};

心得与备忘录

通用方法

  1. 插入虚拟头节点dummyHead，可以避免空链表并避免对头节点操作的特判
  2. 创建一个当前节点cur，对整个链表进行遍历（cur = cur->next），而不用链表中原本存在的节点对链表进行遍历
  3. NULL节点表示不存在的节点；虚拟节点实际上是存在的，其值为0，是人为创建的节点
  4. 递归时，需要先检查递归的终止条件，然后执行递归步骤

203.移除链表元素

  1. 想要删除一个节点，需要先用tmp存下它，然后再delete删去之。
  2. 以后写，尽量采用方法2，即加入虚拟头节点。
  3. cur -> next表示的是cur节点的next变量（即指针域），而cur -> val表示的是cur节点的val变量（即节点的值）。通过构造函数也可以给这两个变量直接赋值。
  4. 在方法1中，一定要加上判断条件cur != NULL，因为当链表为空时，while (cur -> next != NULL) 这个条件将尝试访问 NULL 指针的 next 成员，这将触发未定义行为，从而导致程序报错。在方法2中，则不需要加上判断条件cur != NULL，因为有虚拟头节点的存在，链表不可能为空，至少有一个节点（即虚拟头节点）。当然，在方法2中加上这个判断条件也不会影响程序的正常运行。

707.设计链表

  1. 想清楚一个极端情况：返回第0个节点的值，是否会出现空指针异常等错误。
  2. cur节点都赋值为_dummyHead
  3. 注意删除第n个节点时的内存释放问题
  4. 在第n个节点前增加或者删除一个节点，应该让cur指向第n-1个节点，cur->next指向第n个节点。
  5. 注意插入节点时先更新后面的边，再更新前面的边
  6. 只要传入参数index，就要记得对index进行判断，排除掉不需处理的情况。对get函数和deleteAtIndex函数，判断条件都是index < 0 || index > _size - 1，但对addAtIndex函数，判断条件是index < 0 || index > _size，因为index = _size表示将节点插入到链表的末尾。
  7. 别忘记_size ++ / _size —

206.反转链表

双指针解法

代码量少，思维量大！需要明确：cur和pre初始的取值；循环终止的条件；如何更新pre和cur。画图理解即可。

递归解法

递归解法1参照双指针解法写。这题推荐就用双指针解法，比较清楚明白，且空间复杂度为O(1)，优于递归解法的空间复杂度O(n)。递归解法2相比于递归解法1更好理解。

发表于 更新于 分类于

链接

视频

https://www.bilibili.com/video/BV1QB4y1D7ep

https://www.bilibili.com/video/BV1tZ4y1q7XE

https://www.bilibili.com/video/BV1SL4y1N7mV/

文章

https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80

题目

https://leetcode.com/problems/squares-of-a-sorted-array/

https://leetcode.com/problems/minimum-size-subarray-sum/

https://leetcode.com/problems/spiral-matrix-ii/

知识

  1. cpp中sort函数的用法：sort(a.begin(), a.end())，排序后的结果就存储在a中。
  2. vector<int> result(A.size(), 0);的意思是创建一个长度为A.size()，数值全部为0的vector。

  3. cpp中的问号表达式——条件运算符

    len = sub < len ? sub: len;表示若sub < len，则len = sub；否则len等于len，保持不变。

    len == INT32_MAX ? 0: len;表示若len等于INT32_MAX，则l表达式值为0，否则表达式值为len。

  4. INT32_MAX：这是一个在 C++ 中定义的常量，代表 32 位整数类型（即 int 类型）可以表示的最大值。
  5. 初始化一个二维vector，让其中的元素全部为0：vector<vector<int>> res(n, vector<int>(n, 0));，即初始化一个全部元素为0的一维数组，然后将其复制n遍。

初次尝试

977.有序数组的平方

暴力做法，先平方，再排序。双指针做法有点思路，但由于不知道如何创建一个值为0且长度与nums相同的vector，因此不能完全正确地写出代码。

209.长度最小的子数组

滑动窗口我听yxc讲过，但是已经完全忘了，直接看视频讲解，然后看文字版讲解。

暴力解法：

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 minSubArrayLen(int target, vector<int>& nums) {
        int len = INT32_MAX;
        int sub = 0;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int s = 0;
            for (int j = i; j < nums.size(); j ++ )
            {
                s += nums[j];
                if (s >= target)
                {
                    sub = j - i + 1;
                    len = len < sub ? len: sub;
                    break;
                }
            }
        }

        return len == INT32_MAX ? 0: len;
    }
};

暴力做法超时了。还是需要滑动窗口。

59.螺旋矩阵II

yxc讲过这题，我印象中涉及到一个向量，撞墙了就拐弯，遇到自己之前走过的地方也拐弯，挺生动形象的，但我已经忘记怎么写了。

实现

977.有序数组的平方

取平方后，最大的元素一定在原数组的两边。故用左右指针，从数组的两边向中间推进。需要一个新的数组来存储结果，新的数组的下标由大到小来更新。

for+if写法

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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 创建ans数组来存储答案
        vector<int> ans(nums.size(), 0);

        int n = nums.size() - 1;

        // 由于每次循环都要比较两个数的平方的大小关系，因此将最后一个数放入ans时
        // i和j都会等于该数的索引，因此要求i可以等于j
        for (int i = 0, j = nums.size() - 1; i <= j; )
        {
            if (nums[i] * nums[i] <= nums[j] * nums[j])
            {
                ans[n -- ] = nums[j] * nums[j];
                j -- ;
            }
            else
            {
                ans[n -- ] = nums[i] * nums[i];
                i ++ ;
            }
        }
        return ans;
    }
};

for + while写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(), 0);

        int k = nums.size() - 1;

        for (int l = 0, r = nums.size() - 1; l <= r; )
        {
            // 一定要记得加上l <= r的条件
            while (l <= r && nums[l] * nums[l] >= nums[r] * nums[r])
            {
                res[k -- ] = nums[l] * nums[l];
                l ++ ;
            }
            while (l <= r && nums[l] * nums[l] < nums[r] * nums[r])
            {
                res[k -- ] = nums[r] * nums[r];
                r -- ;
            }
        }
        return res;
    }
};

while+while写法

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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans(nums.size(), 0);

        int k = nums.size() - 1;

        int i = 0, j = nums.size() - 1;
        while (i <= j)
        {
            while (i <= j && nums[i] * nums[i] <= nums[j] * nums[j])
            {
                ans[k -- ] = nums[j] * nums[j];
                j -- ;
            }

            while (i <= j && nums[i] * nums[i] > nums[j] * nums[j])
            {
                ans[k -- ] = nums[i] * nums[i];
                i ++ ;
            }
        }
        return ans;
    }
};

while + if写法

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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(), 0);

        int k = nums.size() - 1;

        int l = 0, r = k;

        while (l <= r)
        {
            if (nums[l] * nums[l] <= nums[r] * nums[r])
            {
                res[k -- ] = nums[r] * nums[r];
                r -- ;
            }
            else
            {
                res[k -- ] = nums[l] * nums[l];
                l ++ ;
            }
        }
        return res;
    }
};

209.长度最小的子数组

其实核心思想也是双指针，只不过取两指针中间的集合像是一个正在滑动的窗口，因此也叫滑动窗口。用一个for循环替代暴力做法里的两个for循环。一个for循环中的循环变量j若表示滑动窗口的起始位置，则j在遍历的过程中，终止位置也需要去遍历，这与暴力做法无异。因此for循环中的循环变量j表示滑动窗口的终止位置，起始位置需要动态移动地去获得。滑动窗口的精髓在于如何移动起始位置。

若滑动窗口的起始位置和终止位置间的数的和>=target，那么起止位置可以向后移动，即窗口可以缩小，看缩小后的窗口是否还可以符合条件。若满足条件，则可更新滑动窗口。更新滑动窗口时，需要同时更新滑动窗口的起始位置和滑动窗口中元素和的值。

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
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = INT32_MAX; // result
        int i = 0; // i是滑动窗口的起始位置
        int sub = 0; // 窗口长度
        int sum = 0; // 窗口之和

        // j是滑动窗口的终止位置
        for (int j = 0; j < nums.size(); j ++ )
        {
            sum += nums[j]; // 将新的终止位置放到窗口的和中去

            // 更新滑动窗口
            while(sum >= target)
            {
                sub = j - i + 1; 
                len = len < sub ? len: sub;
                sum -= nums[i];
                i ++ ;
            }
        }
        return len == INT32_MAX ? 0: len;
    }
};

59.螺旋矩阵II

不涉及算法，是道模拟题。不易写对的原因是转圈的过程中需要处理的边界条件很多。

边界条件：正方形的4个边界点

循环不变量：
循环——不断转圈
不变量——对每条边的处理规则
对每条边的处理规则应该不变。按照左闭右开的规则处理正方形的每一条边，每条边只处理头节点，不处理尾节点。

n * n的矩阵，需要转n / 2圈，若n为奇数，则中心那个值最后单独赋即可。每一圈的终止位置在上一圈的基础上-1。

示意图如下所示：
Snipaste_2024-01-26_06-26-17.png

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
      
        int startx = 0, starty = 0;
        int offset = 1, count = 1;

        int i, j;
        int loop = n / 2;

        while (loop -- )
        {
            for (j = starty; j < n - offset; j ++ )
                ans[startx][j] = count ++ ;
            for (i = startx; i < n - offset; i ++ )
                ans[i][j] = count ++ ;
            for (; j > starty; j -- )
                ans[i][j] = count ++ ;
            for (; i > startx; i -- )
                ans[i][j] = count ++ ;
          
            startx ++ ;
            starty ++ ;
            offset ++ ;
        }

        if (n % 2) ans[n / 2][n / 2] = count;
        return ans;
    }
};

心得与备忘录

977易错点

  1. 一定要新建一个数组ans，不能在原数组的基础上修改，否则会混乱。
  2. 一定要注意左指针和右指针可以相等，因为最后总要处理两个元素，两个指针最终总会移到一起去。否则当两个指针指向同一个数时，该数会被落下，不会被添加到答案数组中。
  3. 这道题在for/while循环内用if或者while都可以，但用while的时候需要记得加上判断条件：while(l <= r && ....)，不加l <= r的条件会报错：run time error。

209心得

滑动窗口方法其实脱胎于暴力做法。要特别注意遍历的是窗口的终止位置。

更新窗口的起始位置时，同时需要更新窗口中元素之和。

不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度至多是 2 × n 也就是O(n)。

209易错点

一定要记得把滑动窗口的初始位置定义在循环之外。

一定要记得在移动窗口初始位置的同时改变窗口中元素的sum。

59易错点

  1. 注意每一条边都是左开右闭
  2. 注意画图理解
  3. 注意为n为奇数时单独给中心点赋值
  4. 注意如何定义一个二维所有元素为0的矩阵
  5. offsetx/y和startx/y不会出现在同一个式子中

备忘

看代码随想录的数组总结

数组总结

数组题目中：整数二分一道（704）。双指针三道（27, 977, 包括滑动窗口209），双指针题目的难度是递增的，27最简单，977稍难，209最难。模拟题一道：59。

从方法上来说，704和59都应该采用循环不变量的原则，27、977、209则都是双指针算法的应用。

引用总结文章：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80
中的一幅图片：

img

发表于 更新于 分类于

链接

文章

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

https://programmercarl.com/%E5%89%8D%E5%BA%8F/%E5%85%B3%E4%BA%8E%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%8C%E4%BD%A0%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84%E9%83%BD%E5%9C%A8%E8%BF%99%E9%87%8C%EF%BC%81.html#%E7%A9%B6%E7%AB%9F%E4%BB%80%E4%B9%88%E6%98%AF%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6

https://programmercarl.com/%E5%89%8D%E5%BA%8F/%E5%85%B3%E4%BA%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%8C%E5%8F%AF%E8%83%BD%E6%9C%89%E5%87%A0%E4%B8%AA%E7%96%91%E9%97%AE%EF%BC%9F.html

题目

https://leetcode.com/problems/binary-search/

https://leetcode.com/problems/remove-element/

知识

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

注意：

  • 数组下标都是从0开始的

  • 数组内存空间的地址是连续的

  • 正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址

  • C++中，要注意vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组

  • 数组的元素是不能删的，只能覆盖

  • C++中二维数组在地址空间上是连续的（在现代系统上，二维数组中的每个int占用4个字节）

  • Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。输出的值不是真正的地址，而是经过处理的数值

时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。有时业界也默认O代表的就是一般情况，而不是严格的上界。面试中说道算法的时间复杂度是多少指的都是一般情况。

数据用例的不一样，时间复杂度也是不同的。

我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大。

我们统一说 logn，也就是忽略底数的描述。

空间复杂度

是对一个算法在运行过程中占用内存空间大小的量度。

来看一下例子，什么时候的空间复杂度是$O(1)$呢，C++代码如下：

1
2
3
4
int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

第一段代码可以看出，随着n的变化，所需开辟的内存空间并不会随着n的变化而变化。即此算法空间复杂度为一个常量，所以表示为大O(1)。

当消耗空间和输入参数n保持线性增长，这样的空间复杂度为O(n)，来看一下这段C++代码

1
2
3
4
int* a = new int(n);
for (int i = 0; i < n; i++) {
    a[i] = i;
}

随着n的增大，开辟的内存大小呈线性增长，即 O(n)。

递归的时候，会出现空间复杂度为logn的情况。

思路

第一想法

Leetcode 704 二分查找

这题应该是整数二分，虽然我在yxc的算法基础课里学过这题，但时隔几个月我已经彻底忘了（不管是原理还是实现），从头开始吧。

Leetcode 27 移除元素

试试暴力做法吧，双指针做法想不出来。根据yxc的经验，暴力做法成功后再想办法去优化。

看完代码随想录后的想法

Leetcode 704 二分查找

二分法的使用前提：数组为有序数组，且数组中无重复元素。满足这两个性质的题目可尝试二分法。

二分法中区间的定义有两种：左闭右闭和左闭右开。每一次边界的处理都要坚持根据区间的定义来操作。

Leetcode 27 移除元素

暴力做法：遍历数组->找到需要移除的元素->将该元素后面的所有元素都前移一位->索引前移一位，数组长度减1

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

实现

Leetcode 704 二分查找

cpp中的vector中求数组的长度没有len函数，应该用size函数。

cpp中两个整数的做除法如果得到的结果变量类型为整数，则是向下取整的。

cpp中的vector是动态数组，要先向用push_back向其中添加元素，然后才能通过索引来访问元素。

左闭右闭和左闭右开的写法中，需要注意right初始值的选取的不同（由于一种写法的右边界可以取到，另一种写法的右边界取不到）。还需要注意分成三类讨论，即target > nums[mid], target < nums[mid]和target == nums[mid]。这样就可以避免处理大于等于和小于等于的情况。

返回总是返回mid，不要尝试返回l或者r，可能会遇到边界问题。

用(l + r) >> 1比(l + r) / 2要更快一点。

建议采用l + (r - l) / 2代替(r + l) / 2，前者可以防止(r + l)溢出整数的范围。

时间复杂度：O(log n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 左闭右闭写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右闭，因此要求左右边界均可取到，因此r的值要与右边界的索引相同
        int l = 0, r = nums.size() - 1;
        
        // 当left==right，区间[left, right]依然有效，所以用 <=
        while (l <= r)
        {
            int mid = (l + r) / 2; // (l + r) >> 1速度更快
            // 分三类情况讨论
            // 因为区间是右闭的，所以r不可能取为mid，最大为mid - 1
            if (target < nums[mid]) r = mid - 1; 
            // 因为区间是左闭的，所以l不可能取为mid，最小为mid + 1
            else if (target > nums[mid]) l = mid + 1;
            // return l/r都是错误的，可以通过模拟一个输入知道错误原因
            else return mid; 
        } 
        return -1;   
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 左闭右开写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右开，因此target不能取为右边界的值，要保证区间完全覆盖住target，因此r的值要比右边界的索引大1
        int l = 0, r = nums.size();
        
        // 右边界取不到，因此是l < r
        while (l < r)
        {
            int mid = (l + r) / 2;
            // 因为区间是左闭的，所以l不可能取为mid，最小为mid + 1
            if (target > nums[mid]) l = mid + 1;
            // 因为区间是右开的，所以r可以取为mid
            else if (target < nums[mid]) r = mid;
            // return l是错误的，可以通过模拟一个输入知道错误原因
            else return mid;
        }
        return -1;
    }
};

Leetcode 27 移除元素

暴力做法

若不前移i，则若数组中出现连续的两个val时，结果会发生错误，不能完全移除数组中所有的val。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();

        for (int i = 0; i < size; i ++ )
        {
            // 遍历数组，找到需要移除的元素
            if (nums[i] == val)
            {
                // 将该元素后面的所有元素都前移一位，覆盖掉需要移除的元素
                for (int j = i + 1; j < size; j ++ )
                    nums[j - 1] = nums[j];
                // 索引前移一位，数组长度减1
                i -- ;
                size -- ;
            }
        }
        return size;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(1)

快慢双指针做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 快指针用于遍历所有元素、慢指针用于记录更新后数组的下标
        int slow = 0;

        for (int fast = 0; fast < nums.size(); fast ++ )
        {
            if (nums[fast] != val)
                nums[slow ++ ] = nums[fast];
        }
        return slow;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

相向双指针做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 相向双指针方法
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int l = 0, r = nums.size() - 1;

        while (l <= r)
        {
            // 跳过所有不需要移除的元素，剩下需要移除的元素
            while (l <= r && nums[l] != val) l ++ ;
            // 跳过所有需要移除的元素，剩下不需要移除的元素
            while (l <= r && nums[r] == val) r -- ;

            // 将右边不需要移除的元素覆盖掉左边需要移除的元素(交换左右两边的元素)
            if (l < r) nums[l ++ ] = nums[r -- ];
        }
        // 返回左边的最后一个值的索引
        return l;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

注意：while (l <= r && nums[l] != val)和while (l <= r && nums[r] == val)中的两个判断条件不可以写反，否则会出现Runtime Error。这是因为短路原则，最好先进行边界检查，再访问数组。

逻辑：数组的左边放等于val的元素，因此需要跳过所有不等于val的元素；数组的右边放不等于val的元素，因此需要跳过所有等于val的元素。交换数组的左右两边，让数组的左边放不等于val的元素，数组的右边放等于val的元素，然后输出数组左边的最后一个值的索引。

相向双指针方法的基本过程我大致理解了，但还不理解其的细节和应用。

心得与备忘录

Leetcode 704 二分查找

我认为代码随想录的做法比yxc的讲解更加清晰。清楚地归纳总结出了左闭右闭和左闭右开的写法，并根据选择区间的开闭性质清晰地写出了代码。同时，分成三类讨论，避免了处理大于等于和小于等于的情况。

还没有做35和34，等到二刷来做。

Leetcode 27 移除元素

相向双指针方法的理解有待加深。

发表于 更新于 分类于

Django项目总结

项目介绍

Game based on Django framework, developed by yifanChen

Website

https://app5894.acapp.acwing.com.cn/

Repository

https://github.com/yfchenkeepgoing/Django_app

Gameplay

  1. Right-click to move
  2. Left-click plus ‘Q’ for the skill: Fireball, with a cooldown of 3 seconds
  3. Left-click plus ‘F’ for the skill: Flash, with a cooldown of 5 seconds
  4. In multiplayer mode, the winning player gains 10 points, and the losing player loses 5 points

Technology Stack

  1. Frontend: JQuery
  2. Backend: Django
  3. Database: SQLite, Redis
  4. Network Protocols: HTTPS, WSS
  5. RPC: Thrift
  6. Authorization Protocol: OAuth
  7. Authentication: JWT

Features

  1. Complete menu interface and game interface
  2. Frontend and backend separation, with AcApp and Web versions on the frontend
  3. Deployed with Nginx to interface with the AcApp
  4. Comprehensive account system, username and password login, and one-click login with AcWing & GitHub OAuth
  5. Online multiplayer and chat system implemented via WSS protocol
  6. Matchmaking system implemented through Thrift service
  7. Cross-origin issues resolved through Rest Framework and JWT authentication, achieving complete frontend-backend separation
  8. The ranking board displays the top ten players ranked by score

Django项目的框架

一个Django项目，大致由以下六部分组成：

  1. templates目录：管理html文件
  2. urls目录：管理路由，即链接与函数的对应关系，即每个链接交给哪个函数处理的信息，存储在urls文件夹中。
  3. views目录：视图，管理http函数（函数实现在views目录中）
  4. models目录：管理数据库数据。
  5. consumers目录：管理websocket函数（views管理http函数，即负责单向连接的函数；consumers管理双向连接的函数，比如联机对战和聊天的逻辑）
  6. static目录：管理静态文件，比如：
  • css文件：对象的格式（网页每部分的格式），比如位置、长宽、颜色、背景、字体大小等
  • js：对象的逻辑（项目的核心），比如对象的创建与销毁、事件函数、移动、变色等，渲染html也会在js部分（前端）
  • image：图片
  • audio：声音

urls文件夹、views文件夹、models文件夹和consumers文件夹都由python文件组成，如果想通过import将文件导入，则需要在文件夹下创建 __init__.py文件（即索引文件，内容为空即可）。在所有python文件夹中都需要创建这样的函数，否则在import时就无法进去，会报错。

项目核心逻辑

本项目由于是一个小游戏，因此前端的js代码占比较大。游戏单人模式的实现纯粹由前端完成，我用js代码实现了一个简易的游戏引擎。游戏的单人模式不需要前后端交互。

需要前后端交互的部分有：

  1. 注册与登录：涉及到写入、读取、查询数据库
  2. acwing和GitHub一键登录：即OAuth授权登录
  3. 实现联机对战和聊天系统：涉及到在多名玩家之间同步五个事件（函数）：create_player, move_to, shoot_fireball, attack, message。前四个用于实现联机对战，最后一个用于实现聊天系统。
  4. Rest Framework与JWT身份验证：是对第一点和第二点的补充。
  • JWT（json web token）相比于django自带的登录验证方式（通过session_id）安全性更高。
  • 方便实现真正意义上的前后端分离，即后端只需要提供实现好的api给前端调用，而Rest Framework为这些api的调试提供了可视化界面。
  • JWT可以解决跨域产生的问题。
  • 可以使用http的四大类请求方法：get, post, delete, put，而不像之前仅仅使用get方法，这又提高了令牌的安全性。

纯后端的部分只有匹配系统的实现。匹配系统的实现涉及到两个后端（即django web server和match system）之间的通信，匹配系统本身涉及到多线程和锁等方面的知识。

我认为本项目的重点主要在于前后端交互的部分，前后端交互其实有一套统一的范式：先在views中实现后端的函数；然后在urls中为后端的函数定义url链接；再在前端代码中利用ajax技术通过url获得后端传来的数据（前后端一般以json的格式传递数据）；最后通过前端使用或展示数据。如果给用户设计了一套通过点击鼠标或者使用键盘向后端请求数据的模式，那么还需要在前端进行按键索引和绑定监听函数等操作。

改进项目

  1. 使用功能更强大的前端框架，比如Vue或者React，取代简单的JQuey。
  2. 使用更多种类型的数据库，比如关系型数据库MySQL，文档数据库MongoDB，对象存储服务等等。
  3. 使用另外几种实现前后端通信的技术取代ajax，比如Fetch API，Server-Sent Events (SSE)，GraphQL和WebRTC，以提高系统的性能。
  4. 学习并尝试使用Springboot框架和Go语言的后端框架。
  5. 使用k8s来自动化部署、扩展和管理容器化应用程序。

漫谈

后端的主要分类

算法与推荐系统、开发各种服务、数据库

对于实现客户端与服务器之间的通信功能的技术的选择

除了AJAX，现代Web开发中还有几种其他技术可以实现类似的客户端与服务器之间的通信功能。一些技术在特定场景下比AJAX更高效。以下是一些常用的技术：

  1. Fetch API： Fetch API提供了一种更简洁和强大的方式来发起网络请求。它基于Promise，使得写异步代码更加简洁和直观。Fetch API是AJAX的现代替代方案，被广泛支持和使用。
  2. WebSocket： WebSocket提供了全双工通信渠道，使得客户端和服务器可以实时、双向地通信。它非常适用于需要频繁和即时数据更新的应用，如在线游戏、聊天应用和实时数据流。
  3. Server-Sent Events (SSE)： SSE允许服务器主动向客户端发送新数据。它是单向的，只有服务器可以发送消息给客户端。SSE适合实现如股票行情、新闻订阅等场景，其中服务器定期推送更新。
  4. GraphQL： GraphQL是一种数据查询和操作语言，它允许客户端以更灵活的方式请求数据。与REST相比，GraphQL可以减少数据传输量，因为它允许客户端精确指定所需的数据。
  5. WebRTC： WebRTC（Web Real-Time Communication）允许在不需要安装插件的情况下在Web应用中实现实时通信功能，常用于视频聊天和点对点数据共享。

每种技术都有其特定的应用场景和优势。选择哪一种技术取决于应用的具体需求：

  • 对于简单的异步数据请求，AJAX和Fetch API都是不错的选择。
  • 对于需要高实时性的应用，WebSocket或WebRTC可能更合适。
  • 对于服务器主动推送数据的场景，SSE是一个好的选择。
  • 对于需要更灵活数据交互的场景，GraphQL提供了更好的解决方案。

在性能方面，WebSocket和WebRTC通常在需要频繁和快速通信的场景下比AJAX更高效，因为它们建立了持久的连接，而不是像AJAX那样为每个请求创建新的连接。

如何使用MySQL，MongoDB，对象存储服务等外置的数据库（它们不像sqlite，不集成于后端框架内）

  • 租一台数据库服务器
  • 在框架中负责数据库的部分配置数据库服务器的连接/登录
  • 下载该框架下使用该种数据库的包
  • 在框架中负责数据库的部分调用包中的api完成对数据库的各种操作，比如读、写、删除等。

在 Django 中，通常不需要直接使用 SQL 语句来操作 MySQL 数据库，因为 Django 提供了一个强大的 ORM（对象关系映射）系统，允许你通过 Python 代码来操作数据库。这意味着你可以使用 Django 的模型和查询 API 来查询和操作数据，而无需直接编写 SQL 语句。

Django 本身不直接支持 MongoDB，因为它是一个 NoSQL 数据库，与 Django 的 ORM 系统设计理念不同。如果你想在 Django 项目中使用 MongoDB，可以采取以下方法：

  • 使用 Djongo： Djongo 是一个将 Django ORM 映射到 MongoDB 的工具。通过 Djongo，你可以在一定程度上使用 Django ORM 的风格来操作 MongoDB。
  • 使用 PyMongo： PyMongo 是 MongoDB 的官方 Python 驱动程序。使用 PyMongo，你可以直接以 Python 代码与 MongoDB 交互，但这意味着你需要手动编写数据库操作逻辑，而不是使用 Django ORM。

对于对象存储服务（如 Amazon S3），通常使用的是 RESTful API 而非传统的数据库查询语言。在 Django 项目中使用对象存储通常涉及以下步骤：

  • 选择合适的库： 例如，对于 Amazon S3，你可以使用 boto3，这是 AWS 的官方 Python SDK。
  • 进行配置和认证： 通常需要设置认证凭据和相关配置。
  • 使用 SDK 提供的 API： 使用 SDK 提供的方法来上传、下载、列出文件等。

JWT可以存放在内存、local storage和cookie中，这三个存放地各自有优缺点

Cookie：
优点：自动由浏览器管理，并且可以设置为HttpOnly（无法通过JavaScript访问，增加安全性），支持跨域访问控制（SameSite属性）。
缺点：容易受到CSRF（跨站请求伪造）攻击，尽管可以通过适当的防范措施（如使用CSRF Token）来缓解。

LocalStorage：
优点：易于使用，可以在浏览器会话间持久存储。
缺点：容易受到XSS（跨站脚本攻击）攻击，因为恶意脚本可以访问LocalStorage并窃取令牌。

内存（JavaScript变量）：
优点：在浏览器关闭时自动清除，不容易受到XSS攻击（只要不将令牌暴露给恶意脚本）。
缺点：不持久，用户刷新页面或关闭浏览器时会丢失，可能需要重新认证。

最佳实践：
安全性考虑：通常推荐将JWT存储在HttpOnly的Cookie中，因为这样可以防止JavaScript访问令牌，从而减少XSS攻击的风险。

CSRF防范：如果使用Cookie，应结合CSRF保护机制。

易用性：如果需要在会话间持久保存用户的登录状态，LocalStorage可能更为方便。但是，务必注意XSS攻击的风险，并采取适当的安全措施。

短期使用：对于需要高安全性且可接受在会话结束后用户需要重新登录的场景，可以考虑仅将JWT存储在内存中。

在实践中，选择哪种方式取决于应用的安全需求、用户体验需求以及开发者对相关安全风险的管理能力。在处理任何形式的认证信息时，安全总是首要考虑的因素。在本项目中，出于安全性和短期使用的考量，我将JWT存储在了内存，即js变量中。如果没有明确地将JWT存储在Local Storage或Cookie中，那么它们就是存储在内存中。这意味着令牌只在当前页面会话中有效，一旦页面被关闭或刷新，令牌就会丢失。

发表于 分类于

迁移云服务器

1、租云服务器，配置其免密登录

将本地的公钥复制到云服务器的~/.ssh/authorized_keys中，或者使用云服务器平台提供的密钥，在本地的.ssh文件夹中添加密钥在本地的位置
第一次登录云服务器（未配置免密登录）的具体流程可以参照以下步骤：

IR_Group_7_project Demo Instruction

  1. Login our VM instance
    Move key to secure location (eg. ~/.ssh in linux), then
1
2
chmod 600 path/to/shaoxi_key.pem
ssh -i path/to/shaoxi_key.pem shaoxi@52.174.147.101

2、在云服务器中安装docker

安装步骤参见官网：https://docs.docker.com/engine/install/ubuntu/
一般安装的版本为20.10.9，使用命令：VERSION_STRING=5:20.10.9~3-0~ubuntu-focal
查看docker是否安装成功：docker --version

3、在云服务器平台开放以下端口

22， 8000， 443， 80， 20000，协议均为TCP，源和目的地都为任何（0.0.0.0）

4、将本地的C:\Users\chen yi fan\django_lesson_1.tar上传到云服务器里

在powershell中执行的具体的命令为：
scp .\django_lesson_1.tar azureuser@20.123.135.13:~/

5、将镜像xxxx从本地文件xxxx.tar中加载出来

sudo docker load -i xxxx.tar

6、查看镜像是否成功加载出来

查看所有镜像的命令: sudo docker images

7、使用镜像重新创建并运行容器

docker run -p 20000:22 -p 8000:8000 -p 80:80 -p 443:443 --name django_server -itd django_lesson:1.1

8、登录到容器中

sudo docker attach django_server
登录为root用户

9、创建非root用户

adduser acs
赋予其sudo权限：usermod -aG sudo acs
设置密码

10、配置容器的免密登录

配置免密登录的过程是：在容器的.ssh/authorized_keys中写入本地的.ssh文件夹（C:\Users\chen yi fan.ssh）中的公钥的内容
然后修改本地的.ssh/config文件，添加容器的信息，例如：

1
2
3
4
Host django_azure
    HostName 20.123.135.13
    User acs
    Port 20000

11、从本地/其他云服务器上登录到容器的命令

ssh acs@ip -p 20000
退出容器时注意不要关闭容器，而是挂起容器：ctrl+p ctrl+q

12、完成容器的一些配置：

nginx配置：
（1）修改yxc的acapp中的服务器IP
（2）将服务器的IP添加到项目的settings.py的ALLOWED_HOSTS中
（3）将yxc提供的nginx.conf写入容器的/etc/nginx/nginx.conf文件中
（4）将yxc提供的acapp.key写入容器的/etc/nginx/cert/acapp.key文件中
（5）将yxc提供的acapp.pem写入容器的/etc/nginx/cert/acapp.pem文件中
（6）启动nginx服务：sudo /etc/init.d/nginx start
（7）启动uwsgi服务：uwsgi --ini scripts/uwsgi.ini

redis配置：
（1）安装redis：pip install django_redis
（2）启动redis-server：sudo redis-server /etc/redis/redis.conf
（3）用top命令看有没有进程叫redis-server

django channels配置：
（1）安装channels_redis：pip install channels_redis
（2）启动django_channels：
在~/acapp目录下执行：daphne -b 0.0.0.0 -p 5015 acapp.asgi:application

同时启动https（uwsgi）和wss（daphne）协议的服务后，项目就应该可以正常运行

13、启动https和wss服务

启动https服务：uwsgi --ini scripts/uwsgi.ini

启动wss服务：daphne -b 0.0.0.0 -p 5015 acapp.asgi:application

重启云服务器

在云平台暂停云服务器后重新启动服务器并进入容器

1. 在云平台启动云服务器

需要等待5-10分钟才能完成重启的过程

2. 查看云服务器中已有的容器

运行命令：sudo docker ps -a

3. 启动被暂停/退出的容器

运行命令：sudo docker start django_server

4. 进入容器

在vscode上选择django_azure，点击进入即可

5. 启动容器中的服务

主要需要启动以下五个服务：

启动nginx服务：sudo /etc/init.d/nginx start

启动redis-server：sudo redis-server /etc/redis/redis.conf

启动uwsgi（https）服务：uwsgi --ini scripts/uwsgi.ini

启动wss服务：daphne -b 0.0.0.0 -p 5015 acapp.asgi:application

启动match system服务：./main.py

发表于 分类于

如何搭建和维护个人博客

个人博客的实现方式

使用GitHub Pages和Hexo框架搭建和维护个人博客

注意事项

注意1

尽量避免在一点不止一行的情况下使用：

的结构，因为这会导致网页上的博客渲染异常。在这种情况下，建议每一点使用一个小标题

注意2

在线博客的刷新需要几分钟时间，请在更新博客后稍安勿躁。在线博客各部分的更新速度不同，比如博客内容先更新了，但日志还没有更新，这是正常现象，稍稍等待即可

注意3

由于托管博客的仓库有两个分支，其中的master分支总会在我部署博客时实时更新，因此source分支在发布新博客时更新即可，不需要实时更新

注意4

使用VSCode在本地编辑博客即可，博客的内容可以复制自Typora，在VSCode中点击md文件左上角的铅笔符号（Edit in VSCode）即可在VSCode中编辑博客内容，每次编辑完后记得运行部署脚本将博客更新部署到网站上

博客结构

本博客计划同时按照标签页（tags）和分类页（categories）进行分类。分类是更大的范畴，主要分为算法、web开发、工具使用、个人随笔和找工记录五大类。标签页是更小的范畴，有Python, C++, Java, Django, Springboot, Typora, GitHub Pages, Hexo, VsCode, 简历等等。一般一篇文章只隶属于一个category，但可以同时拥有多个标签。

本博客可以通过网址：
https://yfchenkeepgoing.github.io/
访问，注意由于GitHub Pages是静态网页，因此出现延迟请稍安勿躁。另外，本博客所在的仓库地址为：https://github.com/yfchenkeepgoing/yfchenkeepgoing.github.io
其中有两个分支，分别为master和source。master托管了正在运行的博客，其中的内容在每次运行部署脚本后就会被更新。source托管了博客文件夹的所有源文件，需要通过git命令进行更新。博客网页与master分支中的内容进行了绑定。

个人博客的特点和功能

  1. 配置站点信息
  2. 修改为next主题
  3. 进行了next主题的配置，包括样式、favicon、avatar、rss、code、top、reading_process、bookmark、github_banner、pangu、math、pjax
  4. 采用gitalk存储并显示评论，需要评论者使用GitHub登录
  5. 使用了标签页和分类页
  6. 拥有搜索页

如何搭建个人博客

参见知乎链接：
https://zhuanlan.zhihu.com/p/371995929

其中指导非常详细，但过程较为繁琐，本文不再赘述。本文的重点在于如何维护搭建好的个人博客。

如何维护个人博客

本地调试

进入博客的根目录下，然后调用 Hexo 的 generate 命令，将 Hexo 编译生成 HTML 代码，命令如下：

1
hexo generate

然后我们利用 Hexo 提供的 serve 命令把博客在本地运行起来，命令如下：

1
hexo serve

然后通过链接：http://localhost:4000/即可访问到渲染出的博客页面。注意：在这种情况下，博客页面只对自己可见，因此上述命令只能用于调试。

维护在线博客

增加新的文章并将其分类到特定的tags和categories中

新建一篇名为HelloWorld的文章，在本地博客的根目录下执行命令：

1
hexo new hello-world

创建的文章会出现在 source/_posts 文件夹下，是 MarkDown 格式。
在文章开头通过如下格式添加必要信息：

1
2
3
4
5
6
7
8
9
10
11
12
---
title: hello-world # 自动创建，如hello_world
date: 日期 # 自动创建，如2024-01-20 02:07:51
tags: 
- 标签1
- 标签2
- 标签3
categories:
- 分类1
- 分类2
- 分类3
---

开头下方撰写正文，MarkDown 格式书写即可。这样在下次编译的时候就会自动识别标题、时间、类别等等，另外还有其他的一些参数设置，可以参考文档：https://hexo.io/zh-cn/docs/writing.html

标签和分类的区别

Tags（标签）：
标签是用来描述博客文章中的具体细节的关键词。
它们是扁平的，不形成层次结构。
标签可以非常具体，也可以非常多，用于描述文章的具体内容，如“Python”、“Web开发”、“机器学习”等。
一个文章可以有多个标签，标签的数量通常比分类多。

Categories（分类）：
分类通常用来表示博客文章的主要主题或大的分组。
它们是层次性的，可以有子分类，形成一个结构化的树状层次，例如：“技术”可以有子分类如“编程”、“网页设计”等。
分类通常较少，更宽泛，用于将文章分配到几个广泛的、互相排斥的主题中。
一个博客文章通常只属于一个或少数几个分类。

使用示例：
假设您写了一篇关于Python网络编程的博客文章。您可以将这篇文章归类到“编程”分类下，并给它加上“Python”、“网络编程”、“套接字编程”等标签。

总结：
分类用于表示文章的主要主题，是更广泛的分组工具。
标签用于详细描述文章的内容和细节，是更具体的关键词。

通过部署脚本部署在线博客

在根目录下新建一个 deploy.sh 的脚本文件，内容如下：

1
2
3
4
5
hexo clean

hexo generate

hexo deploy

在部署发布的时候只需要执行：

1
sh deploy.sh

就可以完成博客的更新了，非常方便。

注意，在发布博客时只能执行上述命令，不能执行 ./deploy.sh，否则博客无法正常发布。

发表于 更新于 分类于

（1）标题

一级标题

二级标题

三级标题

四级标题

五级标题
六级标题

（2）快捷键

普通模式和源代码模式：ctrl+/
md语法正确显示需要在有文字的一行后面再空一行，把鼠标放在有文字的最后一行的后两行的位置

标题：按下ctrl和+，则当前行变成第六级的标题，每按一次ctrl和+则当前标题的等级提升一级。按下ctrl和-则是按下ctrl和+的逆向操作。

（3）字体

加粗
倾斜
斜体加粗
删除线 （~2删除线~2）
==高亮==
我是^上标^
我是~下标~ （注意用英文的~）

（4）列表

无序列表：
下一级是加号前面空两格
第一级是实心的圆，第二级是空心的圆，第三级开始都是实心的小方框

  • 一二三四五
    • 上山打老虎
      • 老虎没打到
        • 打到小松鼠

有序列表：

  1. 一二三四五
  2. 上山打老虎
  3. 老虎没达到
  4. 打到小松鼠

（5）表格

MON TUE WED THU FRI
上山 上山 上山 上山 上山
打老虎 打老虎 打老虎 打老虎 打老虎

在普通模式下，输入：|MON|TUE|WED|THU|FRI|，再输入回车，即可出现表格，可以增加表格的行和列，以及左右居中等等

（6）引用

下一级别：加一个>

一二三四五

上山打老虎

老虎没达到

打到小松鼠

（7）分割线

疯狂打——-即可

==（7）代码==

我是代码

1
2
3
4
5
6
7
8
# include <iostream>

using namespace std;

int main()
{
	cout << "hello world" << endl;
}

（8）字数和侧边栏

字数在右下角
侧边栏在左侧，可以通过在普通模式中点击左下角的小圆圈呼出
大纲也在侧边栏中

（9）插入图片

将图片放入到图片文件夹中，然后复制图片将其直接粘贴进来即可

Snipaste_2023-12-27_04-15-35

Snipaste_2023-12-27_04-12-14

（10）改变字体颜色

将字体改变为红色：<font color=red>文字 </font>

==平常用高亮即可，不要用红色==

(11) diff代码块

1
2
3
- 这行被删除了
+ 这行被添加了
  这行没有改变

(12) enter和shift enter的区别

enter: 新起一段（空一行）
shift enter: 新起一行

(13) markdown source code


## （1）标题

# 一级标题

## 二级标题

### 三级标题

#### 四级标题

##### 五级标题

###### 六级标题

## （2）快捷键

普通模式和源代码模式：ctrl+/
md语法正确显示需要在有文字的一行后面再空一行，把鼠标放在有文字的最后一行的后两行的位置

标题：按下ctrl和+，则当前行变成第六级的标题，每按一次ctrl和+则当前标题的等级提升一级。按下ctrl和-则是按下ctrl和+的逆向操作。

## （3）字体

**加粗**
*倾斜*
***斜体加粗***
~~删除线~~ （~*2删除线~*2）
==高亮==
我是^上标^
我是~下标~       （注意用英文的~）

## （4）列表

无序列表：
下一级是加号前面空两格
第一级是实心的圆，第二级是空心的圆，第三级开始都是实心的小方框

+ 一二三四五
  + 上山打老虎
    + 老虎没打到
      + 打到小松鼠

有序列表：

1. 一二三四五
2. 上山打老虎
3. 老虎没达到
4. 打到小松鼠

## （5）表格

| MON    | TUE    | WED    | THU    | FRI    |
| ------ | ------ | ------ | ------ | ------ |
| 上山   | 上山   | 上山   | 上山   | 上山   |
| 打老虎 | 打老虎 | 打老虎 | 打老虎 | 打老虎 |

在普通模式下，输入：|MON|TUE|WED|THU|FRI|，再输入回车，即可出现表格，可以增加表格的行和列，以及左右居中等等

## （6）引用

下一级别：加一个>

> 一二三四五
>
>> 上山打老虎
>>
>>> 老虎没达到
>>>
>>>> 打到小松鼠
>>>>
>>>
>>

## （7）分割线

疯狂打-----即可

---

##==（7）代码==

`我是代码`


1
2
3
4
5
6
7
8
# include <iostream>

using namespace std;

int main()
{
	cout << "hello world" << endl;
}


## （8）字数和侧边栏

字数在右下角
侧边栏在左侧，可以通过在普通模式中点击左下角的小圆圈呼出
大纲也在侧边栏中

## （9）插入图片

将图片放入到图片文件夹中，然后复制图片将其直接粘贴进来即可

![Snipaste_2023-12-27_04-15-35](D:/OneDrive%20-%20stu.xjtu.edu.cn/%E5%9B%BE%E7%89%87/Snipaste_2023-12-27_04-15-35.png)

![Snipaste_2023-12-27_04-12-14](D:/OneDrive%20-%20stu.xjtu.edu.cn/%E5%9B%BE%E7%89%87/Snipaste_2023-12-27_04-12-14.png)

## （10）改变字体颜色

将字体改变为红色：``文字 ``

==平常用高亮即可，不要用红色==

## (11) diff代码块


1
2
3
- 这行被删除了
+ 这行被添加了
  这行没有改变


## (12) enter和shift enter的区别

enter: 新起一段（空一行）
shift enter: 新起一行

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment