✨今日算法三题
文章目录
1.最后一块石头的重量
题目描述
思路详解
这里采用最大堆进行解题。
我们首先考虑，每次拿出两个最大的进行比较，然后大的减去小的重新放入不就完成了嘛。
首先我们创建一个优先队列，遍历重量，放入队列。依次取出重量最大的和第二大的，如果a>b就把a-b重新放入。直到队列里面的元素只剩1个的时候，输出结果。
代码与结果
class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a); for (int stone : stones) { pq.offer(stone); } while (pq.size() > 1) { int a = pq.poll(); int b = pq.poll(); if (a > b) { pq.offer(a - b); } } return pq.isEmpty() ? 0 : pq.poll(); } }
'
2.装满杯子需要的最短总时长
题目描述
思路详解
这个题也是思考了很久。
分两种情况：
- 第一种：很好想，有一种水特别多，那么答案就是这种水的杯数。
- 第二种：就是一定可以匹配完成或者匹配到只剩一杯。
我们只需要先排序，在分情况就好。
代码与结果
class Solution { public int fillCups(int[] amount) { Arrays.sort(amount); int sum=amount[0]+amount[1]+amount[2]; if(amount[1]+amount[0]>=amount[2]) sum=(sum+1)/2; else sum=amount[2]; return sum; } }
移除石子的最大得分
题目描述
思路详解
本题的思路看起来简单，也不是很好想。
我们先排一下序，两种情况：
- 第一种：前两个的和小于第三个，这时候我们一直拿最后一堆和任意一堆，结果就是a+b。
- 第二种： 前两个数的和大于第三个数，那么前两堆一定可以内部抵消一部分。只需总和除以2就好。
代码与结果
class Solution { public int maximumScore(int a, int b, int c) { int[] arr = new int[] { a, b, c }; Arrays.sort(arr); a = arr[0]; b = arr[1]; c = arr[2]; if (a + b <= c) { return a + b; } else { return (a + b + c) / 2; } } }
✨总结
今天的还是有不小难度的，主要考察数学思维和优先队列。加油！！！
