数位dp 数位分解：将一个数按照各个数位进行分解，例如将123分解为1、2、3。数位dp主要涉及到对这些数位的状态进行动态规划，通常，状态表示当前处理到的位置、当前已经得到的数值等信息。 可用于解决如数位上包含特定数字、数字之和等问题。 数位dp模板 2376. 统计特殊整数(2120) 123456789101112131415161718192021222324class Solution { public int countSpecialNumbers(int n) { char cs[] = String.valueOf(n).toCharArray(); int memo[][] = new int[cs.length][1 << 10]; for (int i = 0; i < cs.length; i++) Arrays.fill(memo[i], -1); return dfs(0, 0, true, false, cs, memo); } // ...

划分型dp 对数组或者字符串进行位置划分，划分成几个子数组或者子字符串 判定能否划分 一般定义f[i]表示长为i的前缀a[:i]能否划分，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑a[L:j]是否满足要求 2369. 检查数组是否存在有效划分(1780) 计算划分最优值 定义f[i]表示对于前缀[0:i)所得到的最优解，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑子数组[L:i)对最优解的影响 2707. 字符串中的额外字符(1736) 约束划分个数 定义f[i][j]表示对于前缀[0:i)划分成j个连续子数组所得到的最优解，枚举最后一个子数组的左端点L，从f[L][j-1]转移到f[i][j]，并考虑子数组[L:i)对最优解的影响 2911. 得到 K 个半回文串的最少修改次数(2608) 不相交区间 2008. 出租车的最大盈利(1872)

数据结构优化dp 其它优化dp 3181. 执行操作可获得的最大总奖励 II

网格图dp 在网格图上的移动 62. 不同路径 1594. 矩阵的最大非负积

背包 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，枚举右，维护左 二重哈希 第一个哈希的value被当作key放入第二个哈希 3092. 最高频率的 ID 字符串哈希 请看字符串哈希 前缀和+哈希表 请看前缀和 遍历过程维护集合大小 在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示 12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录集合大小 for (; j < n && map.size() <= k; j++) { if (ma ...

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输 ...