算法专题九: 哈希表与字符串

用户11317877

发布于 2024-10-22 13:33:00

9700

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

哈希表

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;
    }
};

完

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

int