Hello World

你好，这里是snkkkts，你也可以叫我snk（雾

总之，这里是我的个人博客。在接下来的的几年里，我会在这里更新很多的内容，从数据结构与算法的学习笔记，到数学分析、线性代数等数学内容，再到经典好书的摘抄和读书心得，再到平时的随笔等等都会在这个博客上更新。

如果你也有一些想法想要分享，那么欢迎评论哦~

从构建出发

算法竞赛中，我们通常会遇到有关树形结构或图结构的问题，而如何有效地构建结构，利用好树和图的各种特点成为了解题的第一步。下文中我将给出恰当的方法来实现树和图中的基本操作。

例1： 给定一颗树，树根为\(1\)，每个点的点权为\(V_i\)，请实现这样的结构，使之可以遍历每个节点所在的深度，也可以遍历每个深度所有的节点

输入格式： 输入的第一行包括一个整数\(n\)。

第二行包含\(n-1\)个整数\(F_i\)，相邻整数间用一个空格分隔，分别表示第\(2\)至\(n\)个节点的父节点编号

第三行包含\(n\)个整数\(V_i\)，相邻整数之间使用一个空格分隔，分别表示每个节点的点权

代码如下：

1
2
3
4
5
6
7
8
9
10
11

n = int(input())
father = [0, 0] + list(map(int, input().split()))
values = [0] + list(map(int, input().split())) # 存每个节点的值
dep = [0] * (n + 1) # 每个节点的深度
dep_node = [[] for _ in range(n + 1)]   # 存每个深度的节点
deep_max = 0    # 深度的最大值

for i in range(1, n + 1):   # 求每个深度有哪些节点
    dep[i] = dep[father[i]] + 1 # 一个节点的深度是它父节点深度 + 1得到的，这样我们就递归地得到了每个节点的深度
    deep_max = max(deep_max, dep[i])    # 维护深度的最大值
    dep_node[dep[i]].append(i)  # i节点所在深度为dep[i],于是为dep_node的第dep[i]层添加i

这样我们就得到了数组\(fathers\), \(values\), \(dep\), \(dep\_node\)和整数\(deep\_max\),它们分别表示：

• 编号为\(i\)的节点的父节点\(fathers[i]\)
• 编号为\(i\)的节点的点权\(values[i]\)
• 编号为\(i\)的节点的深度\(dep[i]\)
• 深度为\(i\)的第\(j\)个节点\(dep\_node[i][j]\)
• 树的最大深度\(deep\_max\)

在得到这些基础属性后，我们就可以很方便地对树进行遍历等操作

在实际问题中，我们也会看到另一种树形结构的构筑，它的输入并没有直接告诉我们对于某个节点\(i\)，它的父节点是什么，而是类似图结构一样，告诉我们节点\(u\)和\(v\)之间存在一条边，对于这样的输入，我们可以用图的邻接表来构建恰当的树形结构。

例2：给定一颗有\(n\)个节点的有根树，其中节点\(i\)的点权为\(a_i\)，请设计一种结构，使我们可以得到每个点对应的深度

输入格式：输入的第一行包含两个正整数\(n,m\)，用一个空格分隔。

第二行包含\(n\)个整数\(a_1, a_2,...,a_n\),相邻整数之间使用一个空格分隔。

接下来\(n-1\)行，每行包含两个正整数\(u_i,v_i\),表示节点\(u_i\)和\(v_i\)之间有一条边

代码如下：

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

n, m = map(int, input().split())
values = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]  # 用邻接表存储节点与边的信息
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

dep = [0] * (n + 1)
dep[1] = 1

def depth(node, father):
    for children in g[node]:
        if children != father:
            dep[children] = dep[node] + 1
            depth(children, node)   # 递归地计算每个节点的深度

depth(1, 0)

回溯

什么是回溯

通常来说，我们会这样介绍回溯算法：回溯法采用试错的思想，它尝试分步地解决一个问题。在分布解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效地正确的解答的时候，它将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，它通过反复地重复上述的步骤来解决问题。回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。

给定一棵二叉树，搜索并记录所有值为7的节点，请返回节点列表。

1
2
3
4
5
6
7
8
9

def pre_order(root: TreeNode):
    """前序遍历：例题一"""
    if root is None:
        return
    if root.val == 7:
        # 记录解
        res.append(root)
    pre_order(root.left)
    pre_order(root.right)

尝试与回退

之所以被称为回溯算法，是因为该算法在探索解空间时会采用“尝试”与“回退”的策略，通过撤销上一步的选择，退回到之前的状态，它得以访问其他的选择。

在二叉树中搜索所有值为7的节点，请返回根节点到这些节点的路径

排序算法

  在本章中，我们将致力于研究针对对象集进行排序的算法。我们要对一个集合的元素进行重新排列，以使它们按照从小到大的顺序进行排列（或以此顺序生成一个新的副本）。Python中对数据排序提供了内在支持，包括对列表list类的sort方法，还有以排好的顺序生成一个包含任意元素集合的内置的sorted函数。这些内置函数使用了一些高级算法，并进行了高度的优化。我们很少有需要从头开始实现排序的特殊情况，但了解这些算法的底层逻辑和预期效率仍是有必要的。下面我们将逐个介绍。

树

  作为一种非线性的数据结构，树（tree）表现出与链表、数组等线性结构在组织关系上的差异，这种组织关系比一个序列中两个元素之间简单的“前”和“后”关系更加丰富和复杂。这种关系在树中是分层的（hierarchical），一些元素位于“上层”，而一些元素位于“下层”。树为数据提供了一个更加真实、自然的组织结构，由此实现的一系列算法也比使用线性数据结构要快得多。出于篇幅原因，我们仅在下文中介绍树的一些基本的内容。

链表

  在本章中，我们将介绍一种名为链表的数据结构，它为基于数组的序列提供了另一种选择。基于数组的序列和链表都能够对其中的元素保持一定的顺序，但采用的方式截然不同。数组提供更加集中的表示法，一个大的内存块能够为许多元素提供存储和引用。相对的，一个链表依赖于更多的分布式表示方法，采用称作节点的轻量级对象，分配给每一个元素。每个节点维护一个指向它的元素的引用，并含一个或多个指向相邻节点的引用，这样做的目的是为了集中地表示序列的线性顺序。

栈、队列和双端队列

1. 栈

  定义： 堆栈（stack）又称为栈 或 堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆栈常用一维数组或链接串列来实现。常与另一种有序的线性资料集合队列相提并论。用户可以在任何时刻向栈中插入一个对象，但只能取得或者删除最后一个插入的对象（即栈顶）。下面是一个使用到堆栈的实例。