Codilty [ Lesson 7 | Stacks and Queues ] Fish - JavaScript

質問する
You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.
The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.
Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:
0 represents a fish flowing upstream,
1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:
If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.
For example, consider arrays A and B such that:
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.
Write a function:
function solution(A, B);
that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.
For example, given the arrays shown above, the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [0..1,000,000,000];
each element of array B is an integer that can have one of the following values: 0, 1;
the elements of A are all distinct.
もんだいぶんせき
2つの配列を与えます.
A列には魚の大きさがあり、B列には魚の移動方向があります.
魚たちは自分の方向に泳いで、出会った魚の中で自分より小さい魚を食べて、それから消滅します.これはすべての魚の経過と残りの魚の数を求める問題です.
B列は2種類あり,0は上流,1は下流に流れる.B配列のインデックス値が0より小さい場合、0と1の魚に無条件に遭遇する.その時A列は魚の大きさを見て、もっと小さい魚を除いて、次のインデックスを比較します.
問題を解く
stackの問題を解決する必要がある場合は、stackに何を入れるべきかを設定することが重要です.この問題では,stackに生存する魚のインデックスを比較することによってstackに入れるべきである.また,インデックス値が増加するにつれて,比較魚のインデックスは生存魚よりも大きくなるべきである.大きさにかかわらず下流に流れる魚のインデックスが上流に流れる魚より大きくなれば会う理由がないので、2匹とも生き延びることができます.

スタックは最初に0を加え、比較するインデックスは1で始まります.

B[1]が0(上流への魚)であり、B[0]が1(下流への魚)である場合、A[1]はA[0]に比べてA[1]が大きいとスタックに残った魚は消滅する.

でなければ、既存の魚が大きいか次の魚に遭遇していないため、比較のインデックスが追加されます.

コード#コード#

function solution(A, B) {
    // write your code in JavaScript (Node.js 8.9.4)
    let leng = A.length;
    let stack = [];
    let n = 1

    stack.push(0)
    while(n<leng){
        if(B[n]==0 && B[stack[stack.length-1]]==1){
            if(A[n]>A[stack[stack.length-1]]){
                stack.pop()
            }else{
                n++
            }
        }else{
            stack.push(n);
            n++;
        }
    }

    return stack.length
}

最終結果

ソース
https://app.codility.com/programmers/lessons/7-stacks_and_queues/