LeetCode算法题-Ransom Note(Java实现)
这是悦乐书的第212次更新,第225篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第80题(顺位题号是383)。给定一个任意赎金票据字符串和另一个包含所有杂志字母的字符串,如果赎金票据可以从杂志中构建,则写一个函数将返回true;否则,它将返回false。杂志字符串中的每个字母只能在赎金票据中使用一次。例如:
canConstruct(“a”,“b”) - > false
canConstruct(“aa”,“ab”) - > false
canConstruct(“aa”,“aab”) - > true
注意:您可以假设两个字符串仅包含小写字母。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
因为只有小写字母,可以将magazine所使用到的字符存入一个长度为26的数组,然后再去遍历ransomNote所使用到的字符,只要数组中某一位元素小于0,则返回false。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for (int i=0; i<magazine.length(); i++) {
arr[magazine.charAt(i)-'a']++;
}
for (int j=0; j<ransomNote.length(); j++) {
if (--arr[ransomNote.charAt(j)-'a'] < 0) {
return false;
}
}
return true;
}
03 第二种解法
思路和第一种解法一样,只不过是将传入的两个字符串先转换成字符数组而已。
此解法的时间复杂度是O(n),空间复杂度是O(n)。
public boolean canConstruct2(String ransomNote, String magazine) {
int[] arr = new int[26];
char[] note = ransomNote.toCharArray();
char[] maz = magazine.toCharArray();
for (int i=0; i<maz.length; i++) {
arr[maz[i]-'a']++;
}
for (int j=0; j<note.length; j++) {
if (arr[note[j]-'a']-- == 0) {
return false;
}
}
return true;
}
04 第三种解法
使用HashMap,先将magazine所使用的字符以及出现次数分别作为key和value存入其中,然后遍历ransomNote的字符,如果其当前字符在map中存在,并且其value值在减1后依然大于等于0,那么将此字符所对应的value值减1,反之直接返回false。
此解法因为用到了HashMap的contains方法,因此时间复杂度最好情况是O(n),最坏情况是O(n^2),空间复杂度是O(n)。
public boolean canConstruct3(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<magazine.length(); i++) {
char c = magazine.charAt(i);
map.put(c, map.getOrDefault(c, 0)+1);
}
for (int j=0; j<ransomNote.length(); j++) {
char c = ransomNote.charAt(j);
if (map.containsKey(c) && map.get(c)-1 >= 0) {
map.put(c, map.get(c)-1);
} else {
return false;
}
}
return true;
}
05 第四种解法
依旧是使用HashMap,但是将第三种解法里面的两个循环压缩到一个循环里。循环遍历的对象依旧是ransomNote,获取当前字符c,同时定义一个变量pos,先判断c是否存在于map中,如果c存在于map中,则获取其对应的value并加1,再重新赋值给pos,如果pos大于magazine的长度,直接返回false。
接着重新获取pos的值,等于当前字符在magazine所在的索引(从pos位开始查找),如果pos等于-1,说明当前在ransomNote使用的字符不存在于magazine中,直接返回false,如果pos不等于-1,则将ransomNote的当前字符作为key,该字符在magazine中出现的pos为value存入map中。
此解法因为用到了HashMap的contains方法,因此时间复杂度最好情况是O(n),最坏情况是O(n^2),空间复杂度是O(1)。
public boolean canConstruct4(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : ransomNote.toCharArray()) {
int pos = 0;
if (map.containsKey(c)) {
pos = map.get(c) + 1;
if (pos >= magazine.length()) {
return false;
}
}
pos = magazine.indexOf(c, pos);
if (pos == -1) {
return false;
}
map.put(c, pos);
}
return true;
}
06 小结
算法专题目前已连续日更超过两个月,算法题文章80+篇,