给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
注意:
S 和 J 最多含有50个字母。 J 中的字符不重复。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jewels-and-stones 著作权归领扣网络所有。
优化一下,不过发现提交代码没什么时间区别!:
1 public int numJewelsInStones(String J, String S) { 2 if (S == null || S.isEmpty()) return 0; 3 if (J == null || J.isEmpty()) return 0; 4 5 6 //考虑更高的空间性能,使用byte数组。ASCII码中字母的跨度为65~122,所以定义数组长度为58最节省。 7 //BitSet arr=new BitSet(); //BetSet默认创建长度为64的(扩容每次扩容64)数组,里面默认false 8 byte[] arr = new byte[58]; //如果用最小占8位的byte数组开辟58的空间就可以 9 int sum = 0; 10 11 for(int i = 0;i<J.length();i++){ 12 //改变58个长度中对应下表的值就可以,后面检查到这个值从默认的0改为1 ,或者默认false改为true 13 //即说明宝石类型J中含有该字母 14 15 //arr.set(J.charAt(i) - 65); 16 arr[J.charAt(i) - 65] = 1; 17 } 18 for(int i =0;i<S.length();i++){ 19 //用手上的石头S每一个字母去求它对应的数组的下标值,判断如果默认值被更改了, 20 //说明手上的石头是包含在宝石类型数组J中的,这时累加1 21 22 //if(arr.get(S.charAt(i) - 65) == true) sum++; 23 if(arr[S.charAt(i) - 65] == 1) sum++; 24 } 25 return sum; 26 27 }
原来的方法
1 public int numJewelsInStones(String J, String S) { 2 3 if (S == null || S.isEmpty()) return 0; 4 if (J == null || J.isEmpty()) return 0; 5 6 byte[] arr = new byte[58]; 7 int count = 0; 8 for (char ch : J.toCharArray()) { 9 arr[ch - 65] = 1; 10 } 11 for (char ch : S.toCharArray()) { 12 if(arr[ch -65] == 1) { 13 count++; 14 }; 15 } 16 return count; 17 }