PRoblem: 给了一个字符串a和b，如果a中的字符全部来自b(b中的字符每个只能使用一次)，就返回true，否则返回false Solution: 1. 最好的办法就是先将b中的字符构造一个hash表，然后对应a中的字符看b中的hash值够不够，如果不够就返回false。 2. 效率低一些的办法就是将两个字符串排序，然后一个一个比较看是否存在。 notes: 1. hash表重新改变大小这个过程非常耗时，需要重新计算hash值，所以最好的办法是在使用前就指定好大小。
//Solution1:class Solution {public: bool canConstruct(string ransomNote, string magazine) { unordered_map<char, int> map(26); for(int i = 0; i < magazine.size(); i++) map[magazine[i]]++; for(int i = 0; i < ransomNote.size(); i++) if(--map[ransomNote[i]] < 0) return false; return true; }};//Solution2:class Solution {public: bool canConstruct(string ransomNote, string magazine) { sort(ransomNote.begin(), ransomNote.end()); sort(magazine.begin(), magazine.end()); int l = 0, r = 0; while(l < ransomNote.size()) { while(ransomNote[l] != magazine[r] && r < magazine.size()) r++; if(r >= magazine.size()) return false; l++; r++; } return true; }};新闻热点
疑难解答
