(新卷,100分)- 数大雁（Java & JS & Python）
(新卷,100分)- 数大雁（Java & JS & Python）
题目描述
一群大雁往南飞，给定一个字符串记录地面上的游客听到的大雁叫声，请给出叫声最少由几只大雁发出。
具体的：
- 大雁发出的完整叫声为”quack“，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个”quack”。
- 大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
- 如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。
输入描述
一个字符串，包含大雁quack的叫声。1 <= 字符串长度 <= 1000，字符串中的字符只有’q’, ‘u’, ‘a’, ‘c’, ‘k’。
输出描述
大雁的数量
用例
| 输入 | quackquack |
| 输出 | 1 |
| 说明 | 无 |
| 输入 | qaauucqckk |
| 输出 | -1 |
| 说明 | 无 |
| 输入 | quacqkuac |
| 输出 | 1 |
| 说明 | 无 |
| 输入 | qququaauqccauqkkcauqqkcauuqkcaaukccakkck |
| 输出 | 5 |
| 说明 | 无 |
题目解析
首先看一个例子：
对于标黄的"uack"，我们应该归属于哪一个绿色的"q"呢？
- 如果归属于第一个绿色"q"，那么该例子就至少有两只大雁
- 如果归属于第二个绿色"q"，那么该例子就至少有一只大雁
这里的两个"q"更准确的描述是：
- 第一个"q"是前一次完整叫声中的第一个"q"
- 第二个"q"是前一次完整叫声后的第一个"q"
下面我对这两种理解都做了实现
归属于第一个"q"解法（90%通过率）
大雁会依次完整发出”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 q = new LinkedList<>();
int u = 0, a = 0, c = 0;
ArrayList 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())
