贪心算法的设计与分析

发布于 2023-09-19  310 次阅读


内容纲要

1、专题名称

贪心算法的设计与分析

2、实践内容

2.1 实践内容 1

(1)题目要求

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

  • 1 <= nums.length <= 10^4^
  • 0 <= nums[i] <= 10^5^
(2)算法设计

这题贪心算法的核心是尽可能多到达远的地方,因此可以遍历一次数组,计算经过每格后可到达的最远的地方,并判断目前所在的格子是否为可到达的最远地方,若是最远地方,判断是否为最终格

若为,则返回true

若为,则返回false

(3)代码实现
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxfar = 0;
        bool yes = true;
        for(int i = 0 ; i < nums.size() ; i++ )
        {
            maxfar = max(maxfar,(nums[i]+i));
            if(maxfar == i && i != nums.size()-1)
            {
                yes = false;
                break;
            }
        }
        return yes;
    }
};
(4)算法分析

时间复杂度:O(n)

空间复杂度:O(1)

算法优点:实现简单。

缺点:稍微难想一点。

2.2 实践内容 2

(1)题目要求

平衡字符串 中,'L''R' 字符的数量是相同的。

给你一个平衡字符串 s,请你将它分割成尽可能多的子字符串,并满足:

  • 每个子字符串都是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量

示例 1:

输入:s = "RLRRLLRLRL"
输出:4
解释:s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ,每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2:

输入:s = "RLRRRLLRLL"
输出:2
解释:s 可以分割为 "RL"、"RRRLLRLL",每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意,s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3:

输入:s = "LLLLRRRR"
输出:1
解释:s 只能保持原样 "LLLLRRRR" 。

提示:

  • 2 <= s.length <= 1000
  • s[i] = 'L' 或 'R'
  • s 是一个 平衡 字符串
(2)算法设计

此题可以遍历一次字符数组,将问题转化为判断遍历完某个字符后的LR是否相等,若相等,则可以组成一个平衡字符串,累加记录即可。

(3)代码实现
class Solution {
public:
    int balancedStringSplit(string s) {
        int sum = 0,left = 0,right = 0;
        for(int i = 0 ; i < s.size() ; i++ )
        {
            if(s[i] == 'R')
            right ++;
            else
            left ++;
            if(left == right)
            sum ++;
        }
        return sum;
    }
};
(4)算法分析

时间复杂度:O(n)

空间复杂度:O(1)

算法优点:空间复杂度低,时间复杂度低。

缺点:稍微难想一点。

2.3 实践内容 3

(1)题目要求
  • n 个人被分成数量未知的组。每个人都被标记为一个从 0n - 1唯一ID

    给定一个整数数组 groupSizes ,其中 groupSizes[i] 是第 i 个人所在的组的大小。例如,如果 groupSizes[1] = 3 ,则第 1 个人必须位于大小为 3 的组中。

    返回一个组列表,使每个人 i 都在一个大小为 groupSizes[i] 的组中。

    每个人应该 恰好只 出现在 一个组 中,并且每个人必须在一个组中。如果有多个答案,返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。

    示例 1:

    输入:groupSizes = [3,3,3,3,3,1,3]
    输出:[[5],[0,1,2],[3,4,6]]
    解释:
    第一组是 [5],大小为 1,groupSizes[5] = 1。
    第二组是 [0,1,2],大小为 3,groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
    第三组是 [3,4,6],大小为 3,groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。 
    其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。

    示例 2:

    输入:groupSizes = [2,1,3,3,3,2]
    输出:[[1],[0,5],[2,3,4]]

    提示:

    • groupSizes.length == n
    • 1 <= n <= 500
    • 1 <= groupSizes[i] <= n
(2)算法设计

使用哈希表记录每个大小的值里的i个人,遍历传入数组,当某个大小值里的人数等于该值时,打包到输出数组,以此遍历。

(3)代码实现
class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int,vector<int>> groups;
        int n = groupSizes.size();
        for(int i = 0 ; i < n ; i++ )
        {
            int size = groupSizes[i];
            groups[size].push_back(i);
        }
        vector<vector<int>> groupList;
        for (auto &[size, people] : groups) {
            int groupCount = people.size() / size;
            for (int i = 0; i < groupCount; i++) {
                vector<int> group;
                int start = i * size;
                for (int j = 0; j < size; j++) {
                    group.push_back(people[start + j]);
                }
                groupList.push_back(group);
            }
        }
        return groupList;
    }
};
(4)算法分析

时间复杂度:O(n)

空间复杂度:O(n)

算法优点:稍微易想。

缺点:要对C++的哈希表有一定的理解。

2.4 实践内容 4

(1)题目要求

给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和最大 的子序列。

与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些(也可能不分离)元素得到。

注意,题目数据保证满足所有约束条件的解决方案是 唯一 的。同时,返回的答案应当按 非递增顺序 排列。

示例 1:

输入:nums = [4,3,10,9,8]
输出:[10,9] 
解释:子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。 

示例 2:

输入:nums = [4,4,7,6,7]
输出:[7,7,6] 
解释:子序列 [7,7] 的和为 14 ,不严格大于剩下的其他元素之和(14 = 4 + 4 + 6)。因此,[7,6,7] 是满足题意的最小子序列。注意,元素按非递增顺序返回。  

示例 3:

输入:nums = [6]
输出:[6]

提示:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100
(2)算法设计

对数组进行递减排序,并对数组进行累加求总和sum,从最大的元素开始,累加求和sums直到符合sums > sum,输出遍历过的数组成的数组。

(3)代码实现
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int sums = accumulate(nums.begin(),nums.end(),0),sum = 0;
        vector<int> res;
        sort(nums.begin(),nums.end(),greater<int>());
        for(int i = 0 ; i < nums.size() ; i++ )
        {
            sum += nums[i];
            res.push_back(nums[i]);
            if(sum > sums/2)
            break;
        }
        return res;
    }
};
(4)算法分析

时间复杂度:O(n)

空间复杂度:O(n)

算法优点:时间复杂度优,且简单易想。

缺点:空间复杂度一般

3、问题与总结

问题:以上题目都可用C++的API更简单地解题,学习这些API用了较长时间。

总结:总体耗时较短,且对C++STL库的使用更加熟练

4、完成情况证明

世界のネズミは彼らが望むものに依存し、彼らは彼ら自身から誰も求めません
最后更新于 2023-09-19