跳转至

weekly-contest-315

A

Statement

Metadata

给你一个 不包含 任何零的整数数组 nums ,找出自身与对应的负数都在数组中存在的最大正整数 k

返回正整数 k ,如果不存在这样的整数,返回 -1

 

示例 1:

输入:nums = [-1,2,-3,3]
输出:3
解释:3 是数组中唯一一个满足题目要求的 k 。

示例 2:

输入:nums = [-1,10,6,7,-7,1]
输出:7
解释:数组中存在 1 和 7 对应的负数,7 的值更大。

示例 3:

输入:nums = [-10,8,6,7,-2,-3]
输出:-1
解释:不存在满足题目要求的 k ,返回 -1 。

 

提示:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

Metadata

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

 

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

 

Constraints:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int findMaxK(vector<int> &nums) {
        auto mp = map<int, bool>();
        for (const auto &a : nums) {
            mp[a] = true;
        }

        int res = -1;
        for (const auto &a : nums) {
            if (a > 0 && mp.count(-a)) {
                res = max(res, a);
            }
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

B

Statement

Metadata

给你一个由 整数组成的数组 nums

你必须取出数组中的每个整数,反转其中每个数位,并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。

返回结果数组中 不同 整数的数目。

 

示例 1:

输入:nums = [1,13,10,12,31]
输出:6
解释:反转每个数字后,结果数组是 [1,13,10,12,31,1,31,1,21,13] 。
反转后得到的数字添加到数组的末尾并按斜体加粗表示。注意对于整数 10 ,反转之后会变成 01 ,即 1 。
数组中不同整数的数目为 6(数字 1、10、12、13、21 和 31)。

示例 2:

输入:nums = [2,2,2]
输出:1
解释:反转每个数字后,结果数组是 [2,2,2,2,2,2] 。
数组中不同整数的数目为 1(数字 2)。

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Metadata

You are given an array nums consisting of positive integers.

You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.

Return the number of distinct integers in the final array.

 

Example 1:

Input: nums = [1,13,10,12,31]
Output: 6
Explanation: After including the reverse of each number, the resulting array is [1,13,10,12,31,1,31,1,21,13].
The reversed integers that were added to the end of the array are underlined. Note that for the integer 10, after reversing it, it becomes 01 which is just 1.
The number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).

Example 2:

Input: nums = [2,2,2]
Output: 1
Explanation: After including the reverse of each number, the resulting array is [2,2,2,2,2,2].
The number of distinct integers in this array is 1 (The number 2).

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int f(int x) {
        int res = 0;
        while (x) {
            res = res * 10 + (x % 10);
            x /= 10;
        }

        return res;
    }

    int countDistinctIntegers(vector<int> &nums) {
        auto se = set<int>();
        for (const auto &a : nums) {
            se.insert(a);
            se.insert(f(a));
        }

        return int(se.size());
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

C

Statement

Metadata

给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num  ,则返回 true ;否则,返回 false

reverse(k) 表示 k 反转每个数位后得到的数字。

 

示例 1:

输入:num = 443
输出:true
解释:172 + 271 = 443 ,所以返回 true 。

示例 2:

输入:num = 63
输出:false
解释:63 不能表示为非负整数及其反转后数字之和,返回 false 。

示例 3:

输入:num = 181
输出:true
解释:140 + 041 = 181 ,所以返回 true 。注意,反转后的数字可能包含前导零。

 

提示:

  • 0 <= num <= 105

Metadata

Given a non-negative integer num, return true if num can be expressed as the sum of any non-negative integer and its reverse, or false otherwise.

 

Example 1:

Input: num = 443
Output: true
Explanation: 172 + 271 = 443 so we return true.

Example 2:

Input: num = 63
Output: false
Explanation: 63 cannot be expressed as the sum of a non-negative integer and its reverse so we return false.

Example 3:

Input: num = 181
Output: true
Explanation: 140 + 041 = 181 so we return true. Note that when a number is reversed, there may be leading zeros.

 

Constraints:

  • 0 <= num <= 105

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

constexpr int N = 1e5 + 10;

class Solution {
public:
    vector<bool> vis{};

    int f(int x) {
        int res = 0;
        while (x) {
            res = res * 10 + (x % 10);
            x /= 10;
        }

        return res;
    }

    void init() {
        vis = vector<bool>(N, false);
        for (int i = 0; i < N; i++) {
            int x = i + f(i);
            if (x < N) {
                vis[x] = true;
            }
        }
    }

    bool sumOfNumberAndReverse(int num) {
        if (vis.empty()) {
            init();
        }

        return vis[num];
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

D

Statement

Metadata

给你一个整数数组 nums 和两个整数 minK 以及 maxK

nums 的定界子数组是满足下述条件的一个子数组:

  • 子数组中的 最小值 等于 minK
  • 子数组中的 最大值 等于 maxK

返回定界子数组的数目。

子数组是数组中的一个连续部分。

 

示例 1:

输入:nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出:2
解释:定界子数组是 [1,3,5] 和 [1,3,5,2] 。

示例 2:

输入:nums = [1,1,1,1], minK = 1, maxK = 1
输出:10
解释:nums 的每个子数组都是一个定界子数组。共有 10 个子数组。

 

提示:

  • 2 <= nums.length <= 105
  • 1 <= nums[i], minK, maxK <= 106

Metadata

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

  • The minimum value in the subarray is equal to minK.
  • The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i], minK, maxK <= 106

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    long long countSubarrays(vector<int> &nums, int minK, int maxK) {
        ll res = 0;

        int n = int(nums.size());

        int l1 = 0;
        int l2 = 0;
        auto se = multiset<int>();
        auto se2 = multiset<int>();

        for (int i = 0; i < n; i++) {
            int a = nums[i];
            se.insert(a);
            se2.insert(a);

            while (l1 <= i) {
                int mi = *se.begin();
                int mx = *(--(se.end()));

                if (mi < minK || mx > maxK) {
                    se.erase(se.lower_bound(nums[l1]));
                    ++l1;
                } else {
                    break;
                }
            }

            while (l2 < l1) {
                se2.erase(se2.lower_bound(nums[l2]));
                ++l2;
            }

            while (l2 <= i) {
                int mi = *se2.begin();
                int mx = *(--(se2.end()));

                if (mi == minK && mx == maxK) {
                    se2.erase(se2.lower_bound(nums[l2]));
                    ++l2;
                } else {
                    break;
                }
            }

            if (l1 <= i) {
                int mi = *se.begin();
                int mx = *(--(se.end()));

                if (mi == minK && mx == maxK) {
                    // cout << i << " " << l << " " << mi << " " << mx << endl;

                    res += l2 - l1;
                }
            }
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

最后更新: October 11, 2023
回到页面顶部