网站建设学什么的,建工集团领导班子名单,全国公路建设信用网站,电商网站搜索引擎怎么做3.1 哈希表理论基础
哈希表理论基础
3.2 有效的字母异位词
242.有效的字母异位词 C
bool isAnagram(char * s, char * t){int array[26] {0};int i 0;while (s[i]) {// 并不需要记住字符的ASCII码#xff0c;只需要求出一个相对数值就可以了array[s[i] - a];i;}i 0;whi…3.1 哈希表理论基础
哈希表理论基础
3.2 有效的字母异位词
242.有效的字母异位词 C
bool isAnagram(char * s, char * t){int array[26] {0};int i 0;while (s[i]) {// 并不需要记住字符的ASCII码只需要求出一个相对数值就可以了array[s[i] - a];i;}i 0;while (t[i]) {array[t[i] - a]--;i;}for (i 0; i 26; i) {// 如果数组有元素不为0说明字符串s和t 一定是谁多了字符或者谁少了字符if (array[i] ! 0)return false;}// 数组所有元素都为0说明字符串s和t是字母异位词return true;
}cpp
class Solution {
public:bool isAnagram(string s, string t) {int array[26] {0};for (int i 0; i s.size(); i) {array[s[i] - a];}for (int j 0; j t.size(); j) {array[t[j] - a]--;}for (int k 0; k 26; k) {if (array[k] ! 0) {return false;}}return true;}
};383.赎金信 c
bool canConstruct(char * ransomNote, char * magazine){int array[26] {0};if (strlen(ransomNote) strlen(magazine)) return false;int i 0;while (magazine[i]) {array[magazine[i] - a];i;}i 0;while(ransomNote[i]) {array[ransomNote[i] - a]--;if (array[ransomNote[i] - a] 0)return false;i;}return true;
}cpp
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.length() magazine.length()) {return false;}int array[26] {0};for (int i 0; i magazine.length(); i) {array[magazine[i] - a];}for (int j 0; j ransomNote.length(); j) {array[ransomNote[j] - a]--;if (array[ransomNote[j] - a] 0) {return false;}}return true;}
};49. 字母异位词分组 class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {vectorvectorstring result;unordered_mapstring, vectorstring map;for (string s : strs) {string key s;sort(key.begin(), key.end());map[key].emplace_back(s);}for (auto it : map) result.emplace_back(it.second);return result;}
};438. 找到字符串中所有字母异位词滑动窗口哈希 class Solution {
public:vectorint findAnagrams(string s, string p) {int len_s s.length();int len_p p.length();if (len_s len_p)return vectorint ();vectorint count_s(26);vectorint count_p(26);vectorint res;for (int i 0; i len_p; i) {count_s[s[i] - a];count_p[p[i] - a];}if (count_s count_p)res.push_back(0);for (int j 0; j len_s - len_p; j) {count_s[s[j] - a]--;count_s[s[j len_p] - a];if (count_s count_p)res.push_back(j 1); // 注意这里左边已经移动了一位了所以要加1}return res;}
};3.3 两个数组的交集
349. 两个数组的交集 c语言
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize nums1Size nums2Size ? nums1Size : nums2Size;// 用calloc直接全部初始化为0malloc则是随机值int *res calloc(lessSize, sizeof(int));int hash[1001] {0};for (int i 0; i nums1Size; i) {hash[nums1[i]];}int count 0;for (int j 0; j nums2Size; j) {if (hash[nums2[j]] 0) {res[count] nums2[j];}hash[nums2[j]] 0;}*returnSize count;return res;
}cpp 解法一
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result;// 存放结果之所以用unordered_set是为了给结果去重unordered_setint set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2中的结果在set中出现过if (set.find(num) ! set.end()) {result.insert(num);}}return vectorint (result.begin(), result.end());}
};解法二
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result;int hash[1001] {0};for (int n1 : nums1) {hash[n1] 1;}for (int n2 : nums2) {if (hash[n2] 1) {result.insert(n2);}}return vectorint(result.begin(), result.end());}
};350. 两个数组的交集||
C语言
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize nums1Size nums2Size ? nums1Size : nums2Size;int* ret calloc(lessSize, sizeof(int));int hash[1001] {0};int count 0;int i;for (i 0; i nums1Size; i) {hash[nums1[i]];}for (i 0; i nums2Size; i) {if (hash[nums2[i]] 0) {ret[count] nums2[i];hash[nums2[i]]--;}}*returnSize count;return ret;
}C
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_mapint, int num_map;for (int n1 : nums1) {num_map[n1];}vectorint res;for (int num : nums2) {if (num_map.count(num)) {res.push_back(num);num_map[num]--; if (num_map[num] 0) {num_map.erase(num);}}}return res;}
};3.4 快乐数unordered_set
202. 快乐数 class Solution {
public:int getSum(int n) {int sum 0;while (n) {sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {if (1 n)return true;unordered_setint sum_set;int sum 0;while (1) {sum getSum(n);if (1 sum)return true;// 如果这个sum曾经出现过说明已经陷入了无限循环了立刻return falseif (sum_set.find(sum) ! sum_set.end()) {return false;} else {sum_set.insert(sum);n sum;}}}
};3.5 两数之和unorderd_map)
1.两数之和 class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int map;for (int i 0; i nums.size(); i) {int s target - nums[i];auto iter map.find(s);// 遍历当前元素并在map中寻找是否有匹配的keyif (iter ! map.end()) {return {iter-second, i};} else {// 如果没找到匹配对就把访问过的元素和下标加入到map中map.insert(pairint, int(nums[i], i));}}return {};}
};3.6 四数相加||
454. 四数相加|| class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint, int map; //key:ab的数值value:ab数值出现的次数int target 0;int count 0;// 统计abcd 0 出现的次数// 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中for (int a : nums1) {for (int b : nums2)map[a b];}// 在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话//就把map中key对应的value也就是出现次数统计出来。for (int c : nums3) {for (int d : nums4) {target 0 - (c d);if (map.find(target) ! map.end()) {count map[target];}}}return count;}
};3.7 赎金信
383.赎金信 class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.length() magazine.length()) return false;int array[26] {0};for (char s1 : magazine) {array[s1 - a];}for (char s2 : ransomNote) {array[s2 - a]--;if (array[s2 - a] 0)return false;}return true;}
};3.8 三数之和
15.三数之和 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(), nums.end());// 排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了for (int i 0; i nums.size(); i) {if (nums[i] 0) return res;// 正确去重a方法if (i 0 nums[i] nums[i - 1]) continue;int left i 1;int right nums.size() - 1;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 0) right--;else if (sum 0)left;else {res.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (left right nums[right] nums[right - 1])right--;while (left right nums[left] nums[left 1])left;// 找到答案时双指针同时收缩right--;left;}}}return res;}
};3.9 四数之和
18. 四数之和 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint res;sort(nums.begin(), nums.end());// 一级剪枝for (int k 0; k nums.size(); k) {if (nums[k] target nums[k] 0)break; // 这里使用break统一通过最后的return返回// 一级去重对nums[k]去重if (k 0 nums[k] nums[k - 1])continue;for (int i k 1; i nums.size(); i) {// 二级剪枝if (nums[k] nums[i] target nums[k] nums[i] 0)break;// 二级去重对nums[i]去重if (i k 1 nums[i] nums[i - 1])continue;int left i 1;int right nums.size() - 1;while (left right) {// 会溢出long sum (long)nums[k] nums[i] nums[left] nums[right];if (sum target)right--;else if (sum target)left;else {res.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对nums[left]和nums[right]去重while (left right nums[right] nums[right - 1])right--;while (left right nums[left] nums[left 1])left;// 找到答案时双指针同时收缩right--;left;}}}}return res;}
};参考《代码随想录》哈希表
