LeetCode 刷題總結(jié)（1）

1.兩數(shù)之和

AC代碼

思路

  • 剛開始就是用雙層for循環(huán)寫，然后秉承著謙虛的態(tài)度看了題解，發(fā)現(xiàn)真的有O(N)的算法一遍哈希表。

  • 主要就是利用map建立從數(shù)到數(shù)組下標的map，然后每次計算出target-nums[i]的值，然后看map里面有對應(yīng)的下標，有的話就輸出，沒有就繼續(xù)。

  • map的值為0時，如何區(qū)分stl的map知識有限，如何判斷0是數(shù)組里面沒有這個數(shù)還是查詢的引索為0呢？只要儲存的時候下標+1，用的時候減一就行了，這樣map值為0，一定是沒有這個數(shù)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            int pos = target - nums[i];
            if (m[pos] != 0 && m[pos] != i + 1) {
                pos = m[pos] - 1;
                ans.push_back(pos > i ? i : pos);
                ans.push_back(pos < i ? i : pos);
                break;
            }
            m[nums[i]] = i + 1;
        }
        return ans;
    }
};

2. 兩數(shù)相加

沒想到第二題就是鏈表了，LeetCode給出的這種帶構(gòu)造函數(shù)的結(jié)構(gòu)體挺好的，用起來方便了很多，開始創(chuàng)建一個head，后面直接返回head->next就好。

  1. next自動賦值為NULL（我覺得可以搞成next默認參數(shù)為NULL，自由度更大一點）
  2. 必須傳遞參數(shù)，限制使用，更安全

AC代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* temp, *ans;
        int carry = 0, n;
        ans = temp = new ListNode(0);
        while (l1 != NULL || l2 != NULL) {
            //用邏輯或鏈接，把兩個鏈表都遍歷完

            n = (l1 == NULL ? 0 : l1->val) + (l2 == NULL ? 0 : l2->val) + carry;
            //注意某個鏈表此時可能遍歷完的可能

            temp->next = new ListNode(n%10);
            carry = n / 10;
            //計算

            if (l1 != NULL)l1 = l1->next;
            if (l2 != NULL)l2 = l2->next;
            //注意到鏈表為空或已經(jīng)遍歷完
            temp = temp->next;
            //集體指向next
        }
        if (carry) temp->next = new ListNode(carry);
        //如果還有剩余的進位，再new一個

        return ans->next;
        //返回頭結(jié)點的next（頭結(jié)點沒意義）
    }
};

7. 整數(shù)反轉(zhuǎn)

第一次AC的，28ms

思路

  • 先干掉負號，sprintf變字符串，調(diào)用std的reverse函數(shù)，反轉(zhuǎn)，再變回數(shù)字，然后把符號還原
  • 由于要考察對溢出的處理，就偷梁換柱用了long long，超過int范圍的就返回0
class Solution {
public:
    int reverse(int y) {
        long long x = y;
        bool negative = (x < 0);
        if (negative) x *= -1;
        char n[1024];
        sprintf(n, "%lld", x);
        std::reverse(n, n + strlen(n));
        sscanf (n, "%lld", &x);
        if (negative) x *= -1;
        return x >= 2147483647 || x <= -2147483648 ? 0 : x;
    }
};

看了的高分同學(xué)的代碼第二次AC的20ms

手動大哭，憑什么一樣的算法，人家就是最高分，我就是中位數(shù)？？

這位同學(xué)代碼塊的原因主要是解除了與stdio的同步，cin.tie(nullptr)對cin，cout進行加速了，把取消同步的代碼刪除后，反而比我第一次AC的代碼慢了。也不知道是什么原因。

static int x = [](){ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
class Solution {
public:
    int reverse(int y) {
        long long x = y;
        long long ans = 0;
        while (x) {
            ans *= 10;
            ans += x % 10;
            x /= 10;
        }
        return ans >= 2147483647 || ans <= -2147483648 ? 0 : ans;
    }
};

9. 回文數(shù)

第一次AC代碼

思路

轉(zhuǎn)字符串，直接循環(huán)比

class Solution {
public:
    bool isPalindrome(int x) {
        char n[16] = {0};
        sprintf(n, "%d", x);
        int len = strlen(n);
        for (int i = 0; i < len/2; i++) {
            if (n[i] != n[len - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};

看了高分同學(xué)代碼后的第二次AC的代碼

思路

把數(shù)字當十進制轉(zhuǎn)十進制，算一次的結(jié)果剛好和原來的數(shù)反轉(zhuǎn)過來，如果大于0，比較兩個數(shù)是否相等，否則反轉(zhuǎn)一定不合條件，返回false

class Solution {
public:
    bool isPalindrome(int x) {
        long long y = 0;
        for (int z = x; z; z /= 10) {
            y = y*10 + z % 10;
        }
        return x >= 0 ? y == x : false;
    }
};

13. 羅馬數(shù)字轉(zhuǎn)整數(shù)

剛開始毫無思路，后來看了評論里大佬的思路才寫出來。

第一次AC代碼

思路

  1. 把幾個符號的ASCII值當下標，儲存符號的對應(yīng)的值
  2. 遍歷字符串，對于每一個字符，如果后一個字符的值大于自身，從總數(shù)中減去自己的值，如果后面的值小于等于自身（III，MMII），則在總數(shù)中加上自己
static const auto io_sync_off=[](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();
class Solution {
public:
    int romanToInt(string s) {
        int m[100] = {0};
        m['M'] = 1000;
        m['D'] = 500;
        m['C'] = 100;
        m['L'] = 50;
        m['X'] = 10;
        m['V'] = 5;
        m['I'] = 1;
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            //防止越界，不管最后一個字符，循環(huán)結(jié)束后單獨考慮
            if (m[s[i]] >= m[s[i+1]]) ans += m[s[i]];
            else ans -= m[s[i]];
        }
        ans += m[s[s.length() - 1]];
        //最后一個字符沒有后面一個，不論如何，都加上它的值
        return ans;
    }
};

14. 最長公共前綴

第一次AC代碼

思路

  1. 找到最短的字符串
  2. 從1開始截取字符串，跟其他字符串的前綴比較，直到出現(xiàn)前綴不同
static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans;
        for (int i = 0; i < minlen(strs); i++) {
            bool find = false;
            char cmp = strs[0][i];
            for (int j = 0; j < strs.size(); j++) {
                if (cmp != strs[j][i]) {
                    find = true;
                    break;
                }
            }
            if (!find) ans.append(1, cmp);
            else break;
        }
        return ans;
    }
    int minlen(vector<string>& strs) {
        if (strs.size() == 0) return 0;
        int min = strs[0].length();
        for (int i = 1; i < strs.size(); i++) {
            if (strs[i].length() < min) min = strs[i].length();
        }
        return min;
    }
};

看了題解后利用二分查找法的AC代碼（Edition 1）

思路

  1. 找到最短的字符串的下標
  2. 把最短的字符串一分為二，自己變成前半段，后半段存在另一個string里面
  3. 比較一次，如果前綴都相同，把右半邊一分為二，拼接到左半半，右半半變成自己的右半半。
  4. 一次比較完成后
    1. 如果前綴都相同，且后半半只剩一個字符了，把這個字符拼過去再查一次，有問題就恢復(fù)，沒問題保留，返回此時的左半半；如果前綴
    2. 如果前綴不同，左半半只剩下一個字符了，在比較一次，看看這個字符是不是公共前綴，是就返回，否則返回空串（沒有公共前綴）
static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1) return strs[0];
        if (!strs.size()) return "";
        int min = IndexOfMinLen(strs);
        if (!strs[min].length()) return "";
        string sub = strs[min].substr(0, strs[min].length() / 2);
        string right = strs[min].substr(strs[min].length() / 2, strs[min].length() - strs[min].length() / 2);
        while (1){
            bool find = false;
            for (int i = 0; i < strs.size(); i++) {
                if (strs[i].substr(0, sub.length()) != sub) {
                    find = true;
                }
            }
            if (find) {
                if (sub.length() == 1) {
                    for (int i = 0; i < strs.size(); i++) {
                        if (strs[i].substr(0, sub.length()) != sub) {
                            find = true;
                        }
                    }
                    if (find) {
                        sub = "";
                    }
                    break;
                }
                right = sub.substr(sub.length() / 2, sub.length() - sub.length()/2);
                sub = sub.substr(0, sub.length()/2);
                
            } else {
                if (right.length() == 1) {
                    for (int i = 0; i < strs.size(); i++) {
                        if (strs[i].substr(0, sub.length()+1) != sub + right) {
                            find = true;
                        }
                    }
                    if (!find) {
                        sub += right;
                    }
                    break;
                }
                sub.append(right.substr(0, right.length()/2));
                right = right.substr(right.length() / 2, right.length() - right.length()/2);
            }
        }
        return sub;
    }
    int IndexOfMinLen(vector<string>& strs) {
        int min = strs[0].length();
        int pos = 0;
        for (int i = 1; i < strs.size(); i++) {
            if (strs[i].length() < min) {
                min = strs[i].length();
                pos = i;
            }
        }
        return pos;
    }
};

根據(jù)題解寫的簡化版二分查找（Edition 2）

思路

  1. 每次截取一半，遍歷比較
  2. 如果前綴相同，把邊界右移一半
  3. 如果前綴不同，把邊界前移一半
static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1) return strs[0];
        if (!strs.size()) return "";
        int min = IndexOfMinLen(strs);
        if (!strs[min].length()) return "";
        int len = strs[min].length();
        int left = 1, right = strs[min].length();
        string sub;
        while (left <= right){
            int mid = (left + right) / 2;
            sub = strs[min].substr(0, mid);
            bool find = false;
            for (int i = 0; i < strs.size(); i++) {
                if (strs[i].substr(0, sub.length()) != sub) {
                    find = true;
                }
            }
            if (find) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        sub = strs[min].substr(0, (left + right) / 2);
        return sub;
    }
    int IndexOfMinLen(vector<string>& strs) {
        int min = strs[0].length();
        int pos = 0;
        for (int i = 1; i < strs.size(); i++) {
            if (strs[i].length() < min) {
                min = strs[i].length();
                pos = i;
            }
        }
        return pos;
    }
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容