leetcode解題記錄

Easy

1.Two Sum

寫這題的用意是為了熟悉Leetcode的寫法，畢竟和其他OJ不太一樣。
:::success
Runtime: 280 ms, faster than 36.74% of C++ online submissions for Two Sum.
Memory Usage: 10 MB, less than 99.62% of C++ online submissions for Two Sum.
:::

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        int i,j,ns=nums.size();
        for(i=0;i<ns;i++){
            for(j=i+1;j<ns;j++){
                if(nums[i]+nums[j]==target){
                    return vector<int> {i,j};
                }
            }
        }
        return vector<int> {i,j};
    }
};

20210522

13.Roman to Integer

:::success
Runtime: 24 ms, faster than 8.20% of C++ online submissions for Roman to Integer.
Memory Usage: 8.1 MB, less than 25.82% of C++ online submissions for Roman to Integer.
:::
以前都傻傻地建表，連IV、IX那種都一起建，結果跑迴圈轉換的時候就很複雜。這個做法只要看前一位是否小於其後一位，有就減，沒有就加。

class Solution {
public:
    int romanToInt(string s) {
        int res,i;
        map<char, int> list;
        list['I']=1;
        list['V']=5;
        list['X']=10;
        list['L']=50;
        list['C']=100;
        list['D']=500;
        list['M']=1000;
        res=list[s[s.length()-1]];
        for(i=s.length()-2;i>=0;i--){
            if(list[s[i]]<list[s[i+1]]){
                res-=list[s[i]];
            }
            else{
                res+=list[s[i]];
            }
        }
        return res;
    }
};

20210523

14.Longest Common Prefix

原本想說跑迴圈把所有字串一一確認是否有那個字，但這樣還是太麻煩，看到某人的解法，先照lexicographic的順序從小排到大，然後比較頭尾。我照做就過了，但這隻程式和我想得不太一樣，我偷偷修改中間的字串，結果頭尾比較的結果也被影響。
像是我輸入[“delta”,”flow”,”flight”]，我以為會跑出”fl”，結果是””。
看來我還不太了解vector
:::success
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Common Prefix.
Memory Usage: 9.1 MB, less than 70.71% of C++ online submissions for Longest Common Prefix.
:::

class Solution {
public:
    string prefix;
    string longestCommonPrefix(vector<string>& strs) {
        sort(strs.begin(),strs.end());
        for(int i=0;i<strs[strs.size()-1].size();i++){
            if(strs[0][i]==strs[strs.size()-1][i]){
                prefix+=strs[0][i];
            }
            else{
                break;
            }
        }
        return prefix;
    }
};

20210703

977.Squares of a Sorted Array

這題真的簡單，我是用counting sort來解。
Step 1
開一個array來記錄每個數字出現多少次，如果是負數的話，就先乘-1再統計。
Step 2
照著數字的順序平方後輸出。
:::success
Runtime: 36 ms, faster than 43.13% of C++ online submissions for Squares of a Sorted Array.
Memory Usage: 26.7 MB, less than 31.46% of C++ online submissions for Squares of a Sorted Array.
:::

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums){
        int cnt[10001]={0},i;
        for(i=0;i<nums.size();i++){
            if(nums[i]<0){nums[i]*=-1;}
            cnt[nums[i]]++;
        }
        vector<int> res;
        for(i=0;i<=10000;i++){
            while(cnt[i]){
                res.push_back(i*i);
                cnt[i]--;
            }
        }
        return res;
    }
};

20220215

20.Valid Parentheses

這題唯一需要注意的點是，會有這種「只有右括號」的測資，所以一開始最好先數左、右括號的數量，如果不相同就直接return false。一樣的話再來判斷能不能全接。

新技能包：str.erase(n)，這個函式會刪除str的第n+1個字元。
:::success
Runtime: 6 ms, faster than 10.73% of C++ online submissions for Valid Parentheses.
Memory Usage: 6.2 MB, less than 96.34% of C++ online submissions for Valid Parentheses.
:::

class Solution {
public:
    bool isValid(string s) {
        string pq; //pq = parentheses_queue
        int sl = s.length(), i, pqi=0;
        //先判斷左右括號的數量是否一樣
        int lp=0,rp=0;
        for(i=0;i<sl;i++){
            if(s[i]=='(' || s[i]=='[' || s[i]=='{'){lp++;}
            else{rp++;}
        }
        if(lp == rp){
            //進行比對
            for(i=0;i<sl;i++){
                if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
                    pq += s[i];
                    pqi++;
                }
                else if(pqi > 0){
                    if(s[i]==')' && pq[pqi-1]=='('){
                        pq.erase(pqi-1);
                        pqi--;
                    }
                    else if(s[i]==']' && pq[pqi-1]=='['){
                        pq.erase(pqi-1);
                        pqi--;
                    }
                    else if(s[i]=='}' && pq[pqi-1]=='{'){
                        pq.erase(pqi-1);
                        pqi--;
                    }
                }
            }

            //返回結果
            if(pqi == 0){
                return true;
            }
            else{
                return false;
            }
        }
        else{
            return false;
        }
    }
};

26.Remove Duplicates from Sorted Array

一開始看到只需要return k值，我便直接投機取巧地==return 尾-頭+1==，結果出來的答案怪怪的，於是我便重新看下題目。才發現這題的函式雖然只需要回傳k值，但是看到題目給的code可以發現，求出k值以後，nums還會被用到別的地方，所以在求出k值的同時，我們也要把nums改成不重複的樣子。
:::success
Runtime: 9 ms, faster than 81.97% of C++ online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 18.4 MB, less than 38.14% of C++ online submissions for Remove Duplicates from Sorted Array.
:::

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int ns = nums.size(), i, target = 0;
        for(i=1 ; i<ns ; i++){
            if(nums[i] != nums[target]){
                target++;
                nums[target] = nums[i];
            }
        }
        return target+1;
    }
};

20220218

1480. Running Sum of 1d Array

d
:::success
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Running Sum of 1d Array.
Memory Usage: 8.4 MB, less than 93.67% of C++ online submissions for Running Sum of 1d Array.
:::

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int i, ns = nums.size();
        if(ns == 1){
            return nums;
        }
        else{
            for(i=1 ; i<ns ; i++){
                nums[i] += nums[i-1];
            }
        }
        return nums;
    }
};