互联网行业分为哪几类_bms营销方法_bing搜索引擎下载_张家界seo

哈希表

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;}//处理前导0while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

---

完