不知不覺 30-Day LeetCoding Challenge 這個挑戰就完成一週了,我想不知不覺的,馬上就會完成一個月的目標了吧。
經過昨天的 Medium 洗禮,今天的題目相較下就親切了不少:Counting Elements
剛想說怎麼搜尋不到這個題目的編號,原來是這週的新題目!!根據官方說明總共會有五個新題目,想必這就是其中之一了。
還沒加入的只好趕快手刀加入這個 Event,開始刷題才看得到這題囉。
Challenge Overview
https://leetcode.com/discuss/general-discussion/551411/30-Day-LeetCoding-Challenge
In this LeetCoding Challenge, we challenge participants to solve a different problem every day. These problems are carefully hand-picked from LeetCode’s curated collection of frequently asked interview questions, including 5 brand-new problems, and they will be displayed on the 30-Day LeetCoding Challenge Explore Card according to their challenge date.
這個題目雖然是新題目難度還沒出來,不過我個人感覺應該是 Easy,可以很直覺地想到用 vector/map 來解題。
題目給定一個整數陣列 arr,算出總共幾個 x in arr,也同時存在 x+1 in arr
Input: arr = [1,3,2,3,5,0] Output: 3 Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.
class Solution {
public:
int countElements(vector<int>& arr) {
int ans = 0;
vector<int>::iterator it;
vector<int>::iterator itFind;
for(it = arr.begin(); it != arr.end(); it++){
itFind = find(arr.begin(), arr.end(), (*it)+1);
if(itFind != arr.end())
ans++;
}
return ans;
}
};
雖然用 Vector 寫起來簡單易懂,但是缺點也顯而易見,就是時間複雜度會是 O(NN)
下面用 map 改寫一下,時間就直接變成 O(N) 拉
class Solution {
public:
int countElements(vector<int>& arr) {
int ans = 0;
unordered_map<int, int> m;
for(auto i : arr)
m[i]++;
for(auto i : arr){
if(m.count(i+1)) {
ans++;
}
}
return ans;
}
};
持續了一個禮拜,看到這個真的是說不出來的開心,從一開始腦袋打結每個 API 都要到處 Google,到現在開始慢慢可以 vector/map 打天下的寫出 AC,終於開始有種醒腦的感覺。
雖然看到論壇討論有人說太簡單,但是這只是第一個禮拜,對我這個剛開始刷題的新手來說真的很友善,相信到後面就會出現越來越有挑戰性的題目了吧。