我一直在尝试做这个 HackerEarth 问题,但最后几个测试用例似乎总是超时
我是一年级学生,所以我真的不知道如何优化它
我尝试查看 java 解决方案,但它只是将更大的案例放入代码中,有效地消除了优化它的需要
import java.io.*;
import java.util.*;
public class police {
static int t,n,k;
static char[][] test;
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
t = Integer.parseInt(st.nextToken());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
test = new char[n][n];
int ret = 0;
for (int b = 0; b < n; b++) {
st = new StringTokenizer(br.readLine());
for (int a = 0; a < n; a++) {
test[b][a] = st.nextToken().charAt(0);
}
}
for (int b = 0; b < n; b++) {
ret += solve(test[b]); //calculate each row
}
System.out.println(ret);
}
}
static int solve(char[] a) { //given a row, calculate the maximum number of catches
int ret = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 'P') {
for (int b = i - k; b <= i + k; b++) { //scan area to see if police can catch a thief
if (b >= 0 && b < n && a[b] == 'T') {
a[b] = 'C'; //caught
break;
}
}
a[i] = 'U'; //used
}
}
for (int i = 0; i < n; i++) //count
if (a[i] == 'C')
ret++;
return ret;
}
}
我很确定它与 solve 方法有关,如果有人能帮助我,那就太棒了
最佳答案
您是对的,您在 solve
中使用的方法方法是超时的原因。
首先你需要了解algorithm complexity和 Big O notation
问题约束是:
1 <= N <= 1000
1 <= K <= N * N
这些表明您的解决方案的复杂性最多应为 O(N * N)
.换句话说,最多两个嵌套的 for 循环,每个循环的复杂度为 O(N)。
在您的解决方案中,您正在执行以下操作:
for (int b = 0; b < n; b++) {
ret += solve(test[b]); //calculate each row
}
好的,这个循环是必不可少的,因为您必须遍历网格中的所有行。复杂性:O(N)
然后在你的解决方法中:
for (int i = 0; i < n; i++) {
if (a[i] == 'P') {
for (int b = i - k; b <= i + k; b++) { //scan area to see if police can catch a thief
if (b >= 0 && b < n && a[b] == 'T') {
a[b] = 'C'; //caught
break;
}
}
a[i] = 'U'; //used
}
}
这些嵌套的for循环才是问题的真正原因,外循环的复杂度是O(N)
并且内部循环复杂度也可能是 O(N)
对于 K
的高值(value).所以三个for循环的总复杂度可以达到O(N * N * N)
这肯定会超时。
这是我对这个问题的解决方案,我只修改了 solve
方法:
static int solve(char[] a) { //given a row, calculate the maximum number of catches
int ret = 0;
ArrayDeque<Integer> policeMenQueue = new ArrayDeque<>(); // queue for holding positions of policemen
ArrayDeque<Integer> thievesQueue = new ArrayDeque<>(); // queue for positions of thieves
for (int i = 0; i < n; i++) {
if(!policeMenQueue.isEmpty()) { // check if the leftmost policeman can catch a thief at current position (i)
Integer mostLeftPoliceMan = policeMenQueue.getFirst();
if(i - mostLeftPoliceMan > k) { // if he cannot then we must remove him as he will no longer be able to catch any thieves
policeMenQueue.removeFirst();
}
}
if(!thievesQueue.isEmpty()) { // check if the leftmost thief can be caught be a policeman at current position (i)
Integer mostLeftThief = thievesQueue.getFirst();
if(i - mostLeftThief > k) { // if not then we must remove him as he will no longer be caught by any policemen
thievesQueue.removeFirst();
}
}
if(a[i] == 'P') {
if(!thievesQueue.isEmpty()) { // the leftmost thief can be caught by current policeman
ret++;
thievesQueue.removeFirst(); // ok this thief is caught, remove him
} else {
policeMenQueue.addLast(i); // just add the policeman to keep his position in the queue
}
}
if(a[i] == 'T') {
if(!policeMenQueue.isEmpty()) { // the current thief can be caught by the leftmost policeman
ret++;
policeMenQueue.removeFirst(); // ok this policeman has already caught a thief (used), remove him
} else {
thievesQueue.addLast(i); // just add the thief to keep his position in the queue
}
}
}
return ret;
}
我的想法:从左到右在每一行上循环,如问题所述:每个警察只能抓到一个小偷,我们希望抓到的小偷数量最大化,所以每个小偷被抓到对我们有利最左边的警察(因为我们从左到右)。
例如考虑这一行:
P P T T
想象一下 K = 2
在位置 3
的小偷是我们的恩情被警察抓到位置1
因为这个警察抓不到位置上的小偷4
当然还有位置2
的警察在这种情况下可以抓到两个小偷,但请记住,我们必须最大化抓到小偷的数量,并且每个警察只能抓到一个小偷,所以我们希望每个小偷都被最左边可以抓到他的警察抓到。
我的解决方案取决于 queue
数据结构(Java 中的 ArrayDeque
),如果您不知道它是如何工作的或者我为什么使用它,请看这里:https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
关于java - 如何优化初学者 HackerEarth 代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53892027/