查找1

ryluo 2020-08-23 19:32:22

两个数组的交集(349)

image-20200823193310347


题目分析:

求两个数组的交集,直接使用哈希表分别遍历两个数组即可,但是需要注意,这里多个相同的值最终只算一个,所以在得到一个答案之后需要将其标志位置零,不至于得到多个相同的结果。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;
        vector<int> ans;

        for(int i = 0; i < nums1.size(); i++)  
            mp[nums1[i]] = 1;

        for(int i = 0; i < nums2.size(); i++){
            if(mp[nums2[i]] == 1){
                ans.push_back(nums2[i]);
                mp[nums2[i]] = 0;
            }
        }
        return ans;
    }
};


两个数组的交集II(350)

image-20200823194019479

题目分析:

这道题相对于第一题就是多了可以重复的条件,在使用哈希表记录数据的时候注意元素的增减。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;
        vector<int> ans;
        for(int i = 0; i < nums1.size(); i++)
            mp[nums1[i]] ++;

        for(int i = 0; i < nums2.size(); i++)
            if(mp[nums2[i]]){
                mp[nums2[i]] --;
                ans.push_back(nums2[i]);
            }

        return ans;
    }
};


两个数组的交集III(350)

image-20200823200015275

题目分析:

本题就是判断两个字符串中所有的字符是否相等,并且所有字符出现的次数也要相等。

可以使用两个哈希表分别存储两个字符出现的次数,然后随便遍历一个检查一下字符的数量是否相等即可。

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> mp1;
        unordered_map<char, int> mp2;
        if (s.size() != t.size()) return false;

        bool ans = true;
        for(auto c: s) mp1[c] ++;
        for(auto c: t) mp2[c] ++;

        for(int c: s)
            if(!(mp2[c] && mp2[c] == mp1[c])) return false;

        return ans;
    }
};


快乐数(202)

image-20200823200347775

题目分析:

本题中的无限循环,是结题的关键,如果把中间的所有结果用一个哈希表存起来,如果出现了重复的值,就说明是无限循环,那么直接返回false,否则直到结果等于1。

class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int, int> mp;
        int sum = 0;
        while(true){
            while(n > 0){
                int tmp = n % 10;
                sum += tmp * tmp;
                n /= 10;
            }
            if (sum == 1) break; 
            else n = sum, sum = 0;

            if(mp[n] != 0) return false;
            mp[n] = 1;
        }
        return true;
    }
};


同构字符串(205)

image-20200823212025591

题目分析:

这道题本质上是判断s中的相同字符是否可以映射到t中的相同字符,并且t中的相同字符是否可以映射到s的相同字符。可以使用两个哈希表分别记录s到t的映射以及t到s的映射,然后从前往后扫描字符串,判断相同字符是否都映射到相同字符。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> st, ts;
        for(int i = 0; i < s.size(); i++){
            if(st.count(s[i])){
                if(st[s[i]] != t[i]) return false;
            }
            else st[s[i]] = t[i];

            if(ts.count(t[i])) {
                if(ts[t[i]] != s[i]) return false;
            }
            else ts[t[i]] = s[i];
        }
        return true;
    }
};


单词规律(290)

image-20200823211739446

题目分析:

做这道题之前一定要先去做一下Leetcode205,同构字符串,思路基本上是一模一样的,多一些前处理而已。

相比于205多了一步将字符串分割的操作,其他的和Leetcode205是完全一样的。

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, string> ps;
        unordered_map<string, char> sp;
        vector<string> ss;

        int k = 0;
        int len = str.size();
        string tmp;
        while(k < len){
            if(str[k] != ' ') tmp += str[k];
            else {
                ss.push_back(tmp);
                tmp.clear();
            }
            if (k == len - 1) ss.push_back(tmp);
            k ++;
        }

        if(pattern.size() != ss.size()) return false;
        for(int i = 0; i < pattern.size(); i++){
            if(ps.count(pattern[i])){
                if(ps[pattern[i]] != ss[i]) return false;
            }
            else ps[pattern[i]] = ss[i];

            if(sp.count(ss[i])){
                if(sp[ss[i]] != pattern[i]) return false;
            }
            else sp[ss[i]] = pattern[i];
        }
        return true;
    }
};


根据字符出现频率排序(451)

image-20200823223030235

题目分析:

先使用哈希表扫一遍字符串,统计每个字符出现的次数,然后构建一个vector,其中元素是pair,最后自定义一种排序方式来得到最终的结果。

需要注意的是自定义sort的比较方式的时候一定得是static函数,不然会报错。

class Solution {
public:
    static bool cmp(const pair<int,char> a, const pair<int, char> b){
        if(a.first >= b.first) return true;
        else return false;
    }
    string frequencySort(string s) {
        string ss = "";
        unordered_map<char, int> mp;
        for(auto c: s) mp[c] ++;

        vector<pair<int, char>> pp;
        for(auto it: mp) pp.push_back(make_pair(it.second, it.first));

        sort(pp.begin(), pp.end(), cmp);
        for(auto it: pp)
            ss += string(it.first, it.second);

        return ss;
    }
};