今天周日，放松了一点，只有三道题。

299. 猜数字游戏 ， 127. 单词接龙 ， 841. 钥匙和房间

299.猜数字游戏 题目描述：

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• • 猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛），
  • 有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

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

示例：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

看到这题就想到了哈希表的做法，但还是卡了一下，本来是定义了一个map哈希表，secret[i]作为键，i作为值，遍历guess值，搜索guess[i]在map中能否找到对应的值，如果找到并且对应的值与i相等，就Acount++，找到但不对应就Bcount++，但是会有重复的数，所以一开始将secret数组放入哈希表时就会把上一个相同的数字对应的值给覆盖掉了。所以这种做法还是不行，如果没有重复数字的话应该可以。

改变map哈希表的键值对，以secret[i]为键，secret[i]这个数字在secret数组中出现的次数为值，这样就能够解决这道题目了。

先遍历secret数组与guess数组，因为题目提示给出了这两个数组的大小相同，所以可以遇到secret[i] == guess[i]时就Acount++，不然的话就将map[secret[i]]加一。最后再将guess数组遍历一次，跳过secret[i] == guess[i]的情况，如果secret[i]在哈希表中能查找到，就Bcount++。

class Solution {
public:
    string getHint(string secret, string guess) {
        unordered_map<int, int> mp;
        int Acount = 0;
        int Bcount = 0;
        for (int i = 0; i < secret.size(); i++){
            if (secret[i] == guess[i]){
                Acount++;
            }
            else mp[secret[i]]++;
        }
        for (int i = 0; i < guess.size(); i++){
            if (secret[i] != guess[i] && mp[guess[i]] > 0){
                Bcount++;
                mp[guess[i]]--;
            }
        }
        string out = to_string(Acount) + 'A' + to_string(Bcount) + 'B';
        return out;
    }
};

127.单词接龙 题目描述：

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

本题显然是一个无向图的应用，寻找最短路径最好的办法还是使用广度优先搜索，因为广度优先搜索是一圈一圈的往外搜索，第一次搜索到一个节点时，我们就已经k