跳至主要内容

16. 3Sum Closest

· 閱讀時間約 1 分鐘

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -104 <= target <= 104
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;
    }
};
  • T: $O(N^2)$
  • S: $O(\log N)$

15. 3Sum

· 閱讀時間約 1 分鐘
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;
    }
};
  • T: $O(N^2)$
  • S: $O(\log N)$

14. Longest Common Prefix

· 閱讀時間約 1 分鐘

Hint

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);
    }
};
  • T: $O(N \log N)$
  • S: $O(1)$

13. Roman to Integer

· 閱讀時間約 1 分鐘

Hint

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;
    }
};
  • T: $O(N)$
  • S: $O(1)$

12. Integer to Roman

· 閱讀時間約 1 分鐘

Hint

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;

    }
};
  • T: $O(N)$
  • S: $O(1)$

11. Container With Most Water

· 閱讀時間約 1 分鐘
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;
    }
};
  • T: $O(N)$
  • S: $O(1)$

9. Palindrome Number

· 閱讀時間約 1 分鐘
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;
    }
};
  • T: $O(N)$
  • S: $O(1)$

8. String to Integer (atoi)

· 閱讀時間約 3 分鐘

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

  1. Whitespace: Ignore any leading whitespace (" ").
  2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present.
  3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
  4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

Example 1:

Input: s = "42"

Output: 42

Explanation:

The underlined characters are what is read in and the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^

Example 2:

Input: s = " -042"

Output: -42

Explanation:

Step 1: " -042" (leading whitespace is read and ignored) ^ Step 2: " -042" ('-' is read, so the result should be negative) ^ Step 3: " -042" ("042" is read in, leading zeros ignored in the result) ^

Example 3:

Input: s = "1337c0d3"

Output: 1337

Explanation:

Step 1: "1337c0d3" (no characters read because there is no leading whitespace) ^ Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+') ^ Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit) ^

Example 4:

Input: s = "0-1"

Output: 0

Explanation:

Step 1: "0-1" (no characters read because there is no leading whitespace) ^ Step 2: "0-1" (no characters read because there is neither a '-' nor '+') ^ Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit) ^

Example 5:

Input: s = "words and 987"

Output: 0

Explanation:

Reading stops at the first non-digit character 'w'.

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
class Solution {
public:
    int myAtoi(string s) {
        // 紀錄正負號，預設是正號
        int sign = 1;
        int res = 0;
        int i = 0;
        int n = s.size();
        // 掃 s，略過空白格
        while (i < n && s[i] == ' ') i++;

        // 紀錄正負號，i++
        if (i < n && s[i] == '+') {
            sign = 1;
            i++;
        } else if (i < n && s[i] == '-') {
            sign = -1;
            i++;
        }
        // 現在的 i 就是整數的起始位置
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0';
            // 檢查有沒有超過 32-bit signed integer 的範圍
            if ((res > INT_MAX / 10) || (res == INT_MAX / 10 && digit > INT_MAX % 10)) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            // 10 進位
            res = 10 * res + digit;
            i++;
        }
        return sign * res;
    }
};
  • T: $O(N)$
  • S: $O(1)$

7. Reverse Integer

· 閱讀時間約 1 分鐘

Given a signed 32-bit integer x, return xwith its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123 Output: 321

Example 2:

Input: x = -123 Output: -321

Example 3:

Input: x = 120 Output: 21

Constraints:

  • -231 <= x <= 231 - 1
class Solution {
public:
    int reverse(int x) {
        int reversed = 0;
        while(x != 0) {
            int digit = x % 10;
            x /= 10;
            if(reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && digit > INT_MAX % 10))
                return 0;
            if(reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && digit < INT_MIN % 10))
                return 0;
            reversed = reversed * 10 + digit;
        }
        return reversed;
    }
};
  • T: $O(\log N)$
  • S: $O(1)$