leetcode-771-Jewels and Stones(建立哈希表,降低时间复杂度)

题目描述:

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

要完成的函数:

int numJewelsInStones(string J, string S) 

说明:

1、给定两个字符串,字符串中的所有字符都代表石头种类,其中J字符串中的石头种类是玉石,S字符串中的石头种类是你已有的石头种类。要求根据J字符串判断你已有的石头中有多少是玉石,返回玉石的个数。字符大小写敏感。

2、这道题很容易,暴力解法就是双重循环,时间复杂度是O(n^2),我们也可以通过增加空间复杂度,建立哈希表,来降低时间复杂度。

代码如下:

    int numJewelsInStones(string J, string S) 
    {
        unordered_set<char>set1(J.begin(),J.end());//转换为set存储
        int i=0,s1=S.size(),count=0;
        while(i<s1)
        {
            count+=set1.count(S[i]);//如果S[i]代表的石头是玉石,那么count+=1
            i++;
        }
        return count;
    }

上述代码实测9ms,beats 79.34% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

33470
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

36040
来自专栏java工会

java冒泡排序和快速排序

38130
来自专栏赵俊的Java专栏

奇偶分割数组

18240
来自专栏Aloys的开发之路

华为面试题——一道关于指针方面的编程题(C/C++)

    int A[nSize],其中隐藏着若干0,其余非0整数,写一个函数int Func(int* A, int nSize),使A把0移至后面,非0整数...

32880
来自专栏一枝花算不算浪漫

HashMap中的hash算法总结

算法一直是我的弱项,然而面试中基本是必考的项目,刚好上次看到一个HashMap的面试题,今天也来学习下 HashMap中的hash算法是如何实现的。

49920
来自专栏小樱的经验随笔

洛谷 P1019 单词接龙【经典DFS,温习搜索】

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”...

39860
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

8220
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

14430
来自专栏小樱的经验随笔

HDU 1024 Max Sum Plus Plus【动态规划求最大M子段和详解 】

Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

55540

扫码关注云+社区

领取腾讯云代金券