灵神专题
灵神算法题单——定长滑动窗口（进阶）
2134. 最少交换次数来组合所有的 1 II 断环成链+滑动窗口 思路先算出数组中1有多少，然后看这么长的窗口里0最少是多少，此时即为最少交换次数。 首先遍历算出1的数量k，然后用Insert拼接数组，从而实现循环。 然后双指针遍历数组，是0就ant++,如果窗口长度超了，缩一下j，当窗口建立完毕时更新mi class Solution {public:int minSwaps(ve
灵神算法题单——不定长滑动窗口（求最短最小）
209. 长度最小的子数组 class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int ant=0,mi=1000005;int q[100009];int hh=0,tt=-1;for(int i=0;i<nums.size();i++){q[++tt]=nums[i];ant+=nums[i
灵神算法题单：不定长滑动窗口
3. 无重复字符的最长子串 class Solution {public:int lengthOfLongestSubstring(string s) {int n=s.length(),ans=0,left=0;unordered_map<char,int> w;for(int i=0;i<n;i++){char c=s[i];while(w[c])w.erase(s[left++]);w[
灵神DP题单---划分型 DP---§6.1 判定能否划分
这里的状态定义一般使用DP【i】 表示 考虑前i个东西能否满足条件，然后我们枚举上一次的转移位置就好了 2369. 检查数组是否存在有效划分 需要注意的是我习惯从1开始写，所以要处理好边界的下标问题 class Solution {public:bool validPartition(vector<int>& nums) {int n = nums.size();v
字符串匹配算法（z函数模版）来自灵神。
一个字符串s求出s的z[i]，z[i]表示以s[i:n]这一段和s[0:n]的从前往后的连续相等字母个数。 比如 abacaba,z[2] = (acaba与abacaba比较) = 1。
13.单调栈（接雨水、柱状图最大矩形）【灵神基础精讲】
单调栈【灵神基础精讲】 https://www.bilibili.com/video/BV1VN411J7S7/ 单调栈和单调队列的关系：单调队列=单调栈+滑窗 单调栈，顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。 适用问题：单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到下一个比他大（小）的元素。也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决
739 每日温度（单调栈）（灵神笔记）
题目 每日温度 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1: 输入: temperatures= [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0] 示例
1000 合并石头的最低成本（区间DP）（前缀和）（灵神笔记）
题目 合并石头的最低成本 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。 每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。 返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。 示例 1： 输入：stones = [3,2,4,1], K = 2 输出：20 解释： 从 [3, 2, 4, 1] 开始。
1039 多边形三角剖分的最低得分（状态机DP）（灵神笔记）
题目 多边形三角剖分的最低得分 你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。 返回 多边形进行三角剖分后可以得到的最低分 。
516 最长回文子序列（区间DP）（灵神笔记）
题目 最长回文子序列 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例 1： 输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。 示例 2： 输入：s = “cbbd” 输出：2 解释：一个可能的最长回文子序列为 “bb” 。 提示
188 买卖股票的最佳时机IV（状态机DP）（灵神笔记）
题目 买卖股票的最佳时机IV 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1： 输入：k = 2, prices = [2,4,1
309 买卖股票的最佳时机含冷冻期（状态机DP）（灵神笔记）
题目 链接 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: prices = [1,2,3,0
1626 无矛盾的最佳球队（排序+动态规划）（灵神笔记）
题目 1626 假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。 然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。 给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i]
每日一题 1143最长公共子序列（LCS）（灵神版本）
题目 题目 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串
每日一题 72编辑距离（LCS）（灵神笔记）
题目 编辑距离 你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1： 输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose