力扣（leetcode）题目总结——哈希表篇

【题目描述】

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。

【输入输出实例】

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

【算法思路】

只需进行一次for循环，在每一次循环过程中，在哈希表(map容器，以对组的形式存放数据)中查找是否存在key == target - nums[i]的值(哈希表的查找效率高)。

如果查找到，则返回{ value, i }；如果未查找到，将nums[i]作为key值，下标i作为value值存放到哈希表中，继续下一次查找。

【算法描述】

vector<int> twoSum(vector<int>& nums, int target)  //用哈希表查找 
{
	unordered_map<int,int> hashtable;  //创建哈希表(map容器)
    for(int i = 0;i < nums.size(); i++)
    {
		// auto为unordered_map<int,int>::iterator
		//查找哈希表中 key == target-nums[i]的元素。若查找到返回该元素的迭代器，未查找返回.end()
		auto it = hashtable.find(target - nums[i]);      
		if(it != hashtable.end())
		{
			return {it->second, i};  //查找成功
        }
        hashtable[nums[i]] = i;  //更新哈希表中数据，key和value互换
    }
    return {-1, -1};  //查找失败
}

【题目描述】

给你一个整数，将其转为罗马数字。罗马数字包含以下七种字符：I(1)，V(5)，X(10)，L(50)，C(100)，D(500)和M(1000)。

例如，罗马数字2写做II，即为两个并列的1。12写做 XII，即为X+II。 27 写做 XXVII, 即为 XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：

• I可以放在V(5)和X(10)的左边，来表示4和9。
• X可以放在L(50)和C (100)的左边，来表示40和90。
• C可以放在D(500)和M(1000)的左边，来表示 400和900。

【输入输出实例】

示例 1：

输入：num = 3
输出：“III”

示例 2：

输入：num = 4
输出：“IV”

示例 3：

输入：num = 9
输出：“IX”

示例 4：

输入：num = 58
输出：“LVIII” (L = 50, V = 5, III = 3)

示例 5：

输入：num = 1994
输出：“MCMXCIV” (M = 1000, CM = 900, XC = 90, IV = 4)

【算法思路】

总共13个独特的符号：

确定罗马数字的规则是：对于罗马数字从左到右的每一位，选择尽可能大的符号值。

根据罗马数字的唯一表示法，为了表示一个给定的整数num，我们寻找不超过num的最大符号值，将num减去该符号值，然后继续寻找不超过num的最大符号值，将该符号拼接在上一个找到的符号之后，循环直至num为0。最后得到的字符串即为num的罗马数字表示。

编程时，可以建立一个数值-符号对(一一对应)的列表，按数值从小到大排列。从列表尾部开始往前遍历每个数值-符号对，若当前列表数值不超过num，则从num中不断减去该数值，直至num小于当前值时，然后遍历下一个次小的数值-符号对。若遍历中num为0则跳出循环。

【算法描述】

string intToRoman(int num) 
{
    const pair<int,string> list[13] =   //建立 数值-符号 映射的列表
    {
        {1, "I"},
        {4, "IV"},
        {5, "V"},
        {9, "IX"},
        {10, "X"},
        {40, "XL"},
        {50, "L"},
        {90, "XC"},
        {100, "C"},
        {400, "CD"},
        {500, "D"},
        {900, "CM"},
        {1000, "M"},
    };
    string str;    //存放要输出的罗马数字
    int i = 12;    //表示映射列表的下标
    //不断寻找不超过num的最大符号值，找到后减去，再继续寻找
    while(num) 
    {
        if(num >= list[i].first)  //找到不超过num的最大符号值
        {
            num -= list[i].first;    //减去
            str += list[i].second;   //保存对应的罗马字符
        }
        else
        {
            i--;   //继续向下寻找
        }
    }
    return str;
}

【题目描述】

给你一个罗马数字，将其转为整数。罗马数字包含以下七种字符：I(1)，V(5)，X(10)，L(50)，C(100)，D(500)和M(1000)。

例如，罗马数字2写做II，即为两个并列的1。12写做 XII，即为X+II。 27 写做 XXVII, 即为 XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：

• I可以放在V(5)和X(10)的左边，来表示4和9。
• X可以放在L(50)和C (100)的左边，来表示40和90。
• C可以放在D(500)和M(1000)的左边，来表示 400和900。

【输入输出实例】

示例 1:

输入: s = “III”
输出: 3

示例 2:

输入: s = “IV”
输出: 4

示例 3:

输入: s = “IX”
输出: 9

示例 4:

输入: s = “LVIII”
输出: 58 (L = 50, V= 5, III = 3)

示例 5:

输入: s = “MCMXCIV”
输出: 1994 (M = 1000, CM = 900, XC = 90, IV = 4)

【算法思路】

按照题目的描述，可以总结如下规则：

• 当小值在大值的左边，则减小值，如 IV = 5 - 1 = 4；

• 当小值在大值的右边，则加小值，如 VI = 5 + 1 =6；

• 由上可知，右值永远为正，因此最后一位必然为正。

总之，把一个小值放在大值的左边，就是做减法，否则为加法。在代码实现上，可以往后看多一位，对比当前位与后一位的大小关系，从而确定当前位是加还是减法。当没有下一位时，做加法即可。

如下图举例所示：

【算法描述】

int romanToInt(string s) 
{
    int sum = 0;    //记录最后整数结果
    int prenum = getnum(s[0]);  //前一个罗马字符表示的数字
    for(int i = 1; i < s.size(); i++)  //遍历罗马字符串s
    {
        int num = getnum(s[i]);  //当前罗马字符表示的数字
        //通过比较当前罗马数字和前一个罗马数字的大小来判断是加prenum还是减prenum
        if(num > prenum)
        {
            sum -= prenum;
        }
        else
        {
            sum += prenum;
        } 
        prenum = num;    //更新prenum
    }
    sum += prenum;   //右值永远为正，因此最后一位必然为正，直接加
    return sum;
}
//实现 罗马字符-数字 的映射函数
int getnum(char ch)
{
    switch(ch)
    {
        case 'I':
            return 1;
        case 'V':
            return 5;
        case 'X':
            return 10;
        case 'L':
            return 50;
        case 'C':
            return 100;
        case 'D':
            return 500;
        case 'M':
            return 1000;
        default:
            return 0;
    }
}

【题目描述】

给定一个字符串s和一个字符串数组words。words中所有字符串长度相同。 s 中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。可以以任意顺序返回答案。

【输入输出实例】

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：子串"barfoo"开始位置是0。它是words中以 [“bar”,“foo”] 顺序排列的连接。
子串"foobar"开始位置是9。它是words中以 [“foo”,“bar”] 顺序排列的连接。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

【算法思路】

因为单词长度是固定的，我们可以计算出截取字符串的单词个数是否和words里相等，所以我们可以借用哈希表。

一个哈希表是word，用来存放words中的单词及出现的次数；一个哈希表hash是截取的字符串，即从 s 中不断划分单词，存放匹配成功的单词及出现的个数，再比较两个哈希是否相等。

先考虑如何能找到 s 划分的所有指定长度 n 的单词？从下标 i 开始把 s 划分为字母为 n 的单词，i 的取值为 0 ~ n-1，则只需要循环 n次就可以划分出所有长度为 n 的单词，因为从 i = n+1 开始划分与 i = 0 开始划分的单词是一样的。

从下标 i 开始划分 s，通过移动右指针right以间隔 n 来遍历 s。若此单词不在word中，表示匹配不成功，则要清除之前hash中记录的单词，并且移动窗口左指针到下一个单词继续匹配。若此单词在word中，表示匹配成功，则将该单词加入到hash中，并检查该单词是否匹配多次，即检查该单词在hash中出现的次数是否比word中高，若是则需要缩小窗口，也就是left右移，将移出窗口的单词在hash中–，直到hash中出现的次数小于word中次数。

最后只要成功匹配的单词数达到 m 时，则表示找到了一个串联子串，其left为该字串的起始下标，放入result即可。

【算法描述】

//滑动窗口
vector<int> findSubstring(string s, vector<string>& words) 
{
    vector<int> result;    //存放结果
    int m = words.size();    //单词数
    int n = words[0].size();    //每个单词的字母数
    int len = s.size();
    unordered_map<string, int> word;    //存放words中的单词及出现的个数
    for(string str : words)
    {
        word[str]++;
    }
    //从下标i开始把s划分为字母为n的单词
    //只需要循环n次就可以划分出所有长度为n的单词，因为从i = n+1开始划分与i = 0开始划分的单词是一样的
    for(int i = 0; i < n; i++)  
    {
        int left = i;   //滑窗左指针
        int right = i;  //滑窗右指针
        int count = 0;   //记录已成功匹配的单词数
        unordered_map<string, int> hash;   //存放匹配成功的单词及出现的个数
        while(right + n <= len)
        {
            string str(s.begin() + right, s.begin() + right + n);  //左闭右开：划分单词
            right += n;   //窗口右边界右移一个单词的长度
            if(word.find(str) == word.end())  //此单词不在words中，表示匹配不成功
            {
                count = 0;   //重置，清除之前记录的单词
                hash.clear();
                left = right;  //移动窗口左指针
            }
            else  //此单词在words中，表示匹配成功
            {
                hash[str]++;  //将单词加到hash中
                count++;
                while(hash[str] > word[str]) //一个单词匹配多次，需要缩小窗口，也就是left右移
                {
                    string temp(s.begin() + left, s.begin() + left + n);
                    hash[temp]--;
                    count--;
                    left += n;
                }
            }
            if(count == m)  //成功匹配的单词数达到m时，表示找到了一个串联子串
            {
                result.push_back(left);
            }
        }
    }
    return result;
}

【题目描述】

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

【输入输出实例】

示例 1：

输入：board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：true

示例 2：

输入：board =
[[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

【算法思路】

由于board中的整数限定在1到9的范围内，因此可以分别建立哈希表来存储任一个数在相应维度上是否出现过。维度有3个：所在的行，所在的列，所在的以粗实线分隔的3x3宫。

遍历到每个数的时候，例如board[i][j]，我们判断其是否满足三个条件：

• 在第 i 个行中是否出现过；
• 在第 j 个列中是否出现过；
• 在第 *j/3 + (i/3)3 个 3x3宫 中是否出现过；

关于第三点从 数组下标 到 3x3宫序号 的变换，为什么是 *j/3 + (i/3)3 呢？

重述一遍问题：给定 i 和 j ，如何判定board[i][j]在第几个3x3宫呢？ 显然属于第几个 3x3宫 是由 i 和 j 的组合唯一确定，例如board[2][2]一定是第0个box，board[4][7]一定是第5个box，可以画出来看一下，但是规律在哪里呢？我们可以考虑一种简单的情况： 一个3x9的矩阵，被分成3个 3x3宫，如图：

显然每个数属于哪个 3x3 宫 就只取决于纵坐标，纵坐标为 0/1/2 的都属于box[0]，纵坐标为 3/4/5 的都属于box[1]，纵坐标为 6/7/8的都属于box[2]。也就是j/3。

而对于 9x9 的矩阵，我们光根据 j/3 得到 0/1/2 还是不够的，需要加上一个 3 的倍数，例如加0x3，表示本行的box，加1x3，表示在下一行的box，加2x3，表示在下两行的box， 这里的 0/1/2 怎么来的？和 j/3 差不多同理，也就是i/3。

【算法描述】

//只遍历一次
bool isValidSudoku(vector<vector<char>>& board) 
{
    bool row[9][9] = {false};  //哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
    bool col[9][9] = {false};  //哈希表存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
    bool block[9][9] = {false};  //哈希表存储每一个以粗实线分隔的3x3宫内的每个数是否出现过，默认初始情况下，在每个3x3宫内中每个数都没有出现过
    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            // 遍历到第i行第j列的那个数，我们要判断这个数在其所在的行有没有出现过
            // 同时判断这个数在其所在的列有没有出现过
            // 同时判断这个数在其所在的3x3宫中有没有出现过
            if(board[i][j] != '.')
            {
                int index = board[i][j] - '1';    //board[i][j]为数字1~9，哈希映射转换为下标0~8
                //如果board[i][j]这个数在行、列、或3x3宫内重复出现，直接返回false
                //注意：j/3+(i/3)*3 是 3x3宫 和 block下标 的对应关系，每个3x3宫对应block的一行
                if(row[i][index] || col[j][index] || block[j/3 + (i/3)*3][index])
                {
                    return false;
                }
                //之前都没出现过，现在出现了，就给它置为1，下次再遇见就能够直接返回false
                row[i][index] = true;    //board每行 映射为 row每行
                col[j][index] = true;    //board每列 映射为 col每行
                block[j/3 + (i/3)*3][index] = true;    //board每3x3宫 映射为 block每行
            }
        }
    }
    return true;
}


//多次遍历——依次判断三个规则（不推荐）
bool isValidSudoku(vector<vector<char>>& board) {
    for(int i = 0; i < 9; i++)
    {
        unordered_set<char> hash1;  //哈希表存储每一行的每个数是否出现过
        unordered_set<char> hash2;  //哈希表存储每一列的每个数是否出现过
        for(int j = 0; j < 9; j++)
        {
            if(board[i][j] != '.')    //检查数字1~9在每一行只能出现一次
            {
                if(hash1.find(board[i][j]) != hash1.end())
                {
                    return false;
                }
                hash1.insert(board[i][j]);
            }
            if(board[j][i] != '.')    //检查数字1~9在每一列只能出现一次
            {
                if(hash2.find(board[j][i]) != hash2.end())
                {
                    return false;
                }
                hash2.insert(board[j][i]);
            }
        }
    }
    for(int k = 0; k < 9; k += 3)  //检查数字1~9在每一个以粗实线分隔的3x3宫内只能出现一次
    {
        unordered_set<char> hash1;
        unordered_set<char> hash2;
        unordered_set<char> hash3;
        for(int i = k; i < k + 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(board[i][j] != '.')
                {
                    if(hash1.find(board[i][j]) != hash1.end())
                    {
                        return false;
                    }
                    hash1.insert(board[i][j]);
                }
            }
            for(int j = 3; j < 6; j++)
            {
                if(board[i][j] != '.')
                {
                    if(hash2.find(board[i][j]) != hash2.end())
                    {
                        return false;
                    }
                    hash2.insert(board[i][j]);
                }
            }
            for(int j = 6; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    if(hash3.find(board[i][j]) != hash3.end())
                    {
                        return false;
                    }
                    hash3.insert(board[i][j]);
                }
            }
        }
    }
    return true;
}

【题目描述】

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。题目数据 保证 输入数独仅有一个解

【输入输出实例】

示例 1：

输入：board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：board =
[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],
[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],
[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],
[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],
[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],
[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],
[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],
[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],
[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

【算法思路】

1. 状态压缩

   使用 bitset<9> 来压缩存储每一行、每一列、每一个 3x3 宫格中 1-9 是否出现。（其中 3x3 宫格的哈希索引可见[36、有效的数独](# 36、有效的数独)）

   • 这样每一个格子就可以计算出所有不能填的数字，然后得到所有能填的数字，用 getPossibleStatus() 函数实现；
   • 填入数字和回溯时，只需要更新存储信息；
   • 每个格子在使用时，会根据存储信息重新计算能填的数字。

2. 回溯

   每次都使用 getNext() 选择能填的数字最少的格子开始填，这样填错的概率最小，回溯次数也会变少。

   • 使用 fillNum() 在填入和回溯时负责更新存储信息；
   • 一旦全部填写成功，一路返回 true ，结束递归。

图解：

【算法描述】

class Solution {
public:
    // 填充坐标(x,y)对应的数字在该行、列、块中出现的位置
    void fillNum(int x, int y, int n, bool flag) {
        row[x][n] = flag ? 1 : 0;
        col[y][n] = flag ? 1 : 0;
        block[y/3 + (x/3)*3][n] = flag ? 1 : 0;
    }

    // 计算出坐标(x,y)对应的格子所有能填的数字
    bitset<9> getPossibleStatus(int x, int y) {
        return ~(row[x] | col[y] | block[y/3 + (x/3)*3]);
    }

    // 选择出能填的数字最少的格子坐标
    vector<int> getNext(vector<vector<char>>& board) {
        int minCount = 10;
        vector<int> v = {0, 0};
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] == '.') {
                    bitset<9> bit = getPossibleStatus(i, j);
                    if(bit.count() < minCount) {
                        minCount = bit.count();
                        v = {i, j};
                    }
                }
            }
        }
        return v;
    }

    // 回溯遍历，直到所有数字都填进去才成功
    bool dfs(vector<vector<char>>& board, int count) {
        if(count == 0) {
            return true;
        }
        // 选择出能填数字最少的格子开始填，这样填错的概率最小，回溯次数也会变少
        vector<int> v = getNext(board);
        // 遍历该格子所有能填的数
        bitset<9> n = getPossibleStatus(v[0], v[1]);
        for(int i = 0; i < n.size(); ++i) {
            // 第i位置为true，表示可以选择填入该下标对应的数
            if(n.test(i)) {
                board[v[0]][v[1]] = '1' + i;
                fillNum(v[0], v[1], i, true);
                if(dfs(board, count-1))  return true;
                fillNum(v[0], v[1], i, false);
                board[v[0]][v[1]] = '.';
            }
        }
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        // 状态压缩 
        row = vector<bitset<9> >(9, bitset<9>());
        col = vector<bitset<9> >(9, bitset<9>());
        block = vector<bitset<9> >(9, bitset<9>());
        int count = 0;
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] == '.') {
                    count++;
                    continue;
                }
                int n = board[i][j] - '1';
                fillNum(i, j, n, true);
            }
        }
        // 回溯
        dfs(board, count);
    }

public:
    vector<bitset<9> > row;     // 行
    vector<bitset<9> > col;     // 列
    vector<bitset<9> > block;   // 块
};

【题目描述】

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

【输入输出实例】

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

【算法思路】

要找的数一定在 [1, N + 1] 这个区间中(这里N是数组的长度)。因此，我们可以就把原始的数组当做哈希表来使用。

我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置，2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第1个遇到它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则就是数值为 i 的数映射到下标为 i - 1 的位置。

【算法描述】

/******************* 将数组视为哈希表 *******************/
int firstMissingPositive(vector<int>& nums) 
{
    int len = nums.size();
    for(int i = 0; i < len; i++)
    {
        //将数组中≤len的正整数放到其对应下标的位置，即nums[i]放到下标为nums[i]-1号位置
        if(nums[i] != i + 1)
        {
            //不符合条件或重复的nums[i]原地不动
            if(nums[i] <= 0 || nums[i] > len || nums[i] == nums[nums[i] - 1]) 
            {
                continue;
            }
            swap(nums[i], nums[nums[i] - 1]);   //交换位置
            i--;  //将当前下标的数组元素换位后，再次检测换位后的当前元素是否还可以继续换位
        }
    }
    //所有符合条件的数组元素放到对应下标位置后，再遍历数组，找到第一个和位置不对应的元素，返回其下标即为缺失的第一个正整数
    for(int i = 0; i < len; i++)
    {
        if(nums[i] != i + 1)
        {
            return i + 1;
        }
    }
    return len + 1;
}

【题目描述】

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

【输入输出实例】

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

【算法思路】

两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志(即相同点)，哈希表的值为一组字母异位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

使用排序来作为哈希表的键值。由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

【算法描述】

vector<vector<string>> groupAnagrams(vector<string>& strs) 
{
    vector<vector<string>> result;   //存放最后结果
    unordered_map<string, vector<string>> hash;   //哈希表
    //将strs容器中每个字符串str排序，以排序后的字符串为key值存放排序前的字符串str
    for(string str : strs)  
    {
        string s = str;
        sort(s.begin(), s.end());
        hash[s].push_back(str);
    }
    //[字母异位词]排序后肯定一样，所以将所有key值对应内容插入result中
    for(auto it : hash)
    {
        result.push_back(it.second);
    }
    return result;
}

【题目描述】

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

【输入输出实例】

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

【算法思路】

我们在 s 上滑动窗口，通过移动 right 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，就开始右移左指针 left 收缩窗口，如果能收缩，我们就收缩窗口直到得到最小窗口。

如何确定窗口内已经包含 t 全部字符？通过两个哈希表smap、tmap来存放s、t中字符出现次数，tmap在初始就记录好，smap在更新中逐渐记录，如果tmap中记录字符都小于smap中，说明s窗口已经覆盖t字符。

在扩大窗口时，右窗口新移入的字符，如果在t中，才记录到smap，每次扩大窗口都要检查当前窗口是否已经覆盖，如果覆盖就开始收缩左指针，缩小窗口，同时更新最小字串。

【算法描述】

string minWindow(string s, string t) {
    // 记录t字符串的各字符次数
    unordered_map<char, int> smap, tmap;
    for(const auto& i : t) {
        tmap[i]++;
    }

    int minNum = INT_MAX;       // 记录子串最小长度
    string result = "";         // 记录最小字串
    int left = 0, right = 0;    // 左右指针
    while(right < s.size()) {
        // 右窗口新加入字符是否为t中字符，若是则加入smap
        if(tmap.find(s[right]) != tmap.end()) {
            ++smap[s[right]];
        }
        // 当前s窗口内子串已经覆盖了t，右移左指针，记录最小字串
        while(check(tmap, smap)) {
            if(minNum > right-left+1) {
                minNum = right - left + 1;
                result = s.substr(left, minNum);
            }
            if(tmap.find(s[left]) != tmap.end()) {
                --smap[s[left]];
            }
            ++left;
        }
        ++right;
    }
    return result;
}

// 检查count中是否覆盖了origin中字符
bool check(unordered_map<char, int>& origin, unordered_map<char, int>& count) {
    for(const auto& i : origin) {
        if(count[i.first] < i.second) {
            return false;
        }
    }
    return true;
}

恭喜你全部读完啦！古人云：温故而知新。赶紧收藏关注起来，用之前再翻一翻吧~

📣推荐阅读

C/C++后端开发面试总结：点击进入 后端开发面经 关注走一波

C++重点知识：点击进入 C++重点知识 关注走一波

力扣（leetcode）题目分类：点击进入 leetcode题目分类 关注走一波