程序员进阶之算法练习（九十一）leetcode
题目1 最大平均值和的分组
题目链接 题目大意： 给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组。分数由每个子数组内的平均值的总和构成。 注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。 返回我们所能得到的最大 分数 是多少。答案误差在 10 ^ -6 内被视为是正确的。
示例 1: 输入: nums = [9,1,2,3,9], k = 3 输出: 20.00000 解释: nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 我们也可以把 nums 分成[9, 1], [2], [3, 9]. 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
示例 2: 输入: nums = [1,2,3,4,5,6,7], k = 4 输出: 20.50000
提示: 1 <= nums.length <= 100 1 <= nums[i] <= 1e4 1 <= k <= nums.length
题目解析： 题目的分数是由平均值计算，我们以[1,2,3,4]这4个数字的数组来看看分数的计算： 1234 分成[123],[4]=2+4=6 [12],[34]=1.5+3.5=6 [1],[234]=1+3=4 容易知道越小的数字单独一组收益越低，越大的数字单独一组收益越高，并且理论最大值应该改1+2+3+4=10。 基于此，我们容易知道可以用dp[i][j]，来表示前i个数字分为j组的最大分数。 对于数字a[i]，有两种选择：并入前面的分组，或者新增分组； 并入分组的情况，对于k∈[1, i - 1] dp[i][j]=max(dp[i][j], dp[k][j-1]+sum(k+1, i)/(i-k) )； 新增分组的情况，dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i])； 其中新增分组的情况，就是k=i-1的情况。 状态转移复杂度O(N)，状态数O(N ^ 2)，总的复杂度是O(N ^ 3);
class Solution {
double dp[N][N];
public:
double largestSumOfAverages(vector<int>& nums, int m) {
auto n = nums.size();
vector<double> sum;
sum.push_back(0);
for (int i = 0; i < n; ++i) sum.push_back(sum.back() + nums[i]);
for (int i = 1; i <= n; ++i) {
dp[i][i] = sum[i];
dp[i][1] = sum[i] / i;
for (int j = 2; j < i; ++j) {
dp[i][j] = 0;
for (int k = i - 1; k > 0; --k) {
// 对于k∈[1, i - 1] dp[i][j]=max(dp[i][j], dp[k][j-1]+sum(k+1, i)/(i-k) )；
dp[i][j] = max(dp[i][j], dp[k][j - 1] + (sum[i] - sum[k]) / (i - k));
}
cout << i << " " << j << " " << dp[i][j] << endl;
}
}
return dp[n][m];
}
}leetcode;题目2 在二叉树中分配硬币
题目链接 题目大意： 给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
示例 1：
输入：[3,0,0] 输出：2 解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
示例 2：
输入：root = [0,3,0] 输出：3 解释：将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。
题目解析： 遍历二叉树，方式采用后序遍历； 对于点x，如果孩子节点数为负数，则从点x迁移欠下的点数过去；如果孩子节点为正数，则迁移多出来的部分到点x； 这样遍历完之后，累计迁移的代价就是最小的移动次数。
复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
int ans;
void dfs(TreeNode *node) {
if (node->left) {
dfs(node->left);
ans += abs(node->left->val - 1);
node->val += node->left->val - 1;
}
if (node->right) {
dfs(node->right);
ans += abs(node->right->val - 1);
node->val += node->right->val - 1;
}
}
public:
int distributeCoins(TreeNode* root) {
ans = 0;
dfs(root);
return ans;
}
}leetcode;题目3 节点与其祖先之间的最大差值
题目链接 题目大意： 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。 （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13] 输出：7 解释： 我们有大量的节点与其祖先的差值，其中一些如下： |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
提示： 树中的节点数在 2 到 5000 之间。 0 <= Node.val <= 1e5
题目解析： 根据题目的要求，要找到两个有父子关系的节点，然后另他们之间的差尽可能大； 首先简化题目要求，假设不是一棵树，而是一条直线上的若干个节点，我们要如何找到任意两个节点，使其绝对差尽可能大？ 最直接的做法，我们可以枚举任意两个节点，这样的复杂度是O(N ^ 2)； 但是这样效率太低，我们可以从左到右遍历，记录最小值和最大值，最终用最大值减去最小值就可以得到最大的差值，这样的复杂度是O(N)； 同理，当问题由一条线变成一棵树时，我们同样只要遍历整个树，在过程中不断更新当前节点到根节点这一条线中的最大值和最小值，这样就能快速得到最大的差值；
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 {
int ans;
void dfs(int maxVal, int minVal, TreeNode* curNode) {
maxVal = max(maxVal, curNode->val);
minVal = min(minVal, curNode->val);
ans = max(ans, maxVal - minVal);
if (curNode->left) dfs(maxVal, minVal, curNode->left);
if (curNode->right) dfs(maxVal, minVal, curNode->right);
}
public:
int maxAncestorDiff(TreeNode* root) {
ans = 0;
dfs(root->val, root->val, root);
return ans;
}
};题目4 监控二叉树
题目链接 题目大意： 给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
题目解析： 贪心，从叶子节点开始，尽可能往上去放摄像机； 更具体的描述，每个点有3个状态，0表示初始状态，1表示放置了摄像机，2表示没有放置摄像机，但是在影响范围内； 对于某一个点，假设其左孩子是left，右孩子是right； 如果left和right中有一个为状态0，则该点必须放置摄像机，设置状态为1；（包括0+0, 0+1, 0+2, 1+0，2+0共5种状态） 如果left和right中有一个点为状态1，则该点可以不用放置摄像机，设置为状态2；（包括1+1，1+2，2+1共3种状态） 如果left和right都为状态2，则看如果看是否有父节点，如果没有父节点，则必须放置摄影机，设置状态为1；有父节点则设置状态为0，由父节点来设置摄影机；（包括状态2+2共1种状态）
为了实现上述的判断，遍历方式必须采用后序遍历。
复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
void dfs(TreeNode *node, TreeNode *parent, int &sum) {
if (node->left) {
dfs(node->left, node, sum);
}
if (node->right) {
dfs(node->right, node, sum);
}
if ((node->left && node->left->val == 0) || (node->right && node->right->val == 0)) {
node->val = 1;
++sum;
}
else if ((node->left && node->left->val == 1) || (node->right && node->right->val == 1)) {
node->val = 2;
}
else {
if (parent) {
node->val = 0;
}
else {
node->val = 1;
++sum;
}
}
}
public:
int minCameraCover(TreeNode* root) {
int ret = 0;
dfs(root, NULL, ret);
return ret;
}
}leetcode;题目5 最大频率栈
题目链接 题目大意： 实现 FreqStack，模拟类似栈的数据结构的操作的一个类。
FreqStack 有两个函数：
push(int x)，将整数 x 推入栈中。 pop()，它移除并返回栈中出现最频繁的元素。 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
示例： 输入： ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] 输出：[null,null,null,null,null,null,null,5,7,5,4] 解释： 执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后： pop() -> 返回 5，因为 5 是出现频率最高的。 栈变成 [5,7,5,7,4]。 pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。 栈变成 [5,7,5,4]。 pop() -> 返回 5 。 栈变成 [5,7,4]。 pop() -> 返回 4 。 栈变成 [5,7]。
提示： 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。 如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。 单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。 单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。 所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。
题目解析： 每个数字出现的时候，计算下当前这个数字出现了几次，得到两个信息：value和count；
假设当前有k个桶，桶1放count为1的数字，桶2放count为2的数字；
比如说【5，7，5】第3个数字5，value=5，count=2，则放入桶2的末尾；
pop的时候，找到当前出现的最后一个桶，把桶里最后一个元素拿出来，如果该桶空了，就pop掉。
class FreqStack {
vector<vector<int> > vec;
unordered_map<int, int> cntMap; // 前面出现过的次数
public:
FreqStack() {
}
void push(int x) {
int count = cntMap[x];
if (vec.size() <= count) {
vector<int> tmpVec;
tmpVec.push_back(x);
vec.push_back(tmpVec);
}
else {
vec[count].push_back(x);
}
++cntMap[x];
}
int pop() {
int ret = vec.back().back();
vec.back().pop_back();
if (vec.back().empty()) {
vec.pop_back();
}
cntMap[ret]--;
return ret;
}
}leetcode;