代码编织梦想

leetcode:1782. 统计点对的数目【图论抽象 + 点对统计 + 去重判断】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 # (x, y) x < y为一个点对 # (x, y)与点对中至少一个点相连的边的数量 = #

leetcode:1203. 项目管理【双topo:组间topo + 组内topo】_leetcode 1203-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 没有第一个条件,就是简单topo排序有了第一个条件,每个小组都需要完全隔开,因此不同小组间也需要一个topo排step1:对于gr

leetcode:1862. 向下取整数对和【遍历底数固定maxn取倍数的clogc做法 + counter前缀和记录区间中元素个数】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 朴素做法平方复杂度通过cnt记录元素出现的次数遍历分母x寻找出现在[kx, k(x + 1) - 1]的元素个数这个需要对cnt进

leetcode:1847. 最近的房间【排序 + 二分 + 离线查询】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 size肯定要排序每个query找到更大的size,然后对应的id在对应id里面二分,找到最临近的能否使得id持续集成?也就是不用

leetcode:210. 课程表 ii【拓扑排序模板之bfs入度表实现法 + 判环】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 先修到后修形成一条有向边先加入入度为0的,然后dq popleft,每加入一个新的dq 其对应的下一个点的入度减1如果入度减到0,

leetcode:1857. 有向图中最大颜色值【topo判环 + dp求解图论】_图上颜色最大交集-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 topo判环颜色有限只有26个,起点就是入读为0的点那么,能否遍历终点和颜色,也就是26n的复杂度,找到每个终点对应的每个颜色出现

leetcode:363. 矩形区域不超过 k 的最大数值和【上下边界框定 + 从左往右遍历 + sortedlist找最接近答案的前缀和】_最大区域顺序边界框-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 最直观的是o(mmnn)的二维前缀和 + 遍历左上右下做法但是会超时考虑固定上下边界,从左到右逐次加入每列框定的和用stl记录所有

leetcode:1801. 积压订单中的订单总数【heapq】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 sell维护price最小的,buy维护price最大的每加入一个,去看另一个的堆顶,看看能否抵消一直while看,直到不能抵消的

leetcode:1746. 经过一次操作后的最大子数组和【子数组 + 识别状态 + 舍去负贡献】_leetcode 1746-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 对于子数组,dp[i]表示最后一位取i的最大和可以翻转or不翻转,另计一维dp[i][0]表示到i前(包括)未翻倍,但最后选idp

leetcode:lcp 64. 二叉树灯饰【经典树状dp】_64二叉树灯-爱代码爱编程

分析 考虑当前节点的状态:它可能受祖先的开关2影响,可能受父亲的开关3影响 由于是树状,显然是一个树状dfs的结构 里面参数需要记录受开关2和开关3的影响 开关2的影响纪录奇偶,开关3的影响记录有无 两种情况:考虑当前

leetcode:2478. 完美分割的方案数【预处理 + dp定义 + 前缀和优化】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 开头必定是prime,结尾必定是not primek = 1特判找到所有可能的结尾点(最后一个不考虑)结尾点i必须满足s[i]-&

leetcode:1114. 按序打印【atomicinteger保证并发安全 + incrementandget】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 用firstJobFinish和secondJobFinish来判断第一二项工作是否做完用while循环通过get获取这两个Ato

leetcode:1326. 灌溉花园的最少水龙头数目【小区间覆盖大区间 + 经典排序dp】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 把所有小区间限制在[0, n]转换为小区间覆盖大区间的最少个数按左端点排序dp[i]表示覆盖[0, i]的最少区间数假设当前区间是

leetcode:2551. 将珠子放入背包中【从整体考虑 + 思维转换】_leetcode 2551-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 # 思维题,从整体考虑 # 假设k个区间是[a1, b1], ... , [ak, bk] # ai &l

leetcode:854. 相似度为 k 的字符串【异位词最少交换次数 + bfs暴搜 + 多记录当前匹配到的idx + 剪枝】-爱代码爱编程

分析 一开始无脑暴搜 就是随缘乱换 然后只限制了不重复 这种换发会导致许多不必要的消耗 无脑乱换bfs class Solution: def kSimilarity(self, s1: str, s2:

leetcode:1168. 水资源分配优化【思维转换 + 最小生成树】_leetcode 1168-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 # 必须要有一个水井 # 假设所有水井都从供水局0出发 # 在x处造一口井,等价与连接0和x,cost=w

leetcode:1439. 有序矩阵中的第 k 个最小数组和【最小堆 + 状态记录】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 最小堆存【当前状态和,对应状态】状态 = 每行取的是第几位的listseen记录已选取的状态,防止重复每次pop最小状态和,然后得

leetcode:1591. 奇怪的打印机 ii【思维转换 + topo排序】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 我们想从白板画到targetGrid需要判断是否存在一个图画的顺序满足要求对于两个颜色c1和c2怎么确定先后?找到c1的最大覆盖矩

leetcode:1187. 使数组严格递增【换or不换 + 二分贪心换最小增量 + dfs记忆化】-爱代码爱编程

目录 题目截图题目分析ac code总结 题目截图 题目分析 arr2时用来替换的,先set去重再sort排序逐为遍历arr1,如果第i位大于前一位,可以换or不换;如果小于等于,则必须换换的

leetcode:576. 出界的路径数【用第几次作为维度 + 滚动数组优化】-爱代码爱编程

目录 题目截图题目分析无脑三维有脑二维总结 题目截图 题目分析 我们想找在maxMove出界的那么在第几次出界呢,在哪里出界呢?第几次i,哪里[j,k]因此dp[i][j][k]表示第i次落在