排序算法总结
一些知识 稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。 非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。 原地排序：指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换。 非原地排序：需要利用额外的数组来
数组实现线段树
常规线段树，数组实现！！！ 问题例题 数组区间内最小值、最大值、总和等问题； 定义 线段树 segmentTree 是一个二叉树，线段树可以用树也可以用数组（堆式存储）来实现。 线段树结构有点像堆，一般用数组来表示线段树的结构； 在index = 0的位置保存根节点，则左子节点是2 * index + 1,右子节点是2 * index + 2; (若在index = 1的位置保存根节点，则左
常见字符串动规解法总结
总结 根据连续还是非连续定义dp数组，也就是注意区分子序列或子串； dp[i]含义有以nums[i]结尾的【j，i】区间，或【0，i】区间范围内； 遍历顺序根据递推公式确定，可能有： 一维dp[i]一般是从前往后遍历； 二维dp[i][j]分情况： 如果是一个字符串，例如回文串，从下往上遍历； 如果是两个字符串，一般是从上往下、从左往右遍历； 注意初始化； 最长公共子序
递归与贪心与动态规划
递归递归三部曲 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。 确定单层
背包问题
背包问题 一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包 01背包：问题描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 一维dp 确定dp数组以及下标的含义： 1p[j] 表示容量为j的背包的价值总和最大是多少 确定递推公式： 1dp[j
回溯算法
可解决的问题 组合问题：N个数里面按一定规则找出k个数的集合 切割问题：一个字符串按一定规则有几种切割方式 排列问题：N个数按一定规则全排列，有几种排列方式 棋盘问题：N皇后，数独等等 总结模板123456789101112void backtracking(参数) { if (终止条件) { 存放结果; return; }
差分数组
定义差分数组是把原数组中后一个元素减前一个元素的差构成一个新的数组，作为辅助数组使用； 12345678diff[0] = nums[0];diff[1] = nums[1] - nums[0];diff[2] = nums[2] - nums[1];...nums[0] = diff[0];nums[1] = diff[1] + nums[0] = diff[0] + diff[1];num
单调栈与单调队列
不管是单调栈还是单调队列，都有金字塔形状和倒金字塔形状，按照具体题意分析； 单调栈问题类型： 在数组里面找到下一个比当前元素大的元素数值或下标、接雨水等等； 栈里面可以存下标或数值，建议存下标； 单调栈分为金字塔形状和倒金字塔形状； 按遍历方向不同，有不同的实现方式； 样式代码123456789101112131415161718192021222324252627282930313233
