不知不覺 30-Day LeetCoding Challenge 這個挑戰就完成一週了,我想不知不覺的,馬上就會完成一個月的目標了吧。

經過昨天的 Medium 洗禮,今天的題目相較下就親切了不少:Counting Elements
剛想說怎麼搜尋不到這個題目的編號,原來是這週的新題目!!根據官方說明總共會有五個新題目,想必這就是其中之一了。
還沒加入的只好趕快手刀加入這個 Event,開始刷題才看得到這題囉。

Challenge Overview
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.

https://leetcode.com/discuss/general-discussion/551411/30-Day-LeetCoding-Challenge

這個題目雖然是新題目難度還沒出來,不過我個人感覺應該是 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,終於開始有種醒腦的感覺。
雖然看到論壇討論有人說太簡單,但是這只是第一個禮拜,對我這個剛開始刷題的新手來說真的很友善,相信到後面就會出現越來越有挑戰性的題目了吧。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料