admin管理员组文章数量:1487745
LeetCode之vector
前言
本篇是对vector的一个巩固练习, 题目分别在leetcode和牛客网
博客主页: 酷酷学!!!
感谢关注~
正文开始
1. 杨辉三角
题目思路
首先我们需要返回二维数组, 那么首先创建二维数组, 观察可发现, 杨辉三角的每一行的第一列和最后一列都是1, 其余位置都是上一行的同位置的值和上一行的前一个为位置的值. 由此我们来构建杨辉三角
参考代码
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for(int i = 0; i < numRows; i++)
{
vv[i].resize(i+1,0);
vv[i][0] = vv[i][vv[i].size()-1] = 1;
}
for(int i = 0; i < vv.size() ; i++)
{
int m = vv[i].size();
for(int j = 0;j < m;j++)
{
if(vv[i][j] == 0)
{
vv[i][j] = vv[i-1][j-1]+vv[i-1][j];
}
}
}
return vv;
}
};2. 删除有序数组的重复项
题目思路
采用双指针法, 快指针用来遍历数组, 慢指针用来记录待插入的位置, 因为是有序, 所以我们不需要考虑其它的地方, 重复的数组一定是挨着的, 所以如果快指针和前一个位置的值不相等, 就往慢指针的地方放.
参考代码
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int removeDuplicates(vector<int>& nums) {
size_t n = nums.size();
int fast = 1, slow = 1;
while(fast < n)
{
if(nums[fast] != nums[fast - 1])
{
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};3. 只出现一次的数字Ⅲ
题目思路
本题有点类似于我们之前做的单身狗的进阶版本, 如果找出数组中唯一只出现一次的数字, 我们可以使用异或进行求解, ^ 相同为0, 不同为1 , 自己和自己异或也是0 , 所以如果里面的一个数和所有的数组都异或一遍, 结果一定是那个唯一的数字, 那么本题如果全部异或则是最后两个不同的数字异或的结果.
如果我们能够将这两个数字分到不同的组中, 然后不同的组分别异或, 则最后的分别求出组中唯一的数字, 不就可以了吗, 那么怎么分组呢, 首先需要保证这两个数字进行分开, 然后相同的数也要分到不同的组, 相同的数二进制是一样的, 我们考虑用二进制分, 两个数异或的结果, 如果为1, 则说明这两个数在这一位上不同, 就根据这一位进行分组, 当然任意一位的1都可以, 我们从右往左找到为1的位, 进行分组, 这一位为0的为一组, 为1的为一组, 那些相同的数字这一位一定也是一样的, 所以所有数字都已经分好了, 然后再分别异或, 结果采用列表返回, 这个是vector构造方法中的一种.
参考代码
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int len = nums.size();
int tmp = 0;
int count1 = 0, count2 = 0;
//tmp为那两个数异或的结果,据此进行分组
for(int i = 0; i< len ; i++)
{
tmp = tmp ^ nums[i];
}
//找到一个值为1的位,进行分组
int pos = -1;
for(int i = 0; i< 32 ; i++)
{
if(tmp & 1 == 1)
{
pos = i;
break;
}
tmp = tmp >> 1;
}
//分组
for(int i = 0; i< len ; i++)
{
if((nums[i] >> pos) & 1 == 1)
{
count1 = count1 ^ nums[i];
}
else
{
count2 = count2 ^ nums[i];
}
}
return {count1,count2};
}
};4. 只出现一次的数字Ⅱ
题目思路
我们知道计算机存储整数都是以二进制的方式进行存储, C++对符号位也会进行区分, 根据题目描述, 只有一个数字出现了一次, 其余数字都出现了三次, 因为二进制的位除了1就是0, 所以我们可以将所有数的二进制位按位与1求出来, 对每一位遍历数组, 将数组的元素这个位上的所有数组都求和, 如果能被3整除, 则说明那个唯一一个数的这一位为0, 如果被除以3余数为1,则说明那个唯一一个数的这一位为1, 然后将求得的位数为别加到ans中,即为唯一的数.
参考代码
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
int n = nums.size();
for(int i = 0; i< 32 ;i++)
{
int tmp = 0;
for(int j = 0; j < n; j++)
{
tmp += (nums[j] >> i) & 1;//每个数的所有位相加
}
if(tmp % 3 == 1)
{
ans |= (1<<i);//ans是1的位
}
}
return ans;
}
};5. 数组中出现次数超过一半的数字
题目思路
首先由题意得那个数超过数组长度的一半, 那如果我们将数组进行排序, 那么那个数一定出现在中间位置, 由此求出, 我们这里采用C++SLT中的方法sort进行排序.
参考代码
代码语言：javascript代码运行次数：0运行复制#include <limits>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int MoreThanHalfNum_Solution(vector<int>& numbers) {
sort(numbers.begin(),numbers.end());
return numbers[numbers.size()/2];
}
};补充讲解sort()
在c语言阶段, 我们一般使用qsort函数进行排序, 那样比较麻烦, 我们还需要传递一个比较函数的指针, 没有sort使用起来方便, sort包含在头文件 < algorithm > 这个库中, 参数为迭代器区间, 排序时, 我们只需传递容器的迭代区间即可.
举个例子
代码语言：javascript代码运行次数：0运行复制#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
vector<int> v1;
v1.push_back(213);
v1.push_back(12);
v1.push_back(3);
v1.push_back(0);
v1.push_back(27);
sort(v1.begin(), v1.end());
auto it1 = v1.begin();
while (it1 != v1.end())
{
cout << *it1 << " ";
++it1;
}
cout << endl;
greater<int> gt;
sort(v1.begin(), v1.end(), gt);//降序
auto it2 = v1.begin();
while (it2 != v1.end())
{
cout << *it2 << " ";
++it2;
}
cout << endl;
return 0;
}sort函数默认的排序方式是升序, 当然我们可以进行降序, 可以看到sort的第三个参数, 这里可以传递一个函数指针或者一个函数对象, 这个函数的返回值可以转化为一个bool值,从而区分两个数的前后顺序. 这里我们可以传递gerater的对象, 默认为比较为>,当然还有less默认比较为<
完
如果认为此文对您有帮助, 感谢您的关注, 三连!!!
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-07-29，如有侵权请联系 cloudcommunity@tencent 删除leetcodevector函数数组指针本文标签： LeetCode之vector
版权声明：本文标题：LeetCode之vector 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/shuma/1754790687a3179611.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论