774. Jewels and Stones

oujie 发布于2019-07-30 17:01 / 3077人阅读

摘要：题目链接思路从题目得知，我们是求字符串在字符串中出现的次数。也就是说，就可以获得答案。当然可以利用数据结构进行优化。算法复杂度时间空间代码用优化

题目链接：Jewels and Stones

思路：
从题目得知，我们是求字符串J在字符串S中出现的次数。也就是说，one-pass就可以brute force获得答案。
当然可以利用set()数据结构进行优化。

算法复杂度：

时间：O(M*N) or O(M + N) where M is the length of J and N is the length of S
空间：O(1) or O(M) where M is the length of J

代码：

class Solution(object):
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        count = 0
        for s in S:
            if s in J:
                count +=1
        return count

用set()优化：

class Solution(object):
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        setJ = set(J)
        return sum(s in setJ for s in S)

GPU云服务器云服务器 Jewels Stones And between and

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41969.html

Leetcode PHP题解--D1 771. Jewels and Stones

摘要：由于是按难易度排序的，因此本题是第一题。先把问题简化为中只有一个字符的情形，因为字符串可以看作是一个字符数组。这个函数的作用就是，根据闭包函数，过滤数组元素。要注意是字符串，需要先转换成数组才行。 771. Jewels and Stones 由于是按难易度排序的，因此本题是第一题。题目链接 771. Jewels and Stones 题目分析从第二个参数S中找第一个参数J 中出...

Bamboy 2019-07-01 12:33 评论0 收藏0
Leetcode 刷题（持续更新）

摘要：字母区分大小写，因此和是不同类型的石头。输入输出暴力解法将宝石中的每个元素在石头中的数量相加的时间复杂度为石头中的每个元素此元素在宝石中则官方解法哈希表将搜索的时间复杂度变为本文章基于Datewhale第30期组队学习 2021.11.15 # 1 两数之和# 给定一个整数数组 nums...

XanaHopper 2021-11-16 11:45 评论0 收藏0
Datawhale刷题LeetCode

摘要：数据结构与算法简介及攻略两数之和数组串联学到无返回值，是在原始数组进行的修改宝石与石头官方题解我觉得我的方法应该进行简化数组基础加一寻找数组的中心下标左求和中间值数组所有旋转数组旋转图像螺旋矩阵对角线遍历 Task1：数据结构与算法简介、LeetCode ⼊⻔及攻略 0001.两数之和 cl...

YanceyOfficial 2021-11-16 11:45 评论0 收藏0
[LeetCode] 403. Frog Jump

Problem A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a li...

赵连江 2019-08-16 13:38 评论0 收藏0
leetcode403. Frog Jump

摘要：石头的位置用整数数组来表示。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用数据结构来记录该结果，其中的为的数，它的对应的是从该出发的所有的上一步的步长。题目要求 A frog is crossing a river. The river is divided into x units and at each unit the...

Soarkey 2019-08-16 16:44 评论0 收藏0