LeetCode刷题笔记-数据结构-day8

ゝ一世哀愁。 2023-10-01 16:10 21阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day8
 *   *  49.字母异位词分组
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  43.字符串相乘
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-数据结构-day8 ##

### 49.字母异位词分组 ###

#### 1.题目描述 ####

> 原题链接：[49. 字母异位词分组][49.]

![image-20220122103745155][]

#### 2.解题思路 ####

算法：哈希表

1.  我们把一个字符串排序后的字符串为`key`，所有的**字母异位词**为`value`
2.  遍历所有的字符串`x`，把它们排序后的字符串`t`作为`key`，自己本身作为`value`的一部分存入`map`
3.  最后遍历`map`，将所有的`value`存入答案就行

#### 3.代码 ####

class Solution {
        
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
            vector<vector<string>> res;
            map<string,vector<string>> hash;
            for(auto x:strs){
        
                string t=x;
                sort(t.begin(),t.end());
                hash[t].push_back(x);
            }
            for(auto [a,b]:hash){
        
                res.push_back(b);
            }
            return res;
        }
    };

### 43.字符串相乘 ###

#### 1.题目描述 ####

> 原题链接：[43. 字符串相乘][43.]

![image-20220122103825150][]

#### 2.解题思路 ####

1.  长度为`n`和长度为`m`的数字相乘，最多只会有`n+m`位，我们这里将两个数分别存入两个`vector`数组中，方便计算，最终的答案存入`C`
2.  两个数相乘，`num1[i]*num2[j]`的结果累加到`C[i+j]`
3.  计算完后，在对`C`数组遍历，将大于等于10的位进位
4.  最后需要判断不能有前导零，然后累加答案

#### 3.代码 ####

class Solution {
        
    public:
        string multiply(string num1, string num2) {
        
            int n=num1.size(),m=num2.size();
            vector<int> C(n+m);
            vector<int> A,B;
            for(int i=n-1;i>=0;i--) A.push_back(num1[i]-'0');
            for(int i=m-1;i>=0;i--) B.push_back(num2[i]-'0');
    
            for(int i=0;i<n;i++){
        
                for(int j=0;j<m;j++){
        
                    C[i+j]+=A[i]*B[j];
                }
            }
            for(int i=0,t=0;i<C.size();i++){
        
                t+=C[i];
                C[i]=t%10;
                t/=10;
            }
            string res;
            int k=C.size()-1;
            while(k>0&&!C[k])  k--;
            while(k>=0) res+=C[k--]+'0';
            return res;
        }
    };

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16][]

[49.]: https://leetcode-cn.com/problems/group-anagrams/
[image-20220122103745155]: https://img-blog.csdnimg.cn/img_convert/a3b66de619e76fe49afe81d5dea5e677.png
[43.]: https://leetcode-cn.com/problems/multiply-strings/
[image-20220122103825150]: https://img-blog.csdnimg.cn/img_convert/c63ae29decb667c2909896b0e5b4d5de.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/241803e41596425185084735cb96f221.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16