4 Leetcode Problem Explanations

LC-7：Reverse Integer#

Idea
- No need for extra judgment for negative numbers, the logic is consistent
- Mainly check for overflow during (* 10 operation), two methods
  - ⭐ Both are clever
  - Method 1: Use long long to store the reversed number, then convert to int to check for overflow
  - Method 2: Check for overflow each time a digit is added during reversal
    - Compared with INT_MAX: 【Already greater than INT_MAX/10】 or 【Equal to INT_MAX/10 and the number to add > 7】
    - Compared with INT_MIN: 【Already less than INT_MIN/10】 or 【Equal to INT_MIN/10 and the number to add < -8】
Code
- Method 1: Using long long

class Solution {
public:
    int reverse(int x) {
        // Personal answer
        // No need to consider the negative sign
        long long t = 0;
        while (x) {
            t = t * 10 + x % 10;
            x /= 10;
        }
        // Check if the result is within int range
        return int(t) == t ? t : 0;
    }
};

- Method 2: Check during digit addition

class Solution {
public:
    int reverse(int x) {
        // Official answer
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;  // The digit to be added, calculated in advance to check for overflow
            x /= 10;
            // Corresponding to the maximum value INT_MAX
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            // Corresponding to the minimum value INT_MIN
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

- - The digit to be added pop is calculated in advance

LC-9：Palindrome Number#

Idea
- A palindrome number will never overflow because it is equal to itself
- ⭐ Reverse half of the number
  - No need to consider overflow
  - But remember to consider the case of odd digits!
- Initially exclude 【negative numbers】 and 【numbers greater than 0 that end with 0】
- PS: Converting to string
  - Can use the string class in C++, combined with to_string()
  - Use two pointers to compare from both ends

string  str = to_string(x);

Code

class Solution {
public:
    bool isPalindrome(int x) {
        // 【Negative numbers】 and 【numbers greater than 0 that end with 0】 are directly excluded
        if (x < 0 || x % 10 == 0 && x != 0) return false;
        int rev = 0;
        // Only reverse half, no need to consider overflow
        while (rev < x) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        // Remember to consider the case of odd digits
        return rev == x || rev / 10 == x;
    }
};

LC-13：Roman to Integer#

Idea
- Involves addition and subtraction, can use switch...case...
- Traverse the string in order, adding an extra layer of judgment for special characters
Code

class Solution {
public:
    int romanToInt(string s) {
        int ans = 0;
        // Traverse from left to right
        for (int i = 0; i < s.size(); i++) {
            // There are many conditions to check, use switch...case...
            switch (s[i]) {
                // First consider the naive case
                case 'V' :
                    ans += 5;
                    break;
                case 'L' :
                    ans += 50;
                    break;
                case 'D' :
                    ans += 500;
                    break;
                case 'M' :
                    ans += 1000;
                    break;
                case 'I' :
                    // Will i + 1 overflow? No, the end of the string has '\0'
                    if (s[i + 1] == 'V') {
                        ans += 4;
                        i++;  // Manually add once more
                    } else if (s[i + 1] == 'X') {
                        ans += 9;
                        i++;
                    } else {
                        ans += 1;
                    }
                    break;  // Remember to break
                case 'X' :
                    if (s[i + 1] == 'L') {
                        ans += 40;
                        i++;
                    } else if (s[i + 1] == 'C') {
                        ans += 90;
                        i++;
                    } else {
                        ans += 10;
                    }
                    break;
                case 'C' :
                    if (s[i + 1] == 'D') {
                        ans += 400;
                        i++;
                    } else if (s[i + 1] == 'M') {
                        ans += 900;
                        i++;
                    } else {
                        ans += 100;
                    }
                    break;
            }
        }
        return ans;
    }
};

- Will i + 1 overflow? No, the end of the string has '\0'

LC-14：Longest Common Prefix#

Idea
- Compare the current common prefix with the next string to update the common prefix
  - The initial common prefix is the first string
  - If it becomes empty midway, return empty directly
  - Continue until all strings are traversed
  - A variable is needed to store the common prefix after each comparison
Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";  // According to convention, first check for empty
        string ans = strs[0];  // Initialize the answer as the first string
        // Start traversing from the second string
        for (int i = 1; i < strs.size(); i++) {
            string t = ans;  // Store the current common prefix t, cannot directly use ans for traversal!
            ans = "";  // Record the common prefix after one comparison
            // Length less than 【the length of the string to be traversed】 and 【the length of the current common prefix】
            for (int j = 0; j < strs[i].size() && j < t.size(); j++) {
                if (strs[i][j] == t[j]) {
                    ans += t[j];
                } else {
                    break;
                }
            }
            if (ans == "") {
                break;
            }
        }
        return ans;
    }
};

- First check for empty array
- A new variable is needed to store the previous common prefix

LC-26：Remove Duplicates from Sorted Array#

Idea
- Already sorted, modify in place
- Two pointers
  - Pointer for storing values + pointer for traversing the array
  - Values of the two pointers
    - If different, store the value at the previous pointer and move both pointers forward
    - If the same, only move the latter pointer
Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        // Pointer p for storage, fast pointer i
        int p = 1;  // The 0th number definitely exists
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1]) {
                nums[p] = nums[i];
                p++;
                // nums[p++] = nums[i];
            }
        }
        return p;
    }
};

- Two pointers~

LC-27：Remove Element#

Idea
- Similar to LC-26, even simpler
- Also two pointers
  - If equal, the fast pointer moves forward
  - If not equal, the storage pointer stores the value and both move forward
Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0) return 0;
        int p = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[p++] = nums[i];  // Store value when not equal
            }
        }
        return p;
    }
};

LC-35：Search Insert Position#

Idea
- Already sorted
- Find the index of the target value or find the insertion position in order
- 0000011111111 special binary search!
Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // Special case: the target value is greater than the maximum number
        if (nums[nums.size() - 1] < target) {
            return nums.size();
        }
        // Special binary search: 000001111111
        int l = 0, r = nums.size() - 1;
        while (l != r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
};

- Remember to consider special cases: 0000000000, check in advance

LC-38：Count and Say#

Idea
- Calculate the next item based on the previous one
  - Counter counts, initially 1, remember to reset to 1
  - Determine how many consecutive characters there are, check if the previous and current characters are equal
Code

class Solution {
public:
    string ans[5] = {"", "1"};  // The 0th item is ignored, the 1st item is "1"
    // ↑ Only need to store two strings alternately
    void func(int s1, int s2) {
        ans[s2] = "";
        int cnt = 1;  // Count: how many times the current character is consecutive
        // cnt starts at 1, from the second character
        for (int i = 1; i < ans[s1].size(); i++) {
            if (ans[s1][i - 1] == ans[s1][i]) {
                cnt++;
            } else {
                ans[s2] += cnt + '0';  // Convert number to character!
                ans[s2] += ans[s1][i - 1];  // cnt of what character
                cnt = 1;
            }
        }
        // Note: The last round has not been output yet
        ans[s2] += cnt + '0';
        ans[s2] += ans[s1][ans[s1].size() - 1];  // The last character
    }
    void swap(int *a, int *b) {
        // Master the swap method
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    // Function given by the problem
    string countAndSay(int n) {
        int a = 1, b = 0;  // Used to swap string indices
        for (int i = 2; i <= n; i++) {
            func(a, b);  // Calculate the next string ans[b] based on the previous string ans[a]
            swap(&a, &b);
        }
        return ans[a];
    }
};

- You can use two strings to alternate records
- Remember to convert numbers to characters
- Note that the last round needs to be output separately

LC-53：Maximum Subarray#

Idea
- ans[x] = maximum continuous sum ending at x
- ans[x] = max(ans[x - 1] + num[x], num[x])
- No need for an array, only two variables are needed
  - Last maximum ans
  - Current maximum now
Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, now = 0;  // You can also directly use nums[0] instead of INT_MIN
        for (int i = 0; i < nums.size(); i++) {
            now = max(now + nums[i], nums[i]);  // Key, the maximum value currently reachable
            ans = max(ans, now);  // Update the current maximum value
        }
        return ans;
    }
};

- Handle ans and now well!

LC-66：Plus One#

Idea
- Simpler than adding large numbers, no need to reverse
  - Just check for carry from back to front
  - Pay attention to handle the carry of the highest digit, using the vector's insert method
Code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        digits[digits.size() - 1]++;
        // Handle the carry for each digit after adding one
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] == 10) {
                digits[i] = 0;
                // Special handling for the carry of the highest digit else
                if (i != 0) {
                    digits[i - 1]++;
                } else {
                    digits.insert(digits.begin(), 1);  // O(N)
                    // insert, digit.begin()
                }
            } else {
                break;
            }
        }
        return digits;
    }
};

- insert
  - O(N)
  - Reference std::vector::insert
- digit.begin()
  - Returns an iterator to the first element in the current vector container
  - Reference Usage of begin() and end() functions, front() and back() in vector container-CSDN

LC-69：Square Root of x#

Idea
- Integer binary search
  - For example: to find the square root of 8
  - Traverse 0 - 8: 0123456789
  - The goal is to get 2
  - So corresponding to 1110000000 situation
Code

class Solution {
public:
    int mySqrt(int x) {
        // 111110000
        long long l = 0, r = x;
        while (l != r) {
            // Define long long
            long long mid = (l + r + 1) / 2;
            if (mid * mid <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

- mid * mid may overflow, so define long long type uniformly

LC-70：Climbing Stairs#

Idea
- This is the Fibonacci sequence
- Two methods: recursion + memoization; iteration
- Extension: may have large integer types; can climb more steps at once
Code

class Solution {
public:
    int ans[50] = {0, 1, 2};
    int climbStairs(int n) {
        // The function return value is int, the result will overflow when n=46
        // Method 1: Recursion + memoization
        if (ans[n]) {
            return ans[n];
        }
        // Remember to save ans[n]
        return ans[n] = climbStairs(n - 1) + climbStairs(n - 2);
        // Method 2: Iteration
        for (int i = 3; i <= n; i++) {
            ans[i] = ans[i - 1] + ans[i - 2];
        }
        return ans[n];
    }
};

- According to the problem, the function returns an int type, so n can be at most 45, it will overflow when n = 46

LC-88：Merge Sorted Array#

Idea
- nums1 has enough space, the extra space equals the length of nums2
- Store from back to front, larger values are stored in nums1 from the back
  - ❌ If stored from front to back, it will overwrite and need to be handled
Code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // nums1 has large space
        for (int i = m + n - 1; i >= 0; i--) {
            // Store from back to front
            if (m == 0 || n != 0 && nums2[n - 1] > nums1[m - 1]) {
                // Store nums2 elements
                nums1[i] = nums2[n - 1];
                n--;
            } else {
                // Store nums1 elements
                nums1[i] = nums1[m - 1];
                m--;
            }
        }
    }
};

- The judgment conditions must be rigorous!
- Store nums2's elements at the back
  - nums1 has been fully traversed, i.e., m = 0
  - Or
  - The corresponding value of nums2 is greater than nums1 and 【nums2 has not been fully traversed yet!】👈 must check
    - i.e., n != 0 && nums2[n - 1] > nums1[m - 1]
- Otherwise, store nums1's elements at the back

LC-118：Pascal's Triangle#

Idea
- The value of each position equals the sum of the upper left and upper values
- The given sample uses vector implementation, cannot use the zero-padding method of arrays!
  - Pay attention to the specific details of vector later
Code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        // Vector cannot leave a circle of 0 like arrays, need to handle the left and right boundaries of each row in advance
        vector<vector<int> > ans;  // In the old standard, there is a space after <int>
        // Special case
        if (numRows == 0) {
            return ans;
        }
        // First row
        ans.push_back({1});
        // The second row corresponds to i = 1
        for (int i = 1; i < numRows; i++) {
            vector<int> v;  // Define a temporary vector to store this row
            v.push_back(1);  // Left boundary
            // The i-th row has i - 1 elements besides the two 1s at both ends
            for (int j = 1; j < i; j++) {
                v.push_back(ans[i - 1][j - 1] + ans[i - 1][j]);
            }
            v.push_back(1);  // Right boundary
            ans.push_back(v);
        }
        return ans;
    }
};

- Vector method: push_back

LC-121：Best Time to Buy and Sell Stock I#

Idea
Only buy and sell once
- Traverse
  - Update the current minimum value: initially set to the first number
  - Update the answer: compare 【temporary answer】 with 【current value - current minimum】
    - The answer is initially 0
  - Output the answer
Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            // Special case needed, otherwise prices[0] does not exist during initialization will cause an error
            return 0;
        }
        int ans = 0, mmin = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            ans = max(ans, prices[i] - mmin);
            mmin = min(mmin, prices[i]);
        }
        return ans;
    }
};

- The answer ans is initially 0, the current minimum value mmin is initially set to the first number prices[0]
  - Using two m's is to avoid naming conflicts with C++'s min() function
  - Special case needed, prices may have no values
  - vector.size()

LC-122：Best Time to Buy and Sell Stock II#

Idea
- Can buy and sell any number of times
- Consider two days at a time, only look at whether you can make a profit between adjacent two days
Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // Divide into several two-day periods
        // Special case can be added
        int ans = 0;
        for (int i = 1; i < prices.size(); i++) {
            // As long as the current day's stock price is higher than the previous day's
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
};

- Special case can be added or not, as prices.size() has already limited the loop

LC-136：Single Number#

Idea
- Essence: Bitwise XOR
  - 0 ^ x = x
  - x ^ x = 0
Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i]; 
        }
        return ans;
    }
};

Additional Knowledge Points#

Prefix Sum#

Quickly calculate the sum of intervals
- Prefix sum array sum
- The sum of the interval [x, y]: sum[y] - sum[x - 1]
- Open an extra 0 position in the array to avoid the case where sum[1 - 1] has no value
Maintain an additional array to avoid the time cost of multiple queries

Points to Consider#

Tips#

Course Summary#

Self-made: 67, 119 (reference 118), 125