2023-06-16：給你一份工作時間表 hours，上面記錄著某一位員工每天的工作小時數(shù)。 我
2023-06-16：給你一份工作時間表 hours，上面記錄著某一位員工每天的工作小時數(shù)。
我們認為當員工一天中的工作小時數(shù)大于 8 小時的時候，那么這一天就是「勞累的一天」。
所謂「表現(xiàn)良好的時間段」，意味在這段時間內(nèi)，「勞累的天數(shù)」是嚴格 大于「不勞累的天數(shù)」。
請你返回「表現(xiàn)良好時間段」的最大長度。
輸入：hours = [9,9,6,0,6,6,9]。
輸出：3。
答案2023-06-16：
大體步驟如下：
1.首先，定義函數(shù)?func longestWPI1(hours []int) int?和?func longestWPI2(hours []int) int，參數(shù)分別為一個 int 型切片 hours，返回值為 int 類型。
2.在?func longestWPI1(hours []int) int?中，聲明一個 map 類型的變量 m，用于保存前綴和 sum 出現(xiàn)的最早位置。新建 map 時，將 0 值和 -1 下標添加到 m 中，表示前綴和為 0 的位置為 -1。
3.在?func longestWPI2(hours []int) int?中，聲明一個長度為 2n+1 的切片 early，用于保存前綴和 sum 第一次出現(xiàn)的位置。新建 early 時，將所有下標初始化為 -2，表示都未被訪問過。將 -1 的值保存至 early[n]，表示前綴和為 0 的位置為 -1。
4.在雙函數(shù)中，都使用變量 ans 和 sum 進行計算，ans 表示最大的表現(xiàn)良好時間段的長度，sum 表示前綴和。
5.遍歷 hours，對于每個元素 hour，若 hour>8，則 sum 加一；否則，sum 減一。
6.如果 sum 大于 0，則表明從第一個時間點到當前時間點都是表現(xiàn)良好時間段，因此更新 ans 為當前時間點 i+1。
7.如果 sum ≤ 0，則表明從第一個時間點到當前時間點出現(xiàn)了不勞累的時間段，需要判斷是否有更長的表現(xiàn)良好時間段。
8.在?func longestWPI1?中，如果 m 中 sum-1 的值存在，則表明從之前的那個位置到當前位置，這段時間內(nèi)有多于一個勞累的時間段與不勞累的時間段，則計算這個時間段長度，并與現(xiàn)有 ans 取最大值。若 m 中不存在，則將當前位置的值保存至 m[sum]。
9.在?func longestWPI2?中，計算出 sum-1+n 的值（n 表示 hours 數(shù)組長度的兩倍，n<<1），并判斷這個值在 early 數(shù)組中是否被保存過，如果有，則表明從之前的那個位置到當前位置，這段時間內(nèi)有多于一個勞累的時間段與不勞累的時間段，則計算這個時間段長度，并與現(xiàn)有 ans 取最大值。若該值未被訪問過，則將當前位置的值保存至 early[sum+n]。
10.遍歷完 hours 后，返回 ans 值即可。
時間復(fù)雜度：
雙函數(shù)中的 for 循環(huán)都只會遍歷一次 hours 數(shù)組，所以時間復(fù)雜度為 O(n)。
空間復(fù)雜度：
在?func longestWPI1?中，使用了一個 map 類型的變量和三個 int 類型的變量，其中 map 的最大空間需求為 hours 數(shù)組長度，所以空間復(fù)雜度為 O(n)。
在?func longestWPI2?中，使用了一個長度為 2n+1 的 int 類型切片和三個 int 類型的變量，其中切片的最大空間需求為 2n+1，所以空間復(fù)雜度為 O(n)。
綜上，兩個函數(shù)的空間復(fù)雜度都為 O(n)。
go完整代碼如下：
package?main
import?"fmt"
func?longestWPI1(hours?[]int)?int?{
????//?key?:?某個前綴和
????//?value?:?這個前綴和最早出現(xiàn)的位置
????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++完整代碼如下：
using?namespace?std;
int?longestWPI1(vector<int>&?hours)?{
????//?key?:?某個前綴和
????//?value?:?這個前綴和最早出現(xiàn)的位置
????unordered_map<int,?int>?mp;
????//?0這個前綴和，最早出現(xiàn)在哪？一個數(shù)也沒有的時候
????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最早出現(xiàn)在哪?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語言完整代碼如下：
int?longestWPI1(int*?hours,?int?hoursSize)?{
????//?key?:?某個前綴和
????//?value?:?這個前綴和最早出現(xiàn)的位置
????int*?mp?=?(int*)malloc(sizeof(int)?*?20002);
????memset(mp,?-1,?sizeof(int)?*?20002);
????//?0這個前綴和，最早出現(xiàn)在哪？一個數(shù)也沒有的時候
????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最早出現(xiàn)在哪?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;
}
//?數(shù)組替代哈希表
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;
}
