題目1 最大平均值和的分組

題目鏈接
題目大意：
給定數(shù)組 nums 和一個(gè)整數(shù) k 笙纤。我們將給定的數(shù)組 nums 分成 最多 k 個(gè)相鄰的非空子數(shù)組组力。分?jǐn)?shù)由每個(gè)子數(shù)組內(nèi)的平均值的總和構(gòu)成。
注意我們必須使用 nums 數(shù)組中的每一個(gè)數(shù)進(jìn)行分組腥椒，并且分?jǐn)?shù)不一定需要是整數(shù)候衍。
返回我們所能得到的最大 分?jǐn)?shù) 是多少。答案誤差在 10 ^ -6 內(nèi)被視為是正確的脱柱。

示例 1:
輸入: nums = [9,1,2,3,9], k = 3
輸出: 20.00000
解釋:
nums 的最優(yōu)分組是[9], [1, 2, 3], [9]. 得到的分?jǐn)?shù)是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我們也可以把 nums 分成[9, 1], [2], [3, 9].
這樣的分組得到的分?jǐn)?shù)為 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

題目解析：
題目的分?jǐn)?shù)是由平均值計(jì)算榨为，我們以[1,2,3,4]這4個(gè)數(shù)字的數(shù)組來(lái)看看分?jǐn)?shù)的計(jì)算：
1234
分成[123],[4]=2+4=6
[12],[34]=1.5+3.5=6
[1],[234]=1+3=4
容易知道越小的數(shù)字單獨(dú)一組收益越低，越大的數(shù)字單獨(dú)一組收益越高随闺，并且理論最大值應(yīng)該改1+2+3+4=10。
基于此龄句，我們?nèi)菀字揽梢杂胐p[i][j]，來(lái)表示前i個(gè)數(shù)字分為j組的最大分?jǐn)?shù)分歇。
對(duì)于數(shù)字a[i]，有兩種選擇：并入前面的分組葬燎，或者新增分組缚甩；
并入分組的情況，對(duì)于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的情況。
狀態(tài)轉(zhuǎn)移復(fù)雜度O(N)庆猫，狀態(tài)數(shù)O(N ^ 2)绅络，總的復(fù)雜度是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) {
                    // 對(duì)于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 在二叉樹(shù)中分配硬幣

題目鏈接
題目大意：
給定一個(gè)有 N 個(gè)結(jié)點(diǎn)的二叉樹(shù)的根結(jié)點(diǎn) root杉畜，樹(shù)中的每個(gè)結(jié)點(diǎn)上都對(duì)應(yīng)有 node.val 枚硬幣衷恭，并且總共有 N 枚硬幣。

在一次移動(dòng)中随珠，我們可以選擇兩個(gè)相鄰的結(jié)點(diǎn)，然后將一枚硬幣從其中一個(gè)結(jié)點(diǎn)移動(dòng)到另一個(gè)結(jié)點(diǎn)茸歧。(移動(dòng)可以是從父結(jié)點(diǎn)到子結(jié)點(diǎn)显沈，或者從子結(jié)點(diǎn)移動(dòng)到父結(jié)點(diǎn)逢唤。)涤浇。

返回使每個(gè)結(jié)點(diǎn)上只有一枚硬幣所需的移動(dòng)次數(shù)。

示例 1：

輸入：[3,0,0]
輸出：2
解釋?zhuān)簭臉?shù)的根結(jié)點(diǎn)開(kāi)始著恩，我們將一枚硬幣移到它的左子結(jié)點(diǎn)上纹烹，一枚硬幣移到它的右子結(jié)點(diǎn)上。

示例 2：

輸入：root = [0,3,0]
輸出：3
解釋?zhuān)簩擅队矌艔母Y(jié)點(diǎn)的左子結(jié)點(diǎn)移動(dòng)到根結(jié)點(diǎn)（兩次移動(dòng)）铺呵。然后，將一枚硬幣從根結(jié)點(diǎn)移動(dòng)到右子結(jié)點(diǎn)幻林。

題目解析：
遍歷二叉樹(shù)音念，方式采用后序遍歷；
對(duì)于點(diǎn)x闷愤，如果孩子節(jié)點(diǎn)數(shù)為負(fù)數(shù)，則從點(diǎn)x遷移欠下的點(diǎn)數(shù)過(guò)去遭居；如果孩子節(jié)點(diǎn)為正數(shù)旬渠，則遷移多出來(lái)的部分到點(diǎn)x；
這樣遍歷完之后告丢，累計(jì)遷移的代價(jià)就是最小的移動(dòng)次數(shù)。

復(fù)雜度解析：
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是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 節(jié)點(diǎn)與其祖先之間的最大差值

題目鏈接
題目大意：
給定二叉樹(shù)的根節(jié)點(diǎn) root岳颇，找出存在于 不同 節(jié)點(diǎn) A 和 B 之間的最大值 V觅捆，其中 V = |A.val - B.val|，且 A 是 B 的祖先掂摔。
（如果 A 的任何子節(jié)點(diǎn)之一為 B术羔，或者 A 的任何子節(jié)點(diǎn)是 B 的祖先乙漓，那么我們認(rèn)為 A 是 B 的祖先）

示例 1：

輸入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
輸出：7
解釋?zhuān)?br> 我們有大量的節(jié)點(diǎn)與其祖先的差值叭披，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出涩蜘。

提示：
樹(shù)中的節(jié)點(diǎn)數(shù)在 2 到 5000 之間。
0 <= Node.val <= 1e5

題目解析：
根據(jù)題目的要求粤策，要找到兩個(gè)有父子關(guān)系的節(jié)點(diǎn)误窖，然后另他們之間的差盡可能大；
首先簡(jiǎn)化題目要求霹俺，假設(shè)不是一棵樹(shù)，而是一條直線(xiàn)上的若干個(gè)節(jié)點(diǎn)愈魏，我們要如何找到任意兩個(gè)節(jié)點(diǎn)，使其絕對(duì)差盡可能大蝌戒？
最直接的做法沼琉，我們可以枚舉任意兩個(gè)節(jié)點(diǎn)桩匪，這樣的復(fù)雜度是O(N ^ 2)；
但是這樣效率太低傻昙，我們可以從左到右遍歷，記錄最小值和最大值僻爽，最終用最大值減去最小值就可以得到最大的差值贾惦，這樣的復(fù)雜度是O(N)敦捧；
同理碰镜，當(dāng)問(wèn)題由一條線(xiàn)變成一棵樹(shù)時(shí)，我們同樣只要遍歷整個(gè)樹(shù)绪颖，在過(guò)程中不斷更新當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)這一條線(xià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 監(jiān)控二叉樹(shù)

題目鏈接
題目大意：
給定一個(gè)二叉樹(shù)牍氛，我們?cè)跇?shù)的節(jié)點(diǎn)上安裝攝像頭。

節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象踱稍、自身及其直接子對(duì)象。

計(jì)算監(jiān)控樹(shù)的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量珠月。

示例 1：

輸入：[0,0,null,0,0]
輸出：1
解釋?zhuān)喝鐖D所示楔敌，一臺(tái)攝像頭足以監(jiān)控所有節(jié)點(diǎn)。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0]
輸出：2
解釋?zhuān)盒枰辽賰蓚€(gè)攝像頭來(lái)監(jiān)視樹(shù)的所有節(jié)點(diǎn)庆聘。 上圖顯示了攝像頭放置的有效位置之一勺卢。

題目解析：
貪心，從葉子節(jié)點(diǎn)開(kāi)始黑忱，盡可能往上去放攝像機(jī)；
更具體的描述菇曲，每個(gè)點(diǎn)有3個(gè)狀態(tài)抚吠，0表示初始狀態(tài)，1表示放置了攝像機(jī)楷力，2表示沒(méi)有放置攝像機(jī)孵户，但是在影響范圍內(nèi)垃帅；
對(duì)于某一個(gè)點(diǎn)，假設(shè)其左孩子是left贸诚，右孩子是right；
如果left和right中有一個(gè)為狀態(tài)0械念，則該點(diǎn)必須放置攝像機(jī)运悲，設(shè)置狀態(tài)為1；（包括0+0, 0+1, 0+2, 1+0班眯，2+0共5種狀態(tài)）
如果left和right中有一個(gè)點(diǎn)為狀態(tài)1，則該點(diǎn)可以不用放置攝像機(jī)宠能，設(shè)置為狀態(tài)2磁餐；（包括1+1，1+2诊霹，2+1共3種狀態(tài)）
如果left和right都為狀態(tài)2，則看如果看是否有父節(jié)點(diǎn)脾还，如果沒(méi)有父節(jié)點(diǎn)，則必須放置攝影機(jī)赛蔫，設(shè)置狀態(tài)為1泥张；有父節(jié)點(diǎn)則設(shè)置狀態(tài)為0鞠值，由父節(jié)點(diǎn)來(lái)設(shè)置攝影機(jī)；（包括狀態(tài)2+2共1種狀態(tài)）

為了實(shí)現(xiàn)上述的判斷彤恶，遍歷方式必須采用后序遍歷鳄橘。

復(fù)雜度解析：
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是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 最大頻率棧

題目鏈接
題目大意：
實(shí)現(xiàn) FreqStack瘫怜，模擬類(lèi)似棧的數(shù)據(jù)結(jié)構(gòu)的操作的一個(gè)類(lèi)本刽。

FreqStack 有兩個(gè)函數(shù)：

push(int x)，將整數(shù) x 推入棧中子寓。
pop()，它移除并返回棧中出現(xiàn)最頻繁的元素斜友。
如果最頻繁的元素不只一個(gè)，則移除并返回最接近棧頂?shù)脑亍?/p>

示例：
輸入：
["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]
解釋?zhuān)?br> 執(zhí)行六次 .push 操作后烹看，棧自底向上為 [5,7,5,7,4,5]洛史。然后：
pop() -> 返回 5，因?yàn)?5 是出現(xiàn)頻率最高的虹菲。
棧變成 [5,7,5,7,4]。
pop() -> 返回 7浪漠，因?yàn)?5 和 7 都是頻率最高的霎褐，但 7 最接近棧頂。
棧變成 [5,7,5,4]冻璃。
pop() -> 返回 5 。
棧變成 [5,7,4]娘纷。
pop() -> 返回 4 。
棧變成 [5,7]赖晶。

提示：
對(duì) FreqStack.push(int x) 的調(diào)用中 0 <= x <= 10^9。
如果棧的元素?cái)?shù)目為零遏插，則保證不會(huì)調(diào)用 FreqStack.pop()。
單個(gè)測(cè)試樣例中厂僧，對(duì) FreqStack.push 的總調(diào)用次數(shù)不會(huì)超過(guò) 10000了牛。
單個(gè)測(cè)試樣例中，對(duì) FreqStack.pop 的總調(diào)用次數(shù)不會(huì)超過(guò) 10000白魂。
所有測(cè)試樣例中，對(duì) FreqStack.push 和 FreqStack.pop 的總調(diào)用次數(shù)不會(huì)超過(guò) 150000蕴坪。

題目解析：
每個(gè)數(shù)字出現(xiàn)的時(shí)候敬锐，計(jì)算下當(dāng)前這個(gè)數(shù)字出現(xiàn)了幾次背传，得到兩個(gè)信息：value和count；

假設(shè)當(dāng)前有k個(gè)桶径玖，桶1放count為1的數(shù)字颤介，桶2放count為2的數(shù)字；

比如說(shuō)【5滚朵，7，5】第3個(gè)數(shù)字5韵吨，value=5移宅，count=2，則放入桶2的末尾漏峰；

pop的時(shí)候，找到當(dāng)前出現(xiàn)的最后一個(gè)桶浅乔，把桶里最后一個(gè)元素拿出來(lái)，如果該桶空了滴劲，就pop掉顾复。

class FreqStack {
    vector<vector<int> > vec;
    unordered_map<int, int> cntMap; // 前面出現(xiàn)過(guò)的次數(shù)
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;