【刷题(17)】技巧

一 技巧基础

二 136. 只出现一次的数字

1 题目

在这里插入图片描述

2 解题思路

哈希表map

其实看到题目数组中某个元素出现的次数也可以直接用unordered_map容器统计每一个元素出现的次数,然后在遍历整个map容器查看是否有元素出现的次数等于1

3 code

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        //第一次遍历,使用哈希来统计数组中元素出现次数
        unordered_map<int,int> map;
        for(int num:nums)
        {
            map[num]++;
        }
        
        //第二次遍历,查看是否有元素出现的次数等于1
        for(int num:nums)
        {
            if(map[num]==1) return num;
        }

        return 0;

    }
};

三 169. 多数元素

1 题目

在这里插入图片描述

2 解题思路

本题常见的三种解法:

  • 哈希表统计法: 遍历数组 nums ,用 HashMap 统计各数字的数量,即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N)O(N) 。
  • 数组排序法: 将数组 nums 排序,数组中点的元素 一定为众数。
  • 摩尔投票法: 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N)O(N) 和 O(1)O(1)O(1) ,为本题的最佳解法。

哈希表+打擂台(边哈希,边打擂台,省去二次遍历哈希表在麻烦)

我们使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后,我们遍历哈希映射中的所有键值对,返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法,维护最大的值,这样省去了最后对哈希映射的遍历。

3 code

class Solution {
public:
    int majorityElement(vector<int>& nums) {

        unordered_map<int,int>map;//哈希
        int majority=0,cnt=0;//打擂台

        //哈希
        for(int num:nums)
        {
            map[num]++;

            //打擂台
            if(map[num]>cnt)
            {
                majority=num;
                cnt=map[num];
            }
        }
        return majority;

    }
};

四 75. 颜色分类

1 题目

在这里插入图片描述

2 解题思路

首先,所有数都≤2,那么索性把所有数组置为2,然后遇到所有≤1的,就再全部置为1,,覆盖了错误的2,这时候所有2的位置已经正确,最后所有≤0的全部置为0,也就覆盖了一些错误的1,这时候,0和1的位置都正确。最重要的就是需要两个指针指向下一个1或0的位置

3 code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n0=0,n1=0;
        for(int i=0;i<nums.size();i++)
        {
            int num=nums[i];

            //先将所有在数置为2
            nums[i]=2;
            //如果数值小于等于1,将数置为1
            //(为0的时候,会将1的计数位前推一位)
            if(num<=1)
            {
            nums[n1]=1;
            n1++;
            }
            //如果数值小于等于0,将数置为0
            if(num<=0)
            {
                nums[n0]=0;
                n0++;
            }
        }
    }
};

五 31. 下一个排列

1 题目

在这里插入图片描述

2 解题思路

这道题是根据 维基百科 ,下图所示:
在这里插入图片描述
翻译过来:

先找出最大的索引 k 满足 nums[k] < nums[k+1],如果不存在,就翻转整个数组;
再找出另一个最大索引 l 满足 nums[l] > nums[k];
交换 nums[l] 和 nums[k];
最后翻转 nums[k+1:]。
举个例子:

比如 nums = [1,2,7,4,3,1],下一个排列是什么?

我们找到第一个最大索引是 nums[1] = 2

再找到第二个最大索引是 nums[4] = 3

交换,nums = [1,3,7,4,2,1];

翻转,nums = [1,3,1,2,4,7]

完毕!

所以,

时间复杂度:O(n)O(n)O(n)

空间复杂度:O(1)O(1)O(1)

在这里插入图片描述

3 code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int cur=nums.size()-2;
        
        //前面大于后面在
        while(cur>=0&&nums[cur]>=nums[cur+1])
        {
            cur--;
        }

        //已经是最大数组了
        if(cur<0)
        {
            sort(nums.begin(),nums.end());
        }
        else
        {//表示找到国降序在一个位置
        int pos=nums.size()-1;
        while(nums[pos]<=nums[cur])
        {
            pos--;
        }

        swap(nums[cur],nums[pos]);
        reverse(nums.begin()+cur+1,nums.end());
        }

    }
};

六 31. 下一个排列

1 题目、

在这里插入图片描述

2 解题思路

题目要求查找重复的整数,很容易想到使用「哈希表」,但是题目中要求「只用常量级 O(1 的额外空间」,该方法不符合题意
还可以考虑使用「力扣」第 41 题:缺失的第一个正数 的技巧,使用「原地哈希」,但是题目要求「你设计的解决方案必须不修改数组 nums」,该方法不符合题意
但是题目中还说:「数字都在 1 到 n 之间(包括 1 和 n)」,查找一个有范围的整数,可以使用「二分查找」(这一点很重要,很多「二分查找」的问题就是要我们找一个整数);
「快慢指针」的做法很有技巧,具体做法请见其它题解。

可以使用「二分查找」的原因

因为题目要找的是一个 整数,并且这个整数有明确的范围,所以可以使用「二分查找」。

重点理解:

这个问题使用「二分查找」是在数组 [1, 2,…, n] 中查找一个整数,而 并非在输入数组数组中查找一个整数。

使用「二分查找」查找一个整数,这是「二分查找」的典型应用,经常被称为「二分答案」。在 题解 中,「题型二」与「题型三」都是这样的问题。

央视《幸运 52》节目的「猜价格游戏」,就是「二分答案」。玩家猜一个数字,如果猜中,游戏结束,如果主持人说「猜高了」,应该猜一个更低的价格,如果主持人说「猜低了」,应该猜一个更高的价格。

继续 解题思路:每一次猜一个数,然后 遍历整个输入数组,进而缩小搜索区间,最后确定重复的是哪个数。

理解题意:

n + 1 个整数,放在长度为 n 的数组里,根据「抽屉原理」,至少会有 1 个整数是重复的;
抽屉原理:把 10 个苹果放进 9 个抽屉,至少有一个抽屉里至少放 2 个苹果。

方法:二分查找

「二分查找」的思路是先猜一个数(搜索范围 [left…right] 里位于中间的数 mid),然后统计原始数组中 小于等于 mid 的元素的个数 count:

如果 count 严格大于 mid。根据 抽屉原理,重复元素就在区间 [left…mid] 里;
否则,重复元素可以在区间 [mid + 1…right] 里找到,其实只要第 1 点是对的,这里肯定是对的,但要说明这一点,需要一些推导,我们放在最后说。

方法:快慢指针

数组形式的链表

题目设定的问题是 N+1 个元素都在 [1,n] 这个范围内。这样我们可以用那个类似于 ‘缺失的第一个正数’ 这种解法来做,但是题意限制了我们不能修改原数组,我们只能另寻他法。也就是本编题解讲的方法,将这个题目给的特殊的数组当作一个链表来看,数组的下标就是指向元素的指针,把数组的元素也看作指针。如 0 是指针,指向 nums[0],而 nums[0] 也是指针,指向 nums[nums[0]].
这样我们就可以有这样的操作

C++
int point = 0;
while(true){
    point = nums[point]; // 等同于 next = next->next; 
}

链表中的环

假设有这样一个样例:[1,2,3,4,5,6,7,8,9,5]。如果我们按照上面的循环下去就会得到这样一个路径:1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9] . . .这样就有了一个环,也就是 6 7 8 9。point 会一直在环中循环的前进。
这时我们设置两个一快(fast)一慢(slow)两个指针,一个每次走两步,一个每次走一步,这样让他们一直走下去,直到他们在重复的序列中相遇,
在这里插入图片描述

3 code

二分查找

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len=nums.size();

        int left=1;
        int right=len-1;

        while(left<right)
        {
            int mid=(left+right)/2;

            //nums中小于等于mid的元素的个数
            int count=0;
            for(int num:nums)
            {
                if(num<=mid)
                {
                    count++;
                }
            }


            if(count>mid)
            {
                //下一轮搜索的区间[left..mid]
                right=mid;
            }
            else
            {
                //下一轮搜索的区间[mid+1..right]
                left=mid+1;
            }
        }
        //退出循环以后 left 与 right 重合,left (或者 right)就是我们要找的重复的整数;
        return left;

    }
};

快慢指针

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int slow = 0;
        int fast = 0;
        //快慢指针相遇
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        //快指针返回终点,继续出发
        fast = 0;
        while (nums[slow] != nums[fast]) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return nums[slow];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/677133.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python开发运维:VSCode与Pycharm 部署 Anaconda虚拟环境

目录 一、实验 1.环境 2.Windows 部署 Anaconda 3.Anaconda 使用 4.VSCode 部署 Anaconda虚拟环境 5.Pycharm 部署 Anaconda虚拟环境 6.Windows使用命令窗口版 Jupyter Notebook 7.Anaconda 图形化界面 二、问题 1.VSCode 运行.ipynb代码时报错 2.pip 如何使用国内…

分布式ID生成方式

1.UUID uuid方式存在问题&#xff1a;占用字节数比较大&#xff1b;ID比较随机&#xff0c;作为MySQL主键写入库时&#xff0c;为了保证顺序性将导致BTree节点分裂比较频繁&#xff0c;影响IO性能。 2.数据库方式 步长step 3&#xff0c;即为机器的数量。 第一台机器&#x…

音视频开发17 FFmpeg 音频解码- 将 aac 解码成 pcm

这一节&#xff0c;接 音视频开发12 FFmpeg 解复用详情分析&#xff0c;前面我们已经对一个 MP4文件&#xff0c;或者 FLV文件&#xff0c;或者TS文件进行了 解复用&#xff0c;解出来的 视频是H264,音频是AAC&#xff0c;那么接下来就要对H264和AAC进行处理&#xff0c;这一节…

C语言 恼人的结合性和优先级和副作用

结合性和优先级和副作用 1.优先级2.结合性3.副作用4.简单区分i&#xff0c;i&#xff0c;i1&#xff1b;ii1&#xff1b;ii 1.优先级 优先级指的是&#xff0c;如果⼀个表达式包含多个运算符&#xff0c;哪个运算符应该优先执⾏。各种运算符的优先级是 不⼀样的。 在C语言中&a…

Docker的部署与基本使用

Docker的部署和基本使用 Docker是一个开源的容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包成独立的、可移植的容器&#xff0c;从而简化了应用程序的部署、管理和扩展过程。这些容器可以在任何支持Docker的平台上运行&#xff0c;确保了应用的一致性和可移植性…

Renesas MCU之使用Keil搭建开发环境

目录 概述 1 软件安装 1.1 软件版本信息 1.2 安装FSP 1.3 安装和配置Keil 2 使用FSP创建工程 2.1 FSP中配置参数 2.2 配置板卡硬件资源 3 Keil中配置项目 3.1 在Keil配置FSP 3.2 添加user src目录 3.3 配置下载项 3.4 测试下载功能 4 使用stm32 NUCLEO板卡的ST-L…

李廉洋:6.3黄金原油美盘尾盘分析及最新动向分析;

黄金消息面分析&#xff1a;上周黄金市场的走势受到了PCE通胀数据和美联储政策预期的显着影响。尽管市场对黄金的长期看涨情绪依然存在&#xff0c;但短期内金价的波动性预计将持续。4月份的PCE通胀数据显示价格压力有所降温&#xff0c;这一结果与分析师预期一致&#xff0c;但…

Java集合思维导图

详细内容请看链接内容 Java集合面试题集——2024最新大厂面试

数字化时代还需要传统智慧图书馆吗

尽管以电子阅览室代表的数字化时代带来了许多便利和创新&#xff0c;但传统智慧图书馆依然具有重要的价值和意义。以下是一些原因&#xff1a; 1. 保存历史文化&#xff1a;传统智慧图书馆是保存历史文化遗产的重要载体&#xff0c;收藏了许多珍贵的古籍、手稿和纸质图书&#…

【AR开发-开源框架】使用Sceneform-EQR快速开发AR应用,当前接入了AREngine、ORB-SLAM,可快速地适配不同的安卓设备

Sceneform-EQR Sceneform 概览 Sceneform是一个3D框架&#xff0c;具有基于物理的渲染器&#xff0c;针对移动设备进行了优化&#xff0c;使您可以轻松构建增强现实应用程序&#xff0c;而无需OpenGL。 借助 Sceneform&#xff0c;您可以轻松地在 AR 应用和非 AR 应用中渲染…

【C++ 初阶】引用 () 实际的一些用法、常引用问题 详解!

文章目录 1. 常引用的背景2. 字符 a 与 整形 97 是相同的&#xff0c;但是具体是怎么比较的呢 &#xff1f; 1. 常引用的背景 注意&#xff1a; &#x1f427;① 权限可以平移、可以缩小&#xff0c;但是权限 不可以放大。 &#x1f427; 类型转换中间会产生临时变量 2. 字…

LeetCode 算法:滑动窗口最大值c++

原题链接&#x1f517;&#xff1a;滑动窗口最大值 难度&#xff1a;困难⭐️⭐️⭐️ 题目 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动…

读AI未来进行式笔记02深度伪造

1. 计算机视觉 1.1. 在人的六感之中&#xff0c;视觉是最重要的 1.1.1. 人类只要看上一眼视频&#xff0c;就能瞬间在脑海中抓取并消化内容和信息 1.1.2. 人类能够对事物进行广义的理解和抽象的认知&#xff0c;即使同一物体在不同的角度…

2. redis配置文件解析

redis配置文件解析 一、redis配置文件1、监听地址2、监听端口3、redis接收请求的队列长度3.1 修改系统参数/内核参数 4、客户端空闲的超时时间5、指定redis的pid文件6、定义错误日志7、定义数据库的数量8、定义持久化存储9、设置redis密码10、redis并发连接11、最大内存策略 二…

SpringBoot接口防抖(防重复提交)

TOC 啥是防抖 所谓防抖&#xff0c;一是防用户手抖&#xff0c;二是防网络抖动。在Web系统中&#xff0c;表单提交是一个非常常见的功能&#xff0c;如果不加控制&#xff0c;容易因为用户的误操作或网络延迟导致同一请求被发送多次&#xff0c;进而生成重复的数据记录。要针对…

元宇宙游戏开启全新虚拟世界大门

近年&#xff0c;元宇宙游戏在游戏领域掀起了一股热潮。 元宇宙游戏作为一种创新的游戏形式&#xff0c;正吸引着众多玩家的目光。这些游戏构建了一个高度沉浸式的虚拟世界&#xff0c;玩家可以在其中体验到前所未有的自由和可能性。 在元宇宙游戏中&#xff0c;玩家们能够通…

计算机毕业设计hadoop+spark+hive物流快递大数据分析平台 物流预测系统 物流信息爬虫 物流大数据 机器学习 深度学习 知识图谱 大数据

1.Python爬虫采集物流数据等存入mysql和.csv文件&#xff1b; 2.使用pandasnumpy或者MapReduce对上面的数据集进行数据清洗生成最终上传到hdfs&#xff1b; 3.使用hive数据仓库完成建库建表导入.csv数据集&#xff1b; 4.使用hive之hive_sql进行离线计算&#xff0c;使用spark之…

IO流(3)

打印流 字节打印流 特有方法实现&#xff1a;数据原样写出。 public class test {public static void main(String [] args) throws IOException, ClassNotFoundException {//打印流//创建字节打印流对象PrintStream psnew PrintStream(new FileOutputStream("c.txt&quo…

macOS的word没有zotero怎么办

打开zotero,首选项,引用,重新安装加载项 然后到word里 点模板和加载项 把zotero勾上,OK了

MyBatis3.4全集笔记

MyBatis 1. MyBatis 简介 MyBatis 本是apache的一个开源项目iBatis, 2010年这个项目由apache software foundation 迁移到了google code&#xff0c;并且改名为MyBatis 。2013年11月迁移到Github。 iBATIS一词来源于“internet”和“abatis”的组合&#xff0c;是一个基于Ja…