《LeetCode题》数据结构入门板块
第1天 数组
217.存在重复元素【简单，哈希表】
题目链接：https://leetcode-cn.com/problems/contains-duplicate/
思路一：数组排序，再遍历。
时间复杂度：O(NlogN)，N为数组长度，排序的复杂度
空间复杂度：O(logN)
class Solution { public: bool containsDuplicate(vector<int>& nums) { sort(nums.begin(), nums.end()); //1.先排序 排序复杂度O(NlogN) int n = nums.size(); for (int i = 0; i < n - 1; i++) { //2.在遍历数组 比较当前元素和下一个元素是否相同 if (nums[i] == nums[i + 1]) { return true; } } return false; } };
思路二：1.哈希表存数；2.再用count函数或find函数查找当前元素哈希表中是否存在；3.存在则返回true；不存在存入当前元素
时间复杂度：O(N)
空间复杂度：O(N)
class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int>s; //无序，只可增删，不可修改 for (int x : nums) { if (s.count(x)) return true; //if (s.find(x) != s.end()) { //find函数返回迭代器 // return true; //} s.insert(x); } return false; } };
53.最大子序和【简单，动态规划，贪心】
题目链接：https://leetcode-cn.com/problems/maximum-subarray/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RcbenvmQ-1636886665415)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113123322039.png)]
思路一：双for循环暴力破解：计算从每一个索引开始的最大子序和
//两for循环暴力破解 //计算从索引0开始的的最大子字符串， 从1开始， 从2开始...... //时间复杂度：O(n^2)， 超出时间限制的 class Solution { public: int maxSubArray(vector<int>& nums) { //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小值 或 最大值 int max = INT_MIN; int n = nums.size(); for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += nums[j]; if (sum > max) { max = sum; } } } return max; } };
思路二：动态规划
时间复杂度：O(n)
空间复杂度：O(n)
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); //先替换元素 for (int i = 1; i < n; i++) { if (nums[i - 1] > 0) { nums[i] = nums[i - 1] + nums[i]; } } //再遍历查找最大值 int res = nums[0]; for (int i : nums) { if (i > res) { res = i; } } return res; } };
我们可以对两个并行for循环进行优化，只用一个for循环解决
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int res = nums[0]; for (int i = 1; i < n; i++) { if (nums[i - 1] > 0) { nums[i] = nums[i - 1] + nums[i]; } if (nums[i] > res) { res = nums[i]; } } return res; } };
接着优化缩短代码，往官方参考答案靠近
class Solution { public: int maxSubArray(vector<int>& nums) { int res = nums[0]; for (int i = 1; i < nums.size(); i++) { nums[i] = max(nums[i], nums[i - 1] + nums[i]); //主要是这句代码 res = max(res, nums[i]); //动态记录最大子序和 } return res; } };
代码随想录动态规划的思路：
五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
53.最大子序和（动态规划）
class Solution { public: int maxSubArray(vector<int>& nums) { if (nums.size() == 0) return 0; vector<int> dp(nums.size()); dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < nums.size(); i++) { dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式 if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值 } return result; } };
思路三：贪心
时间复杂度：O(n)
空间复杂度：O(1)
贪心贪的是哪里呢？
如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
class Solution{ public: int maxSubArray(vector<int>& nums){ //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值 int result = INT_MIN; int sum = 0; for (int i = 0; i < nums.size(); i++){ sum += nums[i]; result = max(result, sum); //如果sum < 0，重新开始找子序串 if (sum < 0){ sum = 0; } } return result; } };
第2天 数组
1.两数之和【简单，哈希表】
题目链接：https://leetcode-cn.com/problems/two-sum/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PybN3GYz-1636886665417)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113130032319.png)]
思路一：双for遍历
class Solution { public: //双for暴力破解 vector<int> twoSum(vector<int>& nums, int target) { vector<int>res; int n = nums.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[j] == target - nums[i]) { res.push_back(i); res.push_back(j); return res; } } } return res; } };
思路二：哈希表
同理可以用unordered_map存入pair对组
class Solution { public: //哈希表 vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); i++) { auto it = hashtable.find(target - nums[i]); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end(); if (it != hashtable.end()) { return { it->second, i }; //返回两个索引 } hashtable[nums[i]] = i; //存数据 } return {}; } };
88.合并两个有序数组【简单，双指针】
题目链接：https://leetcode-cn.com/problems/merge-sorted-array/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ONGhRTIt-1636886665418)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113131043599.png)]
思路一：直接合并，sort排序
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int nums1_length = nums1.size(); for (int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } sort(nums1.begin(), nums1.end()); } };
思路二：双指针，指向两数组开头，从前面扫描，使用多余容器作为合并后的数组
class Solution { public: //方法二，双指针，使用多余容器 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = 0; int p2 = 0; vector<int>res; while (p1 < m || p2 < n) { if (p1 == m) { //nums1排序完了 nums2还有数 res.push_back(nums2[p2]); p2++; continue; } else if (p2 == n) { //nums2排序完了 nums1还有数 res.push_back(nums1[p1]); p1++; continue; } if (nums1[p1] < nums2[p2]) { res.push_back(nums1[p1]); p1++; } else { res.push_back(nums2[p2]); p2++; } } swap(nums1, res); //swap就可以实现两数组交换功能 //for (int i = 0; i < nums1.size(); i++) { // nums1[i] = res[i]; //} } };
思路三：在思路二基础上改进，双指针指向两数组后端，不用多余容器
class Solution { public: //方法三，在方法二基础上改进，不用多余容器 //从后扫描，大的数放在nums1尾部 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = m - 1; //p1中非零元素最后的索引 int p2 = n - 1; int index = nums1.size() - 1; while (p1 >= 0 || p2 >= 0) { if (p1 == -1) { nums1[index] = nums2[p2]; p2--; index--; continue; } else if (p2 == -1) { nums1[index] = nums1[p1]; p1--; index--; continue; } if (nums1[p1] > nums2[p2]) { nums1[index] = nums1[p1]; p1--; index--; } else { nums1[index] = nums2[p2]; p2--; index--; } } } };
还可以在上面优化
class Solution { public: //方法三，在方法二基础上改进，不用多余容器 //从后扫描，大的数放在nums1尾部 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = m - 1; //p1中非零元素最后的索引 int p2 = n - 1; int index = nums1.size() - 1; while (p2 >= 0) { //nums1前面本来就是有序的，所以只要nums2排序完即可 if (p1 == -1) { nums1[index] = nums2[p2]; p2--; index--; continue; } if (nums1[p1] > nums2[p2]) { nums1[index] = nums1[p1]; p1--; index--; } else { nums1[index] = nums2[p2]; p2--; index--; } } } };
第3天 数组
350.两个数组的交集II【简单，哈希表，双指针】
题目链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
349.两个数组的交集：https://leetcode-cn.com/problems/intersection-of-two-arrays/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CUCHsfWg-1636886665420)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113133115597.png)]
思路一：哈希表计数，消消乐
class Solution { public: //哈希表 哈希表计数真猛 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() > nums2.size()) { return intersect(nums2, nums1); //套娃 保证nums2长度大于nums1 } unordered_map <int, int> m; //哈希表存数 for (int num : nums1) { ++m[num]; //键为数，值为出现的次数 } vector<int> intersection; for (int num : nums2) { if (m.count(num)) { //count是查询是否有这个键 intersection.push_back(num); //说明为交集 添加到结果中 --m[num]; if (m[num] == 0) { m.erase(num); } } } return intersection; } };
思路二：排序+双指针遍历
class Solution { public: //排序 双指针遍历 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); vector<int> intersection; int index1 = 0; int index2 = 0; while (index1 < nums1.size() && index2 < nums2.size()) { if (nums1[index1] < nums2[index2]) { index1++; } else if (nums1[index1] > nums2[index2]) { index2++; } else { //相等的情况 intersection.push_back(nums1[index1]); index1++; index2++; } } return intersection; } };
121.买卖股票的最佳时机【简单，贪心，动态规划】
题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZYdQ2Icu-1636886665421)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113141456343.png)]
思路一：双for暴力破解；思路和53.最大子序和很像
class Solution { public: //双for循环暴力破解 超出时间限制 int maxProfit01(vector<int>& prices) { int n = prices.size(); int max_fit = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { max_fit = max(max_fit, prices[j] - prices[i]); //if (prices[j] - prices[i] > max_fit) { // max_fit = prices[j] - prices[i]; //} } } return max_fit > 0 ? max_fit : 0; } };
思路二：贪心
股票，去数组左边的最小值，右边的最大值，差值即为最大利润
时间复杂度：O(n) 一次for循环遍历
空间复杂度：O(1)
class Solution { public: int maxProfit(vector<int>& prices) { int low = INT_MAX; int result = 0; for (int i = 0; i < prices.size(); i++) { low = min(low, prices[i]); // 取最左最小价格 result = max(result, prices[i] - low); // 直接取最大区间利润 } return result; } };
思路三：动态规划
有点难，下次再来补充
以下是同一类型的题号
股票问题
第4天 数组
566. 重塑矩阵【简单】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-scbFl0st-1636886665422)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113150817851.png)]
题目意思：对二维数组的shape进行变换
class Solution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int m = nums.size(); //行数 int n = nums[0].size(); //列数 if (m * n != r * c) { //1.肯定需要变换前后元素个数得满足条件 return nums; } vector<vector<int>> ans(r, vector<int>(c)); //r行， for (int x = 0; x < m * n; ++x) { //2.进行变换，主要是这里的代码 ans[x / c][x % c] = nums[x / n][x % n]; } return ans; } };
118. 杨辉三角【简单】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OLP5XKv0-1636886665423)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113151059349.png)]
class Solution { public: //根据杨辉三角的规律，创建一个容器嵌套容器 vector<vector<int>> generate(int numRows) { vector<vector<int>> ret(numRows); for (int i = 0; i < numRows; ++i) { ret[i].resize(i + 1); //每行扩容 ret[i][0] = ret[i][i] = 1; //每行第一个元素和最后一个元素为1 杨辉三角的特点 for (int j = 1; j < i; ++j) { //遍历每行中元素，为其赋值 ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1]; } } return ret; } };
第5天 数组
36. 有效的数独【中等，桶】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JcsPPsLo-1636886665424)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113151440216.png)]
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { //生成桶 int rows[9][9] = {0}; //9行 int columns[9][9] = {0}; //9列 int subboxes[3][3][9] = {0}; //9个3*3 //双for暴力遍历破解 for (int i = 0; i < 9; i++) { //遍历行 for (int j = 0; j < 9; j++) { //遍历列 char c = board[i][j]; if (c != '.') { int index = c - '0' - 1; //char转化为int char为0~9，index为0~8； 所以-1 rows[i][index]++; columns[j][index]++; subboxes[i / 3][j / 3][index]++; if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) { return false; } } } } return true; } };
73. 矩阵置零【中等】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-McX17QSK-1636886665425)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113152105570.png)]
思路一：记录每个值为0的行列值；然后遍历对特定行特定列置零
class Solution { public: //时间复杂度：O(mn) 空间复杂度：O(0的个数) void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); //行数 int n = matrix[0].size(); //列数 //unordered_map<int, int> pairs; unordered_multimap<int, int> pairs; for (int i = 0; i < m; i++) { //1.哈希表记录0元素的行列位置，存为对组 for (int j = 0; j < n; j++) { if(matrix[i][j] == 0){ //pairs[i] = j; pairs.insert({ i,j }); } } } //2.遍历哈希表的对组，把行列元素置零 for (unordered_multimap<int, int>::iterator it = pairs.begin(); it != pairs.end(); it++) { for (int i = 0; i < m; i++) { matrix[i][(*it).second] = 0; //特定列置零 } for (int j = 0; j < n; j++) { matrix[(*it).first][j] = 0; //特定行置零 } } } };
优化：换成vector容器存储对组，对组为行列
class Solution { public: //时间复杂度：O(mn) 空间复杂度：O(0的个数) void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); //行数 int n = matrix[0].size(); //列数 vector<pair<int, int>>v; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { v.push_back(make_pair(i, j)); } } } for (auto pair : v) { for (int i = 0; i < m; i++) { //特定列置零 matrix[i][pair.second] = 0; } for (int j = 0; j < n; j++) { //特定行置零 matrix[pair.first][j] = 0; } } } };
官方答案为两个容器分别记录值为0的行列
class Solution { public: //使用标记数组 时间复杂度：O(mn) 空间复杂度：O(m+n) void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<int> row(m), col(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!matrix[i][j]) { //标记元素为0的行列 row[i] = col[j] = true; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } } };
思路二：使用两个标记变量
我们可以用矩阵的第一行和第一列代替上面方法中的两个标记数组，以达到 O(1)的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可
时间复杂度：O(mn)
空间复杂度：O(1)，常数空间
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); int flag_col0 = false, flag_row0 = false; for (int i = 0; i < m; i++) { //标记第一列是否有0 if (!matrix[i][0]) { flag_col0 = true; } } for (int j = 0; j < n; j++) { //标记第一行是否有0 if (!matrix[0][j]) { flag_row0 = true; } } for (int i = 1; i < m; i++) { //查看中间是否有0 for (int j = 1; j < n; j++) { if (!matrix[i][j]) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = 1; i < m; i++) { //中间内容置零 for (int j = 1; j < n; j++) { if (!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } } if (flag_col0) { //第一列置零 for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flag_row0) { //第一行置零 for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } };
第6天 字符串
387. 字符串中的第一个唯一字符【简单】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YK8hdxsM-1636886665426)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211113170921415.png)]
思路一：哈希表存键值对，键为元素，值为出现次数
class Solution { public: int firstUniqChar(string s) { unordered_map<char, int> pairs; int n = s.size(); for (int i = 0; i < n; i++) { //1.第一次遍历 先哈希表存入所有数 和元素出现的次数 pairs[s[i]]++; } for (int i = 0; i < n; i++) { //2.第二次遍历 查找哈希表中第一个出现次数为1的元素 返回其索引 if (pairs[s[i]] == 1) { return i; } } return -1; } };
思路二：使用find和rfind查找函数看是索引否相等
class Solution { public: //时间复杂度高， for嵌套find int firstUniqChar(string s) { for (int i = 0; i < s.size(); i++) { //1.从前往后遍历 if (s.find(s[i]) == s.rfind(s[i])) //2.find从前面开始查找 rfind从后面开始查找 如果查找到的两个索引不一样 说明查找到了不同位置 return i; //说明有两个元素； 索引位置一样则就一个元素 } return -1; } };
383. 赎金信【简单，哈希表，桶计数】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t4Uy14qC-1636886665427)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114125953222.png)]
题目意思：判断第二个字符串是不是包含第一个字符串的所有元素
思路一：桶排序
class Solution { public: //计数法 来26个桶装数据 //遍历母串+1， 遍历子串-1， 最终桶中有没有负数 bool canConstruct(string ransomNote, string magazine) { int tong[26] = { 0 }; //1.生成26个桶 for (char s : magazine) { //2.第一次遍历 把主串所有字符计数 int i = s - 'a'; tong[i]++; } for (char s : ransomNote) { //3.第二次遍历 把子串所有字符减数 int i = s - 'a'; tong[i]--; } //最后一个for有无效的遍历，可以优化 for (int i : tong) { //4.第三次遍历 判断是否有桶中的计数为负数的 说明子串中有元素在主串中没有 则输出false if (i < 0) { return false; } } return true; } };
第二次遍历和第二次遍历可以合起来优化，优化结果如下：
class Solution { public: //计数法 来26个桶装数据 //遍历母串+1， 遍历子串-1， 最终桶中有没有负数 bool canConstruct(string ransomNote, string magazine) { int tong[26] = { 0 }; //1.生成26个桶 for (char s : magazine) { //2.第一次遍历 把主串所有字符计数 int i = s - 'a'; tong[i]++; } for (char s : ransomNote) { //3.第二次遍历 把子串所有字符减数 int i = s - 'a'; tong[i]--; if (tong[i] < 0) return false; //判断减数之后是否小于0 小于0说明该元素子串有而主串没有 返回false } return true; } };
思路二：哈希表计数
class Solution { public: //哈希表计数 bool canConstruct(string ransomNote, string magazine) { unordered_map<char, int> res; //生成哈希表 对组（元素，元素出现的次数） for (char s : magazine) { //1.第一次遍历 把主串计数 res[s]++; } for (char s : ransomNote) { //2.第二次遍历 子串计数 即哈希表减数 if (res.count(s)) { //如果哈希表中有这个元素 if (res[s] == 0) { //但是次数为0 再减1就成-1了 所以返回false return false; } res[s]--; //次数不为1 则可以减1 } else { return false; //哈希表中没有这个元素 则返回false } } return true; } };
242. 有效的字母异位词【简单，桶计数，哈希表】
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ml1k1p2o-1636886665427)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114132826787.png)]
题目意思：判断两字符串长度是否相等，元素是否相同
思路一：桶计数
class Solution { public: //桶排序 bool isAnagram(string s, string t) { int tong[26] = { 0 }; for (char ch : s) { //1.第一次循环，第一个字符串计数 int i = ch - 'a'; tong[i]++; } for (char ch : t) { //2.第二次for循环，第二个字符串减数 int i = ch - 'a'; tong[i]--; } for (int i : tong) { //3.第三次for循环 判断桶中计数是否都为0 if (i != 0) { return false; } } return true; } };
优化：分两次for解决
class Solution { public: //桶排序 bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; //1.先判断长度是否相等 int tong[26] = { 0 }; for (int i = 0; i < s.size(); i++) { //2.第一个字符串计数 第二个字符串减数 tong[s[i] - 'a']++; tong[t[i] - 'a']--; } for (int i : tong) { //3.第二次遍历 判断桶中计数是否都为0 if (i != 0) return false; } return true; } };
思路二：骚操作，对两字符串排序，再判断相等
排序时间复杂度高，玩玩可以
class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; //1.先判断长度是否相等 sort(s.begin(), s.end()); //2.在排序 sort(t.begin(), t.end()); return s == t; //3.原来字符串可以这样判断相等 //for (int i = 0; i < s.size(); i++) { // if (s[i] != t[i]) { // return false; // } //} //return true; };
思路三：哈希表
class Solution { public: //哈希表计数 bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; //1.先判断长度是否相等 unordered_map<char, int> res; //2.哈希表计数 第一字符串 对组（元素，元素出现次数） for (char ch : s) { res[ch]++; } for (char ch : t) { //3.哈希表减数 第二字符串 if (!res.count(ch)) { return false; } res[ch]--; //最后>0的情况呢 //if (res[ch] < 0) { // return false; //} } for (unordered_map<char, int>::iterator it = res.begin(); it != res.end(); it++) { //4.遍历哈希表 看计数次数是否都为0 if ((*it).second != 0) { return false; } } return true; } };
同样可以优化成两个for，减少代码量
class Solution { public: //哈希表计数 bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; //1.先判断长度是否相等 unordered_map<char, int> res; //2.哈希表计数 对组（元素，元素出现次数） for (int i = 0; i < s.size(); i++) { res[s[i] - 'a']++; //第一个字符串 计数++ res[t[i] - 'a']--; //第二个字符串 计数-- } for (unordered_map<char, int>::iterator it = res.begin(); it != res.end(); it++) { //3.遍历哈希表 看计数次数是否都为0 if ((*it).second != 0) { return false; } } return true; } };
