不知道是不是為了讓因肺炎疫情只能在家宅的廣大工程師有點事情做,偶然發現 Leetcode 在四月出了一個類似鐵人三十天的計畫,心動不如馬上行動,開始來挑戰一下。

有興趣可以參考 👉https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/

下面節錄一小段解釋,從 4/1 開始為期三十天,每天台北時間 15:00 (UTC+8) 開始會有一題新題目,每一題有 24小時的時間可以解題。

This 30-Day LeetCoding Challenge will start on April 1st, 2020, 00:00AM PST. It is beginner-friendly and available for all premium and non-premium users

Each day at 00:00 AM Pacific Standard Time, a new problem will appear. You’ll then have 24 hours to submit a correct answer for that problem.


事不宜遲愚人節開始今天的第一題:熱身等級難度 Easy 的 136 – Single Number

給定一個陣列,其中每個數字會出現兩次,只有一個出現一次,找出只出現一次那個數字。
因為題目難度不高,因此還多加了 linear time && no extra memory 的條件限制。

Input: [2,2,1]
Output: 1

一陣子沒寫腦袋一時轉不過來,後來靈光一閃想到可以使用 bit operation,如此一來重複的值就會被消掉了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++)
            res ^= nums[i];
        return res;
    }
};

看了一下別人的執行時間,發現排名前面的竟然都有下面這段神奇的 code,一堆 [](){}()
照搬了之後時間還真的神奇地從 16ms —> 8ms

抱持著凡事問 Google 的精神,總之這是 C++11 引入的 Lambda 語法
目的是為了讓 C++ iostream 跟 stdio 解綁,避免兩個要互相 sync 耗費時間

👉 C++的輸出入cin/cout和scanf/printf誰比較快?
👉 解析 static auto x = []() { std::ios::sync_with_stdio(false);std::cin.tie(nullptr);return 0;}()

static int __=[](){
    std::ios::sync_with_stdio(false);
    return 0;
}();

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++)
            res ^= nums[i];
        return res;
    }
};

接下來看下扣,再更極致的直接拿 input nums[0] 來存,節省一次運算時間&完全不用額外 memory

static int __=[](){
    std::ios::sync_with_stdio(false);
    return 0;
}();

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for(int i=1; i<nums.size(); ++i)
            nums[0] ^= nums[i];
        return nums[0];
    }
};

如此一來這題就可以打完收工拉。

發佈留言

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

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