哈希表与字符串的算法之路思路与实现-LeetCode
目录
【哈希表与字符串的算法之路：思路与实现】—— 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 {};
}
};
这个题目也是一个很经典的题目，也是一个一眼题
- 方法一：直接将两个字符串进行排序，相同就是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; // 如果发现重复元素，返回true
else
hash.insert(x); // 如果没有重复元素，将该元素插入集合中
}
// 如果遍历完后没有发现任何重复元素，返回false
return 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]))
{
// 判断当前索引与该元素上次出现索引的差是否小于等于k
if(i - hash[nums[i]] <= k)
return true; // 如果差值小于等于k，返回true，表示找到满足条件的重复元素
}
// 更新当前元素在哈希表中的位置
hash[nums[i]] = i;
}
// 如果遍历完所有元素都没有找到满足条件的重复元素，返回false
return false;
}
};
- 思路：
排序法：
对于每个字符串，将其按字母排序。排序后的字符串可以作为它们的“标识符”，即所有字母异位词排序后得到的字符串是相同的。
例如，“eat”和“tea”排序后都会变成“aet”，这使得我们能够将它们归为一组。
使用哈希表分组：
使用一个哈希表 unordered_map<string, vector>，其中键是排序后的字符串，值是具有相同排序后的字母异位词的字符串集合。
对于每个字符串，排序并将它放入对应的组中。如果该组已经存在，就将其添加到对应组里；如果该组不存在，就创建新组。
提取结果：
最后，从哈希表中提取出所有的字母异位词组并返回。
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)
{
// 获取字符串长度n
int 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），进位需要除以2
ret += 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; // 返回最终的乘积结果
}
};