【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

相关文章

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》:本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本:1.5.0采用1.5.0版本主要