题意 对于每次操作，选择数组中的两项 和 ，可以用这两个数的积 的其他两个因子（这两个因子的积也要等于 ）替换，求 次操作下，能得到的最大数组的和。 思路 根据 贪心 思想，在每次操作中，要使得替换后的和更大，选择两个数的乘积尽可能大，用 和 去替换原来的两个数字。 为什么用这两个数字去替换呢？ 下面就来证明： 根据均值不等式 ，当且仅当 时，等号成立。又因为这个函数是对称的，所以最大值的情况在边界取到。证毕。 具体处理时，顺序并不影响最后的结果，所以可以先对数组进行排序，然后再取出后 项求积，最后求与其他元素的和。 import java.io.*; import java.m...

题意 多行字符串中，每行只取一个字母，问是否能构成字符串中包含 “meituan”。例如，“mmmmmeemeituaaattn” 包含 “meituan”，而 “emituan” 并不包含 “meituan”。 思路 暴力遍历即可，当找到一个字符后，继续找下一个目标字符，不用考虑顺序问题。 import java.io.*; import java.math.BigDecimal; import java.math.BigInteger; import java.util.*; import static java.util.Arrays.deepToString; public cl...

题意 要求构造一个排列 ，在这个排列中，每个相邻项的和记为 ，记 的最大值为 ，最小值为 ，要使得 最小的一个序列。 思路 我们的目的是让相邻的两项和尽可能接近，比较容易想到等差公式中的“首项加末项”。例如， 的情况： 先取 1 和 5，得到的和是 6。此时序列为 ； 再取 2 和 4，得到的和也是 6。此时序列为 或 ，比较下，显然 相邻和极差更小些； 最后取 3，得到的序列为 ，可以检验，相邻和为 ，极差为 。 因此，对于任何一个序列，我们都可以采用这种方法构造出相邻和极差为 的序列。 具体做法，可以使用 双指针 来分别指向当前自然排列（从小到大）的最大值最小值，然后依次放入...

思路 本以为要用到动态规划，其实不用，en 贪不会有什么问题。 根据 贪心策略，对于当前任务 taskDurations[i]，肯定是把其安排在最早空闲的生产线上。 于是用 优先队列（大根堆） 维护每条生产线所执行时间，然后模拟即可。 时间复杂度为 ，空间复杂度为 。 参考代码 import java.util.*; public class Solution { public int animalTaskScheduler (int[] taskDurations, int capacity) { PriorityQueue<Integer>...

思路 最小栈的变体。使用双栈解决，一个维护原本的栈，一个维护当前最大值的栈。 最大栈的意义在于栈顶就是原始栈的最大值，即栈中的元素是非递减的。 时间复杂度为 ，空间复杂度为 ，其中 表示操作数的大小。 参考代码 import java.util.*; public class Solution { Stack<Integer> stack = new Stack<>(); Stack<Integer> maxStack = new Stack<>(); public int[] processStackOperat...

思路 凑硬币原题。考点是完全背包，即每种物品可以选无限个。 定义 f[j] 表示前 个物品中选择物品总面值为 时的总硬币数。 定义状态转移方程：f[j] = max(f[j], f[j - features[i]] + 1)。即考虑从之前的状态中比较面值为 和面值为 硬币的数量。如果选择前者，则表示不选择当前面值的硬币，否则选择当前面值的硬币，然后加 。 时间复杂度为 ，空间复杂度为 ，其中 为物品数量， 为背包容量。 参考代码 import java.util.*; public class Solution { final int INF = 0x3f3f3f3f; ...

思路 桶排。观察到数据范围是 ，所以设置一个偏移量 offset 即可。 最后空间复杂度为 ，时间复杂度为 。 参考代码 import java.util.*; public class Solution { int[] bucket = new int[100000 + 10]; int offset = 5 * 10000; public int[] bucketSort (int[] nums) { List<Integer> list = new ArrayList<>(); for (int...

思路 根据贪心思想，数组 的元素尽量大，而数组 的元素尽量小，并且不难想到， 的长度应始终满足 。 不妨先对数组进行排序（假设从小到大），然后 从后面开始选择， 从数组前面开始选择。然后枚举数组 长度，求和比较是否满足 即可。为了加快求和的速度，用前缀和即可。 最后时间复杂度为 ，空间复杂度为 。 参考代码 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = ne...