LeetCode算法题-Ransom Note(Java实现)

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+篇,