高校网站建设的优势和不足,软件开发工具的基础,南宁网站制作,源码网站取名文章目录 2798.满足目标工作时长的员工数目完整版 2799.统计完全子数组的数目#xff08;滑动窗口#xff09;思路完整版 2800.包含三个字符的最短字符串#xff08;复用思路与三元问题思想#xff09;思路复用减少字符串长度的思路为什么一次性操作两个字符串 完整版进一步… 文章目录 2798.满足目标工作时长的员工数目完整版 2799.统计完全子数组的数目滑动窗口思路完整版 2800.包含三个字符的最短字符串复用思路与三元问题思想思路复用减少字符串长度的思路为什么一次性操作两个字符串 完整版进一步理解”三元问题一次只操作两个字符串“复用逻辑 2798.满足目标工作时长的员工数目
公司里共有 n 名员工按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。
公司要求每位员工工作 至少 target 小时。
给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。
请你用整数表示并返回工作至少 target 小时的员工数。
示例 1
输入hours [0,1,2,3,4], target 2
输出3
解释公司要求每位员工工作至少 2 小时。
- 员工 0 工作 0 小时不满足要求。
- 员工 1 工作 1 小时不满足要求。
- 员工 2 工作 2 小时满足要求。
- 员工 3 工作 3 小时满足要求。
- 员工 4 工作 4 小时满足要求。
共有 3 位满足要求的员工。示例 2
输入hours [5,1,4,2,2], target 6
输出0
解释公司要求每位员工工作至少 6 小时。
共有 0 位满足要求的员工。提示
1 n hours.length 500 hours[i], target 105
完整版
简单模拟题计数即可
class Solution {
public:int numberOfEmployeesWhoMetTarget(vectorint hours, int target) {int count 0;for(int i0; ihours.size(); i) {if(hours[i] target)count;}return count;}
};2799.统计完全子数组的数目滑动窗口
给你一个由 正 整数组成的数组 nums 。
如果数组中的某个子数组满足下述条件则称之为 完全子数组
子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
示例 1
输入nums [1,3,1,2,2]
输出4
解释完全子数组有[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。示例 2
输入nums [5,5,5,5]
输出10
解释数组仅由整数 5 组成所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。提示
1 nums.length 10001 nums[i] 2000
思路
首先我们需要知道有多少种不同的元素然后使用滑动窗口的方式一直扩大右边界直到窗口内的元素种类与原数组相同此时缩小左边界每次缩小左边界都可以对答案进行累加因为滑动窗口内的子数组都是满足条件的。
注意我们为了统计所有满足条件的子数组个数滑动窗口的left左移需要同时统计map里面元素的个数。
完整版
class Solution {
public:int countCompleteSubarrays(vectorint nums) {int nnums.size();unordered_mapint,intcount;unordered_setintuniqueNums;//先得到所有元素的种类数目for(int num:nums){uniqueNums.insert(num);//uset插入元素只能用insert//count[num];count必须在窗口内部更新}int result0;int left0;for(int i0;inums.size();i){count[nums[i]];//nums[i]累积数目//元素种类相同缩小左边界while(count.size()uniqueNums.size()){resultnums.size()-1-i1;//包含所有的子数组情况count[nums[left]]--;if(count[nums[left]]0){count.erase(nums[left]);}left;}//右边界i包含在for循环里面了}return result;}
};2800.包含三个字符的最短字符串复用思路与三元问题思想
给你三个字符串 a b 和 c 你的任务是找到长度 最短 的字符串且这三个字符串都是它的 子字符串 。
如果有多个这样的字符串请你返回 字典序最小 的一个。
请你返回满足题目要求的字符串。
注意
两个长度相同的字符串 a 和 b 如果在第一个不相同的字符处a 的字母在字母表中比 b 的字母 靠前 那么字符串 a 比字符串 b 字典序小 。子字符串 是一个字符串中一段连续的字符序列。
示例 1
输入a abc, b bca, c aaa
输出aaabca
解释字符串 aaabca 包含所有三个字符串a ans[2...4] b ans[3..5] c ans[0..2] 。结果字符串的长度至少为 6 且aaabca 是字典序最小的一个。示例 2
输入a ab, b ba, c aba
输出aba
解释字符串 aba 包含所有三个字符串a ans[0..1] b ans[1..2] c ans[0..2] 。由于 c 的长度为 3 结果字符串的长度至少为 3 。aba 是字典序最小的一个。提示
1 a.length, b.length, c.length 100a b c 只包含小写英文字母。
思路
本题的思路是枚举abc三个字符串所有的拼接情况一边枚举一边进行字母的”复用“
我们的目的是找到一个最短的字符串t它既包含了a也包含了b。为了得到最短字符串需要使用尽可能少的b的字符。
复用减少字符串长度的思路
复用这一步的核心思想就是如果a和b有重叠也就是可以复用的部分那么这个重叠部分肯定出现在a的末尾和b的开头。因此对于字符串b我们可以选择倒着拼接尝试找到这个b开头和a的重叠部分以减少最终生成的字符串t的长度。
如果我们正着拼接即从b的开头开始那么这个重叠部分可能无法有效复用。例如如果a“abc”b“bcd”那么正着拼接的结果可能是abc不使用b的任何字符而实际上我们可以通过使用b的一个字符得到更短的结果abcd。所以我们选择从b的末尾开始倒着拼接检查倒着拼接从不使用b的任何字符到使用b的所有字符这个范围内能不能通过复用b开头和a末尾重叠的部分来使得原字符串包含b。
为什么一次性操作两个字符串
为什么只能一次性合并两个字符串而不是一口气把三个字符串全处理完
这是因为我们需要处理的问题是一个三元问题有三个字符串需要合并。当我们一次处理两个字符串时我们可以将问题简化为两个二元问题这使得问题更容易处理。一次处理两个字符串我们可以找到一个字符串它包含了这两个字符串然后我们再用这个字符串和第三个字符串进行合并这样问题就被简化了。
可以在代码中进行进一步的理解。
完整版
class Solution {
public:string minimumString(string a, string b, string c) {// 创建一个 vector 来存储所有可能的字符串组合vectorstring combinations;// 生成所有可能的字符串组合combinations.push_back(combine(a, b, c));combinations.push_back(combine(a, c, b));combinations.push_back(combine(b, a, c));combinations.push_back(combine(b, c, a));combinations.push_back(combine(c, a, b));combinations.push_back(combine(c, b, a));// 对字符串组合进行排序首先比较长度如果长度相同则按字典序排序sort(combinations.begin(), combinations.end(), [](string s1, string s2) {if (s1.size() s2.size()) return s1 s2;return s1.size() s2.size();});// 返回最短的字符串组合return combinations.front();}// 生成一个既包含 a 又包含 b 的字符串然后将这个字符串和 c 组合生成一个既包含 a, b, c 的字符串string combine(string a, string b, string c) {return combine2(combine2(a, b), c);}// 生成一个既包含 a 又包含 b 的字符串string combine2(string a, string b) {// 从使用 b 的所有字符开始逐步减少使用的字符数量for (int i 0; i b.size(); i) {// 拼接 a 和 b 的后缀生成一个新的字符串string t a b.substr(b.size() - i);// 如果这个新的字符串包含 b则它一定也包含 a所以返回这个字符串if (t.find(b) ! string::npos) return t; }// 如果 a 和 b 完全不重叠则返回 a 和 b 的拼接return ; }
};
进一步理解”三元问题一次只操作两个字符串“
combine2函数的作用是生成一个同时包含两个输入字符串a和b的最小字符串。combine函数则是用于生成同时包含a、b和c三个输入字符串的最小字符串。为了实现这个目标我们需要两次调用combine2函数先将a和b合并然后将合并结果与c进行合并。为了避免代码冗余我们将combine2的功能单独作为一个函数实现。
如果将combine1和combine2两个函数合并也就是一次性处理三个字符串会导致代码重复。比如需要写两次类似的循环来分别处理三个字符串的组合这会使代码变得复杂且难以维护。另一方面通过将combine2函数单独实现我们可以更清晰地表达出代码的逻辑并使得代码更易于阅读和理解。
比如如果真的要一次性处理三个字符串我们只能这么写
string combine(string a, string b, string c ) {// 内部函数用于合并两个字符串auto merge [](string s1, string s2) {for (int i 0; i s2.size(); i) {string t s1 s2.substr(s2.size() - i);if (t.find(s2) ! string::npos) return t; }return ; };// 首先合并a和bstring ab merge(a, b);// 如果c为空直接返回abif (c ) return ab;// 否则继续合并ab和creturn merge(ab, c);
}在这个版本中使用了一个Lambda表达式来处理两个字符串的合并然后根据 c 是否为空来判断是否需要进一步合并。但是这个版本的代码显然更复杂因为我们需要在函数内部再定义一个函数并且引入了一个新的条件判断。所以从代码的清晰性和可维护性角度来说原始的设计将 combine2 函数单独分出来更好。
复用逻辑
复用部分的代码 // 生成一个既包含 a 又包含 b 的字符串string combine2(string a, string b) {// 从使用 b 的所有字符开始逐步减少使用的字符数量for (int i 0; i b.size(); i) {// 拼接 a 和 b 的后缀生成一个新的字符串string t a b.substr(b.size() - i);// 如果这个新的字符串包含 b则它一定也包含 a所以返回这个字符串// 如果 a 和 b 完全不重叠则返回 a 和 b 的拼接if (t.find(b) ! string::npos) return t; }//随意返回一个数值即可return ; }这段复用逻辑实际上是在判断从不包含b任何字符到包含b所有字符这个范围内b开头的元素能不能和a末尾的元素实现复用。一旦能够复用在倒着拼接的新字符串t里出现了完整的b那么就可以直接返回t。
例子a“abbc” b“bb”那么最开始string t a b.substr(b.size() - i);也就是tab.substr(2)实际上此时b.substr(2)是空的也就是最开始是在判断a里面是不是本来就包含了b。
