2023-06-16:给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间
2023/6/17 1:22:08
本文主要是介绍2023-06-16:给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2023-06-16:给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」,意味在这段时间内,「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
输入:hours = [9,9,6,0,6,6,9]。
输出:3。
答案2023-06-16:
大体步骤如下:
1.首先,定义函数 func longestWPI1(hours []int) int
和 func longestWPI2(hours []int) int
,参数分别为一个 int 型切片 hours,返回值为 int 类型。
2.在 func longestWPI1(hours []int) int
中,声明一个 map 类型的变量 m,用于保存前缀和 sum 出现的最早位置。新建 map 时,将 0 值和 -1 下标添加到 m 中,表示前缀和为 0 的位置为 -1。
3.在 func longestWPI2(hours []int) int
中,声明一个长度为 2n+1 的切片 early,用于保存前缀和 sum 第一次出现的位置。新建 early 时,将所有下标初始化为 -2,表示都未被访问过。将 -1 的值保存至 early[n],表示前缀和为 0 的位置为 -1。
4.在双函数中,都使用变量 ans 和 sum 进行计算,ans 表示最大的表现良好时间段的长度,sum 表示前缀和。
5.遍历 hours,对于每个元素 hour,若 hour>8,则 sum 加一;否则,sum 减一。
6.如果 sum 大于 0,则表明从第一个时间点到当前时间点都是表现良好时间段,因此更新 ans 为当前时间点 i+1。
7.如果 sum ≤ 0,则表明从第一个时间点到当前时间点出现了不劳累的时间段,需要判断是否有更长的表现良好时间段。
8.在 func longestWPI1
中,如果 m 中 sum-1 的值存在,则表明从之前的那个位置到当前位置,这段时间内有多于一个劳累的时间段与不劳累的时间段,则计算这个时间段长度,并与现有 ans 取最大值。若 m 中不存在,则将当前位置的值保存至 m[sum]。
9.在 func longestWPI2
中,计算出 sum-1+n 的值(n 表示 hours 数组长度的两倍,n<<1),并判断这个值在 early 数组中是否被保存过,如果有,则表明从之前的那个位置到当前位置,这段时间内有多于一个劳累的时间段与不劳累的时间段,则计算这个时间段长度,并与现有 ans 取最大值。若该值未被访问过,则将当前位置的值保存至 early[sum+n]。
10.遍历完 hours 后,返回 ans 值即可。
时间复杂度:
双函数中的 for 循环都只会遍历一次 hours 数组,所以时间复杂度为 O(n)。
空间复杂度:
在 func longestWPI1
中,使用了一个 map 类型的变量和三个 int 类型的变量,其中 map 的最大空间需求为 hours 数组长度,所以空间复杂度为 O(n)。
在 func longestWPI2
中,使用了一个长度为 2n+1 的 int 类型切片和三个 int 类型的变量,其中切片的最大空间需求为 2n+1,所以空间复杂度为 O(n)。
综上,两个函数的空间复杂度都为 O(n)。
go完整代码如下:
package main import "fmt" func longestWPI1(hours []int) int { // key : 某个前缀和 // value : 这个前缀和最早出现的位置 var m = make(map[int]int) m[0] = -1 var ans, sum int for i, hour := range hours { if hour > 8 { sum++ } else { sum-- } if sum > 0 { ans = i + 1 } else { if j, ok := m[sum-1]; ok { ans = Max(ans, i-j) } } if _, ok := m[sum]; !ok { m[sum] = i } } return ans } func longestWPI2(hours []int) int { n := len(hours) early := make([]int, (n<<1)+1) for i := range early { early[i] = -2 } early[0+n] = -1 ans, sum := 0, 0 for i, hour := range hours { if hour > 8 { sum++ } else { sum-- } if sum > 1 { ans = i + 1 } else { index := sum - 1 + n if index >= 0 && early[index] != -2 { ans = Max(ans, i-early[index]) } } if early[sum+n] == -2 { early[sum+n] = i } } return ans } func Max(x, y int) int { if x > y { return x } return y } func main() { hours := []int{9, 9, 6, 0, 6, 6, 9} ans1 := longestWPI1(hours) ans2 := longestWPI2(hours) fmt.Println("ans1:", ans1) fmt.Println("ans2:", ans2) }
rust完整代码如下:
fn longest_wpi1(hours: Vec<i32>) -> i32 { let mut map = std::collections::HashMap::<i32, i32>::new(); map.insert(0, -1); let mut ans = 0; let mut sum = 0; for (i, hour) in hours.iter().enumerate() { sum += if *hour > 8 { 1 } else { -1 }; if sum > 0 { ans = i as i32 + 1; } else { if let Some(j) = map.get(&(sum - 1)) { ans = ans.max(i as i32 - j); } } map.entry(sum).or_insert(i as i32); } ans } fn longest_wpi2(hours: Vec<i32>) -> i32 { let n = hours.len(); let mut early = vec![-2; (n << 1) + 1]; early[n] = -1; let mut ans = 0; let mut sum = 0; let mut i = 0; while i < n { sum += if hours[i] > 8 { 1 } else { -1 }; if sum > 1 { ans = i as i32 + 1; } else { let index = sum - 1 + n as i32; if index >= 0 && early[index as usize] != -2 { ans = ans.max(i as i32 - early[index as usize]) } } if early[(sum + n as i32) as usize] == -2 { early[(sum + n as i32) as usize] = i as i32; } i += 1; } ans } fn main() { let hours = vec![9, 9, 6, 0, 6, 6, 9]; let ans1 = longest_wpi1(hours.clone()); let ans2 = longest_wpi2(hours); println!("ans1: {}", ans1); println!("ans2: {}", ans2); }
c++完整代码如下:
#include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; int longestWPI1(vector<int>& hours) { // key : 某个前缀和 // value : 这个前缀和最早出现的位置 unordered_map<int, int> mp; // 0这个前缀和,最早出现在哪?一个数也没有的时候 mp[0] = -1; int ans = 0; int sum = 0; for (int i = 0; i < hours.size(); i++) { sum += hours[i] > 8 ? 1 : -1; if (sum > 0) { // 0...i i+1 ans = i + 1; } else { // sum = -4 // -5最早出现在哪 j j+1...i if (mp.count(sum - 1)) { ans = max(ans, i - mp[sum - 1]); } } if (!mp.count(sum)) { mp[sum] = i; } } return ans; } int longestWPI2(vector<int>& hours) { int n = hours.size(); vector<int> early((n << 1) + 1, -2); early[0 + n] = -1; int ans = 0; int sum = 0; for (int i = 0; i < hours.size(); i++) { sum += hours[i] > 8 ? 1 : -1; if (sum > 1) { ans = i + 1; } else { if (sum - 1 + n >= 0 && early[sum - 1 + n] != -2) { ans = max(ans, i - early[sum - 1 + n]); } } if (early[sum + n] == -2) { early[sum + n] = i; } } return ans; } int main() { vector<int> hours = { 9, 9, 6, 0, 6, 6, 9 }; int ans1 = longestWPI1(hours); int ans2 = longestWPI2(hours); cout << "ans1: " << ans1 << endl; cout << "ans2: " << ans2 << endl; return 0; }
c语言完整代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> int longestWPI1(int* hours, int hoursSize) { // key : 某个前缀和 // value : 这个前缀和最早出现的位置 int* mp = (int*)malloc(sizeof(int) * 20002); memset(mp, -1, sizeof(int) * 20002); // 0这个前缀和,最早出现在哪?一个数也没有的时候 mp[10000] = -1; int ans = 0; int sum = 0; for (int i = 0; i < hoursSize; i++) { sum += hours[i] > 8 ? 1 : -1; if (sum > 0) { // 0...i i+1 ans = i + 1; } else { // sum = -4 // -5最早出现在哪 j j+1...i if (mp[sum - 1 + 10000] != -1) { ans = ans > (i - mp[sum - 1 + 10000]) ? ans : (i - mp[sum - 1 + 10000]); } } if (mp[sum + 10000] == -1) { mp[sum + 10000] = i; } } free(mp); return ans; } // 数组替代哈希表 int longestWPI2(int* hours, int hoursSize) { int n = hoursSize; int* early = (int*)malloc(sizeof(int) * (n << 1 | 1)); for (int i = 0; i < (n << 1 | 1); i++) { early[i] = -2; } early[0 + n] = -1; int ans = 0; int sum = 0; for (int i = 0; i < hoursSize; i++) { sum += hours[i] > 8 ? 1 : -1; if (sum > 1) { ans = i + 1; } else { if (sum - 1 + n >= 0 && early[sum - 1 + n] != -2) { ans = ans > (i - early[sum - 1 + n]) ? ans : (i - early[sum - 1 + n]); } } if (early[sum + n] == -2) { early[sum + n] = i; } } free(early); return ans; } int main() { int hours[7] = { 9, 9, 6, 0, 6, 6, 9 }; int ans1 = longestWPI1(hours, 7); int ans2 = longestWPI2(hours, 7); printf("ans1: %d\n", ans1); printf("ans2: %d\n", ans2); return 0; }
这篇关于2023-06-16:给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行