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

2024-11-07 07:35:48

leetcode 经典题分类

链表
数组
字符串
哈希表
二分法
双指针
滑动窗口
递归/回溯
动态规划
二叉树
辅助栈

本系列专栏：点击进入 leetcode题目分类关注走一波

前言：本系列文章初衷是为了按类别整理出力扣（leetcode）最经典题目，一共100多道题，每道题都给出了非常详细的解题思路、算法步骤、代码实现。很多同学刚开始刷题都是按照力扣顺序刷题，其实这样对新手不太适用，刷题效果也很不好。因为力扣题目顺序是随机的，并没有按照算法分类，导致同一类型的算法强化训练不够，最后刷完也是迷迷糊糊的。所以本系列文章就是来帮你完成算法分类，针对每种算法做强化训练，保证让你以后遇到题目直接秒杀！

文章目录

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。

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

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

【输入输出实例】

示例 1：

码农公寓

leetcode 经典题分类

文章目录

两数之和

整数转罗马数字

罗马数字转整数

串联所有单词的子串

有效的数独

解数独

相关文章