268 篇文章 含有標籤「leetcode」

class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students)
    {
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());

        int n = seats.size();
        int moves = 0;
        for (int i = 0; i < n; ++i)
        {
            moves += abs(seats[i] - students[i]);
        }
        return moves;
    }
};

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

class Solution {
public:
    bool checkZeroOnes(string s)
    {
        int zeroCnt = 1, oneCnt = 1;
        int maxZero = 1, maxOne = 1;
        if (s.size() == 1) return s[0] == '1' ? true : false;
        // s = "1101"
        for (int i = 0; i < s.size() - 1; i++)
        {
            if (s[i] == '1' && s[i] == s[i + 1])
            {
                maxOne = max(maxOne, ++oneCnt);
            }
            else
            {
                oneCnt = 1;
            }
            if (s[i] == '0' && s[i] == s[i + 1])
            {
                maxZero = max(maxZero, ++zeroCnt);
            }
            else
            {
                zeroCnt = 1;
            }
        }
        return maxOne > maxZero ? true : false;
    }
};

class Solution {
public:
    int findTheWinner(int n, int k)
    {
        return helper(n, k) + 1;
    }

    int helper(int n, int k)
    {
        if (n == 1) return 0;
        return (helper(n - 1, k) + k) % n;
    }
};

class Solution {
public:
    int findTheWinner(int n, int k)
    {
        int res = 0;
        for (int i = 2; i <= n; i++)
        {
            res = (res + k) % i;
        }
        return res + 1;
    }
};

class Solution {
public:
    int findCenter(vector<vector<int>>& edges)
    {
        vector<int> first = edges[0], second = edges[1];
        return (first[0] == second[0] || first[0] == second[1]) ? first[0] : first[1];
    }
};

/*
 * @lc app=leetcode id=1742 lang=cpp
 *
 * [1742] Maximum Number of Balls in a Box
 *
 * https://leetcode.com/problems/maximum-number-of-balls-in-a-box/description/
 *
 * algorithms
 * Easy (73.70%)
 * Likes:    636
 * Dislikes: 167
 * Total Accepted:    75.7K
 * Total Submissions: 102K
 * Testcase Example:  '1\n10'
 *
 * You are working in a ball factory where you have n balls numbered from
 * lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1),
 * and an infinite number of boxes numbered from 1 to infinity.
 *
 * Your job at this factory is to put each ball in the box with a number equal
 * to the sum of digits of the ball's number. For example, the ball number 321
 * will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be
 * put in the box number 1 + 0 = 1.
 *
 * Given two integers lowLimit and highLimit, return the number of balls in the
 * box with the most balls.
 *
 *
 * Example 1:
 *
 *
 * Input: lowLimit = 1, highLimit = 10
 * Output: 2
 * Explanation:
 * Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
 * Ball Count:  2 1 1 1 1 1 1 1 1 0  0  ...
 * Box 1 has the most number of balls with 2 balls.
 *
 * Example 2:
 *
 *
 * Input: lowLimit = 5, highLimit = 15
 * Output: 2
 * Explanation:
 * Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
 * Ball Count:  1 1 1 1 2 2 1 1 1 0  0  ...
 * Boxes 5 and 6 have the most number of balls with 2 balls in each.
 *
 *
 * Example 3:
 *
 *
 * Input: lowLimit = 19, highLimit = 28
 * Output: 2
 * Explanation:
 * Box Number:  1 2 3 4 5 6 7 8 9 10 11 12 ...
 * Ball Count:  0 1 1 1 1 1 1 1 1 2  0  0  ...
 * Box 10 has the most number of balls with 2 balls.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= lowLimit <= highLimit <= 10^5
 *
 *
 */

// @lc code=start
class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        unordered_map<int, int> m;
        int res = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            m[digitsSum(i)]++;
        }
        for (const auto& [k, v] : m) {
            res = max(res, v);
        }
        return res;
    }
    int digitsSum(int n) {
        int sum = 0;
        while (n) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
};
// @lc code=end

#define ll long long

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers)
    {
        int n = customers.size();
        int endTime = 0;
        ll waitTime = 0;
        for (int i = 0; i < n; ++i)
        {
            endTime = max(customers[i][0], endTime) + customers[i][1];
            waitTime += endTime - customers[i][0];
        }
        return (double)waitTime / n;
    }
};

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words)
    {
        unordered_set<int> st(allowed.begin(), allowed.end());
        int cnt = words.size();
        for (auto word : words)
        {
            for (auto w : word)
            {
                if (!st.count(w))
                {
                    cnt--;
                    break;
                }
            }
        }
        return cnt;
    }
};

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum)
    {
        // Vectors to keep track of the current sum of elements in each row and column

        // Initialize the matrix with dimensions m x n filled with zeros

        // Fill the matrix with appropriate values
        for ()
        {
            for ()
            {
                // Calculate the value to place at matrix[i][j]
                // It should be the minimum of the remaining row sum and column sum

                // Update the current sums for the row and column
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum)
    {
        int m = rowSum.size(), n = colSum.size();

        vector<int> curRowSum(m);
        vector<int> curColSum(n);

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

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                matrix[i][j] = min(rowSum[i] - curRowSum[i], colSum[j] - curColSum[j]);
                curRowSum[i] += matrix[i][j];
                curColSum[j] += matrix[i][j];
            }
        }
        return matrix;
    }
};