948.令牌放置 难度：中等 你的初始能量为 P，初始分数为 0，只有一包令牌。 令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下： 如果你至少有 token[i] 点能量，可以将令牌置为正面朝上，失去 token[i] 点能量，并得到 1 分。 如果我们至少有 1 分，可以将令牌置为反面朝上，获得 token[i] 点能量，并失去 1 分。 在使用任意数量的令牌后，返回我们可以得到的最大分数。 示例 1：
输入：tokens = [100], P = 50 输出：0示例 2：
输入：tokens = [100,200], P = 150 输出：1示例 3：
输入：tokens = [100,200,300,400], P = 200 输出：2解： 执行用时 : 5 ms, 在Bag of Tokens的Java提交中击败了89.36% 的用户 内存消耗 : 38.4 MB, 在Bag of Tokens的Java提交中击败了77.36% 的用户 思路：对token排序，在能量足够的情况下从数组头兑换分数，能量不够时用分数从数组尾换能量 Code:
class Solution { public int bagOfTokensScore(int[] tokens, int P) { if(tokens.length==0)//数组为空返回0 return 0; Arrays.sort(tokens); if(P<tokens[0])//初始能量小于最小令牌，返回0 return 0; int result=0; int front=0;//头指针 int tail=tokens.length-1;//尾指针 int flag=0;//用来判断最后一次翻盘是获取能量还是获取分数，若是获取能量，则为不必要操作，最终结果分数加一，这个字段可以省去一次if判断 while(front<=tail){ if(P>=tokens[front]){ P-=tokens[front]; result++; front++; flag=1; } else { P+=tokens[tail]; result--; tail--; flag=0; } } result=(flag==0)?result+1:result;//判断最后一次操作是获取分数还是能量 return result; } }462. 最少移动次数使数组元素相等 II 给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如:
输入: [1,2,3] 输出: 2 说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： [1,2,3] => [2,2,3] => [2,2,2]解: 执行用时 : 4 ms, 在Minimum Moves to Equal Array Elements II的Java提交中击败了97.95% 的用户 内存消耗 : 37.5 MB, 在Minimum Moves to Equal Array Elements II的Java提交中击败了97.44% 的用户 思路：中位数 Code:
class Solution { public int minMoves2(int[] nums) { if(nums.length==1) return 0; if(nums.length==2) return Math.abs(nums[0]-nums[1]); Arrays.sort(nums); int mid=nums[nums.length/2]; int result=0; for(int i=0;i<nums.length;++i){ result+=Math.abs(mid-nums[i]); } return result; } }403. 青蛙过河 难度：困难 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。 给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。 请注意： 石子的数量 ≥ 2 且 < 1100； 每一个石子的位置序号都是一个非负整数，且其 < 231； 第一个石子的位置永远是0。 示例 1:
[0,1,3,5,6,8,12,17] 总共有8个石子。 第一个石子处于序号为0的单元格的位置, 第二个石子处于序号为1的单元格的位置, 第三个石子在序号为3的单元格的位置， 以此定义整个数组... 最后一个石子处于序号为17的单元格的位置。 返回 true。即青蛙可以成功过河，按照如下方案跳跃： 跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着 跳2个单位到第4块石子, 然后跳3个单位到第6块石子, 跳4个单位到第7块石子, 最后，跳5个单位到第8个石子（即最后一块石子）。示例 2:
[0,1,2,3,4,8,9,11] 返回 false。青蛙没有办法过河。 这是因为第5和第6个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。解： 执行用时 : 132 ms, 在Frog Jump的Java提交中击败了40.32% 的用户 内存消耗 : 68.7 MB, 在Frog Jump的Java提交中击败了23.91% 的用户 思路：dp
class Solution { public boolean canCross(int[] stones) { if(stones.length<3){ if(stones[1]>1) return false; else return true; } int dp[][]=new int[stones.length][]; HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<stones.length;i++){ dp[i]=new int[i]; map.put(stones[i],i); } dp[1][0]=1; for(int i=1;i<stones.length;++i){ for(int j=0;j<i;++j){ if(dp[i][j]!=0){ for(int k=Math.max(0,dp[i][j]-1);k<=dp[i][j]+1;++k){ if(k>0&&map.get(stones[i]+k)!=null){ if(stones[i]+k==stones[stones.length-1]) return true; dp[map.get(stones[i]+k)][i]=k; } } } } } return false; } }