268 篇文章 含有標籤「leetcode」

class Solution {
public:
    int minOperations(vector<string>& logs)
    {
        int depth = 0;
        for (string log : logs)
        {
            if (log == "../")
            {
                depth = max(0, --depth);
            }
            else if (log != "./")
            {
                ++depth;
            }
        }
        return depth;
    }
};

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr)
    {
        int cnt = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] % 2) cnt++;
            else cnt = 0;
            if (cnt == 3) return true;
        }
        return false;
    }
};

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange)
    {
        // 記錄總共喝掉的水瓶數量
        int res = 0;

        // while 迴圈會持續執行,直到剩下的瓶子數量小於可以換一個新瓶子所需的數量
        while (numBottles >= numExchange)
        {
            // 計算無法換新瓶子的剩餘瓶子數
            int m = numBottles % numExchange;

            // 將這次能喝的瓶子數(當前所有瓶子減去無法換的瓶子)加到結果中。
            res += numBottles - m;

            // 更新剩餘的瓶子數,包括無法換的瓶子(m)和換來的新瓶子(numBottles / numExchange)
            numBottles = m + numBottles / numExchange;
        }
        return res + numBottles;
    }
};

class Solution {
public:
    int minDifference(vector<int>& nums)
    {
        int n = nums.size();
        if (n <= 4) return 0;

        int minDiff = INT_MAX;

        sort(nums.begin(), nums.end());

        int left = 0, right = n - 4;
        while (right < n)
        {
            minDiff = min(minDiff, nums[right] - nums[left]);
            ++left; ++right;
        }

        return minDiff;
    }
};

/*
 * @lc app=leetcode id=1508 lang=cpp
 *
 * [1508] Range Sum of Sorted Subarray Sums
 *
 * https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/description/
 *
 * algorithms
 * Medium (63.14%)
 * Likes:    1557
 * Dislikes: 262
 * Total Accepted:    179.2K
 * Total Submissions: 284K
 * Testcase Example:  '[1,2,3,4]\n4\n1\n5'
 *
 * You are given the array nums consisting of n positive integers. You computed
 * the sum of all non-empty continuous subarrays from the array and then sorted
 * them in non-decreasing order, creating a new array of n * (n + 1) / 2
 * numbers.
 *
 * Return the sum of the numbers from index left to index right (indexed from
 * 1), inclusive, in the new array. Since the answer can be a huge number
 * return it modulo 10^9 + 7.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
 * Output: 13
 * Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After
 * sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4,
 * 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2
 * + 3 + 3 + 4 = 13.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
 * Output: 6
 * Explanation: The given array is the same as example 1. We have the new array
 * [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to
 * ri = 4 is 3 + 3 = 6.
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
 * Output: 50
 *
 *
 *
 * Constraints:
 *
 *
 * n == nums.length
 * 1 <= nums.length <= 1000
 * 1 <= nums[i] <= 100
 * 1 <= left <= right <= n * (n + 1) / 2
 *
 *
 */

// @lc code=start
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> rangeSum;
        for (int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                rangeSum.push_back(sum);
            }
        }
        sort(rangeSum.begin(), rangeSum.end());
        int res = 0;
        const int MOD = 1e9 + 7;
        for (int i = left - 1; i < right; i++) {
            res = (res + rangeSum[i]) % MOD;
        }
        return res;
    }
};
// @lc code=end

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr)
    {
        sort(target.begin(), target.end());
        sort(arr.begin(), arr.end());

        for (int i = 0; i < target.size(); ++i)
        {
            if (target[i] != arr[i]) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k)
    {
        int cnt = k;
        for (int num : nums)
        {
            if (num == 1)
            {
                if (cnt < k)
                {
                    return false;
                }
                cnt = 0;
            }
            else
            {
                ++cnt;
            }
        }
        return true;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<int> sorted;
    void inorder(TreeNode* root)
    {
        if (!root) return;
        inorder(root->left);
        sorted.push_back(root->val);
        inorder(root->right);
    }

    TreeNode* construct(vector<int>& sorted, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(sorted[mid]);
        root->left = construct(sorted, left, mid - 1);
        root->right = construct(sorted, mid + 1, right);
        return root;
    }

public:
    TreeNode* balanceBST(TreeNode* root)
    {
        inorder(root);
        return construct(sorted, 0, sorted.size() - 1);
    }
};

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix)
    {
        // Get the dimensions of the matrix

        // Variable to store the maximum of all row minimums
        for ()
        {
            // Variable to store the minimum value in the current row
            for ()
            {
                // Update the row minimum value
            }
            // Update the maximum of row minimums
        }

        // Variable to store the minimum of all column maximums
        for ()
        {
            // Variable to store the maximum value in the current column
            for ()
            {
                // Update the column maximum value
            }
            // Update the minimum of column maximums
        }

        // Check if the maximum of row minimums is equal to the minimum of column maximums
        // If true, return the lucky number

        // If no lucky number is found, return an empty vector
    }
};

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();

        int rMinMax = INT_MIN;
        for (int i = 0; i < m; ++i)
        {

            int rMin = INT_MAX;
            for (int j = 0; j < n; ++j)
            {
                rMin = min(rMin, matrix[i][j]);
            }
            rMinMax = max(rMinMax, rMin);
        }

        int cMaxMin = INT_MAX;
        for (int i = 0; i < n; ++i)
        {

            int cMax = INT_MIN;
            for (int j = 0; j < m; j++)
            {
                cMax = max(cMax, matrix[j][i]);
            }
            cMaxMin = min(cMaxMin, cMax);
        }
        if (rMinMax == cMaxMin)
        {
            return {rMinMax};
        }
        return {};
    }
};