LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。
集合set的使用
t1两个数组的交集
求两个集合的交集，重复元素计算一次。
思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int>set1;
set<int>set2;
vector<int> ans;
for(int i = 0; i < nums1.size(); i++)
set1.insert(nums1[i]);
for(int i = 0; i < nums2.size(); i++)
set2.insert(nums2[i]);
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans));
return ans;
}
};
t2快乐数
题目定义了一种数，当且仅当一个数进行一系列逐位平方和计算后能得到1时，它被称为快乐数。一个数如果不是快乐数，他一定无法通过逐位计算平方和最后得到1.
根据题目定义去计算平方和，把每一次的答案扔进一个set里，每次计算完后查询当前值是否之前计算得到过，如果是，那么可以直接return false。循环边界是当前数字为1.
class Solution {
public:
bool isHappy(int n) {
set<int>ss;
while(1)
{
if(n == 1)
return true;
int res = 0;
while(n > 0)
{
int tmp = n % 10;
res += tmp * tmp;
n /= 10;
if(ss.count(res))
return false;
ss.insert(res);
n = res;
}
}
}
};
t3存在重复元素
给定一个序列，判断它内部是否存在重复的元素。
没什么难度，最水的一道，用一个set来存序列，每次计算判断当前元素是否在之前出现过就行。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int>ss;
int n = nums.size();
for(int i = 0; i < n; i++)
{
if(ss.count(nums[i])) return true;
ss.insert(nums[i]);
}
return false;
}
};
字典dict的使用
t1两个数组的交集II
求两个数组的交集，重复元素多次计算。
跟set里的那道题很像，但这次用map来辅助判断出现次数。
用map记录第一个数组中出现过的每个元素的次数，再去遍历第二个数组。每次遍历判断当前数字在第一个数组中是否出现过，如果是就把当前数字添加到答案，并减去一个次数。若次数耗尽就在map中移除这个数字。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int>ans;
map<int, int>mp;
for(auto el: nums1)
mp[el]++;
for(auto el: nums2)
{
if(mp.count(el))
{
ans.push_back(el);
mp[el]--;
if(!mp[el])
mp.erase(el);
}
}
return ans;
}
};
t2有效的字母异位词
给出两个单词，判断它们是否互为异位词。异位词是指两个单词组成字母完全相同，只是排布顺序不同。
跟上一题有异曲同工的地方。用一个map记录第一个单词中所有字母出现的次数，再去遍历第二个单词，出现一个相同字母就消耗一个次数，没有次数就在map中移除这个单词。最后判断匹配成功的次数是否同时等于两个单词的长度。
class Solution {
public:
bool isAnagram(string s, string t) {
map<char, int>mp;
for(int i = 0; i < s.length(); i++)
mp[s[i]]++;
int cmp = 0;
for(int i = 0; i < t.length(); i++)
{
if(mp.count(t[i]))
{
cmp++;
mp[t[i]]--;
if(!mp[t[i]])
mp.erase(t[i]);
}
}
return (cmp == s.length()) && (s.length() == t.length());
}
};
t3同构字符串
给出两个字符串，判断它们是否是同构地。同构字符串是指两个字符串的组成形式一致，如“egg”与“pdd”都是“122”形式。
有两种做法。第一种是用map保存当前字母在单词中第一次出现的下标位置，然后创造一个变型串，在变型串中把原串的每个字母替换成map中保存的下标，即将“pdd”转化成“122”，最后比较两个单词的变型串，以此为依据来得到答案。
class Solution {
public:
bool isIsomorphic(string s, string t) {
set<char>ss;
map<char, int>mp;
string s1, t1;
int key;
if(s.length() != t.length()) return false;
ss.clear();
mp.clear();
key = 1;
for(int i = 0; i < s.length(); i++)
{
if(!ss.count(s[i]))
{
mp[s[i]] = key;
ss.insert(s[i]);
key++;
}
s1 += to_string(mp[s[i]]);
}
ss.clear();
mp.clear();
key = 1;
for(int i = 0; i < t.length(); i++)
{
if(!ss.count(t[i]))
{
mp[t[i]] = key;
ss.insert(t[i]);
key++;
}
t1 += to_string(mp[t[i]]);
}
//cout << s1 << endl << t1 << endl;
return t1 == s1;
}
};
这个代码中的set其实可以不用，map本身也可以起到判断存在的作用。
第二种做法是在学习题解中学会的，很简洁巧妙，思路也是同源地。对于两个互为同构串的单词，他们的形态是一致地，那么对于两个同构串中位于同一个下标上的每个字母，它们上一次出现的下标也一定是一致地。根据这个点就可以得到第二种代码：
class Solution {
public:
bool isIsomorphic(string s, string t) {
map<char, int>mp1;
map<char, int>mp2;
for(int i = 0; i < s.length(); i++)
{
if(mp1[s[i]] != mp2[t[i]]) return false;
mp1[s[i]] = i;
mp2[t[i]] = i;
}
return true;
}
};
两个map分别保存两个单词中每一位字母上一次出现的位置。这个做法相当巧妙。
t4根据字符出现频率排序
给定一个字符串，根据字母出现的频率重新给单词排序。相同字母要出现在一起，如“aaccca”不可重排为“acacac”，而应该排成“aaaccc”或“cccaaa”。
用一个map存单词中每个字母出现的次数，再对map以次数为关键字排序，从头取出每个字母组成一个新的单词即可。
class Solution {
public:
static bool cmp(const pair<char, int>& a, const pair<char, int>& b)
{
return a.second > b.second;
}
string frequencySort(string s) {
string ans = "";
map<char, int>mp;
for(auto ch: s) mp[ch]++;
vector<pair<char, int>>arr(mp.begin(), mp.end());
sort(arr.begin(), arr.end(), cmp);
for(auto el: arr)
while(el.second--)
ans += el.first;
return ans;
}
};
查找表与求和问题
t1两数之和
给定一个数组与一个目标值，在数组中找到两个数使得他们之和等于目标值，返回这两个数的下标。
用map保存每个数的下标，遍历时检测(目标值-当前数)是否存在在数组中，若存在则可以返回答案。
保存时选择下标+1作为数据，防止处理下标为0的情况。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int, int>mp;
for(int i = 0; i < nums.size(); i++)
{
//防止自己加自己
if(mp[target - nums[i]] && mp[target-nums[i]] != i + 1)
{
ans.push_back(i);
ans.push_back(mp[target-nums[i]]-1);
return ans;
}
mp[nums[i]] = i + 1;
}
return ans;
}
};
t2三数之和
给定一个数组，找出所有和为零的三元组。
这题给超时超傻了，最后看了题解。先讲我自己的做法吧，313个cases过了311个，要不是无序集合不能存tuple估计我就过了。只能说这道题确实不太适合用hash来做。
目标是寻找符合要求的三元组，显然直接三重循环是会爆t的，所以选择定一动二，即使用两重循环枚举第一个与第二个数，在内重循环计算0-(i+j)。这样可以吧时间复杂度降到O(n²)。
用一个map来记录数组中出现过的数、一个set来给三元组们去重。每次计算时检测0-(i+j)是否在数组中，若在且该三元组并未在之前出现过，那么将它加入答案。
值得注意的是，C++中{-1,0,1}与{-1,1,0}被视为两个不同的元组，即使他们组成成员是相同的。所以为了确保同一个元组在作为答案时存在唯一性，需要用一个方法来保证每个元组被计算得到时是有序的，这样才能起到去重作用。
//311/313 cases passed
class Solution {
public:
//元组排序方法
inline static tuple<int, int, int> tSort(tuple<int,int,int>tt)
{
int a = get<0>(tt), b = get<1>(tt), c = get<2>(tt);
int maxn = max(a, max(b, c));
int mini = min(a, min(b, c));
int mid = (a + b + c) - (maxn + mini);
return {mini, mid, maxn};
}
vector<vector<int>> threeSum(vector<int>& nums) {
set<tuple<int,int,int>> mys;
vector<vector<int>> ans;
const int n = nums.size();
for(int i = 0; i < n; i++)
{
unordered_map<int, int> mp;
for(int j = i+1; j < n; j++)
{
int tmp = 0 - (nums[i] + nums[j]);
tuple<int, int, int> tt(nums[i], nums[j], tmp);
tt = tSort(tt);
if((mp[tmp]) && (!mys.count(tt)))
{
//printf("%d,%d,%d\n", get<0>(tt), get<1>(tt), get<2>(tt));
ans.push_back({get<0>(tt), get<1>(tt), get<2>(tt)});
mys.insert(tt);
mp[tmp]--;
}
else mp[nums[j]]++;
}
}
return ans;
}
};
这样做几乎快通过了，但还是差两个点，于是用了法2。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>ans;
const int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++)
{
if(nums[i] > 0) continue;
if(i > 0 && nums[i] == nums[i-1]) continue;
unordered_set<int>mys;
for(int j = i+1; j < n; j++)
{
if(j > i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) continue;
int tmp = 0 - (nums[i] + nums[j]);
if(mys.count(tmp))
{
ans.push_back({nums[i], nums[j], tmp});
mys.erase(tmp);
}
else mys.insert(nums[j]);
}
}
return ans;
}
};
t3四数之和
思路跟二三数之和完全一致，但数据规模的提升使得C++语言下不再适合使用hash来解答，不符合我专题训练的目的，遂跳之。事实上二三四数之和用排序+双指针都能获得较之hash法近十倍优秀的效率，实际运用时并不推荐用hash做此类题目，在此仅作练习目的。
灵活选择键值
t1四数相加 II
给定四个数组，每个数组中选择一个元素，统计元素和为零的四元组个数。
思路也很简单。因为有四个成员，显然不可能直接枚举，所以定二动二。
用两重循环枚举Ai+Bj，把它存入map，然后再用另外的两重循环枚举0-Ci-Dj是否在map中，若是则累加器累加上其出现的次数，最后就是答案。
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int ans = 0;
map<int, int>mp;
for(int i = 0; i < A.size(); i++)
for(int j = 0; j < B.size(); j++)
mp[A[i] + B[j]]++;
for(int i = 0; i < C.size(); i++)
for(int j = 0; j < D.size(); j++)
if(mp[0 - C[i] - D[j]])
ans += mp[0 - C[i] - D[j]];
return ans;
}
};
t2字母异位词分组
给出一系列单词，把同属于一类异位词的单词分到一组。异位词是指字母组成相同，但位置不一定相同的一系列单词。
这里的键值设置有一些巧妙。用一个map，键设置为string，值为string的vector。
每次读入一个string，将它排序。根据定义，异位词的组成字母一定是一样的，所以同属一类的异位词在排序后一定都是同一个单词，然后将这同一类的单词压入当前键值所映射的vector中。最后在挨个把每个vector压入答案中即可。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<string, vector<string>> mp;
vector<vector<string>> ans;
for(string s: strs)
{
string tmp = s;
sort(tmp.begin(), tmp.end());
mp[tmp].push_back(s);
}
for(auto el: mp)
ans.push_back(el.second);
return ans;
}
};
t3回旋镖的数量
给出若干个二维点，定义一个三元组为回旋镖，当且仅当组成它的三个点中有一个点到另外两个点的距离相等，找出这组二维点中回旋镖的数量。
定一动一。对于每个点i，枚举计算每个点j到它的距离，以这个距离为键，以其值为累加器计算距离为|(i,j)|的线段的个数，统计这个个数即为答案。
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int ans = 0;
const int n = points.size();
for(int i = 0; i < n; i++)
{
map<int, int> mp;
for(int j = 0; j < n; j++)
{
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
mp[dx * dx + dy * dy]++;
}
for(auto el: mp)
ans += el.second * (el.second - 1);
}
return ans;
}
};
t4直线上最多的点数
给定一系列二维点，求最多有多少个共线的点。
这是一道hard，但其实没那么难，因为题设有个隐藏设定：平行也算作共线。
所以我们可以直接用斜率做map的键，值做累加器来统计同在一条直线上的点。
具体来讲就是两重循环定一动一去枚举所有的点，以斜率为键来记录同在一条直线上的点的个数，最后统计最大值就可以了。
需要注意的点有两个。第一个是这题有一个数据存在精度问题，所以不能用double做键表示斜率，我采用的是string；第二个是处理原点的问题，我选择的是单独用一个累加变量，检测到0直接++然后continue就行了。
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int ans = 0;
const int n = points.size();
if(n < 3) return n;
for(int i = 0; i < n; i++)
{
int cnt = 0;
int curMax = 0;
map<string, int>mp;
for(int j = i+1; j < n; j++)
{
if(points[i][0] == points[j][0]
&& points[i][1] == points[j][1])
{
cnt++;
continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int tmp = gcd(dx, dy);
string key = to_string(dx / tmp) + "/" + to_string(dy / tmp);
//cout << key << endl;
mp[key]++;
curMax = max(curMax, mp[key]);
}
ans = max(ans, curMax + cnt + 1);
}
return ans;
}
private:
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
};
查找表和滑动窗口
t1存在重复元素II
给定一个数组，找出其中两个下标之差不超过k并且值相等的元素。
这题时间卡的很死，O(n²)必超，所以采用滑动窗口。
用一个set记录当前存在的元素，每次遍历检测当前元素是否存在。为了切合题意，维护set的size为k，即当set.size()>k时，erase掉nums[i-k]就行了。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> mys;
const int n = nums.size();
for(int i = 0; i < n; i++)
{
if(mys.count(nums[i])) return true;
mys.insert(nums[i]);
if(mys.size() > k) mys.erase(nums[i - k]);
}
return false;
}
};
t2存在重复元素 III
跟上一题很像，但这题要找的是满足一个大小区间的数。
思路也很清晰，在上一题滑动窗口的基础上思考题设要求：
“使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t” 其实就是指“nums[i]-t<=nums[j]<=nums[i]+t”。可以利用set的有序性，二分查找第一个大于等于nums[i]-t的值，再判断它是否小于等于nums[i]+t即可。
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> mys;
for(int i = 0; i < nums.size(); i++)
{
auto el = mys.lower_bound((long long)nums[i] - t);
if(el != mys.end() && (*el) <= (long long)nums[i] + t)
return true;
mys.insert(nums[i]);
if(mys.size() > k)
mys.erase(nums[i-k]);
}
return false;
}
};
评论
还没有任何评论，你来说两句吧!