【算法】771. 宝石与石头(java / c / c++ / python / go / rust)

举报
二当家的白帽子 发表于 2021/12/23 18:22:09 2021/12/23
【摘要】 771. 宝石与石头:给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。 样例 1输入: J = "aA", S = "aAAbbbb" 输出: 3 样例 2输入: J = "z...

771. 宝石与石头:

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。

样例 1

输入: 
	J = "aA", S = "aAAbbbb"
    
输出: 
	3

样例 2

输入: 
	J = "z", S = "ZZ"
    
输出: 
	0

限制

  • S 和 J 最多含有50个字母。
  • J 中的字符不重复。

分析

  • 常规做法直接双循环就可以了,循环次数就是S的长度乘以J的长度。
  • 可以先将S放入哈希表,这样在循环J的时候从哈希表查找要比循环S性能更好。
  • 由于宝石种类使用字母表示,所以我们预先知道宝石种类上限,这样可以用数组替代哈希表,性能可以更好。

题解

java

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        // 创建一个宝石对照表
        boolean[] table = new boolean[128];
        int jewelsLen = jewels.length();
        for (int i = 0; i < jewelsLen; ++i) {
            table[jewels.charAt(i)] = true;
        }

        // 统计宝石数量
        int count = 0;
        int stonesLen = stones.length();
        for (int i = 0; i < stonesLen; ++i) {
            if (table[stones.charAt(i)]) {
                count++;
            }
        }

        return count;
    }
}

c

int numJewelsInStones(char * jewels, char * stones){
    // 创建一个宝石对照表
    bool table[128];
    memset(table, false, 128);
    int jewelsLen = strlen(jewels);
    for (int i = 0; i < jewelsLen; ++i) {
        table[jewels[i]] = true;
    }

    // 统计宝石数量
    int count = 0;
    int stonesLen = strlen(stones);
    for (int i = 0; i < stonesLen; ++i) {
        if (table[stones[i]]) {
            count++;
        }
    }

    return count;
}

c++

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        // 创建一个宝石对照表
        bool table[128];
        memset(table, false, 128);
        for (char c : jewels) {
            table[c] = true;
        }

        // 统计宝石数量
        int count = 0;
        for (char c : stones) {
            if (table[c]) {
                count++;
            }
        }

        return count;
    }
};

python

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        # 创建一个宝石对照表
        table = [False] * 128
        for c in jewels:
            table[ord(c)] = True
        # 统计宝石数量
        count = 0
        for c in stones:
            if table[ord(c)]:
                count += 1
        return count

go

func numJewelsInStones(jewels string, stones string) int {
    // 创建一个宝石对照表
	table := [128]bool{}
	for _, c := range jewels {
		table[c] = true
	}

	// 统计宝石数量
	count := 0
	for _, c := range stones {
		if table[c] {
			count++
		}
	}

	return count
}

rust

impl Solution {
    pub fn num_jewels_in_stones(jewels: String, stones: String) -> i32 {
        // 创建一个宝石对照表
        let mut table = vec![false;128];
        jewels.bytes().for_each(|c|{
            table[c as usize] = true;
        });

        // 统计宝石数量
        stones.bytes().filter(|c|{
            table[*c as usize]
        }).count() as i32
    }
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/jewels-and-stones/


非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。