LeetCode 顺序刷题记录（11-20）

12. 整数转罗马数字

标签：数学、字符串

方法一：模拟

const pair<int, string> valueSymbols[] = {
    {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
    {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
    {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
};

class Solution {
public:
    string intToRoman(int num) {
        string roman;
        for (const auto& [value, symbol] : valueSymbols) {
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) break;
        }
        return roman;
    }
};

方法二：硬编码

const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
public:
    string intToRoman(int num) {
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};

13. 罗马数字转整数

标签：哈希表、数学、字符串

class Solution {
private:
    unordered_map<char, int> symbolValue = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };
public:
    int romanToInt(string s) {
        int ret = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            int value = symbolValue[s[i]];
            if (i < n - 1 && value < symbolValue[s[i + 1]]) {
                ret -= value;
            } else {
                ret += value;
            }
        }
        return ret;
    }
};

14. 最长公共前缀

标签：字符串、二分查找

方法一：横向扫描

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ret = strs[0];
        for (int i = 1; i < strs.size(); i++) {
            ret = findCommon(ret, strs[i]);
        }
        return ret;
    }

    string findCommon(string& s1, string& s2) {
        int i = 0;
        while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) {
            i++;
        }
        return s1.substr(0, i);
    }
};

方法二：纵向扫描

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int length = strs[0].size();
        int count = strs.size();
        for (int i = 0; i < length; i++) {
            char c = strs[0][i];
            for (int j = 1; j < count; j++) {
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

方法三：分治

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        return longestCommonPrefix(strs, 0, strs.size() - 1);
    }

    string longestCommonPrefix(const vector<string>& strs, int start, int end) {
        if (start == end) return strs[start];
        int mid = (start + end) / 2;
        string lcpLeft = longestCommonPrefix(strs, start, mid);
        string lcpRight = longestCommonPrefix(strs, mid + 1, end);
        return commonPrefix(lcpLeft, lcpRight);
    }

    string commonPrefix(const string& lcpLeft, const string& lcpRight) {
        int minLength = min(lcpLeft.size(), lcpRight.size());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft[i] != lcpRight[i]) {
                return lcpLeft.substr(0, i);
            }
        }
        return lcpLeft.substr(0, minLength);
    }
};

方法四：排序

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        string start = strs.front();
        string end = strs.back();
        int n = min(start.size(), end.size());
        int i = 0;
        for (; i < n && start[i] == end[i]; i++);
        return start.substr(0, i);
    }
};

15. 三数之和

标签：排序、数组、双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) break;
            int left = i + 1;
            int right = n - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) {
                    --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    ++left;
                    --right;
                    while (left < right && nums[left] == nums[left - 1]) ++left;
                    while (left < right && nums[right] == nums[right + 1]) --right;
                }
            }
            while (i < n - 1 && nums[i] == nums[i + 1]) ++i;
        }
        return ret;
    }
};

16. 最接近的三数之和

标签：排序、数组、双指针

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ret = 1e7;
        auto update = [&](int cur) {
            if (abs(cur - target) < abs(ret - target)) {
                ret = cur;
            }
        };
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) return target;
                update(sum);
                if (sum > target) {
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else {
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                }
            }
        }
        return ret;
    }
};

17. 电话号码的字母组合

标签：哈希表、字符串、回溯

class Solution {
private:
    string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string path;
    vector<string> ret;

    void dfs(string& digits, int pos) {
        if (pos == digits.size()) {
            ret.push_back(path);
            return;
        }
        for (const auto& ch : hash[digits[pos] - '0']) {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        dfs(digits, 0);
        return ret;
    }
};

18. 四数之和

标签：排序、数组、双指针

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 4) return {};
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                long long newtarget = (long long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum > newtarget) {
                        right--;
                    } else if (sum < newtarget) {
                        left++;
                    } else {
                        ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                while (j < n - 2 && nums[j] == nums[j + 1]) j++;
            }
            while (i < n - 3 && nums[i] == nums[i + 1]) i++;
        }
        return ret;
    }
};

19. 删除链表的倒数第 N 个节点

标签：栈、链表、双指针

方法一：计算链表长度

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* newhead = new ListNode(0, head);
        int count = 0;
        ListNode* cur = head;
        while (cur) {
            cur = cur->next;
            count++;
        }
        int gap = count - n;
        cur = newhead;
        while (gap--) cur = cur->next;
        ListNode* del = cur->next;
        cur->next = del->next;
        cur = newhead->next;
        delete del;
        delete newhead;
        return cur;
    }
};

方法二：栈

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* newhead = new ListNode(0, head);
        stack<ListNode*> s;
        ListNode* cur = newhead;
        while (cur) {
            s.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            s.pop();
        }
        ListNode* prev = s.top();
        ListNode* del = prev->next;
        prev->next = del->next;
        cur = newhead->next;
        delete del;
        delete newhead;
        return cur;
    }
};

方法三：双指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode newhead;
        newhead.next = head;
        ListNode* slow = &newhead;
        ListNode* fast = &newhead;
        while (n--) {
            fast = fast->next;
        }
        while (fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* del = slow->next;
        slow->next = del->next;
        delete del;
        return newhead.next;
    }
};

20. 有效的括号

标签：栈、哈希表、字符串

方法一：直接匹配

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        stack<char> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                st.push(s[i]);
            } else if (s[i] == ')' && !st.empty() && st.top() == '(') {
                st.pop();
            } else if (s[i] == '}' && !st.empty() && st.top() == '{') {
                st.pop();
            } else if (s[i] == ']' && !st.empty() && st.top() == '[') {
                st.pop();
            } else {
                return false;
            }
        }
        return st.empty();
    }
};

方法二：哈希表优化

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) return false;
        unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
        stack<char> stk;
        for (const char& ch : s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) return false;
                stk.pop();
            } else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};