2023年7月24日每日一题--771. 宝石与石头

leetcode链接：

771. 宝石与石头

题目分析

方案一

将宝石放到hashset里面，stone按位去遍历。

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int result = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }

        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                result++;
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了67.58% 的Java用户
内存消耗:39.9 MB,击败了46.87% 的Java用户

分析

时间复杂度：
O( n + m ) –> n：jewels的长度 m：stones的长度

空间复杂度：
O( n )

方案二

优化了一下，乌拉

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int result = 0;

        int[] ints = new int[26];
        int[] INTS = new int[26];
        // 方案二：
        for (int i = 0; i < stones.length(); i++) {
            char c = stones.charAt(i);
            if (c >= 'a' && c <= 'z') {
                ints[c - 'a'] += 1;
            } else {
                INTS[c - 'A'] += 1;
            }
        }

        for (int i = 0; i < jewels.length(); i++) {
            char c = jewels.charAt(i);
            if (c >= 'a' && c <= 'z') {
                result += ints[c - 'a'];
            } else {
                result += INTS[c - 'A'];
            }
        }
        
        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了97.98% 的Java用户

分析

时间复杂度：
O( n + m ) –> n：jewels的长度 m：stones的长度

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/jewels-and-stones/solution/bao-shi-yu-shi-tou-by-leetcode-solution/

方法一：暴力

极致的暴力求解，真就纯暴力

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int jewelsCount = 0;
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < stonesLength; i++) {
            char stone = stones.charAt(i);
            for (int j = 0; j < jewelsLength; j++) {
                char jewel = jewels.charAt(j);
                if (stone == jewel) {
                    jewelsCount++;
                    break;
                }
            }
        }
        return jewelsCount;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/jewels-and-stones/solution/bao-shi-yu-shi-tou-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：哈希集合

和方案一类似

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int jewelsCount = 0;
        Set<Character> jewelsSet = new HashSet<Character>();
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < jewelsLength; i++) {
            char jewel = jewels.charAt(i);
            jewelsSet.add(jewel);
        }
        for (int i = 0; i < stonesLength; i++) {
            char stone = stones.charAt(i);
            if (jewelsSet.contains(stone)) {
                jewelsCount++;
            }
        }
        return jewelsCount;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/jewels-and-stones/solution/bao-shi-yu-shi-tou-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。