leetcode
leetcode 1951 ~ 2000
必须拿起的最小连续卡牌数

必须拿起的最小连续卡牌数

难度:

标签:

题目描述

代码结果

运行时间: 107 ms, 内存: 35.6 MB


/* 
 * 思路:
 * 由于Java Stream API主要用于处理集合的操作,这里Stream的用法不太适合这种涉及状态变化和索引操作的问题。
 * 但是我们仍然可以使用Stream API结合传统循环来简化代码结构。
 */

import java.util.HashMap;
import java.util.stream.IntStream;

public class Solution {
    public int minimumCardPickup(int[] cards) {
        HashMap<Integer, Integer> lastSeen = new HashMap<>();
        int[] minDistance = {Integer.MAX_VALUE};
        IntStream.range(0, cards.length).forEach(i -> {
            if (lastSeen.containsKey(cards[i])) {
                minDistance[0] = Math.min(minDistance[0], i - lastSeen.get(cards[i]) + 1);
            }
            lastSeen.put(cards[i], i);
        });
        return minDistance[0] == Integer.MAX_VALUE ? -1 : minDistance[0];
    }
}

解释

方法:

此题解使用了哈希表来存储每个卡牌值最近一次出现的索引。遍历卡牌数组,对于每张卡牌,如果它之前出现过(即在哈希表中存在),则计算当前索引与上一次出现索引的差(即连续卡牌的数量),并更新最小数量。如果没有找到任何匹配的卡牌对,则返回-1。这种方法直接通过索引差计算得到最小连续卡牌数,避免了不必要的重复计算。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在哈希表中存储卡牌值的最新索引而不是其出现次数或其他信息?
在此问题中,存储卡牌值的最新索引是为了直接计算两次相同卡牌出现的连续距离,这是求解最小连续卡牌数的关键。存储出现次数或其他信息不能直接提供两次出现之间的距离,因此不适用于解决此特定问题。
🦆
代码中使用了`ans = len(cards)+1`来初始化最小卡牌数,这样的初始化方法有什么特别的意义吗?
使用`ans = len(cards)+1`初始化最小卡牌数的目的是确保在比较过程中,任何有效的连续卡牌数都小于这个初始值。这样可以保证即使数组中的所有卡牌都不重复,也能正确地返回一个超过任何可能卡牌数的值,从而通过后续的条件判断返回-1,表明没有找到任何连续的卡牌对。
🦆
题解中提到的返回值为-1代表没有找到匹配的卡牌,这种设计对于错误处理和算法的可读性有何影响?
返回-1作为错误或特殊情况的标志是一种常见的编程惯例,有助于调用者区分正常结果和没有找到匹配的特殊情况。这种设计提高了算法的可读性和易用性,使得算法的输出更加直观明确,便于外部代码根据返回值做出适当的处理。
🦆
题解提到每次遇到已经见过的卡牌时,会计算当前索引与上一次出现索引的差,这种方法是否考虑了所有可能的边界条件(如数组中只有一对匹配卡牌等情况)?
是的,这种方法考虑了所有可能的边界条件。每当遇到重复的卡牌时,通过计算当前索引与上一次出现索引的差值来更新最小连续卡牌数,这包括了数组中只有一对匹配卡牌的情况。此外,初始化`ans`为一个大于任何可能卡牌长度的值也保证了即使数组中没有重复卡牌,算法仍然能正确返回-1。

相关问题