文章目錄
- 1.何謂貪心演算法
- 2.分發餅干
- 3.跳躍游戲
- 4.避免重復字母的最小洗掉成本
1.何謂貪心演算法
貪心演算法，顧名思義，重點落在貪心的演算法，即用最小的代價滿足需求
常用于求最優解，貪心演算法的特點是，通過求出區域的最優解來獲得整體的最優解
2.分發餅干
假設你是一位很棒的家長，想要給你的孩子們一些小餅干，但是，每個孩子最多只能給一塊餅干，
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] ，如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足，你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值，
題目鏈接
題目分析：
int Compar(int *x,int *y)
{
return *x-*y;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
qsort(g,gSize,sizeof(int),Compar);
qsort(s,sSize,sizeof(int),Compar);
//先滿足區域最優解，即用最小的餅干，滿足胃口最小的孩子
int count=0;//計數器，記錄滿足了多少個孩子
int sub=0;//孩子陣列下標
for(int i=0;i<sSize;i++)
{
if(sub>=gSize)//沒有孩子了
return count;
if(s[i]>=g[sub])//當前孩子滿足了
{
count++;
sub++;
}
}
return count;
}
3.跳躍游戲
給定一個非負整數陣列，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
題目鏈接
決議：
int jump(int* nums, int numsSize){
if(numsSize==1)
return 0;
int count=0;//記錄跳躍次數
int max=0;//記錄可以跳多遠
int sub=0;//記錄最適宜的下標
int i=0;
while(i<numsSize)
{
if(nums[i]+i>=numsSize-1)//當前點可以直接跳往終點
{ count++;//跳往終點也需要一步
return count;
}
//不能直接跳往終點，則繼續求一下個最優解
sub=0;
max=0;
for(int j=1;j<=nums[i];j++)
{
if((nums[i+j]+j)>max)//下一步的距離加上當前步的距離達到最遠處
{
max=nums[i+j]+j;//記錄可以達到的最遠距離
sub=j;//記錄跳多遠
}
}
count++;//跳一次
i=i+sub;//更新到跳躍位置
}
return count;//更新完位置之后直接跳出了
}
4.避免重復字母的最小洗掉成本
給你一個字串 s 和一個整數陣列 cost ，其中 cost[i] 是從 s 中洗掉字符 i 的代價，
回傳使字串任意相鄰兩個字母不相同的最小洗掉成本，
請注意，洗掉一個字符后，洗掉其他字符的成本不會改變，
題目鏈接
決議：
給定以前以后兩個指標，如果兩個指標對應的值是相等的，則取對應下標的較小值(貪心思想)
需要注意的是連續一串的相同字符，在這里我們需要注意兩個指標的位置，即前面的指標不能挪到已經洗掉的元素上面
又因為后面的指標總是往后走，即當兩個指標位置的字符不相等是，前面的指標直接轉移到后面的指標處
int minCost(char * s, int* cost, int costSize){
int count=0;
int prev_sub=0;
int next_sub=1;
while(next_sub<costSize)
{
if(s[prev_sub]==s[next_sub])//相等
{
count+=(cost[prev_sub]>cost[next_sub]?cost[next_sub]:cost[prev_sub]);//洗掉最小的
if(cost[prev_sub]<cost[next_sub])//洗掉的是前面的
{
prev_sub=next_sub;//防止到達中間已被洗掉字符
next_sub++;
}
else//洗掉的是后面的
{
next_sub++;//只更新后面的坐標，防止連續多個字符出現
}
}
else//不想等
{
prev_sub=next_sub;
next_sub++;
}
}
return count;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272319.html
標籤：其他