题解 | #奶牛排队问题#

奶牛排队问题

https://www.nowcoder.com/practice/e974a33a14a344278c3a359a1ebf833e

一、知识点:

HashMap

二、文字分析:

哈希表来解决。我们可以遍历整个奶牛队列,对于每头奶牛,检查是否存在与其体重相同且在队列中的距离不超过k的奶牛。为了判断距离是否超过k,我们可以使用一个双端队列来保存最近的k个奶牛的位置。如果存在符合条件的奶牛,则返回true;否则,返回false。

三、编程语言:

java

四、正确代码:

import java.util.*;

public class Solution {
    public boolean checkDuplicate(int[] weights, int n, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (map.containsKey(weights[i])) {
                int distance = i - map.get(weights[i]);
                if (distance <= k) {
                    return true;
                }
            }
            map.put(weights[i], i);

            if (!deque.isEmpty() && i - deque.peekFirst() >= k) {
                deque.pollFirst();
            }
            deque.offerLast(i);
        }

        return false;
    }
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务