题目描述 牛妹所在的公司一共有名员工，条生产线，每条生产线有种人数安排策略.例如：个人在生产线上，生产线每天生产个口罩；个人在生产线上，每天生产线能生产个口罩。牛妹想知道通过合理的策略安排最多每天能生产多少口罩？可以不用将所有员工都分配上岗，生产线可以选择闲置 方法一 动态规划 解题思路 这个问题可以用动态规划解决.定义状态数组,表示生产策略不变情况下,条生产线,名员工每天最多生产口罩数量.初始状态:.状态转移:需要得到与之间的关系.生产线增加一条,如果不使用新增的生产线时生产口罩最快,那么;如果使用新增的这条生产线,那么对于新增这条生产线的所有,需要找出生产最快的方案,即.最后,为这两种...

题目描述 将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。 方法一 区间DP 解题思路 定义数组表示之间切割点的最小成本.为了计算每一个子区间的长度，需要向中添加边界点0和绳子长度,然后对所有切割点进行排序.在切割时,对每个区间,假设第个点是最后一个切割的点,那么我们先求出和,代表完成了切割第个点之前所有步骤,并且已经取得了最小值,然后再加上切割第个点的成本即为最后切割时能够获得的最小值.即状态转移方程为,其中,.为了枚举所有区间,实现区间DP,我们可以选择枚举所有的步长和区间起始点,并且把数组初始值设为无穷大.对所有区间枚举完...

题目描述 棋盘中包含四种棋子:炮P、将J、车C、兵B牛妹棋子用大写字母表示,牛牛棋子用小写字母表示问一回合内牛妹能否战胜牛牛 方法一 模拟 解题思路 棋子只能吃掉与自己同一行或同一列的棋子，所以可以只考虑与牛牛的将同一行或同一列的棋子。对于牛妹的兵和将，需要位于牛牛的将上下左右四个相邻的位置；对于牛妹的车，与牛牛的将之间不能有其棋子；对于牛妹的炮，与牛牛的将之间有且只有一个棋子。对于兵和将，要想获胜，需要： 对于车，要想获胜，需要： 对于炮，要想获胜，需要： 按照上述规则，检查与j同一行和同一列的棋子即可。 代码示例 class Solution { public: /** ...

题目描述 要求输出不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）输入只包含一个正整数n（1<=n<20） 方法一 记忆化搜索 解题思路 定义DFS函数，搜索位十进制数字中符合要求数字的个数。在计数时，对于位数为的数字，如果第位为，那么第位必须不能为，所以第位有个数字可以选择，也就是说有种情况；如果第位不为，第位有种选择，第位可以随便选取，有种情况。所以，位数字符合要求的数字个数可以通过位和位答案得到，于是可以通过递归/DFS的思路得到答案。 接下来考虑初始情况即可，当输入为时，仅考虑数字，不含有，故应返回.当输入为时，考虑数字，不含有，故应返回。实际上，上述...

题目描述 有个箱子，第个箱子一开始有个球，进行最多次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第个箱子最多能装个球。如果一个箱子为空，就不能从里面拿球。设相邻箱子的球的数量的差的平方中的最大值为，求进行最多次操作之后最小可以是多少。 方法一 贪心+模拟 解题思路 一个比较直接的思路是使用模拟的方法，结合贪心思想解答。在k次操作中，每次操作只能减少或增加某个箱子的仅一个球，这为模拟提供了可能。在每次操作时，根据贪心的思想，先找到相邻两个数差值最大的地方，然后分为三种情况分别模拟： 接下来，以最大差值处时为例，如果进行操作来增大或者减少。最大差值处与此类似。 代码示例 cl...

题目描述 众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？主要信息：每天吃蛋糕总数三分之一（向下取整）多一个；第n天只剩1个 方法一 递归 解题思路 设前后两天的蛋糕数为和，根据题意有，那么，已经知道第天的蛋糕数为，所以可以通过递归的方法求得第一天的蛋糕数。 代码示例 class Solution { public: /** * 代码中的类名、方法名、参...

题目描述 众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。 给了一个序列，让找出最长的“凸子序列” “凸子序列”：数列中有一个,使得所有且 eg：12345431,是山峰序列，12345234不是山峰序列注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列 明确条件：1.子序列与子串不同，子序列不要求连续而子串要求连续。2.要求严格上升。 方法一 动态规划 解题思路 此题容易联想到比较经典的求最长递增子序列问题，这是使用动态规划的经典问题。先考虑最长递增子序列问题，定义为考虑前个数字，以第个数字结尾的最长递增子序列的长度，这里注意第个数字必须被选...

题目描述 编号为1到n的n个人围成一圈。从编号为1的人开始报数，报到m的人离开。下一个人继续从1开始报数。n-1轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？ 方法一 模拟 解题思路 可以使用循环链表模拟约瑟夫问题。以5个人报数为2的离开为例： 如图所示，每次去掉一个，最后留下的人编号为3。在每次报数时，改变第m个节点前后节点相应的指针以将该节点从链表中删除。 代码示例 class Solution { public: /** * * @param n int整型 * @param m int整型 * @r...

题目描述 假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。 方法一 分而治之 解题思路 要计算两次交易的最大收益，可以把问题分为两部分。找到第k天，求得前k天一次交易的最大收益加上第k天之后一次交易的最大收益。对于一次交易问题，这里直接给出一次遍历的方法。 如上图所示，我们期望在前k天或者k天之后的历史最低点买入股票，用一个变量记录历史最低价格minprice，我们应该以此价格买入股票。然后遍历数组，在第i天买出股票的利润为prices[i] - ...

题目描述 假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。 方法一 贪心算法 解题思路 因为可以进行无限次交易，因此只要后一天价格高于前一天，我们就应该买入前一天的并且在后一天卖出；如果后一天价格低于前一天，则不进行操作。最后的利润为折线图中上升部分的总和。 代码示例 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算最大收益 * @param price...

题目描述 假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。 方法一 分解+组合 解题思路 代码示例 复杂度分析 时间复杂度：时间复杂度为 空间复杂度：空间复杂度为 方法二 解题思路 代码示例 复杂度分析 时间复杂度：时间复杂度为 空间复杂度：空间复杂度为

题目描述 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。注意是节点的编号而非节点的数值。 方法一 分解+组合 解题思路 可以新建两个辅助链表头，之后分别连接奇数位节点和偶数位节点，然后再把这两个链表组合起来得到结果。 代码示例 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /**...

题目描述 有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。[要求]1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)每行有一个整数opt表示操作类型若opt=1，则接下来有一个整数N表示将N加入到结构中。若opt=2，则表示询问当前所有数的中位数 方法一 暴力检索 解题思路 最简单的方法就是存储所有的整数，需要查...