leetcode
leetcode 701 ~ 750
翻转卡片游戏

翻转卡片游戏

难度:

标签:

题目描述

代码结果

运行时间: 32 ms, 内存: 16.7 MB


/*
 * 思路:
 * 1. 使用Stream API进行数据处理。
 * 2. 使用Set记录同时出现在正面和背面的数字。
 * 3. 使用Stream筛选出符合条件的背面数字并找到最小值。
 */
import java.util.*;
import java.util.stream.*;
public class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        Set<Integer> same = IntStream.range(0, fronts.length)
                                      .filter(i -> fronts[i] == backs[i])
                                      .mapToObj(i -> fronts[i])
                                      .collect(Collectors.toSet());
        return IntStream.concat(IntStream.of(backs), IntStream.of(fronts))
                        .filter(x -> !same.contains(x))
                        .min()
                        .orElse(0);
    }
}

解释

方法:

这个题解的思路是先遍历一遍卡片正反面数字,将正反面数字相同的数存入一个集合 same 中。然后再分别遍历正面和反面的数字,找出不在 same 集合中的最小数字作为答案。如果最终没有找到符合条件的数字,就返回 0。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法实现中,为什么选择3000作为初始的最小值?这个值与输入的数字范围有何关联?
在这个算法中,选择3000作为初始的最小值是基于一个假设:卡片上的数字范围不会超过此值。这个值应该大于卡片数字的可能的最大值,以确保在比较过程中任何小于此初始值且不在`same`集合中的数字都能被正确识别为更小值。此选择通常是基于问题描述中给定的数字范围。如果问题没有明确说明,这可能是一个不安全的假设,因此在实际应用中,这个值应该根据实际数字范围来确定。
🦆
在遍历正面和反面数字时,是否考虑了所有卡片正反面数字都在集合`same`中的边界情况?
是的,算法确实考虑了所有卡片的正反面数字都在`same`集合中的边界情况。在这种情况下,没有任何数字可以作为翻转后的最小值,因此所有的数字都会被`same`集合排除。在两次遍历结束后,如果没有找到任何不在`same`中的更小值,`res`将保持为3000,最后通过`res < 3000`的条件检查,算法将返回0。这意味着所有卡片正反面数字都相同,没有可行的翻转。
🦆
为什么算法中需要分别遍历正面和反面的数字来寻找最小值,而不是合并两者后再进行一次遍历?
算法中分别遍历正面和反面数字的原因在于简化逻辑和避免创建额外的数据结构。虽然合并正面和反面数字后进行一次遍历可以达到同样的效果,但这需要额外的空间来存储合并后的列表,并且可能增加合并操作的时间开销。分开遍历可以直接在原始数组上操作,减少了空间和时间复杂度。此外,分别遍历也使得代码逻辑更清晰,易于理解和维护。
🦆
题解中返回结果时,使用了条件`res < 3000`来判断是否找到符合条件的数字,如果输入的数字范围超过了3000怎么办?
如果输入的数字范围超过了3000,当前算法中使用的3000作为初始最小值将不再安全,可能导致算法无法正确返回最小值。在这种情况下,初始值`res`应该设置为大于所有可能的卡片数字的一个值,例如,可以设置为输入数字范围的最大值加1。此外,最好是在问题或输入数据中明确指定数字的上限,以便于正确设置这个初始值。如果没有明确的上限,应该从输入数据中动态确定最大值,以确保算法的正确性和安全性。

相关问题