哈希表字符串

题目链接：

https://leetcode.cn/problems/jewels-and-stones/

方案一：

解题思路：

  • jewels和stones都是字符串，仅由英文字母组成
  • 在计算石头中是否含有宝石时，还要区分大小写（a 和 A 不同）
  • 所以可以将jewels字符串转成 HashSet<Byte> 来存储

  • 遍历stones每个字符时也转换成Byte并判断是否包含在宝石的 Set 结构中

    解题代码：

    1. class Solution {
    2.   public int numJewelsInStones(String jewels, String stones) {
    3.       HashSet<Byte> jewelsSet = new HashSet<>();
    4.       for (Byte j : jewels.getBytes()) {
    5.           jewelsSet.add(j);
    6.       }
    7.       int count = 0;
    8.       for (Byte stone : stones.getBytes()) {
    9.           if (jewelsSet.contains(stone)) {
    10.               count++;
    11.           }
    12.       }
    13.       return count;
    14.   }
    15. }

    运行结果：

    image.png

    复杂度分析：

  • 时间复杂度：O(n)，代码中出现了 2 次循环，以stones为较大基数来计算

  • 空间复杂度：O(n)，代码中将jewels转换成了HashSet<Byte> 来存储

    引发的思考：

    这是许久以来刷的第一道算法题，从方案一的运行结果来看，这可能并不是最优解（空间复杂度应该还能优化），不过当我拿到这个题目时，方案一的解题思路是最自然想到的

感悟：看似是一道很简单的算法题，但是如果没有经过较多的练习，亦或是没有见过/练过那些最优解，可能真的不容易想到最优解；所以，作为程序员，还是要多动手、多练、多思考才是正道；加油~