解题思路 这是一道动态规划求解零钱兑换组合数的问题，主要思路如下： 问题分析： 给定6种面额：1、5、10、20、50、100元 每种面额的数量无限 求组成目标金额 的不同组合数 解决方案： 使用动态规划求解 表示组成金额 的组合数 对每种面额 ，有： 关键点： 初始化 外层循环遍历面额，内层循环遍历金额 注意使用 long 类型避免溢出 代码 cpp java python #include <iostream> #include <vector> using namespace std; int main()...

解题思路 这是一道经典的网格路径问题，使用动态规划求解。主要思路是：对于任意点 ，到达它的路径数等于从上方来的路径数加上从左方来的路径数。 代码 cpp java python #include <iostream> #include <vector> using namespace std; int uniquePaths(int x, int y) { // 创建动态规划数组 vector<vector<int>> dp(x + 1, vector<int>(y + 1, 0)); ...

解题思路 这是一道查找丢失数字并进行组合的问题，主要思路如下： 问题分析： 原始数组包含1到10000的连续数字 丢失了三个数字，其余数字被打乱 需要找出丢失的数字并按从小到大拼接 计算拼接后的数字除以7的余数 解决方案： 使用标记数组记录出现的数字 遍历1到10000找出未出现的三个数字 将三个数字按顺序拼接成字符串 计算最终结果对7的余数 关键点： 使用内存数组标记已出现的数字 注意数字拼接后可能很大，需要考虑大数处理 代码 cpp java python #include <iostream> #include <vecto...

解题思路 这是一道最多进行两次股票交易的问题，主要思路如下： 问题分析： 可以进行最多两次交易 必须先买入才能卖出 第二次交易必须在第一次交易完成后进行 求最大收益 解决方案： 使用动态规划，维护四个状态： : 第一次买入后的最大收益 : 第一次卖出后的最大收益 : 第二次买入后的最大收益 : 第二次卖出后的最大收益 状态转移： 代码 cpp java python class Stock { public: int maxProfit(vector<int>& prices, int n) { ...

解题思路 这是一道数组遍历问题，主要思路如下： 问题分析： 给定 的二维数组 需要从右上角到左下角按对角线方向打印 打印方向是从左上指向右下的平行线 解决方案： 分两部分打印： 从右上角开始，到主对角线 从主对角线下方开始，到左下角 每条对角线都是从左上到右下方向 关键点： 第一部分起点： 到 第二部分起点： 到 每条对角线 和 同时增加 代码 cpp java python class Printer { public: vector<int> arrayPrint(vector<vector<in...

解题思路 这是一道数学规律题，主要思路如下： 问题分析： 对 的序列，每次丢弃奇数位置的数 需要找到最后剩下的数字 例如：对于 ，最后剩下 解决方案： 观察规律可以发现，最后剩下的数是小于等于 的最大2的幂次数减1 通过位运算可以快速求解： 找到大于 的最小2的幂 将该数除以2再减1即为答案 数学证明： 每次删除奇数位后，剩余数字形成新序列 新序列的规律符合2的幂次数减1的形式 代码 cpp java python #include <iostream> using namespace std; int findLast...

解题思路 这是一道使用Huffman编码思想的问题，主要思路如下： 问题分析： 给定一个字符串，需要进行二进制编码 相同的字符必须使用相同的编码 要求编码后的总长度最短 解决方案： 统计每个字符的出现次数 使用优先队列（小顶堆）合并最小的两个长度 类似Huffman树的构建过程 关键点： 先对字符串排序，便于统计连续相同字符 使用优先队列维护最小的两个长度 每次合并后将新长度加入队列 代码 cpp java python #include <iostream> #include <string> #include <q...

解题思路 这是一道数学计算问题，主要思路如下： 问题分析： 已知公司总人数 ，当前平均年龄 每年离职率 ，新员工年龄 岁 需要计算 年后的平均年龄 解决方案： 每年的平均年龄计算公式： 留任员工： 新入职员工： 最终年龄 = 留任员工年龄 + 新员工年龄 迭代 次得到最终结果 关键点： 每年都要更新平均年龄 结果需要向上取整 注意浮点数精度 代码 cpp java python #include <iostream> #include <cmath> using namespace std; // 计算一年...

解题思路 这是一道字符串字典序计数问题，主要思路如下： 问题分析： 求字典序在 和 之间，长度在 到 之间的字符串个数 字符串只包含小写字母(a-z) 结果需要对 取模 解决方案： 分别计算大于s1和大于s2的字符串个数，两者相减得到结果 对于每个长度，计算满足条件的字符串数量 考虑两种情况：当前位置大于目标字符串，或等于目标字符串继续比较 关键点： 处理不同长度的字符串 使用幂运算计算可能的组合数 注意取模运算 代码 cpp java python #include <iostream> #include <strin...

解题思路 这是一道使用单调栈解决的经典问题，主要思路如下： 问题分析： 给定一个直方图，每个柱子宽度为1 需要找到直方图中最大的矩形面积 矩形可以横跨多个柱子 解决方案： 使用单调栈维护递增的高度 当遇到更低的柱子时，计算当前可能的最大矩形 通过栈来找到左右边界 关键点： 在数组末尾添加高度0作为哨兵 利用栈顶元素计算矩形的高度 利用栈来确定矩形的宽度 代码 cpp java python class Solution { public: int largestRectangleArea(vector<int>& hei...

解题思路 这是一道使用DFS求最短路径方案数的问题，主要思路如下： 问题分析： 在 的网格中寻找从经理(1)到商家(2)的最短路径 需要统计最短路径的方案数 有障碍物(-1)不能通过 解决方案： 使用 DFS 遍历所有可能的路径 使用 map 存储不同路径长度对应的方案数 剪枝优化：长于当前最短路径的分支直接返回 关键点： 使用 visited 数组避免重复访问 四个方向的移动使用方向数组 回溯时恢复 visited 状态 代码 cpp java python class Solution { private: // 存储(路径长度，方案...

解题思路 这是一道棋盘操作的模拟题，主要思路如下： 问题分析： 的棋盘，每个位置是 或 每次操作会翻转指定位置周围上下左右四个位置的值 需要按顺序执行所有操作 解决方案： 使用方向数组表示上下左右四个方向 对每个操作位置，检查并翻转周围的棋子 使用异或操作实现翻转（0变1，1变0） 实现细节： 检查边界条件 坐标从1开始需要转换为0开始 使用异或运算简化翻转操作 代码 cpp java python #include <iostream> #include <vector> using namespace std; ...

解题思路 这是一道求数组中满足条件的最大差值的问题，主要思路如下： 问题分析： 给定长度为 的数组 需要找到满足 的 的最大值 即找到后面的数减去前面的数的最大差值 解决方案： 维护一个数组 d 记录前 个数的最小值 遍历数组，用当前值减去前面的最小值，更新最大差值 优化点： 一次遍历计算前缀最小值 一次遍历计算最大差值 无需额外空间，可以原地修改 代码 cpp java python #include <iostream> #include <vector> using namespace std; class...

解题思路 这是一道动态规划问题，主要思路如下： 问题分析： 给定 个位置的墙壁高度 可以增加总共 个单位的高度 需要找到最优的扩容方案 解决方案： 计算左右两侧的单调递增序列 计算每个区间的剩余空间 动态规划处理高度分配 关键步骤： 维护前缀和数组 计算每个区间的最大容量 考虑不同分配方案的组合 代码 cpp java python #include <iostream> #include <vector> #include <algorithm> using namespace std; // 计算从左到...