解题思路：  这是一个动态规划问题 可以从底向上或从上向下进行动态规划 我们选择从底向上，因为这样更容易处理边界情况 从三角形的最后一行开始，向上遍历 对于每一行的每个位置 ， 表示从该位置到底部的最小路径和 状态转移时，当前位置的最小路径和等于下一行相邻两个位置的最小值加上当前位置的值 最终  就是从顶点到底部的最小路径和 状态转移方程： 由于每行的状态只和下一行有关，所以可以使用一维数组优化空间。  代码   cpp   java   python   class Solution { public: int minTrace(vector<vector<int> &gt...

周赛72 写在前面 这期的周赛感觉难度偏高了， 难度整体高了一个档次。 在验题时虽然  偏典，为了不用  ，想用 ，所以也写了老久，建议都写写这个 ，使用左边右开的技巧和  标记的转化个人感觉还是不错的。 如果存在疑问，留言评论区，看到会及时回复的，赛时写了题解，饿了，先吃饭去了喵。 A.小红的01串(一) 直接遍历一遍，求  的个数即可。 void solve(){ string s; cin>>s; int ans=0; for(int i=1;i<s.size();i++){ ans+=s[i]!=s[i-1]; } cout<<ans<<'\n...

解题思路 一、问题分析   题目要求  从数组中选择数字 任意两数差值不超过  求最多可选数字个数    关键点  差值限制意味着选择的数字要在一个范围内 排序后可以简化问题    基本思路  先对数组排序 使用滑动窗口 窗口内的数字差值都不超过  维护最大窗口大小    代码   cpp   java   python   #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n ...

题目要求   种字符的字符串 每种字符出现次数为  求哈夫曼编码后的最短长度    哈夫曼编码原理  出现频率高的字符用短编码 出现频率低的字符用长编码 构建二叉树来得到编码    解题思路   核心算法 1. 每次选择两个最小的频率合并 2. 合并后的频率为两者之和 3. 重复此过程直到只剩一个节点 4. 每次合并会使编码长度增加两个数的和    使用优先队列  维护一个最小堆 每次取出两个最小值 将和放回堆中    代码   cpp   java   python   #include <iostream> #include <queue> using namesp...

解题思路 贪心策略选择，按照活动结束时间排序，每次选择结束时间最早的活动，这样可以为后面的活动留出更多时间空间。 具体步骤    读入所有活动的开始时间和结束时间     按照结束时间从小到大排序     选择第一个活动（结束时间最早的）     遍历剩余活动：   如果当前活动的开始时间  上一个选中活动的结束时间 则选择该活动，更新最后活动的结束时间     输出选中的活动数量    代码   cpp   java   python   #include <iostream> #include <vector> #include <algorithm> ...

解题思路 三种排序算法分析 一、冒泡排序 (Bubble Sort) 1. 基本原理 - 比较相邻的两个元素，如果前者大于后者则交换 - 每一轮将最大的元素"冒泡"到末尾 - 重复n-1轮，直到所有元素有序  2. 时间复杂度  最好情况：，数组已经有序 最坏情况：，数组逆序 平均情况： 空间复杂度： 稳定性：稳定  3. 代码框架 for(int i = 0; i < n-1; i++) { for(int j = 0; j < n-1-i; j++) { if(arr[j] > arr[j+1]) { swap(arr[j], arr[j+1]); }...

解题思路 算法解析   核心思想：  将乘法转换为加法 类似二进制乘法的思路 每次将  翻倍， 右移一位    关键点： // 初始取模，减小数值 a %= p; b %= p; // 使用位运算判断当前位 if(b & 1) // 翻倍使用加法 a = (a + a) % p;    限制条件处理：  所有中间值不超过  只使用加法和取模运算 及时取模控制数值大小    优化说明：  初始取模减小数值 使用位运算优化 及时取模避免溢出    为什么算法正确   原理：  将  看作二进制数 对应位为  时累加当前的   每次翻倍对应二进制位的权重    举例： 计算 7 * 5 % ...

解题思路 暴力做法:  直接计算  并取模 单次询问时间复杂度： 空间复杂度： 这样会超时，需要使用快速幂算法进行优化。  快速幂原理：  将指数  转换为二进制 根据二进制位计算结果 每次平方并取模  代码   cpp   java   python   #include <iostream> using namespace std; // 快速幂计算 (a^b) % p long long quickPow(long long a, long long b, long long p) { long long res = 1; a %= p; while(b) { if(b &a...

解题思路   问题描述：  三个柱子  顺时针排列 只能顺时针移动： 初始所有盘子在  柱 求移动到  和  的最少步数    限制条件：  大盘不能放在小盘上 一次只能移动一个盘  结果需要对  取模    递推公式推导   移动到B的情况：  要将  个盘子移到  需要先将  个盘子移到  再移动最大盘到  再将  个盘子从  通过  移到  所以：    移动到C的情况：  要将  个盘子移到  需要先将  个盘子移到  再移动最大盘经过  到  再将  个盘子从  移到  所以：    状态定义： toB: 将 n 个盘子从 A 移动到 B 的最少步数 toC: 将 n 个盘子从 A ...

解题思路   递归思想：  将  个盘子的移动分解为三步 先将  个盘子移到中间柱子 再将最大的盘子移到目标柱子 最后将  个盘子从中间移到目标柱子    基本情况：  当  时，直接移动这个盘子 记录移动步骤    递归过程： hanoi(n, from, mid, to): if n == 1: move disk from 'from' to 'to' return hanoi(n-1, from, to, mid) move disk n from 'from' to 'to' hanoi(n-1, mid, from, to)    代码   cpp   java   python ...

解题思路   问题分析  需要处理带有'?'的时间格式 每个'?'可以是  的任意数字 需要考虑时间的合法性（小时 ，分钟 ） 计算两个时间之间的分钟差    实现步骤  找出所有  和  可能的合法时间 计算所有可能的时间差 找出最大和最小时间差    代码   c++   java   python   #include <iostream> #include <vector> #include <set> #include <string> #include <climits> // 添加此头文件以使用INT_MAX和INT_M...

解题思路  对每个数分解质因数 用  尝试每个数选择不同的质因数 记录已使用的质因数，避免重复使用 当选择完所有数时，更新最小和  代码   c++   java   python   #include <iostream> #include <vector> #include <set> using namespace std; vector<int> getPrimeFactors(int n) { vector<int> factors; for(int i = 2; i * i <= n; i++) { if(n % i...

解题思路 BFS求最短路径解题思路 1. 问题分析  二维网格中找最短路径 可以上下左右四个方向移动 有障碍物不能通过 需要判断是否能到达目标点  2. 解题步骤   数据结构 - 使用二维数组存储网格 - 使用队列进行BFS - 使用二维数组记录距离 - 定义四个方向的移动：dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1}    BFS实现 - 从起点开始BFS - 每次取出队首位置，尝试四个方向 - 对每个可以移动到的新位置： * 检查是否越界 * 检查是否是障碍物 * 检查是否已访问 * 更新距离并加入队列    判断结果 - 如果到达终点，返回距离 - 如果队列...

解题思路 无向图最短路径解题思路（BFS） 1. 问题分析  无向图中找最短路径 边的权重都是  需要处理不连通的情况 使用 （广度优先搜索）最适合解决这类问题  2. 解题步骤   图的存储  使用邻接表存储图 每个节点存储其相邻节点的列表 因为是无向图，每条边需要存两次    BFS实现  使用队列存储待访问的节点 使用数组记录到每个点的距离 使用  数组标记已访问的点    具体流程  从  号点开始  将  号点加入队列，距离设为  每次取出队首节点，遍历其相邻节点 对未访问的相邻节点，更新距离并加入队列    结果判断  如果能访问到  号点，输出距离 如果不能访问到  号点，输出 ...