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

力扣hot100——技巧

 136. 只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto x: nums) ans ^= x;
        return ans;
    }
};

位运算,异或消去重复的元素

169. 多数元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        map<int, int> mp;
        for (int i = 0; i < n; i++) {
            mp[nums[i]]++;
            if (mp[nums[i]] > n / 2) return nums[i];
        }
        return 0;
    }
};

桶计数

 75. 颜色分类

class Solution {
public:
    void sortColors(vector<int>& a) {
        int k = 0;
        for (int i = 0; i < a.size(); i++) {
            if (!a[i]) {
                swap(a[i], a[k++]);
            }
        }

        for (int i = k; i < a.size(); i++) {
            if (a[i] == 1) {
                swap(a[i], a[k++]);
            }
        }
    }
};

我们可以考虑对数组进行两次遍历。在第一次遍历中,我们将数组中所有的 0 交换到数组的头部。在第二次遍历中,我们将数组中所有的 1 交换到头部的 0 之后。此时,所有的 2 都出现在数组的尾部,这样我们就完成了排序。

31. 下一个排列 

class Solution {
public:
    void nextPermutation(vector<int>& a) {
        for (int i = a.size() - 1; i >= 1; i--) {
            if (a[i] > a[i - 1]) {
                for (int j = a.size() - 1; j >= i; j--) {
                    if (a[j] > a[i - 1]) {
                        swap(a[i - 1], a[j]);
                        break;
                    }
                }
                reverse(a.begin() + i, a.end());
                return ;
            }
        }

        reverse(a.begin(), a.end());
    }
};

思维题:
序列后缀是单调不增的,因此从后往前找到第一个拐点(i - 1),然后将这个元素与后缀中从后往前大于它的第一个元素交互,之后后缀再从小到大排序(翻转)即可

287. 寻找重复数 

class Solution {
public:
    int findDuplicate(vector<int>& a) {
        int n = a.size();
        int l = 0, r = n;
        auto check = [&](int x) -> bool {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] <= x) cnt++;
            }
            return cnt <= x;
        };
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l + 1;
    }
};

我的推理:

假设答案是ans,小于ans的数最多有ans - 1个,大于ans的数最多有n - ans个,设ans的个数有x个

因此总个数 n + 1  <= ans - 1 + n - ans + x 
得 x >= 2

官方题解:

考虑 nums 数组一共有 n+1 个位置,我们填入的数字都在 [1,n] 间,有且只有一个数重复放了两次以上。对于所有测试用例,考虑以下两种情况:

  • 如果测试用例的数组中 target 出现了两次,其余的数各出现了一次,这个时候肯定满足上文提及的性质,因为小于 target 的数 i 满足 cnt[i]=i,大于等于 target 的数 j 满足 cnt[j]=j+1。
  • 如果测试用例的数组中 target 出现了三次及以上,那么必然有一些数不在 nums 数组中了,这个时候相当于我们用 target 去替换了这些数,我们考虑替换的时候对 cnt[] 数组的影响。如果替换的数 i 小于 target ,那么 [i,target−1] 的 cnt 值均减一,其他不变,满足条件。如果替换的数 j 大于等于 target,那么 [target,j−1] 的 cnt 值均加一,其他不变,亦满足条件。

http://www.kler.cn/a/460773.html

相关文章:

  • C++ hashtable
  • Docker安装(Docker Engine安装)
  • C++11右值与列表初始化
  • “大数据+职业本科”:VR虚拟仿真实训室的发展前景
  • [Qt] 常用控件 | QWidget | “表白程序2.0”
  • Angular Firebase CRUD 项目推荐
  • 小程序信息收集(小迪网络安全笔记~
  • FreeRTOS: ISR(中断服务例程)和 TCB(任务控制块)
  • Python面向对象编程全面解析
  • 大模型算法题(2)
  • wps透视数据表
  • 微信公众号 发布 接口405报错
  • 机器学习中的欠拟合
  • echarts 柱形图重叠柱形图legend,双y轴
  • Spring Boot教程之四十一:在 Spring Boot 中调用或使用外部 API
  • Kafka中的Topic和Partition有什么关系?
  • 掌握大数据处理利器:Flink 知识点全面总结【上】
  • ESLint+Prettier的配置
  • 【Cesium】三、实现开场动画效果
  • Rust入门学习笔记
  • Lecture 20
  • Django 中数据库迁移命令
  • 基于SpringBoot的宠物寄养系统的设计与实现(源码+SQL+LW+部署讲解)
  • 一起学Git【第七节:查看文件以及文件的删除】
  • 文献阅读分享:强化学习与大语言模型结合的推荐系统LEA
  • 封装echarts成vue component