【Leetcode】vector刷题

Alt

🔥个人主页Quitecoder

🔥专栏Leetcode刷题

Alt

目录

  • 1.只出现一次的数字
  • 2.杨辉三角
  • 3.删除有序数组中的重复项
  • 4.只出现一次的数字II
  • 5.只出现一次的数字III
  • 6.电话号码的字母组合

1.只出现一次的数字

题目链接:136.只出现一次的数字
题目描述在这里插入图片描述

这道题很简单,我们只需要遍历一遍数组,利用异或操作的性质(一个数与自身异或结果为0,任何数与0异或还是其本身)

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

2.杨辉三角

题目链接:118.杨辉三角
题目描述在这里插入图片描述

这道题我们需要构造二维数组,典型的vector的嵌套使用

在这里插入图片描述
首先,我们先构建二维数组,开辟行数大小:

vector<vector<int>> v(numRows);

接着对每一行进行开辟空间,并将两端初始化为1

for(int i=0;i<numRows;i++)
{v[i].resize(i+1);v[i][0]=1;v[i][i]=1;
}

注意,resize是会进行初始化的,我们没有传值,默认为零

所以我们只需要遍历一遍,遍历到的位置为0,进行相加操作

完整代码如下:

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> v(numRows);for(int i=0;i<numRows;i++){v[i].resize(i+1);v[i][0]=1;v[i][i]=1;}for(int i=0;i<numRows;i++){for(int j=0;j<i;j++){if(v[i][j]==0){v[i][j]=v[i-1][j]+v[i-1][j-1];}}}return v;}
};

3.删除有序数组中的重复项

题目链接:26.删除有序数组中的重复项
题目描述在这里插入图片描述

这题是一道简单的双指针思路的题,由于已经排序好,我们只需要设置两个索引,一个向后遍历,若与前面的索引指向值不相同,则对前面的值进行修改

lass Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() == 0) {return 0;}int slow = 0;for (int fast = 1; fast < nums.size(); fast++) {if (nums[fast] != nums[slow]) {slow++;nums[slow] = nums[fast];}}return slow + 1;}
};

完成了值的覆盖过程

4.只出现一次的数字II

题目链接:137.只出现一次的数字II
题目描述在这里插入图片描述

这个问题的解决方案基于位操作和有限状态自动机的原理。我们要处理的数字是32位整数,因此,我们需要考虑每一位相加后的结果。由于除了一个数字以外,其它数字都出现了三次,我们可以构造一个数字的每一位相加后,模3的结果就是这个只出现一次的数字的相应位

思路如下:

使用两个整数变量onestwosones将会记录每个位只出现一次的情况,而twos将会记录每个位出现两次的情况

对于每个数字num及其每一位,我们更新onestwos

  1. 在第i个位置上,如果ones里的位是1,则表示num要么是第一次遇到i位为1,要么是第四次。如果是第四次,我们已经在twos里记录了两次,所以这次应该把ones里的该位清零,否则保持不变

  2. 同理,如果twos里的位是1,则是第二次遇到i位为1或者是第五次。如果是第五次,我们既要在ones里面加1,同时也要在twos里面清零该位,否则保持不变

  3. 由于我们只需要考虑每个位上1出现的次数,所以任何时候位上的1出现3次,我们都应该清零

最后,ones保留的就是每位上出现一次的结果,而twos将会是0。

class Solution {
public:int singleNumber(vector<int>& nums) {int ones = 0, twos = 0;       for (int num : nums) {ones = (ones ^ num) & ~twos;twos = (twos ^ num) & ~ones;}return ones;}
};

当我们讨论处理出现三次的数字和一个只出现一次的数字时,onestwos 的位操作确实是难以理解的 ,分解这两行代码:

对于每一个新的数字 num,我们用 onestwos 来跟踪彼此独立的状态:

  1. ones = (ones ^ num) & ~twos;

这里,我们正更新 ones 以包含出现一次的位。让我们分解这行代码:

  • ones ^ num:这个按位异或操作背后的思想是:当前的 ones 表示上一步迭代中已经出现一次的位。当我们再次看到这些位时(即 num 中的对应位也是1),我们希望重置 ones 中的那些位(因为出现一次变成了两次)。对于 num 中新出现的1,ones 中还没有记录,这将被加进 ones

  • & ~twos:接下来的按位与操作~twos 结合表示:我们删除 twos 中已经出现两次的位。~twos 是对 twos 取反,意味着取出 twos 中为0的位。只有那些在 twos 中没有记录(即还没达到两次)的1才应该加入 ones。即使刚才 ones ^ num 把某些位变成了1,若那些位在 twos 中已经出现过两次,我们必须确保它们在 ones 中不变成1

结合二者,ones 在每次迭代结束时仅保留那些恰好出现一次的位。如果某位在 ones 中变成了1但已经在 twos 中出现过,我们需要重置 ones 中的那位为0

  1. twos = (twos ^ num) & ~ones;

接着我们更新 twos 来反映那些已经看到两次的位:

  • twos ^ num:与更新 ones 类似,我们对于每个新来的 num,我们都会用按位异或更新 twos。如果在 twos 中的位是1,且对应的 num 中的位也是1,那么它们会重置为0,因为现在这个位出现了第三次,而我们的目标是找到出现了一次和两次的位。如果出现的是一个新的1(即 num 中的1,而 twos 中并没有记录),twos 就会记录它。这会出现加到三的情况,我们随后会处理。

  • & ~ones:这个按位与操作保证如果在 ones 中有1(意味着这个位已经出现了一次),我们不会在 twos 中加入该位。如果某个位同时在 onestwos 中出现,这意味着这个位出现了3次,并且最终会被忽略。

通过 & ~ones,我们确保了一个位仅仅当它在 num 中为1且在 ones 中尚未出现(即 ones 中为0)时,才会被加入 twos

总结来说,这两步操作是相互独立并且排他的:它们保证一个位在 onestwos 中出现,但不会同时出现。我们在整体数组中使用循环来考虑每个数字的影响。最终,由于所有出现三次的数字在这两个变量中都被消去,ones 会留下那个出现一次的唯一位

5.只出现一次的数字III

题目链接:260.只出现一次的数字III
题目描述在这里插入图片描述

此类问题可以通过位运算(异或操作)来解决。首先,我们可以通过对所有数组元素执行异或操作来找出两个只出现一次的元素的异或结果。因为异或操作具有交换律和结合律,同时一个数字和自己进行异或会变成0,所以最终剩下的结果就是那两个只出现一次的数字的异或结果

这个结果中至少有一个位是1(否则这两个数相同),我们可以找到这个数中的任何一个为1的位,用它来把原数组分成两组,一组在该位上是1,一组在该位上是0。这样每组就包含了一个只出现一次的数字和一些成对出现的数字。然后再对这两个组分别进行异或操作,即可得到这两个只出现一次的数字。

下面是这个算法实现:

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {// 第一步,对所有元素进行异或,最终的结果就是两个只出现一次数的异或结果int diff = 0;for (int num : nums) {diff ^= num;}// 找到diff中任何为1的位,可以使用diff & -diff快速找到// 这个操作可以隔离出diff最右端的1unsigned int diff_unsigned = diff;diff_unsigned &= -diff_unsigned;// 使用找到的这一位将数组中的数字分成两组vector<int> results(2, 0); // 最终结果for (int num : nums) {if ((num & diff_unsigned) == 0) {// 第一组,与diff_unsigned对应位为0results[0] ^= num;} else {// 第二组,与diff_unsigned对应位为1results[1] ^= num;}}return results;}
};

在这个代码中:

  • diff_unsigned 最终会被设置为两个目标数字的异或结果。
  • diff_unsigned &= -diff_unsigned; 的结果是取出 diff_unsigned 最右边的1位,也就是两个只出现一次的数在这一位上不同的地方。
  • 然后我们通过判断这一位是否为1来将全部数字分为两组,并再次分别对它们进行异或操作,以此找到两个只出现一次的数。

这条语句 diff_unsigned &= -diff_unsigned; 是一种计算机用来找到一个数字中最右边的1的位,并且保持所有其他位为0的技巧。为了更好地理解这个技巧,我们需要先了解计算机中的数字表示——特别是补码表示法,因为这个技巧与负数的二进制表示相关

在补码表示中,一个负数是通过取其正值的二进制表示的反码(每个位取反)然后加1得到的。例如,假设我们有一个4位的系统:

正数 2 的二进制表示:  0010
反码 (invert):      1101
加1得到负数 -2:      1110

观察发现,从正数2的二进制表示到负数-2的表示,最右边的1以及之前的所有0都保持不变,而最右边的1之后的所有位都翻转了。这给了我们一种找到最右边的1的方法。现在,如果我们对2和-2执行按位与操作:

正数 2:                0010
负数 -2:               1110
按位与:                0010

按位与操作的结果就是只有最右边的1保留了下来,其它所有位都变成了0。换句话说,diff_unsigned &= -diff_unsigned; 将结果的所有位都置为0,除了最右边的1所在的位。

在解决问题时,我们首先会通过对所有数字进行异或得到 diff,这代表了两个只出现一次的数字的差异。
diff 变量首先被转换成一个无符号整数 diff_unsigned,然后对它进行取负和按位与操作,以避免未定义行为。这样就保证了即使 diff 的最高有效位是1,我们也不会超出无符号整型的范围

然后使用 diff_unsigned &= -diff_unsigned; 来保留最右边的1,这是两个独特数字在二进制表示中第一个不同的位。

通过这个位的差异,我们可以将所有的数字分成两组来进一步操作,每组包含一个只出现一次的数字以及成对出现的数字。这个1所在的位将用于分辨哪些数字在该位为0或1 —— 这正是对数组进行划分的依据

6.电话号码的字母组合

题目链接:17.电话号码的字母组合
题目描述在这里插入图片描述

这个问题可以通过回溯法解决,这是一种通过穷举所有可能的解来找到全部解的算法。基本思想是从左到右遍历数字字符串,对于每个数字,向当前的字母组合中添加对应的每个字母,然后对剩余的字符串重复这个过程。

下面是递归解决实现:

class Solution {
public:vector<string> letterCombinations(string digits) {if (digits.empty()) return {}; // 如果输入为空,直接返回空数组vector<string> mappings = {  // 数字到字母的映射"", "", "abc", "def",   // '0','1','2',..."ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};vector<string> result;string current;backtrack(result, digits, 0, current, mappings);return result;}private:void backtrack(vector<string>& result, const string& digits, int index, string& current, const vector<string>& mappings) {if (index == digits.length()) { // 如果到达了数字字符串的末尾,就添加当前的字母组合到结果中result.push_back(current);return;}string letters = mappings[digits[index] - '0']; // 获取当前数字对应的所有字母for (char letter : letters) { // 遍历这些字母current.push_back(letter);   // 添加当前的字母backtrack(result, digits, index + 1, current, mappings);  // 继续处理下一个数字current.pop_back();  // 回溯,移除当前字母,以便尝试下一个字母}}
};

这段代码定义了一个辅助函数 backtrack,用来递归寻找所有可能的字母组合。我们维护一个 current 字符串,它保存当前的部分组合。函数的工作流程是这样的:

  1. 确定终止条件:如果 current 的长度与输入数字字符串的长度相同,说明当前递归路径已经走到头,我们找到了一个完整的字母组合,将其添加到结果中。

  2. 确定递归逻辑:从 mappings 数组中获取当前处理的数字对应的所有可能字母,然后逐一向 current 添加每个字母,并递归地调用自己处理下一个数字。

  3. 回溯处理:每次递归调用完成后,需要将之前添加的字母移除,以便对当前位置尝试不同的字母。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HCIP-Datacom-ARST必选题库_01_ACL【7道题】

一、单选 1.下面是一台路由器的部分配置,关于该配置描述正确的是&#xff1a; 源地址为1.1.1.1的数据包匹配第一条ACL语句rule 0,匹配规则为允许 源地址为1.1.1.3的数据包匹配第三条ACL语句rule 2,匹配规则为拒绝 源地址为1.1.1.4的数据包匹配第四条ACL语句rule 3,匹配规则为允…

Scala 05 —— 函数式编程底层逻辑

Scala 05 —— 函数式编程底层逻辑 该文章来自2023/1/14的清华大学交叉信息学院助理教授——袁洋演讲。 文章目录 Scala 05 —— 函数式编程底层逻辑函数式编程假如...副作用是必须的&#xff1f;函数的定义函数是数据的函数&#xff0c;不是数字的函数如何把业务逻辑做成纯函…

python爬虫学习------scrapy第二部分(第三十天)

&#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; &#x1f388;&#x1f388;所属专栏&#xff1a;python爬虫学习&#x1f388;&#x1f388; ✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天…

底层逻辑(1) 是非对错

底层逻辑(1) 是非对错 关于本书 这本书的副标题叫做&#xff1a;看清这个世界的底牌。让我想起电影《教父》中的一句名言&#xff1a;花半秒钟就看透事物本质的人&#xff0c;和花一辈子都看不清事物本质的人&#xff0c;注定是截然不同的命运。 如果你看过梅多丝的《系统之美…

数据挖掘实验(Apriori,fpgrowth)

Apriori&#xff1a;这里做了个小优化&#xff0c;比如abcde和adcef自连接出的新项集abcdef&#xff0c;可以用abcde的位置和f的位置取交集&#xff0c;这样第n项集的计算可以用n-1项集的信息和数字本身的位置信息计算出来&#xff0c;只需要保存第n-1项集的位置信息就可以提速…

2024年巴黎奥运会临近,中国义乌又爆弹了?网友:这就是硬核实力

奥运订单热潮涌动&#xff0c;中国制造不可或缺 随着巴黎奥运会脚步的日益临近&#xff0c;中国义乌再次聚焦全球视野。 近日&#xff0c;国货探访浙江义乌国际商贸城&#xff0c;发现众多蕴含法国元素的商品被置于显眼位置&#xff0c;吸引众多采购商纷至沓来&#xff0c;争…

android脱壳:一种使用native进行抽取壳脱壳的方法,native版本的frida-fart

前言 写rxposed的时候&#xff0c;搞了很多模块&#xff0c;其中有一个远程调用脱壳的&#xff0c;但是当时使用的是rmi远程调用&#xff0c;因为一些问题无法使用&#xff0c;可能是对抗问题&#xff0c;也有可能是技术问题&#xff0c;所以我又换了一种远程调用方式。 概述…

云原生的基石:containerd引领未来容器发展趋势

文章目录 一、Containerd简介&#xff1a;容器技术的心脏二、Containerd核心原理解析三、Containerd与Docker的关系四、Containerd在云原生应用部署中的作用五、Containerd的扩展性和插件机制六、Containerd的安全特性七、Containerd的性能优化八、Containerd的社区和生态系统九…

【51单片机项目】基于51单片机自制多功能小键盘/模拟USB键盘【附源码】(STC89C52RC+CH9328)

目录 一、效果展示 二、创作灵感 三、硬件电路 注意事项 工作原理 四、源码 main.c 五、附录 CH9328工作原理 CH9328的模式选择 ​编辑 全键盘键码值表 参考链接 一、效果展示 该小键盘具有三种功能&#xff1a; 1、自动输入开机密码 2、每隔一段时间自动按下ct…

通用大模型研究重点之五:llama family

LLAMA Family decoder-only类型 LLaMA&#xff08;Large Language Model AI&#xff09;在4月18日公布旗下最大模型LLAMA3&#xff0c;参数高达4000亿。目前meta已经开源了80亿和700亿版本模型&#xff0c;主要升级是多模态、长文本方面工作。 模型特点&#xff1a;采用标准的…

Unreal Engine创建Plugin

打开UE工程&#xff0c;点击编辑&#xff0c;选择插件 点击“新插件”按钮&#xff0c;选择“空白选项”填入插件名字"MultiPlayerPlugin"&#xff0c;填入插件作者、描述&#xff0c;点击“创建插件”按钮打开C工程&#xff0c;即可看到插件目录&#xff0c;编译C工…

【网络安全】安全事件管理处置 — 安全事件处置思路指导

专栏文章索引&#xff1a;网络安全 有问题可私聊&#xff1a;QQ&#xff1a;3375119339 目录 一、处理DDOS事件 1.准备工作 2.预防工作 3.检测与分析 4.限制、消除 5.证据收集 二、处理恶意代码事件 1.准备 2.预防 3.检测与分析 4.限制 5.证据收集 6.消除与恢复 …

游戏新手村18:游戏广告渠道与广告形式

上文我们说到&#xff0c;渠道为王&#xff0c;渠道可以为我们带来流量和用户&#xff0c;进而带来收入。我们可以通过哪些渠道导入用户呢&#xff1f;每个渠道有哪些优劣呢&#xff1f;在进行游戏营销推广的时候我们该如何选择呢&#xff1f; 根据付费性质&#xff0c;我们可…

鸿蒙ArkUI实战开发-如何通过上下滑动实现亮度和音量调节

场景说明 在音视频应用中通常可以通过上下滑动来调节屏幕亮度和音量大小&#xff0c;本例即为大家介绍如何实现上述UI效果。 说明&#xff1a; 由于当前亮度和音量调节功能仅对系统应用开发&#xff0c;所以本例仅讲解UI效果的实现。 效果呈现 本例效果如下&#xff1a; 当在…

iOS - 多线程-GCD-队列组

文章目录 iOS - 多线程-GCD-队列组1. 队列组1.1 基本使用步骤 iOS - 多线程-GCD-队列组 开发过程中&#xff0c;有时候想实现这样的效果 多个任务并发执行所有任务执行完成后&#xff0c;进行下一步处理&#xff08;比如回到主线程刷新UI&#xff09; 1. 队列组 可以使用GC…

区间图着色问题:贪心算法设计及实现

区间图着色问题&#xff1a;贪心算法设计及实现 1. 问题定义2. 贪心算法设计2.1 活动排序2.2 分配教室2.3 算法终止 3. 伪代码4. C语言实现5. 算法分析6. 结论7. 参考文献 在本文中&#xff0c;我们将探讨如何使用贪心算法解决一个特定的资源分配问题&#xff0c;即区间图着色问…

ruby 配置代理 ip(核心逻辑)

在 Ruby 中配置代理 IP&#xff0c;可以通过设置 Net::HTTP 类的 Proxy 属性来实现。以下是一个示例&#xff1a; require net/http// 获取代理Ip&#xff1a;https://www.kuaidaili.com/?refrg3jlsko0ymg proxy_address 代理IP:端口 uri URI(http://www.example.com)Net:…

【002_音频开发_基础篇_Linux音频架构简介】

002_音频开发_基础篇_Linux音频架构简介 文章目录 002_音频开发_基础篇_Linux音频架构简介创作背景Linux 音频架构ALSA 简介ASoC 驱动硬件架构软件架构MachinePlatformCodec ASoC 驱动 PCMALSA设备文件结构 ALSA 使用常用概念alsa-libALSA Open 流程ALSA Write 流程2种写入方法…

Android Studio查看viewtree

前言&#xff1a;之前开发过程一直看的是手机上开发者选项中的显示布局边界&#xff0c;开关状态需要手动来回切换&#xff0c;今天偶然在Android Studio中弄出了布局树觉得挺方便的。

【STM32F407+CUBEMX+FreeRTOS+lwIP之TCP记录】

STM32F407CUBEMXFreeRTOSlwIP之TCP记录 注意TCP client(socket)示例 TCP_server(socket)效果 注意 如果连接失败&#xff0c;建议关一下代理软件。 配置方面可以参考一下上一篇UDP的文章 STM32F407CUBEMXFreeRTOSlwIP之UDP记录 TCP client(socket) #define LWIP_DEMO_PORT 8…