LeetCode

LeetCode-方法论-map&set-一

594, 349, 350, 1, 290, 205, 451, 202,

map包括有序map和无序map，set也分为有序set和无序set。
map由键值构成，set中元素无重复。

常用操作: find(), insert(), erase(), change(), search(),

#594 最长Harmonius 子序列

  • 描述

    1
    2
    3
    Input: [1,3,2,2,5,2,3,7]
    Output: 5
    Explanation: The longest harmonious subsequence is [3,2,2,2,3].

  • 思路：
    1) 第一步 将数组元素作为key，对应出现的次数作为val，放入map中。如下：

    map | 1st | 2nd | 3rd | 4th| 5th 
-|-|-|-|-|-
key | 1 | 2 | 3 | 5 | 7 |
val | 1 | 3 | 2 | 1 | 1 |

    2) 遍历map：

    对于key=1，如果key=2存在，则子序列长度为： key=1的val + key=2的val： 1+3=4
对于key=2，如果key=3存在，则子序列长度为： key=2的val + key=3的val： 3+2=5
对于key=3，如果key=4不存在，continue
对于key=5，如果key=6不存在，continue
对于key=7，如果key=8不存在，continue
最终返回最大值 5

  • 实现如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int findLHS(vector<int>& nums) {
        // create map
        map<int, int> mp;
        for (auto& item: nums)
            mp[item]++;

        // main process
        int res = 0;
        for (auto itr = mp.begin(); itr!=mp.end(); itr++){
            if ( mp.find(itr->first + 1) != mp.end()){
                res = max(res, mp[itr->first] + mp[itr->first+1]);  // update max
            }
        }
        return res;
    }

#349 Intersection Of Two Arrays

  • 描述

    1
    2
    Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    Output: [9,4]

  • 逻辑

    第一步：将nums1中元素放入set中
第二步：从set中查找nums2中每个元素，
    如果找到，就放入结果set中，如此一来，结果中也没有重复元素。
    如果没找到，continue。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 第一步
        set<int> record(nums1.begin(), nums1.end());

        set<int> resSet;
        // 第二步
        for (int i=0; i<nums2.size(); i++)
            if (record.find(nums2[i]) != record.end()) //in record
                resSet.insert(nums2[i]);
        
        return vector<int>( resSet.begin(), resSet.end() );
    }

#350 INtersection Of Two Arrays II

  • 描述

    1
    2
    Input: nums1 = [1,2,2,1], nums2 = [2,2]
    Output: [2,2]

  • 逻辑

    第一步：将nums1中元素放入map中
第二步：遍历num2中每个元素：
    如果当前元素在map中的频数>0, 那么在结果vector中加入这个元素，同时map中这个元素的频数-1.
    如果当前元素在map中的频数==0，说明这个元素不是共有的，continue。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        // 第一步
        map<int, int> record;
        for (int i=0; i<nums1.size(); i++)
            record[nums1[i]] ++;

        // 第二步
        vector<int> resV;
        for (int i=0;i<nums2.size(); i++){
            if (record[nums2[i]] > 0){
                resV.push_back(nums2[i]);
                record[nums2[i]] -- ;
            }
        }
        return resV;
    }

#1 Two Sum

  • 描述

    1
    2
    3
    4
    5
    6
    7
    Given nums = [2, 7, 11, 15], target = 9,

    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

    NOTE:You may assume that each input would have exactly one solution, 
    and you may not use the same element twice.

  • 逻辑

    遍历nums中所有元素nums[i]：
    如果:map中没有找到target-nums[i]这个值，就把{nums[i], i}放入map中；
    如果:map中找到了target-nums[i]，那么当前值index和target-nums[i]的index放入结果中。done

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<int> twoSum(vector<int>& nums, int target){
        std::unordered_map<int, int> record;
        for (int i=0;i<nums.size();i++){
            // nums[i] is not in the record
            if (record.find(target - nums[i]) == record.end()){
                record[nums[i]] = i;
            }
            else {// nums[i] is in the record
                int res[2] = {record[target-nums[i]], i};
                return vector<int>(res, res+2);
            }
        }
        throw invalid_argument("NO SOLUTION!");
    }

    敲黑板这个问题虽然简单，但有两点值得注意：
    元素逐个放入map，map的value为index。相同的技巧，看#290.

#290 Word Pattern

  • 描述

    1
    2
    Input: pattern = "abba", str = "dog cat cat dog"
    Output: true

  • 逻辑 (不容易想到)

    要使用c++ 中 map容器的一个性质：”空的map中任何key对应的value都是0”。

    第一步：为两个input分别声明map。
第二步：同步遍历pattern和str每一个元素：
    如果 两个map的key对应的value（index）相同，赋值给两个value为index+1;
    否则 返回false
最终判断：最终的循环变量i是否等于input 的长度。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool wordPattern(string pattern, string str) {
        map<char, int> mp1;
        map<string, int> mp2;

        // 从一个string中逐个读取单词
        istringstream in(str);
        int i = 0, n = pattern.size();
        for (string word; in >> word; ++i) {
            if (i == n || mp1[pattern[i]] != mp2[word])
                return false;
            mp2[word] = i + 1;
            mp1[pattern[i]] = i + 1;
        }
        return i == n;
    }

细节：从一个string中逐个读取单词。使用了c++中map的特性，考虑其他更通用的方法。

#205 Isomorphic Strings

  • 描述

    1
    2
    3
    4
    5
    Input: s = "egg", t = "add"
    Output: true

    Input: s = "foo", t = "bar"
    Output: false

  • 思路

    思路与#290相同。用图示表示出来：

    以 s = “egg”, t = “add” 为例：

    以 s = “egg”, t = “ade” 为例：

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool isIsomorphic(string s, string t) {
        unordered_map<char, int> mpS;
        unordered_map<char, int> mpT;

        for (int i=0; i<s.size(); i++){
            if (mpS[s[i]] != mpT[t[i]])
                return false;
            mpS[s[i]]=i+1;
            mpT[t[i]]=i+1;
        }
        return true;
    }

敲黑板逐个放入map

#451 Sort Charactors By Frequency

  • 描述

    1
    2
    3
    4
    5
    Input:
    "aBbbccc"

    Output:
    "cccbbaB"

  • 逻辑

    很直接

    第一步：将string s中元素放入map中，并且把键值对作为元素翻入vector中。
第二步：按value的大小从大到小排序。
第三步：将vector中的元素放入结果string中。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    struct cmpByValue {
        bool operator()(const pair<char, int>& l, const pair<char, int>& r){
            return l.second > r.second;
        }
    };

    string frequencySort(string s) {
        string res;
        // 第一步
        unordered_map<char, int> mp;
        for (int i=0; i<s.length(); i++)
            mp[s[i]] ++;

        // 第二步
        vector<pair<char, int>> mapValue(mp.begin(), mp.end());
        sort(mapValue.begin(), mapValue.end(), cmpByValue());

        // 第三步
        for (int i=0; i<mapValue.size(); i++){
            for (int j=0; j<mapValue[i].second; j++){
                res+=mapValue[i].first;
            }
        }
        return res;
    }

#202 Happy Number

  • 描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Input: 19
    Output: true
    Explanation: 
    1**2 + 9**2 = 82
    8**2 + 2**2 = 68
    6**2 + 8**2 = 100
    1**2 + 0**2 + 0**2 = 1

    Those numbers for which this process ends 1 are happy numbers.

  • 逻辑

    过程如描述中的Explanation。要注意的是，对于不是happy number的数，防止无限循环，将每一步的结果放入set中（不重复）。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int func(int n){
        int res = 0;
        while(n!=0){
            res+=pow(n % 10,2);
            n/=10;   // 每次循环，从高高位到低位得到每一位的数值。
        }
        return res;
    }

    bool isHappy(int n) {
        unordered_set<int> record;
        while (1){
            if (n ==1) return true; 
            
            record.insert(n);
            n = func(n);

            if (record.find(n) != record.end())
                return false;
        }
    }