455. 分發(fā)餅干

假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j]。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

示例 1:

輸入: g = [1,2,3], s = [1,1] 輸出: 1 解釋: 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。 雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。 所以你應(yīng)該輸出1。

示例 2:

輸入: g = [1,2], s = [1,2,3] 輸出: 2 解釋: 你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。 你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。 所以你應(yīng)該輸出2.

提示：

• 1 <= g.length <= 3 * 10(4)

• 0 <= s.length <= 3 * 10(4)

• 1 <= g[i], s[j] <= 2(31) - 1

class Solution {
public:
    int findContentChildren(vector<int>& children, vector<int>& cookies) {
        sort(children.begin(), children.end());
        sort(cookies.begin(), cookies.end());
        int child = 0, cookie = 0;
        while (child < children.size() && cookie < cookies.size()) {
            if (children[child] <= cookies[cookie])
                ++child;
            ++cookie;
        }
        return child;
    }
};

問題的核心是盡可能滿足更多孩子的胃口，每個孩子最多能得到一塊餅干，每塊餅干也只能分給一個孩子，給定一個孩子數(shù)組children代表每個孩子的胃口值，一個餅干數(shù)組cookies代表每塊餅干的大小，求最多有多少孩子能得到餅干滿足胃口。

sort(children.begin(), children.end());這行代碼將children數(shù)組按胃口值從小到大排序。

sort(cookies.begin(), cookies.end());這行代碼將cookies數(shù)組按餅干大小從小到大排序。

int child = 0, cookie = 0;初始化兩個變量child和cookie，分別表示當(dāng)前考慮到的孩子和餅干的索引。

while (child < children.size() && cookie < cookies.size()) {這個循環(huán)繼續(xù)執(zhí)行直到所有孩子都被考慮過或所有餅干都被嘗試分配。

if (children[child] <= cookies[cookie]) ++child;如果當(dāng)前餅干的大小能滿足當(dāng)前孩子的胃口，那么這個孩子被滿足，移動到下一個孩子。

++cookie;無論當(dāng)前的餅干是否能滿足當(dāng)前的孩子，都將考慮下一塊餅干。

時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度：O(nlogn)。主要時間開銷來自于排序children和cookies數(shù)組，假設(shè)children和cookies的長度分別為m和n，那么時間復(fù)雜度為O(mlogm + nlogn)。遍歷數(shù)組的過程時間復(fù)雜度為O(m+n)，所以總體時間復(fù)雜度為O(nlogn)，這里n是兩個數(shù)組中較長的那個的長度。

空間復(fù)雜度：O(1)。除了輸入的數(shù)組外，我們只使用了常數(shù)空間。

135. 分發(fā)糖果

n 個孩子站成一排。給你一個整數(shù)數(shù)組 ratings 表示每個孩子的評分。

你需要按照以下要求，給這些孩子分發(fā)糖果：

• 每個孩子至少分配到 1 個糖果。

• 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。

請你給每個孩子分發(fā)糖果，計算并返回需要準(zhǔn)備的 最少糖果數(shù)目 。

示例 1：

輸入：ratings = [1,0,2] 輸出：5 解釋：你可以分別給第一個、第二個、第三個孩子分發(fā) 2、1、2 顆糖果。

示例 2：

輸入：ratings = [1,2,2] 輸出：4 解釋：你可以分別給第一個、第二個、第三個孩子分發(fā) 1、2、1 顆糖果。 第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件。

提示：

• n == ratings.length

• 1 <= n <= 2 * 10(4)

• 0 <= ratings[i] <= 2 * 10(4)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if (size < 2) {
            return size;
        }
        vector<int> num(size, 1);
        for (int i = 1; i < size; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                num[i] = num[i - 1] + 1;
            }
        }
        for (int i = size - 1; i > 0; --i) {
            if (ratings[i] < ratings[i - 1]) {
                num[i - 1] = max(num[i - 1], num[i] + 1);
            }
        }
        return accumulate(num.begin(), num.end(),0); // std::accumulate 可以很方便地求和
    }
};

定義變量 size 為評分?jǐn)?shù)組 ratings 的長度。

如果 size 小于 2，直接返回 size。因為如果只有一個孩子，那他就是唯一的獲得糖果的人，直接返回1；如果沒有孩子，返回0。

初始化一個大小與 ratings 相同，值全為1的數(shù)組 num。這一步確保了每個孩子至少得到一顆糖果。

第一次遍歷：從左到右遍歷 ratings。

如果當(dāng)前孩子（i對應(yīng)孩子）的評分高于左邊的孩子（ratings[i] > ratings[i - 1]），則當(dāng)前孩子得到的糖果數(shù)應(yīng)該比左邊的孩子多一顆（num[i] = num[i - 1] + 1）。

第二次遍歷：從右到左遍歷 ratings。

如果當(dāng)前孩子（i-1對應(yīng)孩子）的評分高于右邊的孩子（ratings[i] < ratings[i - 1]），則左邊的孩子得到的糖果數(shù)應(yīng)該是其原本的數(shù)目和右邊孩子的糖果數(shù)加一中的較大值（num[i - 1] = max(num[i - 1], num[i] + 1)）。

最后，使用 accumulate 函數(shù)對 num 數(shù)組進(jìn)行求和，得到總共需要的糖果數(shù)，并返回這個值。accumulate 函數(shù)起始值為0，意味著從0開始累加 num 數(shù)組中所有元素的值。

accumulate函數(shù)

accumulate 函數(shù)是 C++ 標(biāo)準(zhǔn)庫中 <numeric> 頭文件提供的一個非常實用的數(shù)值累加函數(shù)。它用于計算一個給定范圍內(nèi)所有元素的累加和，或者在提供了自定義操作時，按照該操作進(jìn)行累加。accumulate 的基本用法是計算序列的總和，但通過自定義加法操作，它也可以用于更復(fù)雜的累加操作，如累乘。

基本用法

基礎(chǔ)版本的 accumulate 接受三個參數(shù)：序列的開始迭代器、結(jié)束迭代器和累加的初始值。如果不指定操作，則默認(rèn)進(jìn)行加法操作。下面是一個簡單的例子：

#include <numeric> // 引入accumulate的頭文件
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0); // 計算總和

在這個例子中，accumulate 從 0 開始，將 v 中的每個元素相加，計算出總和為 15。

使用自定義操作

accumulate 還允許你指定一個自定義的二元操作函數(shù)，來代替默認(rèn)的加法操作。這個二元操作接受兩個參數(shù)：累加值（到當(dāng)前為止的結(jié)果）和序列中的當(dāng)前元素。這使得 accumulate 變得非常靈活，可以實現(xiàn)各種復(fù)雜的累加邏輯。

例如，使用 accumulate 來計算一個數(shù)列的乘積：

#include <numeric>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};
int product = std::accumulate(v.begin(), v.end(), 1, [](int a, int b) {
    return a * b;
});

這里，初始值設(shè)為 1（乘法的單位元），并通過一個 lambda 表達(dá)式指定乘法為累加操作。最終，product 的值為 120，即 1*2*3*4*5 的結(jié)果。

注意事項

accumulate 默認(rèn)使用加法操作時，累加初始值的類型決定了整個操作的類型。例如，如果初始值為整數(shù)，那么即使數(shù)組是浮點數(shù)，累加結(jié)果也會被截斷為整數(shù)。因此，選擇合適的初始值類型是非常重要的。

435. 無重疊區(qū)間

給定一個區(qū)間的集合 intervals ，其中 intervals[i] = [start(i), end(i)] 。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 。

示例 1:

輸入: intervals = [[1,2],[2,3],[3,4],[1,3]] 輸出: 1 解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: intervals = [ [1,2], [1,2], [1,2] ] 輸出: 2 解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: intervals = [ [1,2], [2,3] ] 輸出: 0 解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。

提示:

• 1 <= intervals.length <= 10(5)

• intervals[i].length == 2

• -5 * 10(4) <= start(i) < end(i) <= 5 * 10(4)

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }
    int n = intervals.size();
    sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
        return a[1] < b[1];
    });
    int total = 0, prev = intervals[0][1];
    for (int i = 1; i < n; ++i) {
        if (intervals[i][0] < prev) {
            ++total;
        } else {
            prev = intervals[i][1];
        }
    }
    return total;
 }

檢查區(qū)間數(shù)組是否為空：

if (intervals.empty()) { return 0; }如果區(qū)間數(shù)組為空，則沒有需要移除的區(qū)間，直接返回0。

獲取區(qū)間數(shù)組的大小：

int n = intervals.size();這里定義了一個變量 n 來存儲區(qū)間數(shù)組的長度。

按區(qū)間結(jié)束時間排序：

sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) { return a[1] < b[1]; });使用標(biāo)準(zhǔn)庫函數(shù) sort，通過自定義的比較函數(shù)，將區(qū)間按照結(jié)束時間升序排序。這樣做的目的是盡可能讓區(qū)間不重疊，因為結(jié)束得早的區(qū)間留給后面的區(qū)間的空間就越多。

初始化計數(shù)器和前一個區(qū)間的結(jié)束右端點：

int total = 0, prev = intervals[0][1];初始化需要移除的區(qū)間數(shù)量 total 為0，并將 prev 設(shè)置為第一個區(qū)間的結(jié)束時間。prev 用于記錄當(dāng)前不重疊區(qū)間的最后一個區(qū)間的結(jié)束時間。

遍歷區(qū)間數(shù)組，確定需要移除的區(qū)間數(shù)量：

for (int i = 1; i < n; ++i) { if (intervals[i][0] < prev) { ++total; } else { prev = intervals[i][1]; } }從第二個區(qū)間開始遍歷，如果當(dāng)前區(qū)間的開始時間小于前一個區(qū)間的結(jié)束時間 prev，說明這兩個區(qū)間重疊，需要移除一個區(qū)間，因此 total 自增1。如果不重疊，更新 prev 為當(dāng)前區(qū)間的結(jié)束時間，繼續(xù)向后比較。

標(biāo)準(zhǔn)庫函數(shù)sort

C++ 標(biāo)準(zhǔn)庫中的 sort 函數(shù)是一個非常強大且靈活的排序算法，主要用于對數(shù)組或容器內(nèi)的元素進(jìn)行排序。它位于 <algorithm> 頭文件中。sort 函數(shù)可以對一個序列進(jìn)行默認(rèn)的升序排序，也可以通過自定義比較函數(shù)來指定排序規(guī)則。

基本用法

默認(rèn)情況下，sort 對序列進(jìn)行升序排序。如果你想對一個數(shù)組或者 vector 排序，可以這樣使用：

#include <algorithm> // 引入算法庫
#include <vector>

std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end());

在上述代碼中，v.begin() 和 v.end() 分別是容器 v 的起始迭代器和終止迭代器，sort 函數(shù)會將 v 中的元素從小到大排序。

自定義比較函數(shù)

sort 函數(shù)允許你通過自定義比較函數(shù)來指定排序規(guī)則，這讓你能夠?qū)崿F(xiàn)復(fù)雜的排序邏輯，比如降序排序或者根據(jù)對象的某個屬性排序。

自定義比較函數(shù)可以是一個普通函數(shù)，也可以是一個lambda表達(dá)式。比較函數(shù)需要接受兩個參數(shù)（被比較的元素），并返回一個布爾值，指示第一個參數(shù)是否應(yīng)該位于第二個參數(shù)之前。

使用普通函數(shù)作為比較函數(shù)

bool compare(int a, int b) {
    return a > b; // 降序排序
}

std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), compare);

使用 Lambda 表達(dá)式

Lambda 表達(dá)式提供了一種便捷的方式來定義臨時的比較函數(shù)，這在實現(xiàn)簡單的自定義排序規(guī)則時非常有用：

std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; // 降序排序
});

對象排序

如果你想根據(jù)對象的某個屬性排序，可以這樣做：

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age; // 按年齡升序排序
}

std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Carol", 20}};
std::sort(people.begin(), people.end(), compareByAge);

或者使用 Lambda 表達(dá)式：

std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age; // 按年齡升序排序
});

結(jié)尾

最后，感謝您閱讀我的文章，希望這些內(nèi)容能夠?qū)δ兴鶈l(fā)和幫助。如果您有任何問題或想要分享您的觀點，請隨時在評論區(qū)留言。

同時，不要忘記訂閱我的博客以獲取更多有趣的內(nèi)容。在未來的文章中，我將繼續(xù)探討這個話題的不同方面，為您呈現(xiàn)更多深度和見解。

謝謝您的支持，期待與您在下一篇文章中再次相遇！文章來源地址http://www.zghlxwxcb.cn/news/detail-840795.html

到了這里，關(guān)于【四】【算法分析與設(shè)計】貪心算法的初見的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！