受欢迎的医疗网站建设,常德网站开发哪家好,厦门网站建设网站建设,百度企业官网认证文章目录 Jewels and Stones 宝石与石头问题描述#xff1a;分析代码 Tag Jewels and Stones 宝石与石头
问题描述#xff1a;
给你一个字符串 jewels 代表石头中宝石的类型#xff0c;另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头… 文章目录 Jewels and Stones 宝石与石头问题描述分析代码 Tag Jewels and Stones 宝石与石头
问题描述
给你一个字符串 jewels 代表石头中宝石的类型另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型你想知道你拥有的石头中有多少是宝石。
字母区分大小写因此 “a” 和 “A” 是不同类型的石头。 1 j e w e l s . l e n g t h , s t o n e s . l e n g t h 50 1 jewels.length, stones.length 50 1jewels.length,stones.length50
分析 属于基础性的模拟利用哈希表记录宝石的种类然后遍历石头当石头的类型与宝石的种类匹配那么就找到一个jewel。 因为宝石和石头的种类都是大小写字母表示所以最多的情况下会有52个。
剩下的就是遍历统计了时间复杂度 O ( N ) O(N) O(N),空间复杂度主要是在哈希的空间上 O ( C ) O(C) O(C).
而且数据的规模并不大最大才50所以即使是 O ( N 2 ) O(N^2) O(N2),也可以。
由于这个数据范围的特殊性所以还可以借用位运算进行空间的压缩使用一个long来存放哈希标记。可以选择高32位放大写字母低32位放小写字母。
这样空间就可以降低到 O ( 1 ) O(1) O(1),这属于特殊情况下的trick不具有普遍的适用性可以了解一下。
代码 public int numJewelsInStones(String jewels, String stones) {SetCharacter set new HashSet();for(int i 0;ijewels.length();i){set.add(jewels.charAt(i));}int n stones.length(),ans 0;for(int i 0;in;i){if(!set.contains(stones.charAt(i))) continue;ans;}return ans;}时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( N ) O(N) O(N) Tag
Array
Hash
