leetcode
leetcode 651 ~ 700
宝石与石头

宝石与石头

难度:

标签:

题目描述

代码结果

运行时间: 18 ms, 内存: 0.0 MB


/*
 * 题目思路:
 * 使用 Java Stream API 来实现宝石统计。
 * 将 jewels 转换为一个集合,然后使用流来过滤 stones 中的宝石并计数。
 */
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        // 将 jewels 转换为集合
        Set<Character> jewelSet = jewels.chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
        // 过滤并计数 stones 中的宝石
        return (int) stones.chars()
                .filter(c -> jewelSet.contains((char) c))
                .count();
    }
}

解释

方法:

该题解通过遍历字符串 `stones` 中的每个字符,并检查该字符是否存在于字符串 `jewels` 中。若存在,则认为该石头是宝石。使用 Python 的 `sum` 函数,结合生成器表达式,直接计算出宝石的总数。生成器表达式 `s in jewels for s in stones` 为每个石头类型生成一个布尔值,如果它是宝石,则为 `True`(即1),否则为 `False`(即0)。`sum` 函数将这些布尔值相加,得到宝石的总数。

时间复杂度:

O(n*m)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在算法中使用生成器表达式而不是普通的循环结构?
生成器表达式在处理大量数据时更为内存高效。它按需计算每个元素,而不是一次性将所有元素加载到内存中。这样可以减少内存使用,并有可能提高性能。在本题中,使用生成器表达式可以逐个处理`stones`中的每个字符,避免了额外的内存开销,特别是当`stones`非常长时。
🦆
这种方法中,'s in jewels'操作的时间复杂度是多少?是否存在更高效的方式来检查一个字符是否为宝石?
在字符串中,'s in jewels'操作的时间复杂度为O(j),其中j是`jewels`的长度。因为每次检查都要遍历整个`jewels`字符串来查找字符s。一个更高效的方法是先将`jewels`转换为一个集合,集合的成员检查时间复杂度为O(1)。这样,整体时间复杂度会从O(n*j)降低到O(n),其中n是`stones`的长度。
🦆
如果`jewels`或`stones`字符串特别长,该算法的性能表现如何?是否会有延迟?
如果`jewels`或`stones`特别长,算法的执行时间会增加。尤其是如果不使用集合优化,检查每个字符是否属于`jewels`需要O(j)时间,整个算法的时间复杂度为O(n*j),其中n是`stones`的长度,j是`jewels`的长度。这会导致明显的延迟。如果采用集合进行优化,时间复杂度可以降低到O(n),这极大提高了对长字符串的处理效率。

相关问题