当前位置: 首页 > news >正文

LeetCode315 周赛

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

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

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

提示:

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

示例

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

思路

简单题,类似两数之和。用一个哈希表记录下出现过的数即可。

// C++
class Solution {
public:
    int findMaxK(vector<int>& nums) {
        unordered_set<int> s;
        int ans = -1;
        for (auto &v : nums) {
            if (s.count(-v)) ans = max(ans, abs(v));
            s.insert(v);
        }
        return ans;
    }
};

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

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

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

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

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

示例

输入: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)。

思路

直接对每个数进行反转,并全部放到一个set中做去重。

// C++
class Solution {
public:

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

    int countDistinctIntegers(vector<int>& nums) {
        unordered_set<int> s;
        for (auto& v : nums) {
            s.insert(v);
            s.insert(reverse(v));
        }
        return s.size();
    }
};

2443. 反转之后的数字和

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

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

提示

  • 0 <= num <= 10^5

示例

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

思路

周赛当晚想了很久,观察并找规律。最后还是没有通过。今天重做,根据数据范围10^5,发现直接简单的暴力就能过。

// C++
class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
    bool sumOfNumberAndReverse(int num) {
        for (int i = 0; i <= num; i++) {
            if (i + reverse(i) == num) return true;
        }
        return false;
    }
};

这道题如果将数据范围提高到 10^9,则用暴力会超时。可以折半枚举,只枚举一半的数位,则另一半的数为也一并会确定下来了(因为将数字进行reverse后相加,随着前一半数位的确定,后一半的数位也会随之确定)。

还有一种递归的解法,有点动态规划的思路在里面,反复看了几次看不太懂,便作罢。这里贴个链接,方便日后再来回看。

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

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

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

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

返回定界子数组的数目。

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

提示:

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i], minK, maxK <= 10^6

示例

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

思路

一个连续的子数组内,所有数都必须在区间[minK, maxK]以内。那么只要某个数x不在上述区间内,则满足条件的子数组不可能跨越x这个位置。则我们可以先找出不在区间[minK, maxK]内的那些数字,然后根据这些数字将整个数组划分成若干个子区间,再对每个子区间单独求解即可。

对某个子区间,区间内所有数都在[minK, maxK]范围内。对于某个位置i,我们往左找到最近的j,满足[j, i]内存在minKmaxK,这意味着,若j再往右走一步,则唯一的一个minKmaxK会被移出区间,即[j + 1, i]不满足条件。那么对于以i作为右端点的子区间,其左端点都一定要<= j,才能满足条件,所以以i为右端点的区间,共有j + 1个。并且对于所有> i的右端点,距离其最近的左端点一定是>= j的,这样随着i往右移动,j也只能往右移动,而不会走回头路。所以可以用双指针算法。

// C++
typedef long long LL;
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int n = nums.size();
        // 定义一个函数
        auto f = [&](int l, int r) -> LL {
            if (l > r) return 0;
            LL res = 0;
            int smin = 0, smax = 0; // minK和maxK出现的次数
            for (int i = l, j = l; i <= r; i++) {
                if (nums[i] == minK) smin++;
                if (nums[i] == maxK) smax++;
                if (smin && smax) {
                    // 当minK和maxK都出现后, 尝试右移j
                    while (smin && smax) {
                        if (nums[j] == minK) smin--;
                        if (nums[j] == maxK) smax--;
                        j++;
                    }
                    j--; // 恢复j
                    if (nums[j] == minK) smin++;
                    if (nums[j] == maxK) smax++;
                    // 对于此i, 找到了其左侧最近的j
                    res += j - l + 1;
                }
            }
            return res;
        };
        // 遍历并进行拆分
        LL ans = 0;
        for (int i = 0, last = 0; i < n; i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                // cut off
                ans += f(last, i - 1);
                last = i + 1;
            } else if (i == n - 1) {
                // 最后一个位置
                ans += f(last, i);
            }
        }
        return ans;
    }
};

总结

这场周赛,只做出2题,WHAT A SHAME!掉大分!

T3一直在观察找规律,坐牢直到比赛结束。没有注意到数据范围其实比较小,可以直接用暴力来做。可惜了。

另外T3在数据范围比较大的时候,注意需要用另一种方法来做(双指针+动态规划+DFS),题解看的我脑壳疼,之后再慢慢啃了。

T3这一类可以都归结到数位统计这一大类问题中,事后可以多刷刷相关题目。另外一道类似的题目(升级版)-> 镜像拆分

另外,T4难度没有特别大,听了y总讲解后一下就理解了。有点类似之前做过的某道题,可以根据一些点将大区间拆分成多个小区间,再单独对每个小区间进行求解。

相关文章:

  • MySQL的DML语句
  • 现代数字信号处理及其应用-常见结论
  • 深度学习前10节
  • 初识 GPT-4 和 ChatGPT
  • FFmpeg源码:AV_RB32宏定义分析
  • AWS无服务器 应用程序开发—第十五章 CI/CD
  • 数据库之ACID
  • CSS转换(2D)transform属性及animation动画
  • SD-WAN技术:优化国内外服务器访问的关键
  • [Mac软件]Adobe Substance 3D Stager 2.1.4 3D场景搭建工具
  • uniapp的动态表单实现
  • 关于使用Mxnet GPU版本运行DeepAR报错解决方案
  • MySQL常用函数大全(实例演示)
  • Linux学习笔记(更新中)
  • 论文理解【Offline RL】—— A dataset perspective on offline reinforcement learning
  • 三分钟了解MySQL慢查询
  • cesium拾取pick系列(拾取坐标和对象)
  • 音视频开发入门小知识
  • 数据挖掘-理解业务和数据(二)
  • 温振变送器为何被称为监测工频类设备故障的“利器”?
  • 【面试题】数组去重的五种方法(必会)
  • MySQL索引
  • JavaScript基础总结---重点
  • UnRaid设备共用其他UnRaid主UPS的详细设置方法
  • ESP32的MQTT AT固件烧录+STM32以ESP32的MQTT AT固件的AT指令连接EMQX下mqtt服务器实现消息订阅和发布
  • Python 多进程编程(一)Pool Manager in multiprocessing
  • 灰度变换 - 灰度切割(灰度级分层)+threshold函数
  • MyBatis 框架的思想及其第一次使用
  • 【Unity Shader】Unity中如何创建Cubemap?
  • 面试百问:项目上线后才发现bug怎么办?
  • C语言《文件版本通讯录》
  • 【无人机】基于EKF、UKF、PF、改进PF滤波算法的无人机航迹预测(Matlab代码实现)