題目內容
題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/
題意分析
又是一個有故事的題目,最討厭了,不要管魚的故事的話,大概就是有一個循序數列會從0~N-1這樣子,例如[1,2,3,4,5],但是不會照著順序排列,而是會打散著的排列,如[4,3,2,1,5],然後有另一個陣列B,會指定該數字是往上還是往下,如[0,1,0,0,0],接著往下的若是遇到往上的,就比大小,刪掉較小的數字。
然後回傳最後剩下的數字的數量
解題紀錄
這是我第一次的解題紀錄
function solution(A, B) {
var point = 0
while(point < B.length){
var currnet_direction = B[point]
if(currnet_direction == 0){//往上
while(point > 0 && A[point-1] < A[point]){
//吃掉目標
A.splice(point,1)
B.splice(point,1)
}
//換目標
point++
}else{//往下
while(point < B.length-1 && A[point+1] < A[point]){
//吃掉目標
A.splice(point+1,1)
B.splice(point+1,1)
}
//換目標
point++
}
}
return A.length
}
只拿了12分,慘不忍睹,應該有思考邏輯上的錯誤。
仔細想一下這一題,我覺得應該會是2N左右的複雜度,就是往上遍歷一次、往下遍歷一次。往下遍歷時,選擇方向為下的,且之後的數字的方向為上的,把該吃掉的吃掉。接著再從下往上一次,選擇方向為上的,且之前的數字的方向為下的,把該吃掉的吃掉,應該就會試剩下的了。
下面為嘗試的實作程式碼
function solution(A, B) {
var alive_A = []
var alive_B = []
// 往下
while(A.length > 0){
var target = A.shift()
var target_direction = B.shift()
while(target_direction == 1 && B[0] == 0 && target > A[0]){
A.shift()
B.shift()
}
alive_A.push(target)
alive_B.push(target_direction)
}
A = alive_A
B = alive_B
alive_A = []
alive_B = []
//往上
while(A.length > 0){
var target = A.pop()
var target_direction = B.pop()
while(target_direction == 0 && B[B.length-1] == 1 && target > A[A.length-1]){
A.pop()
B.pop()
}
alive_A.push(target)
alive_B.push(target_direction)
}
return alive_A.length
}
25%,慘不忍睹+1。
![](https://i0.wp.com/claire-chang.com/wp-content/uploads/2023/05/2023-05-09_125306.jpg?resize=532%2C604&ssl=1)
我發現問題是他們往上或往下可能不會只有兩次,而是會不停地變換方向,所以應該會需要把這樣的程式碼抽出來,然後使用迴圈或遞迴的去呼叫。但是比較慘的是,下面的效能測試其實是超時的,若是再透過遞迴或者迴圈,整個效能應該會更差。
觀察之後,因為我是整個陣列去掃,而事實上,他們往上或往下的範圍不會是整個陣列,而會是遇到與自己方向不同的範圍。所以我覺得應該不會是完整的掃過兩次迴圈,而是會有兩層的迴圈,然後根據現在的方向,掃到以自己方向為準最多可吃掉的位置做停止,在構想上應該比較類似我第一次的做法。
function solution(A, B) {
var point = 0
var finish = 0
while(A.length > 0){
if(point >= A.length ){
point = A.length-1
}
//console.log("main", A, B, point)
if(point == 0 && B[point] == 0){
finish ++
A.shift()
B.shift()
}else if(point == A.length-1 && B[A.length-1] == 1){
finish ++
A.pop()
B.pop()
}else{
var target_direction = B[point] == 0 ? -1:1
while(A[point] > A[point+target_direction] && B[point] != B[point+target_direction]){
A.splice(point+target_direction,1)
B.splice(point+target_direction,1)
}
point = point+target_direction
}
}
return finish
}
邏輯正確了,但是效能不佳…要來優化了!
![](https://i0.wp.com/claire-chang.com/wp-content/uploads/2023/05/2023-05-09_151637.jpg?resize=530%2C775&ssl=1)
上面的作法會耗時間是因為下面的原因
- 使用了 while 迴圈,導致較長的運行時間。while 迴圈對於每條魚的比較都需要遍歷數組中的某些元素。相比之下,前面的實現使用了 for 迴圈,因此在處理每條魚時,它只需要對數組中的一個元素進行操作。
- 這個實現使用了多次數組操作,例如 splice()、shift() 和 pop()。這些操作可能會導致重新分配和複製整個數組,導致更長的運行時間。若只使用了一個堆疊紀錄往上的魚,原本的全部都是往下的,操作次數會少得多。
為了解決這個問題,我們可以使用一個堆疊,它用於記錄下游游動的魚,這些魚還沒有被吃掉。從頭到尾遍歷所有魚,並將所有向上游動的魚推入堆疊。如果遇到向下游動的魚,則將其與堆疊中的魚進行比較。如果堆疊中的魚較小,則將其彈出,並繼續與新的堆疊頂部進行比較,直到它遇到較大的魚,或者堆疊為空。
在這個算法中,堆疊中的魚保證向下游動,因此它們是可以被吃掉的魚。當向上游動的魚遇到堆疊頂部的魚時,它們的大小也被比較。如果它們相等,它們都可以保持存活,因為它們不會相互吃掉。如果向上游動的魚比堆疊頂部的魚大,則堆疊中的魚會被吃掉,否則向上游動的魚會被堆疊頂部的魚吃掉。在此過程中,我們不斷更新堆疊的內容,以便在下一輪比較中使用。
最後,堆疊中剩下的所有魚都可以保持存活,因為它們沒有遇到向下游動的魚,或者在它們前面的向下游動的魚都比它們大。
function solution(A, B) {
var alive = 0
var downstream = []
for (var i = 0; i < A.length; i++) {
if (B[i] == 1) {
downstream.push(A[i])
} else {
//開始吃掉之前的往下的魚直到自己被吃掉
while (downstream.length > 0 && downstream[downstream.length - 1] < A[i]) {
downstream.pop()
}
if(downstream.length == 0){
//過關
alive++
}
}
}
return alive + downstream.length
}
https://app.codility.com/demo/results/trainingHMNQVG-XRN/
![](https://i0.wp.com/claire-chang.com/wp-content/uploads/2023/05/2023-05-09_171507.jpg?resize=541%2C635&ssl=1)