目录
哈希表
1. 两数之和
固定一个数, 找前面有没有target - x这个数, 使用哈希表, 每次查找之后把这个数丢入到哈希表中, 哈希表中存储这个数字的下标, 时间复杂度为O(N) , 空间复杂度也为O(N).
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 {-1,-1};
}
};
2. 判断是否为字符重拍排
创建两个哈希表, 依次比较, 但是可以进行优化, 仅需创建一个哈希表, 前面我们可以先处理如果两个字符串长度不相等直接返回false, 然后遍历第二个字符串, 每次遍历之后讲hash对应的位置-- ,如果某个位置减到小于0, 则说明两个字符串不一样, 直接返回false即可
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
if(s1.size () != s2.size()) return false;
int hash[26] = {0};
for(int i = 0; i < s1.size(); i++)
hash[s1[i] - 'a']++;
for(int i = 0; i < s2.size(); i++)
if(--hash[s2[i] - 'a'] < 0)
return false;
return true;
}
};
3. 是否存在重复元素
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> hash;
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]))
return true;
hash[nums[i]]++;
}
return false;
}
};
4. 存在重复元素Ⅱ
如果找到了key和当前元素一样, 那么还需要判断绝对值时候小于k, 只有小于k才能返回, 否则的话更新当前元素的下标存储到哈希表中
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]))
{
if(abs(hash[nums[i]] - i) <= k)
return true;
else hash[nums[i]] = i;
}
hash[nums[i]] = i;
}
return false;
}
};
5. 字母异位词分组
使用哈希表讲字母异位词进行分组, 快速判断是否是字母异位词的方法还有一种就是排序, 排序之后的字符串为key, 原字符串为val进行存储, 就直接进行了分类, 之后遍历hash表, 把y都尾插到返回vector即可.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;
for(auto e : strs)
{
string tmp = e;
sort(tmp.begin(),tmp.end());
hash[tmp].push_back(e);
}
vector<vector<string>> ret;
for(auto [x,y] : hash)
ret.push_back(y);
return ret;
}
};
字符串
1. 最长公共前缀
解法一: 两两比较, 然后求出公共部分
解法二: 同时进行比较, 这里使用解法二, 固定第一个字符串, 将后面所有的字符串都同时与第一个字符串的第一个元素进行比较, 如果不相同直接返回, 如果相同则在本次循环之后ret加上这个字符, 如果循环结束, 则说明第一个字符串就是最长公共前缀.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ret;
for(int i = 0; i < strs[0].size(); i++)
{
char tmp = strs[0][i];
for(int j = 1; j < strs.size(); j++)
{
if(strs[j][i] != tmp)
return ret;
}
ret += tmp;
}
return strs[0];
}
};
2. 最长回文子串
暴力解法: 依次枚举出所有的子数组, 然后在判断是否是回文子串, 时间复杂度为O(N^3) , 并且代码复杂, 这里我们可以使用中心拓展法, 以一个点为中心, 然后向两边进行扩展, 如果相同则指针往两边移动, 统计奇数时只需要left和right在同一个位置, 如果统计偶数回文串时把left = i , right = i + 1即可, 这样就可以统计出所有的回文子串.
class Solution {
public:
string longestPalindrome(string s) {
//中心拓展法
int len = 0, begin = 0, n = s.size();
for(int i = 0; i < n; i++)
{
//奇数回文串
int left = i, right = i;
while(left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if(right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
//偶数回文串
left = i, right = i + 1;
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);
}
};
3. 二进制求和
模拟列竖式即可
class Solution {
public:
string addBinary(string a, string b) {
string ret;
int t = 0 , cur1 = a.size() - 1, cur2 = b.size() - 1;
while(cur1 >= 0 || cur2 >= 0 || t)
{
if(cur1 >= 0) t += a[cur1--] - '0';
if(cur2 >= 0) t += b[cur2--] - '0';
ret += (t % 2) + '0';
t /= 2;
}
reverse(ret.begin(),ret.end());
return ret;
}
};
4. 字符串相乘
算法原理:
整体思路就是模拟我们⼩学列竖式计算两个数相乘的过程。但是为了我们书写代码的⽅便性，我们选择⼀种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位
class Solution {
public:
//无进位相乘
string multiply(string n1, string n2) {
//1.反转
reverse(n1.begin(),n1.end());
reverse(n2.begin(),n2.end());
int m = n1.size(), n = n2.size();
vector<int> tmp(m + n - 1);
//无进位相乘相加
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
//处理进位
int t = 0, cur = 0;
string ret;
while(cur < m + n - 1 || t)
{
if(cur < m + n - 1) t += tmp[cur++];
ret += t % 10 + '0';
t /= 10;
}
//处理前导0
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};
完
标签：hash,string,int,ret,++,算法,表与,哈希,left From： https://blog.csdn.net/2201_75644377/article/details/143092090