解题思路 这是一个序列操作问题。通过观察可以发现，从后向前看，如果序列是递增的，那么这部分不需要操作。 关键点：  从后向前看，递增序列不需要操作 遇到第一个递减位置时停止 前面的元素都需要移动到队首  算法步骤：  从后向前遍历序列 统计末尾的递增序列长度 剩余的元素数量就是最少操作次数  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class Solution { public: int minMoves(vector<int>& nums) { int n...

解题思路 这是一个求最大差值的问题。虽然可以通过排序解决，但题目要求  复杂度，因此需要使用桶排序的思想。 关键点：  最大差值一定不小于  使用  个桶可以保证最大差值一定出现在桶之间 只需要记录每个桶的最大值和最小值  算法步骤：  找出数组的最大值和最小值 创建  个桶 将数字分配到对应的桶中 计算相邻非空桶之间的差值  代码   cpp   java   python   class MaxDivision { public: int findMaxDivision(vector<int>& A, int n) { if (n < 2) return 0; /...

解题思路 这是一个字符串循环移位问题，需要找到所有可能的移位中最长的连续1序列。 关键点：  将字符串复制一遍可以处理所有移位情况 使用双指针技术查找连续1序列 注意结果不能超过原字符串长度  算法步骤：  复制字符串拼接到原串后面 使用双指针遍历查找连续1 取最大长度和原串长度的较小值  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class Solution { public: int findMaxConsecutiveOnes(string s) { string doub...

解题思路 这是一个查找未出现最小正整数的问题。由于数组大小不超过500，所以最小未出现的正整数一定不会超过501。 关键点：  最小未出现正整数的范围是  可以使用原数组作为标记数组 将每个在范围内的正整数放到对应位置  算法步骤：  遍历数组，将每个在  范围内的数放到对应位置 再次遍历数组，找到第一个位置  上的数不是  的位置 该位置  就是最小未出现的正整数  代码   cpp   java   python   class ArrayMex { public: int findArrayMex(vector<int>& A, int n) { // 将每个数放到正...

解题思路 这是一个树形动态规划问题，需要计算所有人从各个节点到达安全出口（根节点）所需的最短时间。 关键点：  每个节点同时只能容纳一个人 人只能向根节点方向移动 每秒只能移动一个节点距离 需要考虑节点阻塞的情况  算法步骤：  构建树的邻接表表示 使用  计算每个子树的疏散时间 对每个节点的子树按疏散时间从大到小排序 考虑子树之间的相互影响  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class Solution { private: vector<vector<i...

解题思路 这是一个数组处理问题，需要计算每个元素左边小于等于它的数字之和。 关键点：  对于每个元素，需要找到其左边所有小于等于它的数 可以使用树状数组优化查询和更新操作 需要离散化数组元素以优化空间使用  算法步骤：  对数组进行离散化处理 使用树状数组维护前缀和 对每个元素，查询小于等于它的数的和  代码   cpp   java   python   class MonoSum { private: static const int MAXN = 505; int tree[MAXN]; int count[MAXN]; int lowbit(int x) { return x &amp...

解题思路 这是一个字符串匹配和动态规划问题。使用  算法找到所有模式串的匹配位置，然后用动态规划求解最大不相交子串数量。 关键点：  使用  算法高效查找所有匹配位置 用动态规划数组  表示到位置  的最大不相交子串数量 对每个位置，考虑是否选择以该位置结尾的匹配  算法步骤：  对每个模式串进行  匹配 记录每个位置结尾的所有可能匹配 动态规划求解最优结果  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class StringMatcher { private: static c...

解题思路 这是一个字符串匹配问题，需要在字符串  中找到字符串  第一次出现的位置。可以使用  算法来高效解决。 关键点：  构建  算法的  数组 利用  数组进行快速匹配 处理边界情况  算法步骤：  计算模式串  的  数组 在主串  中进行匹配 找到匹配位置或返回-1  代码   cpp   java   python   class StringPattern { public: vector<int> getNext(const string& pattern) { int n = pattern.length(); vector<int> next...

解题思路 这是一个图论问题，通过反向建图和拓扑排序来找到字典序最小的全排列。 关键点：  反向建图：将所有边反向，便于从大到小分配数字 使用最大堆维护可选节点 从n到1逆序分配数字，保证字典序最小  算法步骤：  建立反向图的邻接表 找出所有入度为  的点加入最大堆 每次取出堆顶元素，分配最大可用数字 更新邻接点的入度，将新的入度为  的点加入堆  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class Solution { private: static const int MA...

解题思路 这是一个数组处理问题，需要找出数组中最小的  个数，并保持原数组中的相对顺序。 关键点：  不能直接排序，因为需要保持原数组顺序 可以使用临时数组存储原数组的副本并排序 找出第  小的数作为阈值 遍历原数组，保留小于等于阈值的前  个数  算法步骤：  复制原数组并排序，找到第  小的数 遍历原数组，将小于等于阈值的数加入结果数组 如果结果数组长度不足 ，继续添加等于阈值的数直到达到  个  代码   cpp   java   python   class KthNumbers { public: vector<int> findKthNumbers(vector<...

解题思路 这是一个配比问题，需要根据各种原料的配比和容量限制，计算最大可制作的饮料量。 关键点：  对于每种原料 ，实际使用量应该是：配比  * （ 是一个系数） 所有原料的使用量不能超过各自拥有的量  所有原料的总体积不能超过容器容积  需要找到最大的  值  算法步骤：  对于每种原料，计算 （表示该原料能支持的最大系数） 找到所有原料中的最小系数，这就是限制因素 检查在这个系数下总体积是否超过容器容积 如果超过容器容积，需要进行相应调整  代码   cpp   java   python   #include <bits/stdc++.h> using namespace s...

解题思路 这是一个字符串处理问题，需要在字符串末尾添加最少的字符使其成为回文串。 关键点：  从左到右遍历字符串的每个位置  判断从位置  到末尾的子串是否为回文串 如果找到回文子串，则将位置  之前的子串反转后作为结果  算法步骤：  遍历字符串的每个位置 （从  到 ） 获取从位置  到末尾的子串 判断该子串是否为回文串 如果是回文串，则返回位置  之前的子串的反转  代码   cpp   java   python   class Palindrome { public: string addToPalindrome(string A, int n) { for (int i = 1; ...

解题思路 这是一个数字分组问题，使用动态规划来解决。 关键点：  提取数字的非零位并计算总和 如果总和为奇数，直接返回false 使用01背包思想，判断是否能找到一组数字和为总和的一半  算法步骤：  提取数字的各个非零位到数组中 计算所有位数字的和，判断是否为偶数 使用动态规划判断是否存在一组数字和为总和的一半  代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; class Solution { public: bool isMagicNumber(int x) { // 提取非零位数...

解题思路 这是一个括号匹配和移除操作的计数问题。对于每个左括号，我们需要找到其对应的所有可能的右括号。 关键点：   每次移除操作包含两步：  移除第一个左括号（固定的） 移除一个合法的右括号（有多种选择）    合法性判断：  移除括号后，剩余的序列必须是合法的括号序列 需要保持左右括号的平衡    代码   cpp   java   python   #include <iostream> #include <string> using namespace std; int main() { string s; while (cin >> s) { in...