Leetcode Weekly Contest 39

太可惜了，一開始手滑完全忘記 int 乘以 int 會炸～第二題實在是很想用 python 寫XD

給定一個非負整數 $c$，問是否存在整數 $a$ 和 $b$ 滿足 $a^2+b^2=c$？

後來與修拉拉討論以後，發現最簡單的作法是枚舉 $a$、然後硬算 $b=\sqrt{c-a^2}$。

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long long a = 0; a*a <= c; a++) {
            long long b = sqrt(c - a*a);
            if (a*a+b*b==c) return true;
        }
        return false;
    }
};

這題有數學解的樣子：費馬的二平方和定理。若去除平方因子以後，所有的奇質因數都是形如 $4k+1$ 的話，必定有解。

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long long p=2;p*p<=c;p++)
            while (c%(p*p) == 0)
                c /= (p*p);
        if (c%2==0) c/=2;
        for (long long p=3;p*p<=c;p++)
            if (c%p==0) {
                if(p%4==3) return false;
                c/=p;
            }
        return c==0 || c%4==1;
    }
};

Leetcode 635. Design Log Storage System

請你實作一個 Log 查詢系統，可以查詢某一段給定時間的 Log。

不解釋。其實可以直接用字串比對，只要比到指定長度就可以了。因為輸入不大，所以也可以暴力比較。

class LogSystem {
public:
    vector<pair<int, string>> all;
    string c[6] = {"Year", "Month", "Day", "Hour", "Minute", "Second"};
    int len[6] = {4, 7, 10, 13, 16, 19};
    LogSystem() {
        all = vector<pair<int, string>>();
    }
    
    void put(int id, string timestamp) {
        all.push_back({id, timestamp});
    }
    
    vector<int> retrieve(string s, string e, string gra) {
        int j = find(c, c+6, gra) - c;
        s = s.substr(0, len[j]);
        e = e.substr(0, len[j]);
        vector<int> res;
        for(auto it: all)
            if (it.second.substr(0, len[j]) >= s && it.second.substr(0, len[j]) <= e)
                res.push_back(it.first);
        return res;
    }
};

Leetcode 634. Find the Derangement of An Array

給定 $n$，請問 $1$ 到 $n$ 的錯置排列有幾種？請輸出答案除以 $10^9+7$ 的餘數。

經典的錯排問題。有兩種解法：排容方法是

$a_n = 全部 - 至少一個不動點 + 至少兩個不動點 - 至少三個不動點 + \cdots$

這會等於

$a_n = n! - n\times (n-1)! + {n\choose 2} (n-2)! - {n\choose 3} (n-3)! + \cdots + (-1)^n {n\choose n} 0!$

把前面的 $n$ 項各自提出一個 $n$，並整理成遞迴式得到：

$a_n = n\left( (n-1)! - (n-1)\times (n-2)! + {n-1 \choose 2}\times (n-3)! - \cdots \right) + (-1)^n = na_{n-1} + (-1)^n$

剩下就好辦了。另外一種解法是關注 $1$ 被排到哪裡去：假設 $1$ 出現在排列的第 $k$ $(k\neq 1)$ 位，而該排列第一個數是 $k$，那麼扣除 $1$ 和 $k$ 這兩個數字以後，剩下的數字和其位置們形成一個長度為 $n-2$ 的錯排，此情形有 $(n-1)a_{n-2}$ 種。若該排列第一個數字既不是 $1$ 也不是 $k$，那麼我們將第一個數字與 $1$ 所在位置對調，現在恰好有一個不動點，也就是說剩下的 $n-1$ 個數字形成一個錯排：此情形恰好有 $(n-1)a_{n-1}$ 種。所以我們有：

$a_n = (n-1)(a_{n-1} + a_{n-2})$

是個 $n-1$ 倍的費氏數列呢！

class Solution {
public:
    int findDerangement(int n) {
        const long long MOD = 1e9+7;
        long long a=0,b=1,c;
        for(int i=2;i<=n;i++) {
            c=i*(b+a) % MOD;
            a=b;
            b=c;
        }
        return (int)a;
    }
};

Leetcode 632. Smallest Range

給你 $k$ 個排好序的 list，請找出長度最小的區間，使得每一個 list 至少有一個數字出現在這個區間內。所有數字範圍 $[-10^5, 10^5]$，至多 $3500$ 個 list。

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        set<pair<int, int>> q;
        int k = (int)nums.size();
        for(int i = 0; i < k; i++) q.insert({nums[i][0], i});
        int ans = q.rbegin()->first - q.begin()->first;
        int l = q.begin()->first, r = q.rbegin()->first;
        while(true) {
            auto obj = *q.begin();
            int i = obj.second;
            int v = obj.first;
            q.erase(q.begin());
            if(nums[i].back() == v) break;
            q.insert({*upper_bound(nums[i].begin(), nums[i].end(), v), i});
            if (ans > q.rbegin()->first - q.begin()->first) {
                ans = q.rbegin()->first - q.begin()->first;
                l = q.begin()->first, r = q.rbegin()->first;
            }
        }
        return {l, r};
    }
};