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

悠悠 2023-10-01 16:02 46阅读 0赞

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

*  LeetCode刷题笔记-数据结构-day7
 *   *  90.单词规律
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  763.划分字母区间
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

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

### 90.单词规律 ###

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

> 原题链接：[90. 单词规律][90.]

![image-20220121103150201][]

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

算法：哈希表

用两个哈希表：

1.  一个哈希表记录pattern中每个字符对应str中的哪个字符串
2.  一个哈希表记录str中的字符串对应pattern中的哪个字符
3.  遍历过程中，如果发现有冲突就返回false
4.  最后没有冲突，还需判断pattern是否全部对应了，也就是说是否还有剩余字符

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

class Solution {
        
    public:
        bool wordPattern(string str, string s) {
        
            unordered_map<char,string> hash1;
            unordered_map<string,char> hash2;
            int k=0;
            for(int i=0,j=0;i<s.size();i++)
            {
        
                j=i;
                while(j<s.size()&&s[j]!=' ') j++;
                string t=s.substr(i,j-i);
                if(hash1.count(str[k])&&hash1[str[k]]!=t) return false;
                if(hash2.count(t)&&hash2[t]!=str[k]) return false;
        
                hash2[t]=str[k];
                hash1[str[k]]=t;
                k++;
                i=j;
            }
            return k==str.size();
        }
    };

### 763.划分字母区间 ###

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

> 原题链接：[763. 划分字母区间][763.]

![image-20220121103341976][]

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

算法：哈希表+贪心

1.  用一个哈希表记录每个字符出现的最末尾位置
2.  我们只需要保证某个最小区间的所有的数的最小位置和最大位置都在这个区间，那么这个区间就可以加入答案
3.  代码实现：可以用变量`end`记录符合要求区间的最大位置，`start`记录初始位置，直到`i==end`，说明已经符合要求了，可以加入
4.  题目要求尽可能多的片段，所以只要符合要求2就可以加入答案

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

class Solution {
        
    public:
        vector<int> partitionLabels(string s) {
        
                map<char,int> hash;
                for(int i=0;i<s.size();i++) hash[s[i]]=i;
                vector<int> res;
                int start=0,end=0;
                for(int i=0;i<s.size();i++){
        
                    end=max(hash[s[i]],end);
                    if(end==i){
        
                        res.push_back(end-start+1);
                        start=end=i+1;
                    }
                }
                return res;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[90.]: https://leetcode-cn.com/problems/word-pattern/
[image-20220121103150201]: https://img-blog.csdnimg.cn/img_convert/a7d76238a28aa1d1ce2e43fe4dfc5b93.png
[763.]: https://leetcode-cn.com/problems/partition-labels/
[image-20220121103341976]: https://img-blog.csdnimg.cn/img_convert/e5ee52eea47b949978c82d556e1cd043.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/795f8a180c1241c8828a6e958559918e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16