必须拿起的最小连续卡牌数
难度:
标签:
题目描述
代码结果
运行时间: 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`来初始化最小卡牌数,这样的初始化方法有什么特别的意义吗?
▷🦆
题解中提到的返回值为-1代表没有找到匹配的卡牌,这种设计对于错误处理和算法的可读性有何影响?
▷🦆
题解提到每次遇到已经见过的卡牌时,会计算当前索引与上一次出现索引的差,这种方法是否考虑了所有可能的边界条件(如数组中只有一对匹配卡牌等情况)?
▷