268 篇文章 含有標籤「leetcode」

/*
 * @lc app=leetcode id=20 lang=cpp
 *
 * [20] Valid Parentheses
 *
 * https://leetcode.com/problems/valid-parentheses/description/
 *
 * algorithms
 * Easy (41.30%)
 * Likes:    25708
 * Dislikes: 1873
 * Total Accepted:    6M
 * Total Submissions: 14.3M
 * Testcase Example:  '"()"'
 *
 * Given a string s containing just the characters '(', ')', '{', '}', '[' and
 * ']', determine if the input string is valid.
 *
 * An input string is valid if:
 *
 *
 * Open brackets must be closed by the same type of brackets.
 * Open brackets must be closed in the correct order.
 * Every close bracket has a corresponding open bracket of the same type.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: s = "()"
 *
 * Output: true
 *
 *
 * Example 2:
 *
 *
 * Input: s = "()[]{}"
 *
 * Output: true
 *
 *
 * Example 3:
 *
 *
 * Input: s = "(]"
 *
 * Output: false
 *
 *
 * Example 4:
 *
 *
 * Input: s = "([])"
 *
 * Output: true
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= s.length <= 10^4
 * s consists of parentheses only '()[]{}'.
 *
 *
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> closeToOpen = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        stack<char> stk;
        for (const auto& c : s) {
            if (closeToOpen.count(c)) {
                if (!stk.empty() && stk.top() == closeToOpen[c]) stk.pop();
                else return false;
            } else stk.push(c);
        }
        return stk.empty();
    }
};
// @lc code=end

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow = head;
        ListNode* fast = head;
        for(int i = 0; i < n; i++) {
            fast = fast->next;
        }

        if(!fast) return head->next;

        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int diff = INT_MAX;
        int n = nums.size();
        sort(begin(nums), end(nums));
        for (int i = 0; i < n && diff != 0; ++i) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (abs(target - sum) < abs(diff)) {
                    diff = target - sum;
                }

                if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return target - diff;
    }
};

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

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        // Sort the vector of strings lexicographically

        // Find the minimum length between the first and the last string in the sorted vector

        // Initialize an index to track the position of the common prefix

        // Compare characters of the first and last strings in the sorted vector
            // Increment the index if the characters match

        // Return the substring from the start to the position where characters matched
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        sort(strs.begin(), strs.end());

        int minLength = min(strs.front().size(), strs.back().size());

        int i = 0;
        while(i < minLength && strs.front()[i] == strs.back()[i])
        {
            ++i;
        }
        return strs.front().substr(0, i);
    }
};

class Solution {
public:
    int romanToInt(string s)
    {
        // Create a map to store Roman numeral characters and their integer values

        // Initialize the result variable to store the final integer value
        // Loop through each character in the string
        for ()
        {
            // Check if the current character value is less than the next character value
                // If true, subtract the current character's value from the result
                // Otherwise, add the current character's value to the result
        }
        // Return the final integer value
    }
};

class Solution {
public:
    int romanToInt(string s)
    {
        unordered_map<char, int> m = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000},
        };

        int res = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            if (i < s.size() - 1 && m[s[i]] < m[s[i + 1]])
            {
                res -= m[s[i]];
            }
            else
            {
                res += m[s[i]];
            }
        }
        return res;
    }
};

class Solution {
public:
    string intToRoman(int num)
    {
        // Vector of pairs, each pair contains an integer and its corresponding Roman numeral representation

        // Initialize the resulting Roman numeral string
        // Iterate over each symbol in the vector
            // While the current number is greater than or equal to the integer value of the symbol
                // Subtract the integer value from the number
                // Append the corresponding Roman numeral to the result
        // Return the resulting Roman numeral string
    }
};

class Solution {
public:
    string intToRoman(int num)
    {
        vector<pair<int, string>> symbols = {
            {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"}
        };

        string roman;
        for (auto symbol : symbols)
        {
            while (num >= symbol.first)
            {
                num -= symbol.first;
                roman += symbol.second;
            }
        }
        return roman;

    }
};

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int res = 0, curArea = 0;
        while(left < right)
        {
            curArea = min(height[left], height[right]) * (right - left);
            res = max(res, curArea);
            if(height[left] < height[right]) ++left;
            else --right;
        }
        return res;
    }
};

class Solution {
public:
    bool isPalindrome(int x)
    {
        if (x < 0) return false;
        if (x != 0 && x % 10 == 0) return false;
        int reverted = 0;
        while (x > reverted)
        {
            int digit =  x % 10;
            x /= 10;
            reverted = reverted * 10 + digit;
        }
        return x == reverted || x == reverted / 10;
    }
};