(B卷,100分)- 数大雁（Java & JS & Python）

题目描述

一群大雁往南飞，给定一个字符串记录地面上的游客听到的大雁叫声，请给出叫声最少由几只大雁发出。

具体的：

1. 大雁发出的完整叫声为”quack“，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个”quack”。
2. 大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
3. 如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。

输入描述

一个字符串，包含大雁quack的叫声。1 <= 字符串长度 <= 1000，字符串中的字符只有’q’, ‘u’, ‘a’, ‘c’, ‘k’。

输出描述

大雁的数量

用例

题目解析

首先看一个例子：

对于标黄的"uack"，我们应该归属于哪一个绿色的"q"呢？

• 如果归属于第一个绿色"q"，那么该例子就至少有两只大雁
• 如果归属于第二个绿色"q"，那么该例子就至少有一只大雁

这里的两个"q"更准确的描述是：

• 第一个"q"是前一次完整叫声中的第一个"q"
• 第二个"q"是前一次完整叫声后的第一个"q"

下面我对这两种理解都做了实现

归属于第一个"q"解法（90%通过率）

此解法虽然看起来和

很像，但是难度却要大于leetcode这道题，原因是

大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。

而leetcode数青蛙

如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

leetcode这题，如果存在不完整或者不按顺序的叫声，则直接返回-1。结束程序。

而本题，则对于不完整或者不按顺序的叫声，只是不予计数，后面还要继续统计。

比如 quaquck

如果按照leetcode数青蛙逻辑来做的话，结果应该返回-1。

而本题逻辑却需要返回1。

leetcode难度小的原因是，不需要考虑剔除不完整或者不按顺序的叫声。

而本题难度大的原因是，需要考虑剔除不完整或者不按顺序的叫声。

我的解题思路是，求出每个叫声quack的区间范围，即一次叫声的：[q索引位置，k索引位置]。

实现是：从左到右遍历叫声字符串，遇到q，则将其索引位置加入缓存中，

遇到u，则判断u出现的次数是否超过了q出现的次数，若是则忽略本次u，否则u次数++

遇到a，则判断a出现的次数是否超过了u出现的次数，若是则忽略本次a，否则a次数++

遇到c，则判断c出现的次数是否超过了a出现的次数，若是则忽略本次c，否则c次数++

遇到k，则判断c次数是否大于等于1，若否，则忽略本次k，否则出队第一个q出现索引和本次k的索引，组合成一个区间范围，然后u–,a–,c–，表示取出了一次叫声。

按照上面逻辑，我们可以剔除掉不完整或者不按顺序的叫声，并且获得每个合法叫声的区间范围。

接下来就是遍历每一个区间，和后面区间比较，看是否有交集，若有，则记录交集数。

最终最大的交集数就是最多大雁数。

下图是用例3：qququaauqccauqkkcauqqkcauuqkcaaukccakkck

各合法叫声区间的交集示意图

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(quacks) {
  let q, u, a, c, k;
  q = [];
  u = 0;
  a = 0;
  c = 0;

  const range = [];

  for (let i = 0; i < quacks.length; i++) {
    switch (quacks[i]) {
      case "q":
        q.push(i);
        break;
      case "u":
        if (u + 1 <= q.length) u++;
        break;
      case "a":
        if (a + 1 <= u) a++;
        break;
      case "c":
        if (c + 1 <= a) c++;
        break;
      case "k":
        if (1 <= c) {
          range.push([q.shift(), i]);
          u--;
          a--;
          c--;
        }
        break;
      default:
        return -1;
    }
  }

  if (!range.length) return -1;

  let max = 1;
  for (let i = 0; i < range.length; i++) {
    let count = 1;
    for (let j = i + 1; j < range.length; j++) {
      if (range[i][1] >= range[j][0]) count++;
    }
    max = Math.max(max, count);
  }

  return max;
}

Java算法源码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String quack = sc.next();
    System.out.println(getResult(quack));
  }

  public static int getResult(String quack) {
    LinkedList<Integer> q = new LinkedList<>();

    int u = 0, a = 0, c = 0;

    ArrayList<Integer[]> ranges = new ArrayList<>();

    for (int i = 0; i < quack.length(); i++) {
      switch (quack.charAt(i)) {
        case 'q':
          q.add(i);
          break;
        case 'u':
          if (u + 1 <= q.size()) u++;
          break;
        case 'a':
          if (a + 1 <= u) a++;
          break;
        case 'c':
          if (c + 1 <= a) c++;
          break;
        case 'k':
          if (c >= 1) {
            ranges.add(new Integer[] {q.removeFirst(), i});
            u--;
            a--;
            c--;
          }
          break;
        default:
          return -1;
      }
    }

    if (ranges.size() == 0) return -1;

    int ans = 1;
    for (int i = 0; i < ranges.size(); i++) {
      int count = 1;
      for (int j = i + 1; j < ranges.size(); j++) {
        if (ranges.get(i)[1] >= ranges.get(j)[0]) {
          count++;
        }
      }
      ans = Math.max(ans, count);
    }

    return ans;
  }
}

Python算法源码

# 输入获取
quacks = input()


# 算法入口
def getResult():
    q = []
    u, a, c = 0, 0, 0

    rans = []

    for i in range(len(quacks)):
        char = quacks[i]

        if char == 'q':
            q.append(i)
        elif char == 'u':
            if u + 1 <= len(q):
                u += 1
        elif char == 'a':
            if a + 1 <= u:
                a += 1
        elif char == 'c':
            if c + 1 <= a:
                c += 1
        elif char == 'k':
            if c >= 1:
                rans.append([q.pop(0), i])
                u -= 1
                a -= 1
                c -= 1
        else:
            return -1

    if len(rans) == 0:
        return -1

    ans = 1
    for i in range(len(rans)):
        count = 1
        for j in range(i + 1, len(rans)):
            if rans[i][1] >= rans[j][0]:
                count += 1

        ans = max(ans, count)

    return ans


# 算法调用
print(getResult())

归属于第二个"q"解法

此解法思路很简单，即假设每只大雁都连续不断的叫，即某只大雁叫完一次后，接着叫

我们以题目自带的用例4为例：

其中一种颜色标记，就是一只大雁的多次叫声，比如黄色标记，就相当于一只大雁叫了三声quack，这三声quack是不交叉的，因此可以认为是同一只大雁叫的。

这里其实有贪心思维的存在，即认为每个大雁都会发出多次叫声，只要存在多次不交叉的叫声，即认为是一只大雁发出的，这样最终就可以得到最少大雁数量。

具体实现时，需要对输入的字符串进行多轮遍历，每轮遍历确认一只大雁，并将该大雁的多次叫声对应的位置标记为used，这样到下一轮遍历时，就不会造成多个大雁使用同一个叫声。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.next()));
  }

  public static int getResult(String s) {
    char[] quacks = s.toCharArray();

    int count = 0;
    while (find(quacks)) {
      count++;
    }

    // 如果没有找到一只大雁，请返回-1。
    return count == 0 ? -1 : count;
  }

  public static boolean find(char[] quacks) {
    boolean isFind = false;

    int index = 0;
    int[] quack_index = new int[5];

    for (int i = 0; i < quacks.length; i++) {
      if (quacks[i] == "quack".charAt(index)) {
        quack_index[index++] = i;
      }

      if (index == 5) {
        isFind = true;

        for (int j : quack_index) {
          quacks[j] = ' ';
        }

        index = 0;
      }
    }

    return isFind;
  }
}

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  console.log(getResult(await readline()));
})();

function getResult(s) {
  const quacks = [...s];

  let count = 0;
  // 多轮找大雁
  while (find(quacks)) {
    count++;
  }

  return count == 0 ? -1 : count;
}

function find(quacks) {
  let isFind = false;

  let index = 0;
  const quack_index = new Array(5).fill(-1);

  for (let i = 0; i < quacks.length; i++) {
    if (quacks[i] == "quack"[index]) {
      quack_index[index++] = i;
    }

    if (index == 5) {
      isFind = true;

      for (let j of quack_index) {
        quacks[j] = "";
      }

      index = 0;
    }
  }

  return isFind;
}

Python算法源码

# 输入获取
quacks = list(input())


# 一轮找出一只大雁的所有叫声
def find():
    isFind = False

    index = 0
    quack_index = [-1, -1, -1, -1, -1]

    for i in range(len(quacks)):
        if quacks[i] == "quack"[index]:
            quack_index[index] = i
            index += 1

        if index == 5:
            isFind = True

            for j in quack_index:
                quacks[j] = ' '

            index = 0

    return isFind


# 算法入口
def getResult():
    count = 0

    while find():
        count += 1

    return -1 if count == 0 else count


# 算法调用
print(getResult())