龙晓

最长回文子序列516. 最长回文子序列 - 力扣（LeetCode） 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例 1： 输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。 示例 2： 输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。 提示： 1 <= s.length <= 1000 s 仅由小写英文字母组成 问题描述：找到字符串中的最长回文子序列。 状态转移方程： 如果s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] + 2 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 初始条件：dp[i][i] = 1 class Solution {public: int...

编辑距离72. 编辑距离 - 力扣（LeetCode） 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1： 输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e') 示例 2： 输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为...

最长公共子序列（LCS）给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 示例 2： 输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc" ，它的长度为 3 。 示例 3： 输入：text1 =...

最长连续递增序列 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 示例 1： 输入：nums = [1,3,5,4,7]输出：3解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 示例 2： 输入：nums = [2,2,2,2,2]输出：1解释：最长连续递增序列是 [2], 长度为1。 提示： 1 <= nums.length <= 104 -109 <= nums[i] <= 109 class Solution {public: int...

300. 最长递增子序列 - 力扣（LeetCode） 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的。 示例 1： 输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 输入：nums = [0,1,0,3,2,3]输出：4 示例 3： 输入：nums = [7,7,7,7,7,7,7]输出：1 提示： 1 <= nums.length <= 2500 -104 <= nums[i] <= 104 问题描述：找到序列中最长的递增子序列。 状态转移方程：dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i] 初始条件：dp[i] = 1 for all i class...

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 是数组中的一个连续部分。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 输入：nums = [1]输出：1 示例 3： 输入：nums = [5,4,-1,7,8]输出：23 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 问题描述：找到数组中连续子数组的最大和。 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i]) 初始条件：dp[0] = nums[0] class Solution {public: int maxSubArray(vector<int>& nums) { int NL=nums.size(); ...

6. Z 字形变换 - 力扣（LeetCode） 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下： P A H NA P L S I I GY I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。 请你实现这个将字符串进行指定行数变换的函数： string convert(string s, int numRows); 示例 1： 输入：s = "PAYPALISHIRING", numRows = 3输出："PAHNAPLSIIGYIR" 示例 2： 输入：s = "PAYPALISHIRING", numRows = 4输出："PINALSIGYAHRPI"解释：P I NA L S I GY A H RP I 示例...

题目目标是找到支付给定金额 x 所需的最小硬币数。硬币的面值为 1、5 和 11。硬币可重复选取 状态定义： dp[i] 表示支付 i 元所需的最小硬币数。 状态转移方程： dp[i] = min(dp[i-1], dp[i-5], dp[i-11]) + 1 这个方程表示，要支付 i 元，可以选择使用 1 元、5 元或 11 元的硬币，然后取其中的最小值加 1。 初始化： dp[0] 初始化为 0，因为支付 0 元不需要任何硬币。 其他 dp[i] 初始化为一个较大的值（如 0x3f3f3f3f），表示初始时不可达。 动态规划过程： 对于每个金额 i，从 1 到 n，计算 dp[i] 的值。 通过检查 i-1、i-5 和 i-11 的值，更新 dp[i]。 #include<iostream>#include<algorithm>using namespace std;const int N = 1e2 + 10; // 定义最大金额int dp[N]; // dp[i] 表示支付 i 元所需的最小硬币数int main()...

问题类型 核心区别 时间复杂度 典型应用场景 0-1背包 物品唯一 O(NV) 单次采购决策 完全背包 物品无限 O(NV) 货币组合问题 多重背包 物品数量限制 O(NVlog⁡S) 资源有限分配 混合背包 物品数量不固定 二维费用背包 双重约束 O(NMK) 多维度资源优化 分组背包 组内互斥 O(NV) 品牌选择问题 有依赖的背包 主件附件依赖 O($$NV^2$$) 组合商品购买 求背包方案数 求背包具体方案数 0/1背包二维核心逻辑： 二维数组存储状态，dp[i][j]表示前i个物品在容量j时的最大价值 时间/空间复杂度：O(n*m) 特点：直观体现状态转移过程 #include<iostream>using namespace std;const int N = 1010;int v[N], w[N]; // 价值数组和重量数组int dp[N][N]; // 二维DP数组int n, m; //...

Redis简介Redis（Remote Dictionary Server）是一个开源的内存数据结构存储系统。它以键值对形式存储数据，支持多种数据结构，它可以用作数据库、缓存和消息中间件。 它基于内存运行并支持持久化的NoSQL数据库，是当前最热门的NoSQL数据库之一。 MySQL：数据关系型数据库，使用的是表结构。 Redis：非关系型数据库，使用的是key-value 核心特性 支持持久化功能，也就是将数据从内存保存到磁盘中。 支持丰富的数据类型，包括：string、set、sort set、list、hash 支持数据的备份，也就是主从复制。 Redis的优点 性能极高 – Redis能读的速度是110000次/s,写的速度是81000次/s 。 丰富的数据类型 – Redis支持二进制案例的 Strings, Lists, Hashes, Sets 及 Ordered Sets 数据类型操作。 原子 –...