且听疯吟

leetcode contest 315

2022-11-02

leetcode contest 315

前三题确实太水的题目，都是暴力。

6204. 与对应负数同时存在的最大正整数

题目

给你一个 不包含 任何零的整数数组 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

地址

https://leetcode.cn/problems/largest-positive-integer-that-exists-with-its-negative/

题意

哈希

思路

  1. 排序后直接统计即可，即统计 $x$ 与 $-x$ 是否同时出现。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int findMaxK(vector<int>& nums) {
        unordered_set<int> cnt;
        int ans = -1;
        for (auto v : nums) {
            cnt.emplace(v);
        }
        for (auto v : nums) {
            if (v > 0 && cnt.count(-v)) {
                ans = max(ans, v);
            }
        }
        return ans;
    }
};

6205. 反转之后不同整数的数目

题目

给你一个由 正 整数组成的数组 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

地址

https://leetcode.cn/problems/count-number-of-distinct-integers-after-reverse-operations/description/

题意

遍历即可

思路

  1. 我们将其中的每个数 $x$ 按照数位进行反转并得到 $r(x)$，最终用哈希表存储 $x,r(x)$，最终记录哈希表的大小即可。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：空间复杂度为 $O(n)$。

代码

class Solution {
public:
    int countDistinctIntegers(vector<int>& nums) {
        unordered_set<int> cnt;
        for (auto v : nums) {
            cnt.emplace(v);
            string s = to_string(v);
            reverse(s.begin(), s.end());
            int x = stoi(s);
            cnt.emplace(x);
        }
        return cnt.size();
    }
};

6219. 反转之后的数字和

题目

给你一个 非负 整数 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

地址

https://leetcode.cn/problems/sum-of-number-and-its-reverse/

题意

遍历

思路

  1. 由于 $num$ 的范围大小可知，我们直接遍历 $x \in [0,num]$ 即可，检测 $x + r(x) = num$ 是否成立即可。
  2. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 为字符串的长度。
  • 空间复杂度：时间复杂度为 $O(\log n)$。

代码

class Solution {
public:
    bool sumOfNumberAndReverse(int num) {
        for (int i = 0; i <= num; i++) {
            string s = to_string(i);
            reverse(s.begin(), s.end());
            int x = stoi(s);
            if (i + x == num) {
                return true;
            }
        }
        return false;
    }
};

6207. 统计定界子数组的数目

题目

给你一个整数数组 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

地址

https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/

题意

动态规划

思路

  1. 当然如果满足 $minK = maxK$ 则这个题目就非常简单了，我们直接统计 $maxK$ 的连续数字即可。如果 $minK = maxK$ 时间，我们设 $dp[i][0]$ 表示以 $i$ 为结尾且连续子数组种所有的元素范围均在 $(minK, maxK)$ 之间的数目，$dp[i][1]$ 表示以 $i$ 为结尾且连续子数组且包含 $minK$ 且不包含 $maxK$ 的数目，$dp[i][2]$ 表示以 $i$ 为结尾且连续子数组且包含 $maxK$ 且不包含 $minK$ 的数目，$dp[i][3]$ 表示以 $i$ 为结尾且连续子数组且包含 $mink, maxK$ 的数目, 则可以有如下三种判断:

  • 当 $ minK \le num[i] \le maxK$ 时，则此时可以知道
    $$
    dp[i][0] = dp[i-1][0] + 1\
    dp[i][1] = dp[i-1][1] \
    dp[i][2] = dp[i-1][2] \
    dp[i][3] = dp[i-1][3]
    $$

  • 当 $ minK = num[i]$ 时，则此时可以知道:
    $$
    dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + 1 \
    dp[i][3] = dp[i - 1][3] + dp[i - 1][2]
    $$

  • 当 $ maxK = num[i]$ 时，则此时可以知道:
    $$
    dp[i][2] = dp[i - 1][0] + dp[i - 1][2] + 1 \
    dp[i][3] = dp[i - 1][3] + dp[i - 1][1]
    $$

  1. 非常好容易理解的解法如下，设以 $i$ 为右端点的连续子树的数目为 $cnt[i]$，则此时可以知道在合法的连续子数组中一定含有 $maxK, mink$ 且其中所有的元素均满足大于等于 $minK$，且小于等于 $maxK$。则此时我们应当取 $j = \min(minIdx, maxId)$，即距离 $i$ 最近且同时出现 $minK,maxk$ 的索引为 $j$，如果距离 $i$ 最近的非法数字的索引为 $validIdx$：
  • 如果 $validIdx < j$，此时可以构造的合法的连续子数组的数目为 $j - validIdx$；
  • 如果 $validIdx \ge j$，此时可以构造的合法的连续子数组的数目为 $0$；
  1. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int n = nums.size();
        vector<vector<long long>> dp(n + 1, vector<long long>(4));
        if (minK != maxK) {
            for (int i = 1; i <= n; i++) {
                if (nums[i - 1] >= minK && nums[i - 1] <= maxK) {
                    if (nums[i - 1] > minK && nums[i - 1] < maxK) {
                        dp[i][0] = dp[i - 1][0] + 1;
                        dp[i][1] = dp[i - 1][1];
                        dp[i][2] = dp[i - 1][2];
                        dp[i][3] = dp[i - 1][3];
                    } 
                    if (nums[i - 1] == minK) {
                        dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + 1;
                        dp[i][3] = dp[i - 1][3] + dp[i - 1][2]; 
                    }
                    if (nums[i - 1] == maxK) {
                        dp[i][2] = dp[i - 1][0] + dp[i - 1][2] + 1;
                        dp[i][3] = dp[i - 1][3] + dp[i - 1][1];
                    }
                } 
            }
        } else {
            for (int i = 1; i <= n; i++) {
                if (nums[i - 1] == minK) {
                    dp[i][3] = dp[i-1][3] + 1;
                } 
            }
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dp[i][3];
        }
        return ans;
    }
};
  • 直接检测
    class Solution {
    public:
        long long countSubarrays(vector<int>& nums, int minK, int maxK) {
            int n = nums.size();
            int minIdx = -1, maxIdx = -1, validIdx = -1;
            long long ans = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] == minK) minIdx = i;
                if (nums[i] == maxK) maxIdx = i;
                if (nums[i] > maxK || nums[i] < minK) validIdx = i;
                ans += max(0, min(minIdx, maxIdx) - validIdx); 
            }
            return ans;
        }
    };

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛
← leetcode contest 314 leetcode contest 312 →

扫描二维码，分享此文章