当前位置：首页 > news >正文

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

news 来源：原创 2024/5/17 21:56:05

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的一些实际运用场景，欢迎在评论区留言，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉