268 篇文章 含有標籤「leetcode」

/*
 * @lc app=leetcode id=72 lang=cpp
 *
 * [72] Edit Distance
 *
 * https://leetcode.com/problems/edit-distance/description/
 *
 * algorithms
 * Medium (57.62%)
 * Likes:    15237
 * Dislikes: 249
 * Total Accepted:    1M
 * Total Submissions: 1.8M
 * Testcase Example:  '"horse"\n"ros"'
 *
 * Given two strings word1 and word2, return the minimum number of operations
 * required to convert word1 to word2.
 *
 * You have the following three operations permitted on a word:
 *
 *
 * Insert a character
 * Delete a character
 * Replace a character
 *
 *
 *
 * Example 1:
 *
 *
 * Input: word1 = "horse", word2 = "ros"
 * Output: 3
 * Explanation:
 * horse -> rorse (replace 'h' with 'r')
 * rorse -> rose (remove 'r')
 * rose -> ros (remove 'e')
 *
 *
 * Example 2:
 *
 *
 * Input: word1 = "intention", word2 = "execution"
 * Output: 5
 * Explanation:
 * intention -> inention (remove 't')
 * inention -> enention (replace 'i' with 'e')
 * enention -> exention (replace 'n' with 'x')
 * exention -> exection (replace 'n' with 'c')
 * exection -> execution (insert 'u')
 *
 *
 *
 * Constraints:
 *
 *
 * 0 <= word1.length, word2.length <= 500
 * word1 and word2 consist of lowercase English letters.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
                }
            }
        }
        return dp[m][n];
    }
};
// @lc code=end

class Solution {
public:
    string simplifyPath(string path)
    {
        vector<string> dir;
        stringstream ss(path);
        string token;
        while(getline(ss, token, '/'))
        {
            if(token == "..")
            {
                if (!dir.empty()) dir.pop_back();
            }
            else if (!token.empty() && token != ".")
            {
                dir.push_back(token);
            }
        }
        string res;
        for (auto s : dir) res += "/" + s;
        return res.empty() ? "/" : res;
    }
};

/*
 * @lc app=leetcode id=70 lang=cpp
 *
 * [70] Climbing Stairs
 *
 * https://leetcode.com/problems/climbing-stairs/description/
 *
 * algorithms
 * Easy (53.10%)
 * Likes:    22131
 * Dislikes: 862
 * Total Accepted:    3.5M
 * Total Submissions: 6.7M
 * Testcase Example:  '2'
 *
 * You are climbing a staircase. It takes n steps to reach the top.
 *
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can
 * you climb to the top?
 *
 *
 * Example 1:
 *
 *
 * Input: n = 2
 * Output: 2
 * Explanation: There are two ways to climb to the top.
 * 1. 1 step + 1 step
 * 2. 2 steps
 *
 *
 * Example 2:
 *
 *
 * Input: n = 3
 * Output: 3
 * Explanation: There are three ways to climb to the top.
 * 1. 1 step + 1 step + 1 step
 * 2. 1 step + 2 steps
 * 3. 2 steps + 1 step
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= n <= 45
 *
 *
 */

// @lc code=start
class Solution {
public:
    int climbStairs(int n)
    {
        if(n < 2) return n;

        vector<int> dp(n + 1);

        dp[0] = 1, dp[1] = 1;

        for(int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
// @lc code=end

class Solution {
public:
    int climbStairs(int n)
    {
        int previousStep = 1, currentStep = 1;
        for(int step = 2; step <= n; step++)
        {
            int nextStep = previousStep + currentStep;
            previousStep = currentStep;
            currentStep = nextStep;
        }
        return currentStep;
    }
};

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth)
    {
        int n = words.size();
        int start = 0;
        vector<string> res;
        while (start < n)
        {
            int last = start, totalChars = 0;
            while (last < n && totalChars + words[last].size() + last - start <= maxWidth)
            {
                totalChars += words[last++].size();
            }

            string cur;

            int space = maxWidth - totalChars;

            for (int k = start; k < last; ++k)
            {
                cur += words[k];
                if (space > 0)
                {
                    int cnt;

                    if (last == n)
                    {
                        if (last - k == 1)
                        {
                            cnt = space;
                        }
                        else
                        {
                            cnt = 1;
                        }
                    }
                    else
                    {
                        if (last - k > 1)
                        {
                            if (space % (last - k - 1) == 0)
                            {
                                cnt = space / (last - k - 1);
                            }
                            else
                            {
                                cnt = space / (last - k - 1) + 1;
                            }
                        }
                        else
                        {
                            cnt = space;
                        }
                    }
                    cur.append(cnt, ' ');
                    space -= cnt;
                }
            }
            res.push_back(cur);
            start = last;
        }
        return res;
    }
};

class Solution {
public:
    bool isNumber(string s)
    {
        // Check if the string is empty; if so, it's not a valid number
        // ex: s = ""

        // Remove trailing spaces
        // ex: s = "123  "

        // Remove leading spaces
        // ex: s = "  123"

        // Indicates if a decimal point has been encountered
        // Indicates if 'e' (exponent) has been encountered
        // Indicates if any digit has been encountered

        // Iterate through each character in the string
        for ()
        {
            // Convert character to lowercase for uniform processing

            // Check if the current character is a digit
            if ()
            {

            }
            // Check if the current character is a decimal point
            else if ()
            {
                // Decimal point is not allowed if 'e' has been encountered or if there's already a decimal point
                // ex: s = "99e2.5"
            }
            // Check if the current character is 'e' (exponent)
            else if ()
            {
                // 'e' is not allowed if it has already been encountered or if there are no digits before it
                // ex: s = "95a54e53", s = "e797537"
                // Reset digit flag for the part after 'e'
            }
            // Check if the current character is a sign (+ or -)
            else if ()
            {
                // A sign can only appear at the start or immediately after 'e'
            }
            else // Invalid character
        }

        // The string is valid if and only if at least one digit was found
    }
};

class Solution {
public:
    bool isNumber(string s)
    {
        // Check if the string is empty; if so, it's not a valid number
        if (s.empty()) return false;

        // Remove trailing spaces
        while (s.back() == ' ') s.pop_back();

        // Remove leading spaces
        while (s.front() == ' ') s.erase(s.begin());

        bool dot = false;  // Indicates if a decimal point has been encountered
        bool e = false;    // Indicates if 'e' (exponent) has been encountered
        bool digit = false; // Indicates if any digit has been encountered

        // Iterate through each character in the string
        for (int i = 0; i < s.size(); ++i)
        {
            s[i] = tolower(s[i]); // Convert character to lowercase for uniform processing

            // Check if the current character is a digit
            if (isdigit(s[i]))
            {
                digit = true;
            }
            // Check if the current character is a decimal point
            else if (s[i] == '.')
            {
                // Decimal point is not allowed if 'e' has been encountered or if there's already a decimal point
                if (e || dot) return false;
                dot = true;
            }
            // Check if the current character is 'e' (exponent)
            else if (s[i] == 'e')
            {
                // 'e' is not allowed if it has already been encountered or if there are no digits before it
                if (e || !digit) return false;
                e = true;
                digit = false; // Reset digit flag for the part after 'e'
            }
            // Check if the current character is a sign (+ or -)
            else if (s[i] == '-' || s[i] == '+')
            {
                // A sign can only appear at the start or immediately after 'e'
                if (i != 0 && s[i - 1] != 'e') return false;
            }
            else return false; // Invalid character
        }

        // The string is valid if and only if at least one digit was found
        return digit;
    }
};

/*
 * @lc app=leetcode id=64 lang=cpp
 *
 * [64] Minimum Path Sum
 *
 * https://leetcode.com/problems/minimum-path-sum/description/
 *
 * algorithms
 * Medium (64.84%)
 * Likes:    12556
 * Dislikes: 172
 * Total Accepted:    1.3M
 * Total Submissions: 2M
 * Testcase Example:  '[[1,3,1],[1,5,1],[4,2,1]]'
 *
 * Given a m x n grid filled with non-negative numbers, find a path from top
 * left to bottom right, which minimizes the sum of all numbers along its
 * path.
 *
 * Note: You can only move either down or right at any point in time.
 *
 *
 * Example 1:
 *
 *
 * Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
 * Output: 7
 * Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
 *
 *
 * Example 2:
 *
 *
 * Input: grid = [[1,2,3],[4,5,6]]
 * Output: 12
 *
 *
 *
 * Constraints:
 *
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 200
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();

        for (int i = 1; i < m; ++i)
        {
            grid[i][0] += grid[i - 1][0];
        }

        for (int j = 1; j < n; ++j)
        {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=63 lang=cpp
 *
 * [63] Unique Paths II
 *
 * https://leetcode.com/problems/unique-paths-ii/description/
 *
 * algorithms
 * Medium (42.37%)
 * Likes:    8964
 * Dislikes: 521
 * Total Accepted:    1.1M
 * Total Submissions: 2.5M
 * Testcase Example:  '[[0,0,0],[0,1,0],[0,0,0]]'
 *
 * You are given an m x n integer array grid. There is a robot initially
 * located at the top-left corner (i.e., grid[0][0]). The robot tries to move
 * to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only
 * move either down or right at any point in time.
 *
 * An obstacle and space are marked as 1 or 0 respectively in grid. A path that
 * the robot takes cannot include any square that is an obstacle.
 *
 * Return the number of possible unique paths that the robot can take to reach
 * the bottom-right corner.
 *
 * The testcases are generated so that the answer will be less than or equal to
 * 2 * 10^9.
 *
 *
 * Example 1:
 *
 *
 * Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 * Output: 2
 * Explanation: There is one obstacle in the middle of the 3x3 grid above.
 * There are two ways to reach the bottom-right corner:
 * 1. Right -> Right -> Down -> Down
 * 2. Down -> Down -> Right -> Right
 *
 *
 * Example 2:
 *
 *
 * Input: obstacleGrid = [[0,1],[0,0]]
 * Output: 1
 *
 *
 *
 * Constraints:
 *
 *
 * m == obstacleGrid.length
 * n == obstacleGrid[i].length
 * 1 <= m, n <= 100
 * obstacleGrid[i][j] is 0 or 1.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();

        vector<vector<int>> dp(m, vector<int>(n));

        dp[0][0] = obstacleGrid[0][0] ? 0 : 1;

        for (int i = 1; i < m; i++)
        {
            dp[i][0] = !obstacleGrid[i][0] && dp[i - 1][0] ? 1 : 0;
        }
        for (int j = 1; j < n; j++)
        {
            dp[0][j] = !obstacleGrid[0][j] && dp[0][j - 1] ? 1 : 0;
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (!obstacleGrid[i][j])
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=62 lang=cpp
 *
 * [62] Unique Paths
 *
 * https://leetcode.com/problems/unique-paths/description/
 *
 * algorithms
 * Medium (65.00%)
 * Likes:    16985
 * Dislikes: 457
 * Total Accepted:    2.1M
 * Total Submissions: 3.2M
 * Testcase Example:  '3\n7'
 *
 * There is a robot on an m x n grid. The robot is initially located at the
 * top-left corner (i.e., grid[0][0]). The robot tries to move to the
 * bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move
 * either down or right at any point in time.
 *
 * Given the two integers m and n, return the number of possible unique paths
 * that the robot can take to reach the bottom-right corner.
 *
 * The test cases are generated so that the answer will be less than or equal
 * to 2 * 10^9.
 *
 *
 * Example 1:
 *
 *
 * Input: m = 3, n = 7
 * Output: 28
 *
 *
 * Example 2:
 *
 *
 * Input: m = 3, n = 2
 * Output: 3
 * Explanation: From the top-left corner, there are a total of 3 ways to reach
 * the bottom-right corner:
 * 1. Right -> Down -> Down
 * 2. Down -> Down -> Right
 * 3. Down -> Right -> Down
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= m, n <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};
// @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* rotateRight(ListNode* head, int k) {
        // base case
        if (!head || !head->next) return head;

        // 計算 linked list 長度
        ListNode* cur = head;
        int n = 1;
        while(cur->next) {
            cur = cur->next;
            ++n;
        }

        // 接成一個環
        cur->next = head;

        // 因為也有 k 大於 n 的情況
        // 所以這裡要做 k %= n 處理
        k %= n;

        // 再用一個 new_tail pointer 指向 head
        // 新的節點的頭是從末端數回來第 k 個節點，所以是 n - k
        ListNode* new_tail = head;
        for (int i = 0; i < n - k - 1; ++i) {
            // new_tail 移到新的節點的頭
            new_tail = new_tail->next;
        }

        // 新的節點的 head = new_tail->next
        // 以 head = [1, 2, 3, 4, 5] 這個例子來說
        // 現在的 new_head 指向 4
        ListNode* new_head = new_tail->next;

        // 斷開環
        // 以 head = [1, 2, 3, 4, 5] 這個例子來說
        // 現在的 new_tail 指向 3，所以 new_tail->next 要指向 NULL
        new_tail->next = nullptr;
        // 最後 retrun 新的起始點 head
        return new_head;
    }
};