【C++】vector系列力扣刷题日志(136.只出现一次的数字,118.杨辉三角,26.删除有序数组中的重复项,260.只出现一次的数字 |||)

本文主要是介绍【C++】vector系列力扣刷题日志(136.只出现一次的数字,118.杨辉三角,26.删除有序数组中的重复项,260.只出现一次的数字 |||),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

136.只出现一次的数字

118.杨辉三角

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

260.只出现一次的数字 |||


vector的详细介绍及用法这里就不过多赘述了,可以参考上一篇博客:vector的介绍及使用说明

136.只出现一次的数字

题目:

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入:nums = [2,2,1]
输出:1

示例 2 :

输入:nums = [4,1,2,1,2]
输出:4

示例 3 :

输入:nums = [1]
输出:1

题目要求我们找到只出现了一次的元素,我们最先想到的思路是,遍历一遍数组,记录当前的元素并再进行一次遍历,判断该元素的出现次数,如果只出现了一次,就输出结果。定义一个常量来标记当前出现次数:

class Solution {
public:int singleNumber(vector<int>& nums) {for (auto value = nums.begin(); value != nums.end(); value++){int flag = 2;for (auto it = nums.begin(); it != nums.end(); it++){if (*it == *value) {flag--;}}if (flag)return *value;}return 0;}
};

思路没有问题,但是这种解法的性能消耗显然过高,因为使用的是嵌套循环,时间复杂度来到了O(n^2),那么还有没有别的解法呢?来看下面这个思路:

这道题目也可以通过异或运算来解决,异或运算有一个性质:任何数和0做异或运算,结果仍然是原来的数,即a^0=a。任何数和自身做异或运算,结果是0,即a^a=0。

我们只需要让数组内元素两两做异或,再将结果与后一个元素异或,最终的到的结果就是只出现了一次的那个数。

 如此一来,只需遍历一次数组就得到了结果:

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

 可以看到,性能提高了不止一点

118.杨辉三角

题目

给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

题目要求我们创建一个包含杨辉三角的vector容器,存储在一个二维数组当中,我们可以使用vector的push_back方法插入元素,vector会自动扩容,不需要我们管理内存,由于返回的是一个二维数组,我们先创建一个一维数组,再将其插入到二位数组当中即可:

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

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

题目:

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]

这道题目和前面的第一题相似,不过这道题找的是重复项并需要进行删除操作,同样的,我们可以使用vector的erase方法,其实质是将指定的元素进行删除并且将后序的元素向前移动填补空缺,显然符合题目要求:

class Solution {
public:int removeDuplicates(vector<int>& nums) {for (auto value = nums.begin(); value != nums.end(); value++){int flag = 2;for (auto it = nums.begin(); it != nums.end();){if (*it == *value) {flag--;if (flag < 1) {it = nums.erase(it);}else {++it;}}else {++it;}}}return nums.size();
}
};

要注意的是,使用erase删除元素后,原来指向被删除元素的迭代器就不再指向一个有效的元素了,因为被删除元素之后的所有元素都向前移动了一个位置,迭代器指向的位置已经被其他元素占据。如果继续使用这个迭代器进行操作,比如解引用或者递增,就会导致未定义行为

为了避免这种情况,通常建议在调用‘erase’删除元素后,使用‘erase’返回的新的迭代器,以确保迭代器指向的位置是有效的。

260.只出现一次的数字 |||

题目:

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1:

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:

输入:nums = [-1,0]
输出:[-1,0]

示例 3:

输入:nums = [0,1]
输出:[1,0]

此题和第一题更为相像了,这里要找的是两个只出现了一次的元素,所以我们只需要在第一题的基础上,改动以下返回值就可以了,返回一个vector容器,里面存放两个元素:

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int> ret;for (auto value = nums.begin(); value != nums.end(); value++){int flag = 2;for (auto it = nums.begin(); it != nums.end(); it++){if (*it == *value) {flag--;}}if (flag)ret.push_back(*value);}return ret;
}};

在实际运用中我们要熟悉vector的常见接口,在合适的场景中使用出来

以上就是vector的一些实际运用场景,欢迎在评论区留言,觉得这篇博客对你有帮助的,可以点赞收藏关注支持一波~😉

这篇关于【C++】vector系列力扣刷题日志(136.只出现一次的数字,118.杨辉三角,26.删除有序数组中的重复项,260.只出现一次的数字 |||)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问