题单介绍:
精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。
目录
题单介绍:
题目:448. 找到所有数组中消失的数字 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
题目:438. 找到字符串中所有字母异位词 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
写在最后:
题目:448. 找到所有数组中消失的数字 - 力扣(Leetcode)
题目的接口:
class Solution { public: vector findDisappearedNumbers(vector& nums) { } };
解题思路:
这道题直接做的话并不难,
直接把这个数组存进哈希,然后再遍历,
看看有那个数字不在这个数组里面,push进要返回的数组就行:
class Solution { public: vector findDisappearedNumbers(vector& nums) { set st; vector v; for(auto e : nums) st.insert(e); for(int i = 1; i <= nums.size(); i++) { if(st.find(i) == st.end()) v.push_back(i); } return v; } };
但是这段代码因为用的是set,
所以并不是O(N)的时间复杂度,空间复杂度也是O(N),
题目有个进阶要求,
毕竟是简单题,我就去做了一下进阶,
如果想要达成进阶的要求,有一个很妙的解法:
思路如下:
第一遍遍历的时候,标记数组中有数字的位置,
打个比方就是,遍历到1,就把数组第一个位置标记,代表有这个数字,
如果遍历到7,就把数组第7个位置标记,代表有7这个数字,
这样子我们就知道哪些位置没有被标记。
第二次遍历数组,将没有标记的位置的数字存进数组并返回即可
代码如下:
代码:
class Solution { public: vector findDisappearedNumbers(vector& nums) { int n = nums.size(); for(int i = 0; i < n; i++) { nums[(nums[i] - 1) % n] += n; } vector v; for(int i = 0; i < n; i++) { if(nums[i] <= n) v.push_back(i + 1); } return v; } };
过过过过啦!!!!
题目:438. 找到字符串中所有字母异位词 - 力扣(Leetcode)
题目的接口:
class Solution { public: vector findAnagrams(string s, string p) { } };
解题思路:
这道题是一道经典的滑动窗口题目,
滑动窗口的题目解题的思路基本上大同小异,
就是更新右边界,然后找到符合条件的子集之后,
计数或者是将题目要求的内容输入到数组里面之类的操作,
然后移动左边界,最后遍历完就可以返回了。
代码如下:
代码:
class Solution { public: vector findAnagrams(string s, string p) { unordered_map need, window; for(auto e : p) need[e]++; int left = 0, right = 0, cnt = 0; vector ans; while(right < s.size()) { char r = s[right]; right++; if(need.count(r) > 0) { window[r]++; if(window[r] == need[r]) { cnt++; } } if(cnt == need.size()) ans.push_back(left); while(right - left >= p.size()) { char l = s[left]; left++; if(need.count(l) > 0) { if(window[l] == need[l]) { cnt--; } window[l]--; } } } return ans; } };
过过过过啦!!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~