什么是循环不变式 想象你在玩一个寻宝游戏，你需要按照一定的规则在地图上寻找宝藏。循环不变式就像是一种指导你寻宝过程的规则，它是在每一次寻宝过程中始终保持不变的条件或者性质。 比如，循环不变式可以是“当你走到某个地方时，地图上的宝藏总是在你的左手边”，这个条件在你每一步走的过程中都是保持不变的。如果你发现这个条件不成立，就意味着你可能迷路了或者地图有…

散列思想 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。 散列函数 散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。 该如何构造散列函数呢？我总结了…

二分查找 public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] == value) { return mid; } e…

递归 递归的三个关键: 1.定义需要递归的问题（重叠子问题)——数学归纳法思维 2.确定递归边界 3.保护与还原现场 递归形式 时间复杂度 常见问题 指数型 k^n 子集，大体积背包 排列型 n! 全排列，旅行商，N皇后 组合型 n!/m! * (n-m)! 组合选数 递归模板 void recursion(int level, int param…

数组 变长数组(resizable array) C++: vector Java: ArrayList. Python: list 如何实现一个变长数组? 支持索引与随机访问·分配多长的连续空间? 空间不够用了怎么办? 空间剩余很多如何回收? 一个简易的实现方法 初始:空数组，分配常数空间，记录实际长度(size）和容量(capacity) Pu…