【优选算法】（第三十七篇）

在每个树⾏中找最⼤值（medium）

题目解析

讲解算法原理

编写代码

最后⼀块⽯头的重量（easy）

题目解析

讲解算法原理

编写代码

在每个树⾏中找最⼤值（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀棵⼆叉树的根节点root，请找出该⼆叉树中每⼀层的最⼤值。
⽰例1：

输⼊:root=[1,3,2,5,3,null,9]
输出:[1,3,9]
⽰例2：
输⼊:root=[1,2,3]
输出:[1,3]

讲解算法原理

解法（bfs）：
算法思路：
层序遍历过程中，在执⾏让下⼀层节点⼊队的时候，我们是可以在循环中统计出当前层结点的最⼤值的。
因此，可以在bfs的过程中，统计出每⼀层结点的最⼤值。

编写代码

c++算法代码：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
right(right) {}* };*/
class Solution
{
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;if(root == nullptr) return ret;queue<TreeNode*> q;q.push(root);while(q.size()){int sz = q.size();int tmp = INT_MIN;for(int i = 0; i < sz; i++){auto t = q.front();q.pop();tmp = max(tmp, t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(tmp);}return ret;}
};

java 算法代码：

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution
{public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null) return ret;Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int sz = q.size();int tmp = Integer.MIN_VALUE;for(int i = 0; i < sz; i++){TreeNode t = q.poll();tmp = Math.max(tmp, t.val);if(t.left != null) q.add(t.left);if(t.right != null) q.add(t.right);}ret.add(tmp);}return ret;}
}

最后⼀块⽯头的重量（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

有⼀堆⽯头，每块⽯头的重量都是正整数。每⼀回合，从中选出两块最重的⽯头，然后将它们⼀起粉碎。假设⽯头的重量分别为x和y，且x
<=y。那么粉碎的可能结果如下：• 如果x==y，那么两块⽯头都会被完全粉碎；• 如果x!=y，那么重量为x的⽯头将会完全粉碎，⽽重量为y的⽯头新重量为y-x。最后，最多只会剩下⼀块⽯头。返回此⽯头的重量。如果没有⽯头剩下，就返回0。
⽰例：输⼊：[2,7,4,1,8,1]输出：1
解释：
先选出7和8，得到1，所以数组转换为[2,4,1,1,1]，再选出2和4，得到2，所以数组转换为[2,1,1,1]，接着是2和1，得到1，所以数组转换为[1,1,1]，
最后选出1和1，得到0，最终数组转换为[1]，这就是最后剩下那块⽯头的重量。
提⽰：
1<=stones.length<=30
1<=stones[i]<=1000

讲解算法原理

解法（利⽤堆）：算法思路：
其实就是⼀个模拟的过程：• 每次从⽯堆中拿出最⼤的元素以及次⼤的元素，然后将它们粉碎；• 如果还有剩余，就将剩余的⽯头继续放在原始的⽯堆⾥⾯
重复上⾯的操作，直到⽯堆⾥⾯只剩下⼀个元素，或者没有元素（因为所有的⽯头可能全部抵消了）
那么主要的问题就是解决：
• 如何顺利的拿出最⼤的⽯头以及次⼤的⽯头；
• 并且将粉碎后的⽯头放⼊⽯堆中之后，也能快速找到下⼀轮粉碎的最⼤⽯头和次⼤⽯头；
这不正好可以利⽤堆的特性来实现嘛？
• 我们可以创建⼀个⼤根堆；
• 然后将所有的⽯头放⼊⼤根堆中；
• 每次拿出前两个堆顶元素粉碎⼀下，如果还有剩余，就将剩余的⽯头继续放⼊堆中；这样就能快速的模拟出这个过程。

编写代码

c++算法代码：

class Solution
{
public:int lastStoneWeight(vector<int>& stones) {// 1. 创建⼀个⼤根堆priority_queue<int> heap;// 2. 将所有元素丢进这个堆⾥⾯for(auto x : stones) heap.push(x);// 3. 模拟这个过程while(heap.size() > 1){int a = heap.top(); heap.pop();int b = heap.top(); heap.pop();if(a > b) heap.push(a - b);}return heap.size() ? heap.top() : 0;}
};

java 算法代码：

class Solution
{public int lastStoneWeight(int[] stones) {// 1. 创建⼀个⼤根堆PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);// 2. 把所有的⽯头放进堆⾥⾯for(int x : stones){heap.offer(x);}// 3. 模拟while(heap.size() > 1){int a = heap.poll();int b = heap.poll();if(a > b){heap.offer(a - b);}}return heap.isEmpty() ? 0 : heap.peek();}
}