鱼肉练习

Question

试图解决 codility 上的这个挑战 fish 挑战 我无法理解为什么我的代码没有通过所有测试。

function solution($A, $B) {
  // write your code in PHP7.0
  $stack =[];

  foreach($A as $key =>$value) {
    if(empty($stack)){
      array_push($stack,$key);
    }
    else if($B[count($stack)-1] == 1 && $B[$key]==0 )
    {
      if($value > $A[count($stack)-1])
      {
        array_pop($stack);
        array_push($stack,$key);
      }
    }
    else array_push($stack,$key);
  }
  return count($stack);
}

Answer 1

您的代码有两个问题。

1. 代码未正确引用堆栈上的项目。使用

   $B[$stack[count($stack)-1]]

   代替

   $B[count($stack)-1]

   。使用

   $A[$stack[count($stack)-1]]

   而不是

   $A[count($stack)-1]

   。

2. 逆流而上的鱼必须与顺流而下的每一条鱼战斗，而不仅仅是它们遇到的第一条鱼。

以下是成功的解决方案：

function solution($A, $B) {
  // write your code in PHP7.0
  $stack = [];
  $key = 0;
  while($key < count($A)) {
    if(empty($stack)){
      array_push($stack,$key);
      $key++;
    }
    else if($B[$stack[count($stack)-1]] == 1 && $B[$key] == 0){
      if($A[$key] > $A[$stack[count($stack)-1]])
      {
        // fish going upstream eats fish going downstream
        array_pop($stack);
      } else {
        // fish going downstream eats fish going upstream
        $key++;
      }
    }
    else {
      array_push($stack,$key);
      $key++;
    }
  }
  return count($stack);
}

Answer 2

得分 100% 的 Python 解决方案

def solution(A, B):
    ds = []
    up = 0

    for i in range(len(A)):
        if B[i] == 1:
            ds.append(A[i])
        if B[i] == 0:
            if len(ds) == 0:
                up += 1
                continue
            while (len(ds) > 0):
                ele = ds.pop()
                if ele < A[i]:
                    continue
                else:
                    ds.append(ele)
                    break
            if len(ds) == 0:
                up += 1
    return len(ds) + up

Answer 3

100% 快速解决方案：

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    var stack = [(size: Int, direction: Int)]()
outer:
    for i in 0..<A.count {
        let currentFish = (size: A[i], direction: B[i])

        guard !stack.isEmpty, currentFish.direction == 0, stack.last?.direction == 1 else {
            stack.append(currentFish)
            continue
        }

        while stack.last?.direction == 1 {
            if stack.last!.size > currentFish.size {
                continue outer
            } else {
                stack.popLast()
            }
        }
        stack.append(currentFish)
    }
    return stack.count
}

Answer 4

试试这个：

  function solution($A, $B) {
  // write your code in PHP7.0
  $stack =[];

  foreach($A as $key =>$value) {
    if(empty($stack)){
      array_push($stack,$key);
    }
    else if($B[count($stack)-1] == 1 && $B[$key]==0 )
    {
        while(true) {
          if($value > $A[count($stack)-1] && !empty($stack) && $B[count($stack)-1] == 1)
          {
            array_pop($stack);
          }
          else break;
        }
      array_push($stack,$key);
    }
    else array_push($stack,$key);
  }
  return count($stack);

}