[数据结构与算法]C++刷题之旅（35）

LeetCode算法入门（第三十五天）

字符串

49.字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;

        for(string& str: strs){
            string key = str;
            sort(key.begin(), key.end());   //所有互为异位词排序后都为一个单词
            mp[key].push_back(str);   //当遍历过程中，遇到key相同，说明互为异位词，将其压入容器
        }

        vector<vector<string>> ans;
        for(auto it = mp.begin(); it != mp.end(); it++){
            ans.push_back(it->second);   //遍历，依次取出单词组
        }
        return ans;
    }
};

43.字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> A; vector<int> B;
        int m = num1.size(); int n = num2.size();
        //将字符数字转换为正数，倒序压入容器中，
        for(int i = m - 1; i >= 0; i--){
            A.push_back(num1[i] - '0');
        }
        for(int j = n - 1; j >= 0; j--){
            B.push_back(num2[j] - '0');
        }
        vector<int> C;
        int count = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                 C[i + j] += A[i] * B[j];   //两数相乘，并对应为上相加，此时不进位
            }
        }
        for(int k = 0; k < C.size(); k++){
            count += C[k];   //求和，如果有进位会加上进位
            C[k] = count % 10;   //结果的个位
            count = count / 10;   //进位
        }
        int l = C.size() - 1;
        while(l > 0 && !C[l]){   //去除前导0
            l--;
        }
        string res;
        while(l >= 0){
            res += C[l] + '0';   
            l--;
        }

        return res;
    }
};