题意整理 给定一个环形数组，开始的时候，牛牛在起始位置。 每经过1分钟，环形数组中对应元素减去1，并且牛牛会沿着环形数组不断后移。 如果牛牛所在位置，元素值小于等于0，则返回对应位置下标。 方法一（模拟） 1.解题思路 用一个变量记录排队时间。 通过循环，模拟遍历环形数组，没执行一次，排队时间加一，如果对应下标元素值减去排队时间小于等于0，说明可以进入对应的门，直接返回。 测试数据较大的时候，运行超时。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直...

题意整理 给定正整数n，如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。 如果n等于0，返回之前变换次数，如果无法变为0，返回-1。 方法一（模拟） 1.解题思路 用一个死循环，模拟n的值变换的过程。 如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。 如果n小于0，说明不可能再变为0，因为无论是减去3，还是变为n/2，都无法将一个负数变为0或正数。所以直接返回-1。如果n等于0，记录最终变为0时总共执行的变换次数，并返回。 2.代码实现 import java.util.*; public class Solution { /** * *...

题意整理 给定一个数组，计算中位数和平均数。 如果中位数大于平均数，输出1；如果小于，输出-1；如果等于，输出0。 方法一（排序+模拟） 1.解题思路 首先计算中位数和平均数。 计算中位数时，先对数组排序，如果数组长度是奇数，直接返回最中间的元素；如果是偶数，则返回中间两个数的平均数。计算平均数时，先统计累加和，然后再除以数组中元素个数，即可得到平均数。 判断中位数和平均数的大小，输出对应的值。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param arr int...

题意整理 给定n个数，现在要将这n个数分成k个子集，使得相同子集的数量尽可能多。 求满足条件的子集（如果有多个，输出字典序最小的那个）。 方法一（暴力） 1.解题思路 首先统计数组中所有元素出现次数，记录在map数组。 然后确定满足条件的相同子集的个数，最小值显然为1，最大值为，因为最多分成个相同的子集。 线性查找满足条件的最大的子集个数，check的规则是分配次数大于等于k。分配的标准是：如果某个元素至少能被每个子集分1次，则可以分配。 根据找到的最大子集个数，还原对应的子集。 动图展示： 2.代码实现 import java.util.*; public class Solu...

题意整理 给定一个长度为n的字符串和一个整数k。 每一步可以交换下标i与i+k对应的元素，保证交换之后字典序变大。 求最多交换多少步。 方法一（分组+临时计数统计） 1.解题思路 将字符串分为k组，每组的起点分别是0到。 然后分别遍历每一组，并用计数数组记录当前元素访问次数。 如果之前有下标小于当前元素的字符出现，则将其出现次数全部加到结果变量。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param s string字符串 s.size() <= 1e5 ...

题意整理 有n个星球，星球之间通过m条隧道连接，牛牛占有p个星球，牛妹占有q个星球。 求从牛牛占有的星球到牛妹占有的星球需要走过的最短距离。 方法一（弗洛伊德算法） 1.解题思路 首先初始化一个二维数组dist，记录每个星球间的距离。 通过给定的隧道，给dist数组赋值。 走弗洛伊德算法，基本思想是三层循环，枚举中转点、起点和终点，遍历所有可能的情况，取最小距离。 计算完之后，列举牛牛的星球，以及牛妹的星球，计算从牛牛星球到牛妹星球的最短距离。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** ...

题意整理 总共有m个冰淇淋要运输，运输车一次最多装n个，来回一趟各需t分钟。 现在每个冰淇淋都有一个制作时间，求怎样运输花费时间最短，最短时间下怎样运输次数最少。 方法一（动态规划） 1.解题思路 状态定义:表示运输完第i个物品并且回到工厂所需要的最短时间。 状态初始化:将所有状态置为Integer型整数最大值。 状态转移：如果第i个冰淇淋之前有生产冰淇淋，则最多从第个冰淇淋算起，找到运完这一组冰淇淋（最多n个一组）所需的时间，如果时间小于当前的状态，则进行跟新，同时记录前驱状态。 运完最后一个冰淇淋的时间即是最短花费时间，运输次数可根据前驱数组倒推出来。 动图展示： 2.代码实现 ...

题意整理 给定一个一维数轴，起点在原点，每次可以向左或者向右移动0或3或7或11个单位。 为了移动到目标点target，计算最少的移动次数。 输入对应的target坐标集合，返回对应的移动次数集合。 方法一（动态规划） 1.解题思路 首先计算移动到范围内的目标点对应的最少移动次数。 初始化dp数组。 由于范围内的所有情况都统计了，目标点在大于11的范围时，只需从之前的点后移3位、7位或者11位，不用再左移了（所有的点都能通过右移到达，左移会增加移动次数）。所以状态转移方程是：。 根据状态转移方程，计算所有可能的情况，然后将dp数组对应的移动次数赋值到结果数组。 计算范围内目标点的过程：...

题意整理 已知数列第0项为0，第1项为1，递推关系为：。 求数列第n项，结果需要对1000000007取余。 方法一（暴力） 1.解题思路 首先处理第0项和第1项的结果。 用变量x、y分别记录数列第i-2项和第i-1项。 循环对应次数，按递推关系式跟新每次的结果，同时将x换为y，y换为计算出的结果。 测试数据较大时，运行超时。 2.代码实现 import java.util.*; public class Solution { /** * 输出序列的第n项 * @param n long长整型 序列的项数 * @param b long长整型 系...

题意整理 n朵花排成一圈，现在要摆放好这些花，使得相邻花的高度差尽可能小（所有花的高度由一个数组给出）。 求这些花摆放好之后，相邻距离的最大值。 方法一（双端队列） 1.解题思路 为了使得相邻花的高度差尽可能小，那么一定是往圈里先放第一矮和第二矮的花，再在中间放上第三矮和第四矮的花，直到放完所有的花。也可以先放第一高和第二高的花，再放第三高和第四高的花，依次放完所有花。基本步骤： 初始化双端队列，并对数组排序。 遍历数组，将当前数放在队头，下一个数放到队尾，直到放完所有的数。 计算队列中相邻元素间的绝对值，队头和队尾也视为相邻，取所有绝对值的最大值，即是所求的高度差的最大值。 动图展示...

题意整理 输入一个整数x（范围在0到999之间）。 判断它是否是由某个完全平方数对1000取模所得。 方法一（模拟） 1.解题思路 遍历所有可能。 如果x是某个平方数对1000取余，直接返回true。 如果遍历完，还没有找到对应的平方数，则返回false。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param x int整型 * @return bool布尔型 */ //取余常数 int mod=1000; publ...

题意整理 给定长度为n的数组，将数字大的分配给数字小的，使得尽可能多的数不小于给定数字x。 求最多有多少个数不小于x。 方法一（排序+模拟） 1.解题思路 首先初始化结果变量和分配之后多余的数。 将给定数组排序，逆序遍历，保证每次访问的都是当前最大的，如果大于等于x，说明能分配，则计数加一，并加上对应剩余数。如果小于x，但是剩余数加上当前数字大于等于x，还是能分配，计数加一，减去对应剩余数；否则不能分配，直接终止循环。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名...

题意整理 给定一张带权无向图，图中任意两点间有且仅有一条路径。 求从任意点出发，访问完所有节点后，所经过边的权值和的最小值。 方法一（dfs） 1.解题思路 要想边权值最小，所走的路径中必定包含了最长（边权值最大）无重复节点的路径，只要求出这个路径权值和，用所有路径权值和的两倍减去最大路径权值和，即得到所经过边的权值和的最小值。 首先初始化邻接表，遍历点对集合Edge，计算所有边长度的两倍。 先从1号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。 然后再从最远节点处继续进入递归体，寻找最大路径权值和。 找到之后，用所有边长度的两倍减...

题意整理 给定一个长度为n的排列p，以及m个数对，每个数对包含一个和一个。 可以将排列p中下标对应值和下标对应值互换，数对的使用顺序和次数不限。 求任意次操作后字典序最小的排列p。 方法一（并查集） 1.解题思路 并查集简述： 并查集主要用于解决图中的连通域问题，起初并查集里包含n个节点，每个节点都有一个根，初始情况下，根指向自身。然后有两个关键方法，一个是find，一个是union。find用于查找当前节点的根，union用于连接两个节点，连接以后处于同一个连通域，即共享一个根。 首先新建并查集，遍历Pair数组，连接对应节点。 再新建两个邻接表，一个用于记录当前根对应连通域所有节...