class Solution {
public:
int minimumCardPickup(vector<int>& cards) {
}
};
2260. 必须拿起的最小连续卡牌数
给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。
返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。
示例 1：
输入：cards = [3,4,2,3,4,7] 输出：4 解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。
示例 2：
输入：cards = [1,0,5,3] 输出：-1 解释：无法找出含一对匹配卡牌的一组连续卡牌。
提示：
1 <= cards.length <= 1050 <= cards[i] <= 106原站题解
python3 解法, 执行用时: 128 ms, 内存消耗: 36.2 MB, 提交时间: 2023-05-24 17:54:58
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
# 字典用于记录最近一次卡牌值的索引
d = dict()
ans = 100001
for i, item in enumerate(cards):
if (item in d):
ans = min(ans, i - d[item] + 1)
d[item] = i
return -1 if ans == 100001 else ans
python3 解法, 执行用时: 180 ms, 内存消耗: 29.7 MB, 提交时间: 2023-05-24 17:54:38
# 滑动窗口
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
n = len(cards)
left, right = 0, 0
visited = set()
res = float('inf')
while right < n:
num = cards[right]
# 如果num已经在滑窗内
while num in visited:
# 更新res
res = min(res, right - left + 1)
# 收缩左边界
visited.remove(cards[left])
left += 1
# 加入当前数字
visited.add(num)
# 移动右边界
right += 1
if res == float('inf'):
return -1
return res
python3 解法, 执行用时: 132 ms, 内存消耗: 36.2 MB, 提交时间: 2023-05-24 17:54:11
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
dct, ans = {}, len(cards) + 1
for i, card in enumerate(cards):
if card in dct:
ans = min(ans, i - dct[card] + 1)
dct[card] = i
return -1 if ans == len(cards) + 1 else ans
golang 解法, 执行用时: 144 ms, 内存消耗: 13.8 MB, 提交时间: 2023-05-24 17:48:44
func minimumCardPickup(cards []int) int {
ans := len(cards) + 1
pos := map[int]int{}
for i, v := range cards {
if p, ok := pos[v]; ok && i-p+1 < ans { // 找最近出现的 v
ans = i - p + 1
}
pos[v] = i
}
if ans <= len(cards) {
return ans
}
return -1
}
cpp 解法, 执行用时: 256 ms, 内存消耗: 112.4 MB, 提交时间: 2023-05-24 17:48:29
class Solution {
public:
int minimumCardPickup(vector<int>& cards) {
/* map存数值cards[i]出现的最近一次下标 */
unordered_map<int,int> map;
int result = INT_MAX;
for(int i = 0; i < cards.size(); i++){
if(map.count(cards[i]))
result = min(result,i - map[cards[i]] + 1);
map[cards[i]] = i;
}
return result == INT_MAX ? -1 : result;
}
};