网站建设需要个体营业执照吗,php网站开发专员招聘,郑州视频网站建设大概多少钱,怎样wordpressleetcode 经典题分类
链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈
本系列专栏#xff1a;点击进入 leetcode题目分类 关注走一波 前言#xff1a;本系列文章初衷是为了按类别整理出力扣#xff08;leetcode#xff09;最经典题目#xff0c…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值存放到哈希表中继续下一次查找。
【算法描述】
vectorint twoSum(vectorint nums, int target) //用哈希表查找
{unordered_mapint,int hashtable; //创建哈希表(map容器)for(int i 0;i nums.size(); i){// auto为unordered_mapint,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即为XII。 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 pairint,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即为XII。 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还是减prenumif(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 n1 开始划分与 i 0 开始划分的单词是一样的。
从下标 i 开始划分 s通过移动右指针right以间隔 n 来遍历 s。若此单词不在word中表示匹配不成功则要清除之前hash中记录的单词并且移动窗口左指针到下一个单词继续匹配。若此单词在word中表示匹配成功则将该单词加入到hash中并检查该单词是否匹配多次即检查该单词在hash中出现的次数是否比word中高若是则需要缩小窗口也就是left右移将移出窗口的单词在hash中–直到hash中出现的次数小于word中次数。
最后只要成功匹配的单词数达到 m 时则表示找到了一个串联子串其left为该字串的起始下标放入result即可。
【算法描述】
//滑动窗口
vectorint findSubstring(string s, vectorstring words)
{vectorint result; //存放结果int m words.size(); //单词数int n words[0].size(); //每个单词的字母数int len s.size();unordered_mapstring, int word; //存放words中的单词及出现的个数for(string str : words){word[str];}//从下标i开始把s划分为字母为n的单词//只需要循环n次就可以划分出所有长度为n的单词因为从i n1开始划分与i 0开始划分的单词是一样的for(int i 0; i n; i) {int left i; //滑窗左指针int right i; //滑窗右指针int count 0; //记录已成功匹配的单词数unordered_mapstring, 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个boxboard[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(vectorvectorchar 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下次再遇见就能够直接返回falserow[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(vectorvectorchar board) {for(int i 0; i 9; i){unordered_setchar hash1; //哈希表存储每一行的每个数是否出现过unordered_setchar 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_setchar hash1;unordered_setchar hash2;unordered_setchar 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 输入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”]] 解释输入的数独如上图所示唯一有效的解决方案如下所示 【算法思路】 状态压缩 使用 bitset9 来压缩存储每一行、每一列、每一个 3x3 宫格中 1-9 是否出现。其中 3x3 宫格的哈希索引可见[36、有效的数独](# 36、有效的数独) 这样每一个格子就可以计算出所有不能填的数字然后得到所有能填的数字用 getPossibleStatus() 函数实现填入数字和回溯时只需要更新存储信息每个格子在使用时会根据存储信息重新计算能填的数字。 回溯 每次都使用 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)对应的格子所有能填的数字bitset9 getPossibleStatus(int x, int y) {return ~(row[x] | col[y] | block[y/3 (x/3)*3]);}// 选择出能填的数字最少的格子坐标vectorint getNext(vectorvectorchar board) {int minCount 10;vectorint v {0, 0};for(int i 0; i 9; i) {for(int j 0; j 9; j) {if(board[i][j] .) {bitset9 bit getPossibleStatus(i, j);if(bit.count() minCount) {minCount bit.count();v {i, j};}}}}return v;}// 回溯遍历直到所有数字都填进去才成功bool dfs(vectorvectorchar board, int count) {if(count 0) {return true;}// 选择出能填数字最少的格子开始填这样填错的概率最小回溯次数也会变少vectorint v getNext(board);// 遍历该格子所有能填的数bitset9 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(vectorvectorchar board) {// 状态压缩 row vectorbitset9 (9, bitset9());col vectorbitset9 (9, bitset9());block vectorbitset9 (9, bitset9());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:vectorbitset9 row; // 行vectorbitset9 col; // 列vectorbitset9 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(vectorint 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”]]
【算法思路】
两个字符串互为字母异位词当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点可以使用相同点作为一组字母异位词的标志使用哈希表存储每一组字母异位词哈希表的键为一组字母异位词的标志(即相同点)哈希表的值为一组字母异位词列表。
遍历每个字符串对于每个字符串得到该字符串所在的一组字母异位词的标志将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后哈希表中的每个键值对即为一组字母异位词。
使用排序来作为哈希表的键值。由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。
【算法描述】
vectorvectorstring groupAnagrams(vectorstring strs)
{vectorvectorstring result; //存放最后结果unordered_mapstring, vectorstring hash; //哈希表//将strs容器中每个字符串str排序以排序后的字符串为key值存放排序前的字符串strfor(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_mapchar, 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中字符若是则加入smapif(tmap.find(s[right]) ! tmap.end()) {smap[s[right]];}// 当前s窗口内子串已经覆盖了t右移左指针记录最小字串while(check(tmap, smap)) {if(minNum right-left1) {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_mapchar, int origin, unordered_mapchar, int count) {for(const auto i : origin) {if(count[i.first] i.second) {return false;}}return true;
}恭喜你全部读完啦古人云温故而知新。赶紧收藏关注起来用之前再翻一翻吧~ 推荐阅读
C/C后端开发面试总结点击进入 后端开发面经 关注走一波
C重点知识点击进入 C重点知识 关注走一波
力扣leetcode题目分类点击进入 leetcode题目分类 关注走一波
