[Algorithm][贪心][增减字符串匹配][分发饼干][最优除法][跳跃游戏Ⅱ][跳跃游戏]详细讲解

1.增减字符串匹配

1.题目链接

• 增减字符串匹配

2.算法原理详解

• 贪心：
  • 当遇到I：选择当前最小的那个数
  • 当遇到D：选择当前最大的那个数

3.代码实现

vector<int> diStringMatch(string s) 
{
    int left = 0, right = s.size();

    vector<int> ret;
    for(const auto& ch : s)
    {
        if(ch == 'I')
        {
            ret.push_back(left++);
        }
        else
        {
            ret.push_back(right--);
        }
    }
    ret.push_back(left);

    return ret;
}

2.分发饼干

1.题目链接

• 分发饼干

2.算法原理详解

• 预处理：排序
• 贪心：针对当前胃口最小的孩子，挑选饼干
  • 能满足，直接喂
  • 不能满足，直接删掉这个饼干
    

3.代码实现

int findContentChildren(vector<int>& g, vector<int>& s) 
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int ret = 0, n = g.size(), m = s.size();
    for(int i = 0, j = 0; i < n && j < m; i++, j++)
    {
        while(j < m && s[j] < g[i])
        {
            j++;
        }

        if(j < m)
        {
            ret++;
        }
    }

    return ret;
}

3.最优除法

1.题目链接

• 最优除法

2.算法原理详解

• 贪心：除了前两个数以外，其余的数全放在分子上即可
  

3.代码实现

string optimalDivision(vector<int>& nums) 
{
    int n = nums.size();
    if(n == 1)
    {
        return to_string(nums[0]);
    }
    if(n == 2)
    {
        return to_string(nums[0]) + "/" + to_string(nums[1]);
    }

    string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
    for(int i = 2; i < n; i++)
    {
        ret += "/" + to_string(nums[i]);
    }
    ret += ")";

    return ret;
}

4.跳跃游戏 II

1.题目链接

• 跳跃游戏 II

2.算法原理详解

• 贪心：类似层序遍历的过程
  

3.代码实现

int jump(vector<int>& nums) 
{
    int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
    while(left <= right)
    {
        if(maxPos >= n - 1)
        {
            return ret;
        }

		// 遍历当前层，更新下一层最右端点
        for(int i = left; i <= right; i++)
        {
            maxPos = max(maxPos, nums[i] + i);
        }
        left = right + 1;
        right = maxPos;
        ret++;
    }

    return -1; // 跳不到的情况
}

5.跳跃游戏

1.题目链接

• 跳跃游戏

2.算法原理详解

• 贪心：类似层序遍历的过程
  

3.代码实现

bool canJump(vector<int>& nums) 
{
    int left = 0, right = 0, maxPos = 0, n = nums.size();
    while(left <= right)
    {
        if(maxPos >= n - 1)
        {
            return true;
        }

        for(int i = left; i <= right; i++)
        {
            maxPos = max(maxPos, nums[i] + i);
        }
        left = right + 1;
        right = maxPos;
    }

    return false;
}