微信能否做门户网站,网站开发入门培训机构,wordpress app模板,银行网站开发技术方案给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候#xff0c;那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」#xff0c;意味在这段时间内#xff0c;「劳累的天数」是严格 大…给你一份工作时间表 hours上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」意味在这段时间内「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1 输入hours [9,9,6,0,6,6,9] 输出3 解释最长的表现良好时间段是 [9,9,6]。
示例 2 输入hours [6,6,6] 输出0
前缀哈希
class Solution {
public:int longestWPI(vectorint hours) {int sum 0, ans 0; unordered_mapint, int group {{0, -1}};for(int i 0;i hours.size();i){sum (hours[i] 8) ? 1 : -1;if(sum 0){ans i 1;}else if(group.find(sum-1) ! group.end()){ans max(ans, i - group[sum - 1]);}if(group.find(sum) group.end()){group[sum] i;}}return ans;}
};这一题前缀哈希并不是空间最优最优空间是使用贪心栈的做法虽然空间复杂度都是O(n)但是实际的空间使用可能高于 O(n)因为当哈希表需要扩展时会预留更多的空间以减少哈希冲突。
sum (hours[i] 8) ? 1 : -1;这题的思想就是将大于8小时的天数记1小于等于8小时的天数记-1。 if(sum 0){ans i 1;}else if(group.find(sum-1) ! group.end()){ans max(ans, i - group[sum - 1]);}“表现良好的时间段”有两种情况一种是当前的sum能在哈希表中匹配到sum - 1时如果是匹配sum的话这个子段是「劳累的天数」等于「不劳累的天数」。第二种情况是当sum大于0的时候这时候说明整个数组都是表现良好的时间段。
if(group.find(sum) group.end()){group[sum] i;
}并且只哈希表中的键只保存第一次出现的位置。
