链表
1、链表的建立
#include <cstdio> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} //ListNode() : val(0), next(nullptr) {} //ListNode(int x, ListNode *next) : val(x), next(next) {} }; int main(){ }
2、链表反转
给定一个链表的头节点，让我们反转该链表并输出反转后链表的头节点。
样例：
如样例所示，原始链表为1->2->3->4->5->NULL，我们将其翻转输出5->4->3->2->1->NULL。下面我们来讲解双指针的做法。
将一个链表翻转，即将该链表所有节点的next指针指向它的前驱节点。由于是单链表，我们在遍历时并不能直接找到其前驱节点，因此我们需要定义一个指针保存其前驱节点。
每次翻转时，我们都需要修改当前节点的next指针。如果不在改变当前节点的next指针前保存其后继节点，那么我们就失去了当前节点和后序节点的联系，因此还需要额外定义一个指针用于保存当前节点的后继节点。
具体过程如下：
- 定义一个前驱指针
pre和cur指针，pre指针用来指向前驱节点，cur指针用来遍历整个链表，初始化pre = null，cur = head。
- 我们首先保存
cur指针指向节点的后继节点，然后让cur指针指向节点的next指针指向其前驱节点，即cur->next = pre。 pre指针和cur指针分别后移一位，重复上述过程，直到cur指向空节点。- 最后我们返回
pre节点。
图示过程如下：
时间复杂度分析： 只遍历一次链表，时间复杂度是。
#include <cstdio> #include <iostream> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} //ListNode() : val(0), next(nullptr) {} //ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* head = nullptr; // 头插法 void add(int x) { ListNode* node = new ListNode(x); node->next = head; head = node; } void print() { ListNode* p = head; while (p) { printf("%d ", p->val); p = p->next; } } ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; //前驱指针 ListNode* cur = head; while(cur){ ListNode* t = cur->next; //先保存后继节点 cur->next = pre; pre = cur, cur = t; } return pre; } int main() { for(int i = 0; i < 5; i++) add(i); head = reverseList(head); print(); return 0; }
堆
1、什么是堆？
堆(Heap)是一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆也有不同种类的堆，分别为小根堆与大根堆：
- 对于一棵二叉树，若树中的任意一个节点的权值都小于等于其父节点的权值，则称该二叉树满足"大根堆性质"。满足"大根堆性质"的完全二叉树就是"大根堆"
- 若树中任意一个节点的权值都大于等于其父节点的权值，则称该二叉树满足"小根堆性质"。满足"小根堆性质"的二叉树就是"小根堆"
如图所示：
适用范围：海量数据求前n大或者前n小，并且n比较小，堆可以放入内存
基本原理及要点：最大堆求前n小，最小堆求前n大。比如：最大堆求前n小：
- 第一步：将前n个数据都放入堆中，维护一个大小为n的最大堆；
- 第二步：遍历之后的数据，比较当前元素与最大堆里的最大元素（堆顶元素），如果它小于最大元素，则应该替换那个最大元素；
- 第三步：将整个最大堆扫描一遍即可得到所有的前n元素。
扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
2、手写堆（小根堆）
小根堆：父节点比左右儿子小。
一个堆的基本功能：
- 插入一个数；
- 求集合当中的最小值;
- 删除最小值；
- 删除任意一个元素；
- 修改任意一个元素。
如何存贮堆？
考虑用数组来存贮二叉树，根结点下标为1 （不建议从0开始），假设父节点编号为x，那么x的左儿子为：2x，x的右儿子为2x + 1。
2个基本操作：
- down(x)操作：下沉一个节点，自上往下维护这个堆。将当前点x跟它的儿子们相比，把最小的作为新的父结点，也就是继续一次交换，然后递归下去，直到不需要进行交换，就能保持小根堆为止。
- up(x)操作：上升一个节点，自下往上维护这个堆。up(x)只需要把x和它的父结点x / 2进行比较就行，如果父结点较大，那就交换他们俩，然后递归下去，直到不需要交换为止。
如何实现一个堆的基本功能？
- 插入一个数x:
heap[++size] = x; up(size); - 求集合中的最小值 :
heap[1]; - 删除最小值:
heap[1] = heap[size]; size--; down(1); - 删除集合中任意一个数:
heap[k] = heap[size]; size--; down(k); up(k); - 修改集合中任意一个数:
heap[k] = x; down(k); up(k);
down()和up()函数代码模版：
// 值变化，往下维护 void down(int u) { int t = u; // t记录最小值 if (2 * u <= size_ && h[2 * u] < h[t]) t = 2 * u; // 左儿子存在，且值比父亲小 if (2 * u + 1 <= size_ && h[2 * u + 1] < h[t]) t = 2 * u + 1; // // 右儿子存在，且值比父亲小 if (t != u) { swap(h[t], h[u]); down(t); } return; } // 值变化，往上维护 void up(int u) { if (u / 2 > 0 && h[u / 2] > h[u]) { swap(h[u / 2], h[u]); up(u / 2); } return; }
题目要求：
维护一个集合，初始时集合为空，支持如下几种操作：
- I x，插入一个数 x；
- PM，输出当前集合中的最小值；
- DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
- D k，删除第 k 个插入的数；
- C k x，修改第 k 个插入的数，将其变为 x；
输入格式：
- 第一行包含整数 N。
- 接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM
输出样例：
-10 6
C++完整代码
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 100010; int h[N], ph[N], hp[N], cnt; void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } } void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } } int main() { int n, m = 0; scanf("%d", &n); while (n -- ) { char op[5]; int k, x; scanf("%s", op); if (!strcmp(op, "I")) { scanf("%d", &x); cnt ++ ; m ++ ; ph[m] = cnt, hp[cnt] = m; h[cnt] = x; up(cnt); } else if (!strcmp(op, "PM")) printf("%d\n", h[1]); else if (!strcmp(op, "DM")) { heap_swap(1, cnt); cnt -- ; down(1); } else if (!strcmp(op, "D")) { scanf("%d", &k); k = ph[k]; heap_swap(k, cnt); cnt -- ; up(k); down(k); } else { scanf("%d%d", &k, &x); k = ph[k]; h[k] = x; up(k); down(k); } } return 0; }
