不做庸人
动态规划一日一题-10-1-最小编辑距离 动态规划一日一题-10-1-最小编辑距离
最小编辑距离 给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有： 删除–将字符串 A 中的某个字符删除。 插入–在字符串 A 的某个位置插入某个字符。 替换–将字符串 A 中的某个字符替换为另一个字符。 现
2021-10-01 罗林
一日一题 线性dp
位运算 位运算
85.不用加减乘除做加法 写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷＋、－、×、÷ 四则运算符号。 样例输入：num1 = 1 , num2 = 2 输出：3 对于对二进制数进行位运算来说，将其异或就是进行无进
2021-09-27 罗林
acwing
内存限制比较严格的一题(怪) 内存限制比较严格的一题(怪)
地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。 注意：不同目标可能在同一位置。 现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位
2021-09-23 罗林
acwing
头痛的二分查找 头痛的二分查找
二分手册(持续总结更新)经过长时间的保守二分法调试的折磨(主要是边界条件的一些细节). 经常看着别人的代码与自己的代码明明是一样的，但是别人的直接AC,我的要么TLE，要么CE，要么SF…….. 所以，经过长时间的血泪教训与总结，我开始渐渐
2021-09-19 罗林
总结
线性DP专题 线性DP专题
1.最长公共子序列 给定两个长度分别为 N和M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式第一行包含两个整数 N 和 M。 第二行包含一个长度为 N 的字符串，表示字符串 A。 第三行包含
2021-09-18 罗林
acwing
并查集 并查集
并查集1.目的一、合并两个集合即将其中的一个集合作为另外一个集合的son。 二、判断两个元素是否在同一个集合里面集合的表示方式是用树来表示(不一定是二叉树)， 每个节点存储的是当前的节点的父亲节点，根节点存储的是该集合的编号。即只需要两个元
2021-09-15 罗林
acwing
字符串哈希的理解 字符串哈希的理解
字符串哈希 给定一个长度为 n 的字符串，再给定 m个询问，每个询问包含四个整数 l1,r1,l2,r2请你判断 [l1,r1][l1,r1] 和 [l2,r2][l2,r2] 这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小
2021-09-15 罗林
acwing
STL的用法总结-摘自acwing STL的用法总结-摘自acwing
vector（变长数组），倍增的思想，支持比较运算（按字典序） 定义：： vector a; 定义：一个vector数组a vector a(10); 定义：一个长度为10的vector数组a
2021-09-15 罗林
acwing
数据范围的判断-摘自acwing 数据范围的判断-摘自acwing
一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在 10的七次方到10的八次方为最佳。 下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择： n≤30, 指数级别, dfs+剪枝，状态压缩dpn≤
2021-09-12 罗林
acwing
背包问题思考 背包问题思考
背包问题分类：1.01背包问题 有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。 第 ii 件物品的体积是 vivi，价值是 wiwi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价
2021-09-09 罗林
acwing
妙 妙
799.最长连续不重复子序列 给定一个长度为 nn 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入格式第一行包含整数 nn。 第二行包含 nn 个整数（均在 0∼1050∼105 范围内），表示整数序列。 输出格式共
2021-09-09 罗林
acwing
双指针算法专题 双指针算法专题
一、不修改数组找出重复的数字给定一个长度为n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。 请找出数组中任意一个重复的数，但不能修改输入的数组。 样例给定 nums = [2, 3, 5, 4, 3, 2, 6,
2021-09-09 罗林
acwing
4 / 5