阿日哥的向量空间

原题链接：https://www.acwing.com/problem/content/description/790/ 首先根据定理：交换紧邻的一个逆序对会使得整个数组的逆序对数量减一，我们可以得知，冒泡排序中元素交换的次数即等于逆序对的个数。 所以，可以直接使用冒泡排序统计逆序对的数量： void bubble_sort(int nums[], int left, int right) { for (int i = 0; i < right - left; i++) { for (int j = left; j < right - i - 1; j++) { if (nums[j] > nums[j+1]) { swap(nums[j], nums[j+1]); count++; } } }} 但是冒泡排序的复杂度是，效率太低。 我们可以考虑采用分治思想，将数组一分为二，然后求出： 左半部分逆序对的个数 右半部分逆序对 ...

原题链接：https://www.acwing.com/problem/content/789/ 归并算法采用双指针实现，模板实现起来也比较简单。 // merge sort in [left, right)void merge_sort(int nums[], int left, int right) { if (right - left <= 1) return; int mid = (left + right) >> 1; merge_sort(nums, left, mid); merge_sort(nums, mid, right); int i = left, j = mid, k = 0; // i 和 j 不断移动取最小值，直到其中一个越界 while (i < mid && j < right) if (nums[i] < nums[j]) tmp[k++] = nums[i++]; else tmp[k++] = num ...

原题链接：https://www.acwing.com/problem/content/788/ k-选取问题的核心依然是快速划分算法partition()，可以保证在的时间内完成k-选取。 #include <iostream>void swap(int& x, int& y) { if (x == y) return; x ^= y; y ^= x; x ^= y;}int partition(int nums[], int left, int right) { int i = left, j = right - 1; swap(nums[left], nums[(left + right) >> 1]); int pivot = nums[left]; while (i < j) { while (i < j && pivot < nums[j]) j--; if (i < j) nums[i++] = nums[j]; ...

原题链接：https://www.acwing.com/problem/content/description/787/ 快速排序算法最核心的部分是如何根据分界点pivot将数据划分为大于分界点和小于分界点的两部分。假设将划分算法记作partition()，那么partition又分为三种主流的实现。 LUG版 这个版本的缺点在于，对于大部分数据存在重复的情况，这个版本的划分会极不平衡。当数据全部重复时，使用该版本partition()算法的快速排序复杂度在。 这个版本的特点可以总结为： 勤于拓展 懒于交换 int partition(int nums[], int left, int right) { int i = left, j = right - 1; int mid = (left + right) >> 1; // 偷懒直接取中点 swap(nums[i], nums[mid]); int pivot = nums[i]; while (i < j) { while (i < j &a ...

AcWing的算法相关课程可以用来打牢基础，把所有的经典算法手敲一遍后可以加深理解和记忆。这里总结了所有相关的内容和打卡记录。 一、基础算法 排序 AcWing 785. 快速排序 AcWing 786. 第k个数 AcWing 787. 归并排序 AcWing 788. 逆序的数量 二分 AcWing 789. 数的范围 AcWing 790. 数的三次方根 高精度 AcWing 791. 高精度加法 AcWing 792. 高精度减法 AcWing 793. 高精度乘法 AcWing 794. 高精度除法 前缀和与差分 AcWing 795. 前缀和 AcWing 796. 子矩阵的和 AcWing 797. 差分 AcWing 798. 差分矩阵 双指针算法 AcWing 799. 最长连续不重复子序列 AcWing 800. 数组元素的目标和 位运算 离散化 区间合并 二、数据结构 链表与邻接表：树与图的存储 栈与队列：单调队列、单调栈 kmp Trie 并查集 堆 Hash表 三、搜索与图论 DFS与BFS 树与图的遍历：拓扑排序 最短路 最小 ...

多情自古空余恨，好梦由来最易醒。 岂是拈花难解脱，可怜飞絮太飘零。 香巢乍结鸳鸯社，新句犹书翡翠屏。 不为别离肠已断，泪痕也满旧衫青。 自古以来，多情的人总是会留下遗憾，越是美好的梦也越容易醒来。不是拈花一笑就可以解脱，只是可怜了那飘飞的柳絮居无定所。欢聚之地刚刚建好，新作诗句还留在翡翠屏上。肝肠寸断撕心裂肺不是因为离别，伤心痛苦，眼泪也洒满了旧衣衫。

朋友问没有情侣的情人节，我该干嘛？我说在你的他（她）没出现之前，自己好好爱自己，好好照顾自己，好好保护自己，不要让将来的他（她）看见一个伤痕累累的你....

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在为最佳。 下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择： ，指数级别，dfs+剪枝，状态压缩dp ，floyd，dp，高斯消元 ，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford ，块状链表、分块、莫队 ，各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树 , 以及常数较小的算法：单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的的做法：sort、树状数组、heap、dijkstra、spfa ，双指针扫描、kmp、AC自动机、线性筛素数 ，判断质数 ，最大公约数，快速幂，数位DP ，高精度加减乘除 ，k表示位数，高精度加减、FFT/NTT

总结一些Java常用的集合接口以及一些工具类。 Java Collections 类 Collection is the root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate the ...

从llvm::Expected的源码中学习一种实用的C++异常处理方式