STL 容器类型的OJ题篇2

古城微笑少年丶 2023-06-24 15:25 85阅读 0赞

### STL 容器类型 ###

*   *   *  1、猜数字游戏
         *  2、单词规律
         *  3、前 K 个高频单词
         *  4、LRU缓存机制

### 1、猜数字游戏 ###

你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛)你的朋友将会根据提示继续猜，直到猜出秘密数字

请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛

请注意秘密数字和朋友的猜测数都可能含有重复数字

> 示例1  
> 输入: secret = “1807”, guess = “7810”  
> 输出: “1A3B”  
> 解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7

> 示例2  
> 输入: secret = “1123”, guess = “0111”  
> 输出: “1A1B”  
> 解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛

方法一：python 利用字典

思路：题目还是比较复杂的，很难读懂，大致意思是：公牛的条件是:下标相等且下标对应的值也相等，如果 guess 中的值在secret中没有的话，则直接跳过即可，最麻烦的是判断母牛，如果不相等，而且还要根据 secret 出现的次数来判断

步骤一：我们首先把参数 str 格式转换为 list 格式好进行判断

步骤二：定义字典保存好 secret 中元素值以及它的个数，因为这在判断母牛的时候需要用到（只记录非公牛的元素）

步骤三：和步骤二同时进行，记录公牛的个数，公牛的判断方法很简单，只要是相等就计数加1

步骤四：如果下标不相等，首先看guess 中当前元素是否在 字典中，如果不在则跳过，如果在的话，并且对应的value 不等于0，则母牛的计数+1，并且对应的 value 减一，因为题目中要求不可重复。

def getHint(self, secret: str, guess: str) -> str:
            res = ''
            cow = bull = 0
            secret = list(secret)
            guess = list(guess)
            # 用来记录 secret 中的数字以及出现次数
            secret_dict = { }
            # 计算出公牛个数以及把 secret 出现的次数记录下来
            for i in range(len(secret)):
                if guess[i]==secret[i]:
                    bull+=1
                else:
                    if secret[i] not in secret_dict:
                        secret_dict[secret[i]] = 1
                    else:
                        secret_dict[secret[i]]+=1
            for i in range(len(guess)):
                if guess[i]!=secret[i]:
                    if guess[i] in secret_dict and secret_dict[guess[i]]!=0:
                        secret_dict[guess[i]]-=1
                        cow+=1
            return res+str(bull)+'A'+str(cow)+'B'

方法二：C++版本

由于要对 secret 进行猜测，所以对他建立 unordered\_map 容器

string getHint(string secret, string guess) { 
            int countA = 0,countB = 0;
            // 判断公牛数
            for(int i = 0;i<secret.size();++i){ 
                if(secret[i]==guess[i]){ 
                    ++countA;
                }
            }
            // 判断母牛
            unordered_map<char,int>um;
            for(auto& s:secret){ 
                um[s]++;
            }
            for(auto&g:guess){ 
                if(um.count(g) && um[g]){ 
                    --um[g];
                    ++countB;
                }
            }
            return to_string(countA) + 'A' + to_string(countB-countA)+'B';
        }

### 2、单词规律 ###

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律

> 示例1  
> 输入: pattern = “abba”, str = “dog cat cat dog”  
> 输出: true

> 示例2  
> 输入:pattern = “abba”, str = “dog cat cat fish”  
> 输出: false

> 示例3  
> 输入: pattern = “aaaa”, str = “dog cat cat dog”  
> 输出: false

> 示例4  
> 输入: pattern = “abba”, str = “dog dog dog dog”  
> 输出: false

方法一：利用 C++ 容器来解决，这里涉及到一个输入流函数，可以处理字符串，将它放到容器中方便遍历

bool wordPattern(string pattern, string str) { 
            stringstream stream(str);
            string word;
            vector<string>words;
            while(stream>>word){ 
                words.push_back(word);
            }
            if(words.size() != pattern.size()){ 
                return false;
            }
            unordered_map<char,string>um;
            for(int i = 0;i<pattern.size();++i){ 
                if(um[pattern[i]]==""){ 
                    um[pattern[i]] = words[i];
                }else{ 
                    if(words[i] != um[pattern[i]]){ 
                        return false;
                    }
                }
            }
            
            // 上面代码无法处理以下这种对应关系
            // a b b a
            // dog dog dog dog
            for(int i = 1;i<um.size();++i){ 
                if(pattern[i] != pattern[i-1] && 
                um[pattern[i]] == um[pattern[i-1]]){ 
                    return false;
                }
            }
            return true;
        }

方法二：其实对于python来说，字符串很难处理，所以我们首先把两个参数字符串转换为列表

步骤一：如果列表的长度不相等或者去重之后不相等则直接返回 Fasle

步骤二：通过一个字典保存好已近遍历过的列表，如果再次遇到在字典中有的 key ，则把 当前值与字典中 key 对应的 value 比较，如果不相等则返回False,最后出了循环返回 True

def wordPattern(self, pattern: str, str: str) -> bool:
        	# 切割字符串
            s = str.split()
            temp = { }
            pattern = ' '.join(pattern)
            pattern = pattern.split()
            if len(pattern) != len(s) or len(set(pattern)) != len(set(s)):
                return False
            for i in range(len(pattern)):
                if pattern[i] not in temp:
                    temp[pattern[i]] = s[i]
                else:
                    if s[i] != temp[pattern[i]]:
                        return False
            return True

方法三：利用了 zip 函数，zip是将两个数组进行组合成一个元组，例如 a = \[1,2,3,4\] b = \[5,6,7,8\] 则 \[zip(a,b)\] = \[(1,5),(2,6),(3,7),(4,8)\]

def wordPattern(self, pattern, strs):
            strs_list = strs.split()
            return len(strs_list) == len(pattern) and len(set(zip(pattern, strs_list))) == len(set(pattern)) == len(set(strs_list))

### 3、前 K 个高频单词 ###

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

> 示例 1：  
> 输入: \[“i”, “love”, “leetcode”, “i”, “love”, “coding”\], k = 2  
> 输出: \[“i”, “love”\]  
> 解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。注意，按字母顺序 “i” 在 “love” 之前。

> 示例 2：  
> 输入: \[“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”\], k = 4  
> 输出: \[“the”, “is”, “sunny”, “day”\]  
> 解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，出现次数依次为 4, 3, 2 和 1 次。

方法一：利用一个字典将列表中的字符串和次数关联起来，然后再进行排序，排序的规则可以使用 lambda 表达式自定以，最后遍历前 k 个字符串添加到返回列表中。

def topKFrequent(self, words: List[str], k: int):
            dic = { }
            res = []
            for s in words:
                if s not in dic:
                    dic[s] = 1
                else:
                    dic[s]+=1
            # 排序规则 -x[1],x[0] 
            # -x[1] 意思是第二个参数按照升序的方式
            # x[0] 意思是第二个参数相等,第一个参数按照降序方式,也就是字典序
            dic = sorted(dic.items(),key=lambda x:(-x[1],x[0]))
            for key,_ in dic[:k]:
                res.append(key)
            return res

方法二：利用序列式容器保存 string 类型对应的 int 值，然后把键值对保存到 vector<pair<string,int>> 序列式容器中进行排序，排序的规则是 int 值按照降序，如果 int 相等的情况下，string 按照字典序的规则排序

vector<string> topKFrequent(vector<string>& words, int k) { 
            unordered_map<string,int>um;
            for(int i=0;i<words.size();++i){ 
                um[words[i]]++;
            }      
            // 键值对类型的 vector 容器
            // 里面要保存所有的键值对并进行排序
            vector<pair<string,int>>v;
            for(auto&e:um){ 
                v.push_back(e);
            }
            // 如果把 lambda表达式写成一个函数指针，代码易读性更高一些
            sort(v.begin(),v.end(),[](\
            	const pair<string,int>&p1,\
            	const pair<string,int>&p2){ 
            	if((p1.second > p2.second) ||\
                (p1.second == p2.second && p1.first<p2.first)){ 
                    return true;
                }
                return false;
            });
            vector<string>res;
            for(int i=0;i<k;++i){ 
                res.push_back(v[i].first);
            }
            return res;
        }

方法三：利用 map 和 multmap 容器，这些容器都是自带排序功能的

vector<string> topKFrequent(vector<string>& words, int k) { 
            // 功能一：将 string 和 int 建立映射
            // 功能二：先对 string 排序，后面就不用对 string 排序了
            map<string,int>um;
            for(int i=0;i<words.size();++i){ 
                um[words[i]]++;
            }
            // 对键值对中的 int 降序排序 
            multimap<int,string,greater<int>>sortmap;
            for(auto& e : um){ 
                sortmap.insert(pair<int,string>(e.second,e.first));
            }
            vector<string>res;
            //利用 迭代器进行遍历
            auto it = sortmap.begin();
            while(it != sortmap.end() && k--){ 
                res.push_back(it->second);
                ++it;
            }
            return res;
        }

方法四：利用优先级队列

struct cmp{ 
            bool operator()(const pair<string,int> &a,\
                            const pair<string,int> &b){ 
                if(a.second!=b.second){ 
                    return a.second<b.second;
                }else{  
                    return a.first>b.first;
                }
            }
        };
        vector<string> topKFrequent(vector<string>& words, int k) { 
            map<string,int> mp;
            for(string s:words){ 
                mp[s]++;
            }
            // 优先级队列的比较规则需要定义一个结构体，重载()函数
            priority_queue<pair<string,int>,\
                vector<pair<string,int>>,cmp> pq;
            for(auto& m:mp){ 
                pq.push(m);
            }
            vector<string> res;
            while(k--){ 
                res.push_back(pq.top().first);
                pq.pop();
            }
            return res;
        }

### 4、LRU缓存机制 ###

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

> 示例  
> LRUCache cache = new LRUCache( 2 /\* 缓存容量 \*/ );  
> cache.put(1, 1);  
> cache.put(2, 2);  
> cache.get(1); // 返回 1  
> cache.put(3, 3); // 该操作会使得密钥 2 作废  
> cache.get(2); // 返回 -1 (未找到)  
> cache.put(4, 4); // 该操作会使得密钥 1 作废  
> cache.get(1); // 返回 -1 (未找到)  
> cache.get(3); // 返回 3  
> cache.get(4); // 返回 4

哈希表的存储是无序的，用OrderedDict() ，可以做到有序存储，存储的顺序按照进入字典的顺序  
通过pop(key)可以得到key所对应的value  
popitem()可以的到最后一个进表的value，而popitem(last=False)可以得到第一个进表的value

import collections
    class LRUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            # 定义一个字典结构，而这个结构是有序的
            self.catch =  collections.OrderedDict()
        def get(self, key: int) -> int:
            if key not in self.catch:
                return -1
            # 这里之所以不直接获取键值，而是先删除再增加
            # 这样就能保证字典结构第一个数据就是最近最少使用的
            value = self.catch.pop(key)
            self.catch[key] = value
            return value
        def put(self, key: int, value: int) -> None:
            # 如果数据在字典中 则先删除最后再加入
            # 为的也是保证最近最少使用的数据始终是结构的第一个数据
            if key in self.catch:
                self.catch.pop(key)
            elif self.catch and self.capacity==0:
                # 得到第一个进表的value，把它删除
                # 这个函数默认情况是删除最后一个进表的value
                self.catch.popitem(last=False)
            # 写入的数据在表中不存在，所以每写入一个就会使capacity-1
            else:
                self.capacity -= 1
            self.catch[key] = value

特别感谢：[https://www.jianshu.com/p/77d14cf02196][https_www.jianshu.com_p_77d14cf02196]

C++ 利用迭代器实现

class LRUCache { 
    private:
        int cap;
        // 双链表：装着 (key, value) 元组
        list<pair<int, int>> cache;
        // 哈希表：key 映射到 (key, value) 在 cache 中的位置
        unordered_map<int, list<pair<int, int>>::iterator> map;
    public:
        LRUCache(int capacity) { 
            this->cap = capacity; 
        }
        
        int get(int key) { 
            auto it = map.find(key);
            // 访问的 key 不存在
            if (it == map.end()) return -1;
            // key 存在，把 (k, v) 换到队头
            pair<int, int> kv = *map[key];
            cache.erase(map[key]);
            cache.push_front(kv);
            // 更新 (key, value) 在 cache 中的位置
            map[key] = cache.begin();
            return kv.second; // value
        }
        
        void put(int key, int value) { 
    
            /* 要先判断 key 是否已经存在 */ 
            auto it = map.find(key);
            if (it == map.end()) { 
                /* key 不存在，判断 cache 是否已满 */ 
                if (cache.size() == cap) { 
                    // cache 已满，删除尾部的键值对腾位置
                    // cache 和 map 中的数据都要删除
                    auto lastPair = cache.back();
                    int lastKey = lastPair.first;
                    map.erase(lastKey);
                    cache.pop_back();
                }
                // cache 没满，可以直接添加
                cache.push_front(make_pair(key, value));
                map[key] = cache.begin();
            } else { 
                /* key 存在，更改 value 并换到队头 */
                cache.erase(map[key]);
                cache.push_front(make_pair(key, value));
                map[key] = cache.begin();
            }
        }
    };

[https_www.jianshu.com_p_77d14cf02196]: https://www.jianshu.com/p/77d14cf02196