双序列问题 问题描述 双序列动态规划是指在两个序列上进行状态转移的问题。 常见的有最长公共子序列(LCS)、编辑距离等。 通常需要定义状态表示两个序列某个位置的最优解。 最长公共子序列(LCS) 算法思想  定义dp[i][j]表示s1的前i个字符和s2的前j个字符的LCS长度 如果s1[i] == s2[j]，则可以选择该字符作为LCS的一部分 状态转移方程：  当s1[i] == s2[j]时：dp[i][j] = dp[i-1][j-1] + 1 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])   最终答案为dp[n][m]  代码实现   c++  ...

题目链接 小红的顺子 题目描述 小红有一个长度为  的数组，满足  且 ，求顺子的最大长度。 顺子的定义为：对于长度为  的数组 ，如果 （），则称  是顺子。 输入:  第一行一个整数 ，表示数组的长度加1 第二行  个整数，表示严格递增的数组   输出:  一个整数，表示顺子的最大长度  解题思路 这是一个序列问题，可以通过以下步骤解决：   首先理解题目特点：  输入数组已经是严格递增的 不需要排序和去重 只需要找到连续递增（差值为1）的最长子序列    解题策略：  直接遍历数组 检查相邻两个数的差值是否为1 维护最长的连续序列长度    具体步骤：  遍历数组，检查相邻元素 如果 ，...

题目链接 小红的最大中位数 题目描述 小红拿到了一个数组，她准备选择一个子序列，使得该子序列的中位数尽可能大。小红想知道，一共有多少种方案？  奇数长度的子序列中位数为中间的那个数 偶数长度的子序列中位数为中间两个数的平均数  输入:  第一行输入一个正整数 ，代表数组大小 第二行输入  个正整数，代表小红拿到的数组  输出:  一个整数，代表选择的方案数（对  取模）  解题思路 这是一个组合计数问题，可以通过以下步骤解决：   关键发现：  要使子序列的中位数最大，那么中位数一定是原数组中的最大值 只需要统计以最大值为中位数的所有子序列数量    预处理：  对数组排序，找到最大值 统计小...

题目链接 小红购物 题目描述 小红准备买  件物品，第  件物品的价格是 。另外，小红有  种优惠券，第  个优惠券是：买一件价格不小于  的商品时，可以减去  的价格。  每件商品最多只能用一次优惠券 每种优惠券可以用多次  小红想知道，自己买全部商品最少需要花多少钱？ 输入:  第一行输入两个正整数 ，代表商品数量和优惠券的种类数 第二行输入  个正整数，代表每件商品的价格 接下来的  行，每行输入两个正整数 ，代表第  种优惠券的信息  输出:  一个正整数，代表最终需要花的最少钱数  解题思路 这是一个贪心算法问题，可以通过以下步骤解决：   对于每件商品，我们需要决定：  是否使用优...

题目来源：2024年京东春招技术通用岗位第一批笔试 1. 快乐字符串 题目描述 题目链接：快乐字符串 判断一个字符串是否包含以下任意一个连续子串："cheerful"、"glad"、"happy"、"pleased"。 如果包含，则这个字符串被认为是"快乐的"。 解题思路 这是一个简单的字符串匹配问题，我们可以：  对每个输入字符串，检查是否包含任意一个目标子串 使用字符串的find函数或者暴力匹配都可以解决  代码实现 #include <iostream> #include &l...

活动地址： 牛客春招刷题训练营 - 编程打卡活动 简单题 进制转换 可以手动枚举最低位到最高位，也可以使用库函数直接转换。 #include <iostream> #include <string> using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(0); string s; cin>>s; cout<<stoi(s,nullptr,16); return 0; }  中等题 合并表记录 开一个数组，累计每个索引的值。 输出时，枚举整个值域，如果值...

码力全开，春招起航！牛客陪你一起冲刺理想offer！添加圈子才能统计数据，发放牛币哦~https://www.nowcoder.com/creation/circle/418

活动详情 春招备战，每日刷题攒牛币，助你拿offer、领周边~ 点击链接，获取更多训练营相关信息。 加入圈子，才能绑定刷题信息哦。 刷题活动qq群：    题目链接（按日期倒序排列） 第十二周        日期 简单题 中等题 困难题   2025/5/30 藻类植物 小红的蛋糕切割 【模板】整数域三分   2025/5/29 小红的对称串 Y型树 【模板】二分   2025/5/28 小红浏览论坛 游游的排列构造 【模板】最小生成树   2025/5/27 小红的整数配对 小红的取模构造 【模板】单源最短路Ⅲ（非负权图）   2025/5/26 小红的矩阵 游游的最小公倍数 【模板】单源最...

线圆关系 问题描述 线圆关系处理平面上直线/线段与圆之间的基本关系，包括相交判断、交点计算等。常用于碰撞检测和几何构造问题。 基本操作 算法思想  使用点到直线距离 基于判别式判断相交 适用于相交和切线计算 时间复杂度   代码实现   c++   java   python   class Solution { public: // 判断直线与圆相交 int lineCircleIntersect(const Line& line, const Circle& circle) { double dist = line.distanceToPoint(circle.center...

点圆关系 问题描述 点圆关系处理平面上点与圆之间的基本关系，包括点到圆的距离、点在圆内外的判断等。常用于范围查询和碰撞检测问题。 基本操作 算法思想  使用圆心和半径表示圆 基于距离进行判断 适用于范围和位置判断 时间复杂度   代码实现   c++   java   python   class Circle { public: Point center; double radius; Circle(Point c = Point(), double r = 0) : center(c), radius(r) {} // 判断点在圆内 bool contains(const Point&am...

线线关系 问题描述 线线关系处理平面上两条直线/线段之间的基本关系，包括相交判断、交点计算等。常用于几何判定和相交问题。 基本操作 算法思想  使用向量表示直线方向 基于叉积判断相交 适用于相交和平行判断 时间复杂度   代码实现   c++   java   python   class Solution { public: // 判断两线段相交 bool segmentIntersect(const Line& l1, const Line& l2) { Point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2; // 快速排斥实验 ...

点线关系 问题描述 点线关系处理平面上点与直线/线段之间的基本关系，包括点到线的距离、点在线的位置等。常用于几何判定和距离计算问题。 基本操作 算法思想  使用向量表示直线方向 基于叉积判断方向 适用于位置和距离计算 时间复杂度   代码实现   c++   java   python   class Line { public: Point p1, p2; // 直线上两点 Line(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {} // 点到直线距离 double distanceToLine(const Point&a...

点点关系 问题描述 点点关系处理平面上两点之间的基本关系，包括距离计算、向量运算等。常用于最近点对、凸包等问题。 基本操作 算法思想  使用坐标表示点的位置 基于向量进行计算 适用于距离和方向判断 时间复杂度   代码实现   c++   java   python   class Point { public: double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} // 向量加法 Point operator + (const Point& p) const { return Point(x + p.x, y +...

计算几何 基本概念 计算几何处理几何对象的计算问题，包括点、线、多边形等基本图形的各种运算。 特点  时间复杂度：与具体问题相关 空间复杂度：通常为  适用于几何对象的计算和判断  分类    概念 表示方法 功能描述     点 坐标对 二维平面上的位置   向量 坐标差 方向和大小   线段 两个端点 有限直线   直线 点斜式/一般式 无限延伸   多边形 点集合 封闭图形    基本运算 基本运算是计算几何中的常用操作。 特点  时间复杂度：通常为  空间复杂度： 适用于基本几何运算  分类    运算 操作 功能描述     向量运算 加减乘除 向量的基本运算   点积叉积 内积外积...