【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

相关文章

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

如何自定义Nginx JSON日志格式配置

《如何自定义NginxJSON日志格式配置》Nginx作为最流行的Web服务器之一,其灵活的日志配置能力允许我们根据需求定制日志格式,本文将详细介绍如何配置Nginx以JSON格式记录访问日志,这种... 目录前言为什么选择jsON格式日志?配置步骤详解1. 安装Nginx服务2. 自定义JSON日志格式各

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa