242.有效的字母异位词
题目链接:https://leetcode.cn/problems/valid-anagram/description/
我的代码:
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() == t.size()) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
record[s[i] - 'a']++;
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0)
return false;
}
return true;
} else
return false;
}
};
先比较两字符串长度,长度相同则定义一个数组哈希表,索引值就是字母对于‘a’的相对位置,s遇字母加1,t遇字母减1,若循环结束后哈希数组内值全为0则说明两字符串是字母异位词。
349.两个数组的交集
题目链接:https://leetcode.cn/problems/intersection-of-two-arrays/description/
使用set:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> nums(nums1.begin(), nums1.end());
for (int num : nums2) {
if (nums.find(num) != nums.end()) { // 在nums中查找num值,返回一个迭代器,如果找到,迭代器指向该元素,没有找到,迭代器指向nums.end()
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
std::set和std::multiset底层实现都是红黑树,std::unordered_set的底层实现是哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。
使用数组:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int hash[1005] = {0};
for (int i = 0; i < nums1.size(); i++) {
hash[nums1[i]] = 1;
}
unordered_set<int> result;
for (int i = 0; i < nums2.size(); i++) {
if (hash[nums2[i]] == 1)
result.insert(nums2[i]);
}
return vector<int>(result.begin(), result.end());
}
};
定义哈希数组,全部置0,遍历nums1,给索引置1,遍历nums2,检索到哈希数组元素为1,插入result,其中unordered_set
202.快乐数
题目链接:https://leetcode.cn/problems/happy-number/description/
我的代码:
class Solution {
public:
int getSum(int n) { // 求各位数字平方和的函数
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> record;
while (1) {
int sum = getSum(n);
if (sum == 1) {
return true;
} else if (record.find(sum) != record.end()) {
return false;
} else {
record.insert(sum);
}
n = sum;
}
}
};
此题关键在于判断sum是否重复出现,若出现1,则return true,若重复出现,则出现无限循环,直接return false,同时对求各位数字平方和的函数也要熟练。
1.两数之和
题目链接:https://leetcode.cn/problems/two-sum/description/
我的代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> record;
for (int i = 0; i < nums.size(); i++) {
auto iter = record.find(target - nums[i]);
if (iter != record.end()) {
return {i, iter->second};
}
record.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树,这道题目中并不需要key有序,选择std::unordered_map 效率更高。
标签:202,return,int,随想录,record,vector,set,unordered,两数 From: https://www.cnblogs.com/kurumaruq/p/18345320