数据结构自学笔记
Published in：2023-11-02 | category： 学习笔记

数据结构自学笔记——边刷题边记录

本内容就不多说废话了，基本上都是刷题的时候，一边看一边学的，也不算成系统，总之参考一下。最基本的内容就全都略过，从比较复杂（我觉得需要记录一下的东西开始）

0.预先章节

从C(C89甚至ANSI C)语言转到C++(C++ 14)，需要增加的一些内容，仅用于算法学习和实现，不涉及工程问题的“刚好够用”的补充。

0.0 从C到C++（C++99对比C89，增加的“刚好够用”的补充）

0.0.1 bool

bool 类型是 C++ 中的基本类型，只有两个值：true 和 false。C89 中没有 bool 类型，但是可以用 int 类型代替 bool 类型，0 代表 false，非 0 代表 true。

1
2
3
4
// Using C++ 14
// bool
bool a = true;
bool b = false;

0.0.2 nullptr

nullptr 是 C++ 中的关键字，表示空指针，可以用于任何指针类型。C89 中没有 nullptr 关键字，但是可以用 NULL 宏代替 nullptr 关键字。

1
2
3
4
// Using C++ 14
// nullptr
int* a = nullptr;
int* b = NULL;  // Not recommended in C++ language

0.0.3 const

const 是 C++ 中的关键字，表示常量，可以用于任何类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。C89 中没有 const 关键字，但是可以用 #define 宏代替 const 关键字。

0.0.4 long long

long long 是 C++ 中的基本类型，表示长整型，C89 中没有 long long 类型。C89 中有 long 类型，但是 long 类型的长度不够长，不能满足实际的需求，所以 C++ 中增加了 long long 类型。

事实上，在现在的C++语言中，long long 是__int_64的别名，而__int_64是long long的别名，所以long long和__int_64是等价的；对于更大的数据，可以使用__int_128，但是__int_128不是标准的C++语言，而是编译器提供的扩展。

1
2
3
4
// Using C++ 14
// long long
long long a = 1LL;
long long b = 1i64;  // Not recommended in C++ language

0.0.5 static_cast

static_cast 是 C++ 中的关键字，表示静态类型转换，可以用于任何类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。C89 中没有 static_cast 关键字，但是可以用 (type) 表达式代替 static_cast 关键字。

0.0.6 dynamic_cast

dynamic_cast 是 C++ 中的关键字，表示动态类型转换，可以用于任何类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。C89 中没有 dynamic_cast 关键字，但是可以用 (type) 表达式代替 dynamic_cast 关键字。

dynamic_cast 用于类的继承关系中，static_cast 用于基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。

0.1 C++ 14、C++ 11、C++ 03带来的新特性

0.1.1 auto

auto 关键字用于自动推导变量类型，可以用于任何类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。使用时必须注意，auto 推导的变量类型与初始化表达式的类型完全一致，auto 推导的变量类型不会进行任何的隐式转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Using C++ 14
// auto
auto a = 1; // int
auto b = 1.0; // double
auto c = 1.0f; // float
auto d = 1.0L; // long double
auto e = 1LL; // long long
auto f = 1u; // unsigned int
auto g = 1ul; // unsigned long
auto h = 1ull; // unsigned long long
auto i = 1.0e-10; // double
auto j = 1.0e-10f; // float
auto k = 1.0e-10L; // long double

auto l = 'a'; // char
auto m = "abc"; // const char*
auto n = true; // bool
auto o = nullptr; // nullptr_t

auto p = std::string("abc"); // std::string
auto q = std::vector<int>{1, 2, 3}; // std::vector<int>

0.1.2 decltype

decltype 关键字用于获取表达式的类型，可以用于任何类型的表达式，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。使用时必须注意，decltype 获取的表达式类型与表达式的类型完全一致，decltype 获取的表达式类型不会进行任何的隐式转换。

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
// Using C++ 14
// decltype
int a = 1;
decltype(a) b = 1; // int

int* c = &a;
decltype(c) d = &a; // int*

int& e = a;
decltype(e) f = a; // int&
decltype((a)) g = a; // int&
decltype(++a) h = a; // int&
decltype(a++) i = a; // int

int j[10];
decltype(j) k = j; // int[10]

int l(int a, int b) { return a + b; }
decltype(l) m = l; // int(int, int)

auto n = [](int a, int b) { return a + b; };
decltype(n) o = n; // lambda

struct P {
    int a;
    int b;
};
decltype(P::a) p = 1; // int
decltype(P::b) q = 1; // int

template <typename T>
struct Q {
    T a;
    T b;
};
decltype(Q<int>::a) r = 1; // int
decltype(Q<int>::b) s = 1; // int

std::vector<int> t{1, 2, 3};
decltype(t) u = t; // std::vector<int>
decltype(t.begin()) v = t.begin(); // std::vector<int>::iterator
decltype(t.end()) w = t.end(); // std::vector<int>::iterator
decltype(t.cbegin()) x = t.cbegin(); // std::vector<int>::const_iterator
decltype(t.cend()) y = t.cend(); // std::vector<int>::const_iterator
decltype(t.rbegin()) z = t.rbegin(); // std::vector<int>::reverse_iterator
decltype(t.rend()) aa = t.rend(); // std::vector<int>::reverse_iterator
decltype(t.crbegin()) bb = t.crbegin(); // std::vector<int>::const_reverse_iterator
decltype(t.crend()) cc = t.crend(); // std::vector<int>::const_reverse_iterator

0.1.3 lambda

lambda 表达式用于定义匿名函数，可以用于任何类型的表达式，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。使用时必须注意，lambda 表达式的类型与表达式的类型完全一致，lambda 表达式的类型不会进行任何的隐式转换。

1
2
3
4
// Using C++ 14
// lambda
auto a = [](int a, int b) { return a + b; };
// int(int, int)

0.2 STL

0.2.1 std::vector

std::vector 是 C++ 中的容器，用于存储任意类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。std::vector 是一个动态数组，可以动态的增加和删除元素，可以动态的改变容器的大小。

1
2
3
// Using C++ 14
// std::vector
std::vector<int> a{1, 2, 3};

vector 的成员函数：

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
std::vector<int> a{1, 2, 3};

// 获取容器的大小
a.size(); // 3

// 获取容器的最大容量
a.max_size(); // 4611686018427387903

// 判断容器是否为空
a.empty(); // false

// 获取容器的第一个元素
a.front(); // 1

// 获取容器的最后一个元素
a.back(); // 3

// 获取容器的第 i 个元素
a[i]; // 1

// 获取容器的第 i 个元素
a.at(i); // 1

// 获取容器的第一个元素的迭代器
a.begin(); // std::vector<int>::iterator

// 获取容器的最后一个元素的迭代器
a.end(); // std::vector<int>::iterator

// 获取容器的第一个元素的常量迭代器
a.cbegin(); // std::vector<int>::const_iterator

// 获取容器的最后一个元素的常量迭代器
a.cend(); // std::vector<int>::const_iterator

// 获取容器的第一个元素的反向迭代器
a.rbegin(); // std::vector<int>::reverse_iterator

// 获取容器的最后一个元素的反向迭代器
a.rend(); // std::vector<int>::reverse_iterator

0.2.2 std::map

std::map 是 C++ 中的容器，用于存储任意类型的变量，包括基本类型、指针、引用、数组、函数、lambda、类、模板、STL容器、STL迭代器、STL算法等等。std::map 是一个关联容器，可以根据 key 快速的查找 value，key 必须是唯一的，不能重复。

1. 二叉树

1.1 二叉树的遍历

1.1.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
// Using C++ 14
// Preorder
void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << endl;
    preorder(root->left);
    preorder(root->right);
}

// Inorder
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << endl;
    inorder(root->right);
}

// Postorder
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << endl;
}

一些题目和模型

Top K

一个数组，求出其中最小的前 N 个数。

思路：

  1. 用一个最大堆，维护前 N 个数，每次遍历到一个数，如果比堆顶小，就把堆顶弹出，把这个数放进去，最后堆里面就是最小的前 N 个数。

  2. 快速排序，但是由于只需要前 N 个数，在快速排序的时候，如果左边的数的个数大于 N，就只对左边的数进行快速排序。

  3. 使用STL中的nth_element函数，这个函数的作用是把第 N 小的数放在第 N 个位置上，左边的数都比它小，右边的数都比它大。

  4. 随即选择算法，类似于随即排序（快速排序的一种优化），每次随机选择一个数，然后把比这个数小的数放在左边，比这个数大的数放在右边，然后判断左边的数的个数，如果左边的数的个数大于 N，就只对左边的数进行随机选择，否则就对右边的数进行随机选择。其实就是保证了基准数左侧都比他小、右侧都比他大，具体的排序不重要。

技术 数据结构 算法 OJ刷题
Prev:
计算机与数学建模
Next:
在 Termux 上安装 Debian 11 并启用桌面环境

    • Copyright © 2023 - szw0407 | Powered by Hexo | Theme forked from Bamboo by yuang01