268 篇文章 含有標籤「leetcode」

/**
 * 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* reverseList(ListNode* head)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(cur)
        {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};

/**
 * 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* reverseList(ListNode* head)
    {
        if(!head || !head->next) return head;

        ListNode* prev = reverseList(head->next);
        // 1 -> 2 <- 3 <- 4 <- 5
        // ^ head

        head->next->next = head;
        head->next = NULL;
        return prev;
    }
};

class Solution {
public:
    bool isIsomorphic(string s, string t)
    {
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;

        int n = t.size();

        for (int i = 0; i < n; i++)
        {
            if (m1[s[i]] != m2[t[i]])
            {
                return false;
            }
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

class Solution {
public:
    int countPrimes(int n)
    {
        // If n is less than or equal to 2, there are no prime numbers less than n

        // Create a boolean vector to mark prime numbers
        // 0 and 1 are not prime numbers

        // Use the Sieve of Eratosthenes algorithm to mark non-prime numbers
        for ()
        {
            if () // If i is a prime number
            {
                // Mark all multiples of i as non-prime
            }
        }

        // Count the number of prime numbers
        for ()
        {
            // Increment count if i is a prime number
        }
        // Return the total count of prime numbers
    }
};

class Solution {
public:
    int countPrimes(int n)
    {
        if (n <= 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i < n; ++i)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j < n; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        int res = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime[i]) res++;
        }
        return res;
    }
};

class Solution {
public:
    bool isHappy(int n)
    {
        unordered_set<int> seen;
        while (n != 1 && !seen.count(n))
        {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }

    int getNext(int n)
    {
        int totalSum = 0;
        while (n > 0)
        {
            int digit = n % 10;
            n = n / 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }
};

class Solution {
public:
    bool isHappy(int n)
    {
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && slow != fast)
        {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }

    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
};

/*
 * @lc app=leetcode id=200 lang=cpp
 *
 * [200] Number of Islands
 *
 * https://leetcode.com/problems/number-of-islands/description/
 *
 * algorithms
 * Medium (60.29%)
 * Likes:    22949
 * Dislikes: 524
 * Total Accepted:    2.9M
 * Total Submissions: 4.8M
 * Testcase Example:  '[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]'
 *
 * Given an m x n 2D binary grid grid which represents a map of '1's (land) and
 * '0's (water), return the number of islands.
 *
 * An island is surrounded by water and is formed by connecting adjacent lands
 * horizontally or vertically. You may assume all four edges of the grid are
 * all surrounded by water.
 *
 *
 * Example 1:
 *
 *
 * Input: grid = [
 * ⁠ ["1","1","1","1","0"],
 * ⁠ ["1","1","0","1","0"],
 * ⁠ ["1","1","0","0","0"],
 * ⁠ ["0","0","0","0","0"]
 * ]
 * Output: 1
 *
 *
 * Example 2:
 *
 *
 * Input: grid = [
 * ⁠ ["1","1","0","0","0"],
 * ⁠ ["1","1","0","0","0"],
 * ⁠ ["0","0","1","0","0"],
 * ⁠ ["0","0","0","1","1"]
 * ]
 * Output: 3
 *
 *
 *
 * Constraints:
 *
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 300
 * grid[i][j] is '0' or '1'.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int island = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    dfs(grid, i, j);
                    island++;
                }
            }
        }
        return island;
    }
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0') return;

        grid[i][j] = '0';
        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions)
        {
            dfs(grid, i + dir[0], j + dir[1]);
        }
    }
};
// @lc code=end

class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int island = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    grid[i][j] = '0';

                    queue<pair<int, int>> q;

                    q.push({i, j});

                    vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
                    while (!q.empty())
                    {
                        auto node = q.front(); q.pop();
                        for (const auto& dir : directions)
                        {
                            int new_i = node.first + dir[0];
                            int new_j = node.second + dir[1];
                            if (new_i < 0 || new_j < 0 || new_i >= m || new_j >= n || grid[new_i][new_j] == '0') continue;
                            grid[new_i][new_j] = '0';
                            q.push({new_i, new_j});
                        }
                    }
                    island++;
                }
            }
        }
        return island;
    }
};

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;
public:
    UnionFind(vector<vector<char>>& grid) {
        count = 0;
        int rows = grid.size(), cols = grid[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    parent.push_back(i * cols + j);
                    // 將每一個格子當成 root
                    ++count;
                } else {
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }

    int find(int i) {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void Union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty])
                parent[rooty] = rootx;
            else if (rank[rootx] < rank[rooty])
                parent[rootx] = rooty;
            else {
                parent[rooty] = rootx;
                rank[rootx] += 1;
            }
            --count;
        }
    }

    int getCount() const {
        return count;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        if (!rows) return 0;

        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        UnionFind uf (grid);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    for(auto& dir : directions) {
                        int new_i = i + dir[0];
                        int new_j = j + dir[1];
                        if(new_i < 0 || new_j < 0 || new_i >= rows || new_j >= cols || grid[new_i][new_j] == '0')
                            continue;
                        uf.Union(i * cols + j, new_i * cols + new_j);
                    }
                }
            }
        }
        return uf.getCount();
    }
};

/*
 * @lc app=leetcode id=198 lang=cpp
 *
 * [198] House Robber
 *
 * https://leetcode.com/problems/house-robber/description/
 *
 * algorithms
 * Medium (51.66%)
 * Likes:    21832
 * Dislikes: 460
 * Total Accepted:    2.7M
 * Total Submissions: 5.2M
 * Testcase Example:  '[1,2,3,1]'
 *
 * You are a professional robber planning to rob houses along a street. Each
 * house has a certain amount of money stashed, the only constraint stopping
 * you from robbing each of them is that adjacent houses have security systems
 * connected and it will automatically contact the police if two adjacent
 * houses were broken into on the same night.
 *
 * Given an integer array nums representing the amount of money of each house,
 * return the maximum amount of money you can rob tonight without alerting the
 * police.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,2,3,1]
 * Output: 4
 * Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
 * Total amount you can rob = 1 + 3 = 4.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [2,7,9,3,1]
 * Output: 12
 * Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house
 * 5 (money = 1).
 * Total amount you can rob = 2 + 9 + 1 = 12.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 *
 *
 */

// @lc code=start
class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

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

class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();

        if (n == 1) return nums[0];

        int prevPrevMax = nums[0];
        int prevMax = max(nums[0], nums[1]);
        int currentMax = 0;

        for (int i = 2; i < n; ++i)
        {
            currentMax = max(prevMax, prevPrevMax + nums[i]);
            prevPrevMax = prevMax;
            prevMax = currentMax;
        }

        return prevMax;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        reverse(nums.begin(), nums.end());
        k %= nums.size();

        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int left = 0, right = nums.size() - 1;
        reverseArray(nums, left, right);
        k %= nums.size();

        left = 0, right = k - 1;
        reverseArray(nums, left, right);

        left = k, right = nums.size() - 1;
        reverseArray(nums, left, right);
    }
    void reverseArray(vector<int>& nums, int left, int right)
    {
        while (left < right)
        {
            swap(nums[left], nums[right]);
            ++left; --right;
        }
    }
};

/*
 * @lc app=leetcode id=188 lang=cpp
 *
 * [188] Best Time to Buy and Sell Stock IV
 *
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/
 *
 * algorithms
 * Hard (45.01%)
 * Likes:    7593
 * Dislikes: 212
 * Total Accepted:    534.4K
 * Total Submissions: 1.2M
 * Testcase Example:  '2\n[2,4,1]'
 *
 * You are given an integer array prices where prices[i] is the price of a
 * given stock on the i^th day, and an integer k.
 *
 * Find the maximum profit you can achieve. You may complete at most k
 * transactions: i.e. you may buy at most k times and sell at most k times.
 *
 * Note: You may not engage in multiple transactions simultaneously (i.e., you
 * must sell the stock before you buy again).
 *
 *
 * Example 1:
 *
 *
 * Input: k = 2, prices = [2,4,1]
 * Output: 2
 * Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit
 * = 4-2 = 2.
 *
 *
 * Example 2:
 *
 *
 * Input: k = 2, prices = [3,2,6,5,0,3]
 * Output: 7
 * Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit
 * = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3),
 * profit = 3-0 = 3.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= k <= 100
 * 1 <= prices.length <= 1000
 * 0 <= prices[i] <= 1000
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();

        if (n == 0) return 0;

        if (k >= n) return getMaxProfit(prices);

        vector<int> curMaxProfit(k + 1, 0);
        vector<int> maxProfit(k + 1, 0);

        for (int i = 1; i < n; i++)
        {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j >= 1; j--)
            {
                curMaxProfit[j] = max(curMaxProfit[j] + diff, maxProfit[j - 1] + max(0, diff));
                maxProfit[j] = max(maxProfit[j], curMaxProfit[j]);
            }
        }
        return maxProfit[k];
    }
    int getMaxProfit(vector<int>& prices)
    {
        int maxProfit = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] > prices[i - 1])
            {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
};
// @lc code=end

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        int n = nums.size();

        vector<string> strNums(n);

        // 元素轉成 string
        for (int i = 0; i < n; ++i) {
            strNums[i] = to_string(nums[i]);
        }

        sort(strNums.begin(), strNums.end(),
             [](string& a, string& b) { return a + b > b + a; });

        // 因為已經從大排到小了，最前面如果是 0，就直接返回 0
        if (strNums[0] == "0") {
            return "0";
        }

        string res;
        for (string s : strNums) res += s;

        return res;
    }
};