我试图在 GFG 上解决这个问题。谁能告诉我我的代码有什么问题吗？

Question

极客之旅

https://practice.geeksforgeeks.org/contest/job-a-thon-21-hiring-challenge/problems

class Solution {
    public int[] geeksJourney(int geeksTown[], int n, int journey[], int m, int queries[][], int q) {
        Deque<Integer> deque = new ArrayDeque<>();
        int i = 0;
        for (; i < n; i++) {
            deque.addLast(journey[i]);
        }

        boolean dp[] = new boolean[m];

        while(i < m) {
            int j = 0;
            if (deque.peek() == geeksTown[j]) {
                while (j < n && deque.peek() == geeksTown[j]) {
                    deque.removeFirst();
                    if(i<m)deque.add(journey[i]);
                    j++;
                    i++;
                    if (j == n) dp[i-n] = true;
                }
            }
            else
            {
                deque.removeFirst();
                deque.addLast(journey[i]);
                i++;
            }
        }

        int[] ans = new int[q];
        for (i = 0; i < q; i++) {
            int l = queries[i][0]+n-1;
            int r = queries[i][1];
            int count = 0;
            while(l<=r)
            {
                if(dp[l]==true)count++;
                l++;
            }
            ans[i] = count;
        }
        return ans;
    }
}

极客之旅

我知道可能还有其他方法可以解决这个问题，但请告诉我这个方法出了什么问题。 我使用双端队列作为滑动窗口，并将匹配窗口的最后一个索引存储在 dp 中。 为什么这不起作用。我知道可能还有其他方法可以解决这个问题，但请告诉我这个方法出了什么问题。

Answer 1

提供的代码有几个问题：

1. 索引越界错误：在检查是否

   deque.peek() == geeksTown[j]

   的循环中，您在比较元素时没有增加

   j

   ，导致索引比较不正确。此外，您需要确保没有超出

   geeksTown

   数组的边界。

2. 循环条件问题：条件

   while (j < n && deque.peek() == geeksTown[j])

   是有问题的，因为它只适用于第一次出现的

   geeksTown[j]

   。后续发生的情况将无法得到正确处理。相反，您应该使用循环分别遍历

   geeksTown

   和

   deque

   。

3. 双端队列操作：在向

   deque

   添加元素的循环中，您使用

   deque.add(journey[i])

   而不是

   deque.addLast(journey[i])

   。

4. 数组初始化：数组

   dp

   应初始化为

   false

   值。目前，它尚未初始化，其值可能不可预测。

5. 循环终止条件：如果

   while

   小于

   while(i < m)

   ，则

   m

   循环（

   n

   ）的条件可能会导致无限循环。

这是代码的更正版本：

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] geeksJourney(int geeksTown[], int n, int journey[], int m, int queries[][], int q) {
        Deque<Integer> deque = new ArrayDeque<>();
        int i = 0;
        for (; i < n; i++) {
            deque.addLast(journey[i]);
        }

        boolean dp[] = new boolean[m];
        for (int k = 0; k < m; k++) {
            dp[k] = false;
        }

        while (i < m) {
            int j = 0;
            while (j < n && i < m && deque.peek() == geeksTown[j]) {
                deque.removeFirst();
                if (i < m) deque.addLast(journey[i]);
                j++;
                i++;
                if (j == n) dp[i - n] = true;
            }
            if (i < m) {
                deque.removeFirst();
                deque.addLast(journey[i]);
                i++;
            }
        }

        int[] ans = new int[q];
        for (i = 0; i < q; i++) {
            int l = queries[i][0] + n - 1;
            int r = queries[i][1];
            int count = 0;
            while (l <= r) {
                if (l < m && dp[l]) count++;
                l++;
            }
            ans[i] = count;
        }
        return ans;
    }
}

此更正后的代码假设输入数组已正确初始化并提供了有效值。