leetcode weekly-contest-302

发布于 2022-07-17  606 次阅读


Maximum Number of Pairs in Array3

You are given a 0-indexed integer array nums. In one operation, you may do the following:

  • Choose two integers in nums that are equal.
  • Remove both integers from nums, forming a pair.

The operation is done on nums as many times as possible.

Return a 0-indexed integer array answer of size 2 where answer[0] is the number of pairs that are formed and answer[1] is the number of leftover integers in nums after doing the operation as many times as possible.

Example 1:

Input: nums = [1,3,2,1,3,2,2]
Output: [3,1]
Explanation:
Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2].
Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2].
Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2].
No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.

两个相同的数组成一个集合,剩下的放一边,除2和模2

哈希模拟。记录数字,然后模拟结果

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

class Solution {
public:
    vector<int> numberOfPairs(vector<int> &nums) {
        map<int, int> m;
        for (auto &n: nums) {
            m[n]++;
        }
        vector<int> ans(2, 0);
        for (auto&[n, t]: m) {
            ans[0] += t / 2;
            ans[1] += t % 2;
        }
        return ans;
    }
};

int main() {
    Solution s;
    vector<int> v = {1};
    vector<vector<int> > c = {{1}};
    return 0;
}

Max Sum of a Pair With Equal Sum of Digits

You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].

Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions.

Example 1:

Input: nums = [18,43,36,13,7]
Output: 54
Explanation: The pairs (i, j) that satisfy the conditions are:
- (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
- (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

求两个相同字和的数和的最大值,继续模拟

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

class Solution {
public:
    int sum(int x) {
        int ans = 0;
        while (x) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }

    int maximumSum(vector<int> &nums) {
        map<int, priority_queue<int>> p;
        for (auto &n: nums) {
            p[sum(n)].push(n);
        }
        int ans = -1;
        for (auto&[x, y]: p) {
            if (y.size() >= 2) {
                int cnt = y.top();
                y.pop();
                ans = max(ans, cnt + y.top());
            }
        }
        return ans;
    }
};

int main() {
    Solution s;
    vector<int> v = {1};
    vector<vector<int> > c = {{1}};
    return 0;
}

Query Kth Smallest Trimmed Number5

You are given a 0-indexed array of strings nums, where each string is of equal length and consists of only digits.

You are also given a 0-indexed 2D integer array queries where queries[i] = [ki, trimi]. For each queries[i], you need to:

  • Trim each number in nums to its rightmost trimi digits.
  • Determine the index of the kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.
  • Reset each number in nums to its original length.

Return an array answer of the same length as queries, where answer[i] is the answer to the ith query.

Note:

  • To trim to the rightmost x digits means to keep removing the leftmost digit, until only x digits remain.
  • Strings in nums may contain leading zeros.

Example 1:

Input: nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
Output: [2,2,1,0]
Explanation:
1. After trimming to the last digit, nums = ["2","3","1","4"]. The smallest number is 1 at index 2.
2. Trimmed to the last 3 digits, nums is unchanged. The 2nd smallest number is 251 at index 2.
3. Trimmed to the last 2 digits, nums = ["02","73","51","14"]. The 4th smallest number is 73.
4. Trimmed to the last 2 digits, the smallest number is 2 at index 0.
   Note that the trimmed number "02" is evaluated as 2.

预处理一下所有长度,模拟一下离线

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string> &nums, vector<vector<int>> &queries) {
        int l = nums[0].size();
        vector<vector<pair<string, int>>> f(l);
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < nums.size(); j++) {
                f[i].push_back({nums[j].substr(l - i - 1), j});
            }
        }
        for (auto &i: f) {
            sort(i.begin(), i.end());
        }
        vector<int> ans;
        for (auto &i: queries) {
            ans.push_back(f[i[1] - 1][i[0] - 1].second);
        }
        return ans;
    }
};

int main() {
    Solution s;
    vector<int> v = {1};
    vector<vector<int> > c = {{1}};
    return 0;
}

Minimum Deletions to Make Array Divisible6

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If this is not possible, return -1.

Note that an integer x divides y if y % x == 0.

Example 1:

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: 
The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of numsDivide.
We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums = [3,4,3].
The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide.
It can be shown that 2 is the minimum number of deletions needed.

让nums最小的数能被第二个数组整除,好经典!!!!!

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

class Solution {
public:
    int minOperations(vector<int> &nums, vector<int> &numsDivide) {
        sort(nums.begin(), nums.end());
        int g = numsDivide[0];
        for (auto &i: numsDivide) g = __gcd(g, i);
        int ans = 0;
        for (auto &i: nums) {
            if (g % i == 0) {
                return ans;
            }
            ans++;
        }
        return -1;
    }
};

int main() {
    Solution s;
    vector<int> v = {1};
    vector<vector<int> > c = {{1}};
    return 0;
}

绝对不是恋爱脑!