背包 0-1背包 给定一个背包的容量c和n个物品，第i个物品的体积为w[i]，价值为v[i]。每个物品选或不选，求体积和不超过capacity时的最大价值和 核心思路：枚举第i个物品选或不选 初始化一个二维数组dp，其中dp[i][j]表示在考虑前i个物品、背包容量为j的情况下的最大总价值 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) 背包至多装capacity 求方案数 求最大价值和（传统01背包） 背包恰好装capacity 求方案数: 494. 目标和 求最大价值和 求最小价值和 背包最少装capacity 求方案数 求最小价值和 其它 3180. 执行操作可获得的最大总奖励 I 完全背包 给定一个背包的容量c和n种物品，第i种物品的体积为w[i]，价值为v[i]。每种物品无限次重复选，求体积和不超过capacity时的最大价值和 考虑第i个物品选不选时，可以重复选择，所以这里考虑dp[i][c]时，可能多次更新dp[i][c-w[i]] + v[i] dp[i][c] = max(dp[i-1] ...

哈希大法 枚举右维护左 对于双变量问题，例如两数之和 (a_i + a_j = t)，可以枚举右边的 (a_j)，转换成单变量问题。也就是在 (a_j) 左边查找是否有 (a_i = t - a_j)，这可以用哈希表维护。 用哈希记录之前的数，并用于判断情况是否成立 1. 两数之和：经典的枚举右维护左 421. 数组中两个数的最大异或值: 对于每一位bit，枚举右维护左 3381. 长度可被 K 整除的子数组的最大元素和: 枚举右维护之前每个余k索引的前缀和最小值 [3404. 统计特殊子序列的数目]：题目式子变形 + 枚举右维护左 二重哈希 第一个哈希的value被当作key放入第二个哈希 3092. 最高频率的 ID 字符串哈希 请看字符串哈希 前缀和+哈希表 请看前缀和 遍历过程维护集合大小 在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示 12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录 ...

Stream Stream::max(int 和 Integer的不同) 12345int intArr[] = new int[]{1, 2, 3};Arrays.stream(intArr).max().getAsInt(); Integer integerArr[] = new Integer[]{1, 2, 3};Arrays.stream(integerArr).max(Integer::compareTo).get(); Stream中 int 和 Integer 互相转换 mapToObj: int -> Integer 三种方式：mapToObj(Integer::valueOf), mapToObj(i->Integer.valueOf(i)), mapToObj(i->i) 123// int数组转换成Integer列表int nums = new int[]{1, 2, 3};List<Integer> list = Arrays.stream(nums).mapT ...

《Redis设计与实现》：笔记 指令 Redis指令参考：Redis Order 结构 对象9 type：对象的类型 REDIS_STRING，字符串对象 REDIS_LIST，列表对象 REDIS_HASH，哈希对象 REDIS_SET，集合对象 REDIS_ZSET，有序集合对象 数据类型 汇总一个类型对应的多种编码 REDIS_STRING，字符串对象 REDIS_ENCODING_INT 要求字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示 ptr属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int 通过 APPEND 命令， 向一个保存整数值的字符串对象追加了一个字符串值，对象的编码就会从int变成raw REDIS_ENCODING_RAW 字符串对象保存的是一个字符串值，且长度大于 39 字节 ptr指针指向一个SDS对象（sdshdr） REDIS_ENCODING_EMBSTR 字符串对象保存的是一个字符串值，且长度小于等于 39 字节 和raw一样，ptr指针指向一个SDS对象，但它的 ...

Markdown 段内换行 在一行的结尾插入两个或以上的空格 链接地址 链接和文字分开，例如google,baidu 1234[google],[baidu][google]:https://www.google.com[baidu]:https://www.baidu.com 网址链接 用<>包围，例如1234@qq.com（GFM拓展语法可以自动识别，不需要用<>） 1<1234@qq.com> 表情符号 :smile:: :smile: :laughing:: :laughing: 表格 左对齐 居中对齐 右对齐 01 hello a 02 world b 1234| 左对齐 | 居中对齐 | 右对齐 || :--- | :--: | ---: || 01 | hello | a || 02 | world | b | 任务列表 [x] 已完成 [ ] 未完成 12- [x] 已完成- [ ] 未完成 锚点 Markdown 段内换行 链接地址 网址链接 表情符号 表格 任务列表 锚点 拓展 MySql ...

最近公共祖先 描述 问题就是寻找树上两个节点的最近公共祖先节点 边权重均等查询 此题难度超过2500 现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。 另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。 注意： 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。 返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。 示例 1： 1234567输 ...

循环节 循环节：指在序列中出现的一种重复的、周期性的模式。这个模式可以是一组连续的元素，也可以是整个序列的重复。 周期性特征：序列中的循环节反映了序列的周期性特征，即序列中的某一段会以某种方式重复出现。 寻找循环节的方法 快慢指针法：用两个指针，一个每次走一步，另一个每次走两步。如果存在循环节，两个指针最终会相遇。 哈希表法：使用哈希表记录每次遍历的状态，如果发现某个状态已经出现过，说明存在循环节。 统计重复个数 定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。 例如，str == ["abc", 3] =="abcabcabc" 。 如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。 例如，根据定义，s1 = "abc" 可以从 s2 = "ab***dbe***c" 获得，仅需要删除加粗且用斜体标识的字符。 现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = ...

差分数组 1234a[0] a[1] a[2] a[3] a[4] (0)差分数组: a[0] a[1]-a[0] a[2]-a[1] a[3]-a[2] a[4]-a[3] (-a[4])对差分数组求前缀和: a[0] a[1] a[2] a[3] a[4] (0)// 考虑末尾0(-a[4])，那么差分数组之和sum=0 前缀和就是离散版本的“求积分”，差分数组就是离散版本的“求微分” 形成目标数组的子数组最少增加次数 给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。 答案保证在 32 位有符号整数以内。 示例 1： 1234567输入：target = [1,2,3,2,1]输出：3解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。[0,0,0,0,0] 将下标为 0 到 4 的元素（包 ...

前缀和 前缀和是一种数组变换方法，通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样，计算任意区间的和变得非常高效，只需一次前缀和计算即可，而不需要多次重复计算。 123int[] nums;int n = nums.length, sum[] = new int[n+1];sum[i+1] = sum[i] + nums[i]; 需要用sum[0]表示空数组的和 l到r的区间和表示为 sum[r+1] - sum[l] 例如，nums[0]到nums[5]的区间和表示为 sum[6] - sum[0] 二维前缀和 定义sum[i+1][j+1]表示左上角grid[0][0]，右下角grid[i][j]的子矩阵元素和 123456int[][] sum = new int[m + 1][n + 1];for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] ...

单调栈 单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，从栈顶添加和删除元素，其次栈中的所有元素单调递增或者单调递减 在一个队列Deque中，我们offer右边，poll左边，这样左边就是队首，右边是队尾 如果这个Deque作为栈，我们push和pop左边，并且把左边作为栈顶 单调性的判断是从栈顶到栈底（Deque中从左往右看） 单增栈：栈顶到栈底的元素是单调递增的，即栈顶的元素最小 单减栈：栈顶到栈底的元素是单调递减的，即栈顶的元素最大 后上界：对于数组中的某个元素 a[i]，它的后上界是指在它之后的第一个比它大的元素 后下界：对于数组中的某个元素 a[i]，它的后下界是指在它之后的第一个比它小的元素 单调栈在算法中的应用在于它能够在一次扫描(从左到右)即O(n)的复杂度之内找到数组中每一个元素的后上界(单增栈)或者后下界(单减栈) 496. 下一个更大元素 II: 递增栈获得每个元素的后上界 2866. 美丽塔 II(2072) 1944. 队列中可以看到的人数(2105) 2454. 下一个更大元素 IV(2175)：双单调栈 ...