题目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;