Alex's Warm Home

使用单调队列 单调队列是一种主要用于解决滑动窗口类问题的数据结构. 时间复杂度为 O (n). 其原理就是一句话，当队列中前面的数比后面的小 (大) 时，前面的数出队. 实现上，维护一个双向队列， 遍历时仅当一个元素可能成为某区间的最值时才保留它. 代码 import collectionsmonotonous_queue = collections.deque()class Item(object): def __init__(self, i, v): self.index = i self.value = vitems: tuple[Item] = tuple()def front(): return monotonous_queue[0]def back(): return monotonous_queue[-1]for i in range(0, n): if not monotonous_queue.empty() and top().index <= i - length: ...

起源：为什么要有头文件 头文件在 1970 年原始的 C 中并不存在。代码的复用靠的是编译后的链接过程. 这也是当时语言的主流选择. 如此的一个最重要的原因是当时的程序设计哲学讲求二进制复用以兼容不同高级语言的编译产物. 因此，C 程序里可能存在对其它语言函数的调用。比起其它 C 程序， 这些函数对于 C 编译器来说更是一头糨糊. 编译的时候碰到这些函数只会识别为外部符号等待链接。既然如此， 没有任何必要为 C 程序单独处理，这也符合 C 语言尽可能简单易实现的哲学. 如此，函数声明也是不必要的. 事实上，现代的 C 程序依然保持这这种兼容性. 例如以下代码完全可以通过编译. int main(){ puts("Hello");} 这里的 puts 就需要连接 stdio.h 才能正常调用. 那么一个很重要的问题就是，各个编程语言的数据类型风马牛不相及， 链接的时候怎么保证参数和返回值类型检查呢？ 在当时根本不需要考虑这个问题。因为 当时的语言基本上都只有字长一种数据类型. 没错，C 语言的类型系统是后加的。因此为了兼容性，C 语言是弱类型的. 这类编程语言的函数调用...

...

C/C++ 提供 static 关键字修饰变量， 而这个关键字在不同场合下的用法是在是千奇百怪，因此我决定做一个总结. C 语言中的 static 首先，当 C 语言引入这个关键字的时候，它的意思可以概括为: 将被修饰的变量放到程序文件的数据段中. 因此， 它有如下特性: 修饰的变量的作用域最大为本文件. 修饰的变量的生命周期为程序运行期间， 因此可以在一个函数内定义一个静态变量而在外部引用它. 修饰的变量只初始化一次. 也因此，它有如下限制: 修饰的变量必须用常量表达式初始化. 修饰的变量不能出现在结构体内， 除非结构体也是静态的.(因为一个结构体只能使用一块连续的内存) C++ 中的 static C++ 继承了 C 语言的 static 用法，但是为了一时图方便， 就像承认 const 的常量性那样，允许静态变量用变量表达式初始化. 除此之外，C++ 引入了类，顺便用 static...

在指定内存位置创建对象 作为一门允许程序员自己操作内存的语言， C++ 提供了三种方式在指定的内存位置创建对象. 而为什么要在指定位置创建对象呢？作用有三: 预先足够的分配内存，以便减少使用中分配内存的操作. 重复利用内存，减少内存碎片. 方便进行细粒度管理. 实现这个需求的方式有三种. 在接下来的文章中，我们使用如下类作为示例. class Person { private: int age; std::string name; public: int get_age() { return age; } bool set_age(int a) { age = a; return true; } std::string get_name() { return name; } bool set_name(std::string &s) { name = s; ...

用数组实现的二叉树的性质 二叉树 (其实二叉堆也是) 经常可以用数组实现， 但是有些操作可能不够直观需要特别留意 以下假设数组为 0 索引 数组长度 设 l 为数组长度，h 为二叉树高度，则 父子关系 设父节点为 f, 左右子节点为 cl 和 cr. 则 cl 一定为奇数而 cr 一定为偶数.

...

树状数组详解 简介 树状数组，顾名思义，就是像树一样组织的数组. 它的大体样子如下 (数组元素用 a 表示，树节点用 c 表示): 如图所示， 所谓树状数组就是在数组基础上加上一个向右倾斜的树结构维护一定的数组区间信息. 从图上可以看出， 管理 , 管理 , 管理 , 则管理全部 8 个数. 对于没有在图上显示的也是一样的. c 与 a 的对应关系 10 进制下 c 和 a 的下标关系很难看出来，但是在 2 进制下: 其规律就是节点维护数组 a 中 (x - lowbit (x), x] 的和 而 lowbit (x) 就是 x & -x 即 x 只保留最低位的 1 的值. lowbit (x) 不仅代表所反应的区间长度，同时也是在树上的节点高度 构建 由于树状数组顶层节点的值由多个底层节点的值决定， 因此可以先确定底层节点的值再计算顶层的. 运行复杂度为 O (n) // C++ Version// O(n)建树void init() { for (int i = 1; i <= n; ++i) { t[i] += a[i]; int...

xargs 是 *shell* 中负责从标准输入和管道读取给定命令的选项以及参数的一个命令.