選擇排序

我們熟知的選擇排序，其采用的就是貪心策略。 它所采用的貪心策略即為每次從未排序的數(shù)據(jù)中選取最小值，并把最小值放在未排序數(shù)據(jù)的起始位置，直到未排序的數(shù)據(jù)為0，則結(jié)束排序。

void swap(int* arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void selectSort(int* arr, int n)
{
	//降序
	for (int i = 0; i < n; i++)
	{
		int maxIndex = i;
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] >= arr[maxIndex])
				maxIndex = j;
		}
		swap(arr, i, maxIndex);
	}
}

平衡字符串

問(wèn)題描述：

在一個(gè) 平衡字符串 中，‘L' 和 ‘R' 字符的數(shù)量是相同的。

給你一個(gè)平衡字符串 s，請(qǐng)你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個(gè)字符串都必須是平衡字符串，且分割得到的平衡字符串是原平衡字符串的連續(xù)子串。

返回可以通過(guò)分割得到的平衡字符串的 最大數(shù)量 。

貪心策略：從左往右掃描，只要達(dá)到平衡，就立即分割，不要有嵌套的平衡。

故可以定義一個(gè)變量balance，在遇到不同的字符時(shí)，向不同的方向變化，當(dāng)balance為0時(shí)達(dá)到平衡，分割數(shù)更新。

比如：從左往右掃描字符串s，遇到L，balance-1，遇到R，balance+1.當(dāng)balance為0時(shí)，更新cnt++ 如果最終cnt==0，說(shuō)明s只需要保持原樣，返回1

代碼實(shí)現(xiàn)：

class Solution {
public:
    int balancedStringSplit(string s) {
        if(s.size() == 1)
            return 0;
        int cnt = 0;
        int balance = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == 'R')
                --balance;
            else 
                ++balance;
            if(balance == 0)
                cnt++;
        }
        if(cnt == 0)
            return 1;

        return cnt;
    }
};

買股票的最佳時(shí)機(jī)

問(wèn)題描述：

給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

貪心策略：

連續(xù)上漲交易日：第一天買最后一天賣收益最大，等價(jià)于每天都買賣。

連續(xù)下降交易日：不買賣收益最大，即不會(huì)虧錢(qián)。

故可以遍歷整個(gè)股票交易日價(jià)格列表，在所有上漲交易日都買賣（賺到所有利潤(rùn)），所有下降交易日都不買賣（永不虧錢(qián)）

例如從10到50是連續(xù)上漲的5天，可以第一天買入，最后一天賣出，利潤(rùn)為40，等價(jià)于第一天買入第二天賣出，第二天再買入。。。以此類推

代碼實(shí)現(xiàn)：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 0; i < prices.size() - 1; i++)
        {
            if(prices[i] <= prices[i+1])
                profit += prices[i+1] - prices[i];
        }

        return profit;
    }
};

跳躍游戲

問(wèn)題描述：

給定一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。

貪心策略：

根據(jù)題目描述，對(duì)于數(shù)組中的任意一個(gè)位置y，只要存在一個(gè)位置x，它本身可以到達(dá)，并且它跳躍的最大長(zhǎng)度為x+nums[x]，這個(gè)值大于等于y，即x+nums[x] >= y，那么位置y也可以到達(dá)。即對(duì)于每一個(gè)可以到達(dá)的位置x，它使得x+1，x+2，…，x+nums[x] >= y，那么位置y也可以到達(dá)。 一次遍歷數(shù)組中的每一個(gè)位置，并實(shí)時(shí)更新最遠(yuǎn)可以到達(dá)的位置。對(duì)于當(dāng)前遍歷到的位置x，如果它在最遠(yuǎn)可以到達(dá)的位置范圍內(nèi)，那么我們就可以從起點(diǎn)通過(guò)若干次跳躍達(dá)到該位置，因此我們可以用x+nums[x]更新最遠(yuǎn)可以到達(dá)的位置。

在遍歷的過(guò)程中，如果最遠(yuǎn)可以到達(dá)的位置大于等于數(shù)組中的最后一個(gè)位置，那就說(shuō)明最后一個(gè)位置可到達(dá)，直接返回true。遍歷結(jié)束后，最后一個(gè)位置仍不可達(dá)，返回false。

例如：[2, 3, 1, 1, 4]

一開(kāi)始在位置0，可跳躍的最大長(zhǎng)度為2，因此最遠(yuǎn)可以到達(dá)的位置倍更新為2；繼續(xù)遍歷到位置1，由于1<=2，因此位置1可達(dá)。用1加上它最大可跳躍的長(zhǎng)度3，將最遠(yuǎn)可以到達(dá)的位置更新為4，4大于最后一個(gè)位置4，返回true

代碼實(shí)現(xiàn)：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxLen = nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(i <= maxLen)
            {
                maxLen = max(i + nums[i],maxLen);
                if(maxLen >= nums.size() - 1)
                    return true;
            }
        }

        return false;
    }
};

錢(qián)幣找零

問(wèn)題描述：

假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現(xiàn)在要用這些錢(qián)來(lái)支付K元，至少要用多少?gòu)埣垘牛?/p>

貪心策略： 顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們也是這么做的。

代碼實(shí)現(xiàn)：

//按面值降序
struct cmp {
	bool operator()(vector<int>& a1, vector<int>& a2) {
		return a1[0] > a2[0];
	}
};

int solve(vector<vector<int>>& moneyCount, int money)
{
	int num = 0;
	sort(moneyCount.begin(), moneyCount.end(), cmp());
	//首先選擇最大面值的紙幣
	for (int i = 0; i < moneyCount.size() - 1; i++)
	{
		//選擇需要的當(dāng)前面值和該面值有的數(shù)量中的較小值
		int c = min(money / moneyCount[i][0], moneyCount[i][1]);
		money -= c * moneyCount[i][0];
		num += c;
	}
	if (money > 0)
		num = -1;
	return num;
}

多機(jī)調(diào)度問(wèn)題

問(wèn)題描述：

某工廠有n個(gè)獨(dú)立的作業(yè)，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的加工時(shí)間為ti，任何作業(yè)在被處理時(shí)不能中斷，也不能進(jìn)行拆分處理?，F(xiàn)廠長(zhǎng)請(qǐng)你給他寫(xiě)一個(gè)程序：算出n個(gè)作業(yè)由m臺(tái)機(jī)器加工處理的最短時(shí)間。

輸入：第一行T（1<T<100)表示有T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的第一行分別是整數(shù)n，m（1<=n<=10000，1<=m<=100），接下來(lái)的一行是n個(gè)整數(shù)ti（1<=t<=100)。

輸出：所需的最短時(shí)間

貪心策略：

這個(gè)問(wèn)題還沒(méi)有最優(yōu)解，但是用貪心選擇策略可設(shè)計(jì)出較好的近似算法（求次優(yōu)解） 當(dāng)n<=m時(shí)，只要將作業(yè)分給每一個(gè)機(jī)器即可；當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)時(shí)間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給下一個(gè)作業(yè)馬上結(jié)束的處理機(jī)。也就是說(shuō)從剩下的作業(yè)中選擇需要處理時(shí)間最長(zhǎng)的，然后依次選擇處理時(shí)間次長(zhǎng)的，直到所有作業(yè)全部處理完畢，或者機(jī)器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時(shí)間最短的作業(yè)分配給空閑的機(jī)器，那么可能就會(huì)儲(chǔ)秀安其它所有作業(yè)都處理完了只剩下所需時(shí)間最長(zhǎng)的作業(yè)在處理的情況，這樣勢(shì)必效率較低。

代碼實(shí)現(xiàn)：

struct cmp{
	bool operator()(const int& x, const int& y){
		return x > y;
	}
};

int findMax(vector<int>& machines)
{
	int ret = 0;
	for (int i = 0; i < machines.size(); i++)
	{
		if (machines[i] > machines[ret])
			ret = i;
	}

	return machines[ret];
}

int greedStrategy(vector<int>& works, vector<int>& machines)
{
	//降序
	sort(works.begin(), works.end(), cmp());
	int n = works.size();
	int m = machines.size();
	for (int i = 0; i < n; i++)
	{
		int finish = 0;
		int machineTime = machines[finish];
		for (int j = 1; j < m; j++)
		{
			if (machines[j] < machines[finish])
			{
				finish = j;
			}
		}
		machines[finish] += works[i];
	}

	return findMax(machines);
}

活動(dòng)選擇

問(wèn)題描述：

有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1, a2, …, an，教室同一時(shí)刻只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)a[i]都有一個(gè)開(kāi)始時(shí)間s[i]和結(jié)束時(shí)間f[i]。一旦被選擇后，活動(dòng)a[i]就占據(jù)半開(kāi)時(shí)間區(qū)間[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重疊，a[i]和a[j]兩個(gè)活動(dòng)就可以被安排在這一天。求使得盡量多的活動(dòng)能不沖突的舉行的最大數(shù)量。

貪心策略：

1.每次都選擇開(kāi)始時(shí)間最早的活動(dòng)，不能得到最優(yōu)解。

2.每次都選擇持續(xù)時(shí)間最短的活動(dòng)，不能得到最優(yōu)解。

3.每次選取結(jié)束時(shí)間最早的活動(dòng)（結(jié)束時(shí)間最早意味著開(kāi)始時(shí)間也早），可以得到最優(yōu)解。按這種方法選擇，可以為未安排的活動(dòng)留下盡可能多的時(shí)間。如下圖的活動(dòng)集合S，其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序。

代碼實(shí)現(xiàn)：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

int getMaxNum(vector<vector<int>>& events)
{
	sort(events.begin(), events.end(), cmp());
	int num = 1;
	int i = 0;
	for (int j = 1; j < events.size();j++)
	{
		if (events[j][0] >= events[i][1])
		{
			++num;
			i = j;
		}
	}

	return num;
}

無(wú)重疊區(qū)間

問(wèn)題描述：

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。

區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒(méi)有相互重疊。

貪心策略：

法一：與上題活動(dòng)選擇類似，用總區(qū)間數(shù)減去最大可同時(shí)進(jìn)行的區(qū)間數(shù)即為結(jié)果。

法二： 當(dāng)按照起點(diǎn)先后順序考慮區(qū)間時(shí)，利用一個(gè)prev指針追蹤剛剛添加到最終列表中的區(qū)間。遍歷時(shí)，可能遇到三種情況：

情況1：當(dāng)前考慮的兩個(gè)區(qū)間不重疊。這種情況下不移除任何區(qū)間，將prev賦值為后面的區(qū)間，移除區(qū)間數(shù)量不變。

情況2：兩個(gè)區(qū)間重疊，后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之前。由于后一個(gè)區(qū)間的長(zhǎng)度更小，可以留下更多空間，容納更多區(qū)間，將prev更新為當(dāng)前區(qū)間，移除區(qū)間的數(shù)量+1

情況3：兩個(gè)區(qū)間重疊，后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之后。直接移除后一個(gè)區(qū)間，留下更多空間。因此，prev不變，移除區(qū)間的數(shù)量+1

代碼實(shí)現(xiàn)： 法一：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp());
        int num = 1;
        int i = 0;
        for(int j = 1; j < intervals.size(); j++)
        {
            if(intervals[j][0] >= intervals[i][1])
            {
                i = j;
                num++;
            }
        }

        return intervals.size() - num;
    }
};

法二：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        sort(intervals.begin(), intervals.end(), cmp());
        int prev = 0;
        int num = 0;
        for(int i = 1; i < intervals.size(); i++)
        {
            //情況1 不沖突
            if(intervals[i][0] >= intervals[prev][1])
            {
                prev = i;
            }
            else
            {
                if(intervals[i][1] < intervals[prev][1])
                {
                    //情況2
                    prev = i;
                }
                num++;
            }
        }

        return num;
    }
};

到此這篇關(guān)于C++ 算法精講之貪心算法的文章就介紹到這了,更多相關(guān)C++ 貪心算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論