【哈希表与字符串的算法之路：思路与实现】—— LeetCode

两数之和

这题的思路很简单，在读完题目之后，便可以想到暴力枚举，直接遍历整个数组两遍即可，但是时间复杂度高，下面是运行之后的结果

很简单快速的将这个题目写完了，但是有没有更高效，时间复杂度更低的方法呢？
当然！
思路：

• 利用哈希表进行优化已经知道了target，那么遍历让x = target-nums[i]如果x在哈希表中存在，那么就存在这组元素——即结果。

class Solution 
{
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){int x = target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] = i;}return {};}
};

面试题01.02.判定是否为字符重排

这个题目也是一个很经典的题目，也是一个一眼题

• 方法一：直接将两个字符串进行排序，相同就是true，不同就是false。时间复杂度也是最优的

class Solution 
{
public:bool CheckPermutation(string s1, string s2){sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());if(s1 == s2) return true;else return false;}
};

• 方法二：可以用一个数组替代哈希表，将遍历一组字符串进入哈希表，然后再遍历另外一组字符串——从哈希表中依次减少另外一组字符串的个数，最后结果为0便是true，否则剩余数字就是false。

class Solution 
{
public:bool CheckPermutation(string s1, string s2) {if(s1.size() != s2.size()) return false;int hash[26] = { 0 };//先统计第一个字符串的信息for(auto ch : s1)hash[ch - 'a']++;//扫描第二个字符串，看看能不能重排for(auto ch : s2){hash[ch - 'a']--;if(hash[ch - 'a'] < 0) return false;}        return true;}
};

存在重复元素

• 思路：
  将数组一遍遍历，一边插入到哈希表当中，如果遍历到每个元素的时候已经存在该元素，直接返回true即可，如果遍历完之后没有元素了返回false。

class Solution 
{
public:bool containsDuplicate(vector<int>& nums) {// 创建一个无序集合，用于存储nums向量中的唯一元素unordered_set <int> hash;// 遍历nums向量中的每个元素for(auto x : nums){// 如果元素已经在集合中，说明存在重复元素if(hash.count(x)) return true;  // 如果发现重复元素，返回trueelse hash.insert(x);  // 如果没有重复元素，将该元素插入集合中}// 如果遍历完后没有发现任何重复元素，返回falsereturn false;}
};

存在重复元素||

• 思路： 这题跟上面一题基本一样只不过增加了一个| i - j | <= k的条件。

class Solution 
{
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {// 创建一个哈希表，用于存储每个元素及其最后出现的位置unordered_map<int, int> hash;// 遍历nums向量中的每个元素for(int i = 0; i < nums.size(); i++){// 如果当前元素在哈希表中已经存在if(hash.count(nums[i])){// 判断当前索引与该元素上次出现索引的差是否小于等于kif(i - hash[nums[i]] <= k) return true;  // 如果差值小于等于k，返回true，表示找到满足条件的重复元素}// 更新当前元素在哈希表中的位置hash[nums[i]] = i;}// 如果遍历完所有元素都没有找到满足条件的重复元素，返回falsereturn false;}
};

字母异位词分组

• 思路：

1. 排序法：
   对于每个字符串，将其按字母排序。排序后的字符串可以作为它们的“标识符”，即所有字母异位词排序后得到的字符串是相同的。
   例如，“eat”和“tea”排序后都会变成“aet”，这使得我们能够将它们归为一组。

2. 使用哈希表分组：
   使用一个哈希表 unordered_map<string, vector>，其中键是排序后的字符串，值是具有相同排序后的字母异位词的字符串集合。
   对于每个字符串，排序并将它放入对应的组中。如果该组已经存在，就将其添加到对应组里；如果该组不存在，就创建新组。

3. 提取结果：
   最后，从哈希表中提取出所有的字母异位词组并返回。

class Solution 
{
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 创建一个哈希表，key是排序后的字符串，value是与该排序字符串对应的字母异位词列表unordered_map <string, vector<string>> hash;// 1. 将所有字符串排序并分组for(auto& s : strs){// 将字符串复制到tmp中，然后排序string tmp = s;sort(tmp.begin(), tmp.end());// 根据排序后的字符串，将原始字符串加入哈希表的对应组中hash[tmp].push_back(s);}// 2. 从哈希表中提取出结果vector<vector<string>> ret;for(auto&[x, y] : hash){// 将每一组字母异位词加入到结果列表中ret.push_back(y);}// 返回结果return ret;}
};

最长公共前缀和

• 思路：
  这道题的思路是通过逐个字符地检查所有字符串的字符来找出最长公共前缀。从第一个字符串的第一个字符开始，逐个比较该位置上其他字符串的字符是否相同。如果遇到不同的字符或某个字符串的长度不足，就返回当前找到的公共前缀。如果没有遇到不匹配的字符，说明第一个字符串本身就是所有字符串的公共前缀，直接返回它——中心扩展算法

class Solution 
{
public:string longestCommonPrefix(vector<string>& strs) {// 遍历第一个字符串的每一个字符for(int i = 0; i < strs[0].size(); i++){// 获取当前字符char tmp = strs[0][i];// 遍历后续的字符串，检查是否在当前字符位置上与第一个字符串相同for(int j = 1; j < strs.size(); j++){// 如果某个字符串的长度小于等于i，或者字符不匹配，返回从0到i的子串作为公共前缀if(i == strs[j].size() || tmp != strs[j][i])return strs[0].substr(0, i);}}// 如果没有遇到不匹配的情况，说明第一个字符串就是公共前缀return strs[0];}
};

最长回文子串

• 思路：
  这道题要求找到一个字符串中最长的回文子串。回文串是指从前往后和从后往前读都相同的字符串。我们可以通过 中心扩展法 来解决这个问题。每个回文子串都有一个中心，中心可以是一个字符（对于奇数长度回文串）或者两个字符之间（对于偶数长度回文串）。从每个字符（或字符间隙）向外扩展，检查左右两边的字符是否相等，直到不再相等为止。

class Solution 
{
public:string longestPalindrome(string s) {// 获取字符串长度nint n = s.size(), begin = 0, len = 0;// 遍历每个字符，尝试找到以该字符为中心的回文串for(int i = 0; i < n; i++){// 处理奇数长度回文串，以字符s[i]为中心int right = i, left = i;// 扩展左右两边，直到不满足回文条件while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}// 更新最长回文串的起始位置和长度if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}// 处理偶数长度回文串，以字符s[i]和s[i+1]为中心right = i + 1, left = i;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}// 更新最长回文串的起始位置和长度if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}}// 返回最长回文子串return s.substr(begin, len);}
};

二进制求和

• 思路：
  我们从 a 和 b 的末尾（即最低位）开始逐位进行加法运算，类似于手动加法的过程。每一位相加时，判断是否需要进位。进位的处理通过变量 t 来存储，当两位数字加起来大于或等于2时，t 就会向下一位传递进位。最终，逐位的结果被累积到字符串 ret 中，并且需要反转，因为我们从低位到高位计算。整个过程确保处理了两者的不同长度以及最终的进位。

class Solution 
{
public:string addBinary(string a, string b) {string ret; // 用于存储结果的字符串int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0; // cur1, cur2分别是a和b的当前字符索引，t是进位// 遍历两个字符串直到都遍历完并且没有进位while(cur1 >= 0 || cur2 >= 0 || t){// 如果a还有剩余位，取出a对应位置的数字并加到t中if(cur1 >= 0) t += a[cur1--] - '0';  // 如果b还有剩余位，取出b对应位置的数字并加到t中if(cur2 >= 0) t += b[cur2--] - '0';  // 将当前位的结果加到结果字符串中，t % 2是当前位（0或1），进位需要除以2ret += t % 2 + '0';t /= 2; // 更新进位，t // 2}// 由于我们是从低位到高位处理的，最后需要反转结果字符串reverse(ret.begin(), ret.end());return ret; // 返回加法结果的二进制字符串}
};

字符串相乘

• 思路：
  这道题目要求实现两个大整数的乘法。我们不能直接将两个大整数转换为整数进行计算，因为它们的长度可能超出整数类型的表示范围。我们通过模拟竖式乘法的方法来手动计算乘积。首先，我们逆序遍历两个字符串，将每一位的数字相乘并加到临时结果数组中，处理乘法的每一位。然后，我们处理进位，最后将结果反转并处理前导零，得到最终的乘积结果。
  
  

class Solution 
{
public:string multiply(string num1, string num2){// 获取两个字符串的长度int m = num1.size(), n = num2.size();// 反转字符串，以便从低位开始计算reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());// 临时数组用于存储每一位的乘积结果vector<int> tmp(m + n - 1);// 进行无进位的相乘for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');// 处理进位int cur = 0, t = 0;string ret;while(cur < m + n - 1 || t != 0){// 将当前的乘积加到结果中if(cur < m + n - 1) t += tmp[cur++];// 取当前位的数字，并更新进位ret += t % 10 + '0';t /= 10;}// 处理前导零while(ret.size() > 1 && ret.back() == '0') ret.pop_back();// 反转最终的结果字符串reverse(ret.begin(), ret.end());return ret;  // 返回最终的乘积结果}
};