【OJ】vector刷题
1. 136.只出现一次的数字
1.1 分析
如果某一个数字只出现一次，那么进行异或返回的结果就是它本身。 直接遍历一遍顺序表里面的元素，再进行异或，其他出现过不止一次的数据就会在进行异或的时候为0，那么返回的最终结果就是只出现一次的数。
1.2 代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int value= 0;
for(auto e : nums)
{
value ^= e;
}
return value;
}
};2. 118.杨辉三角
2.1 分析
题目给的是等腰三角形这样的数组，但是实际上是像右边这种直角形状的。
开空间在第0行得开一个空间，每一行的多开一个空间。用resize开空间，在初始化的时候，看图中，一行的第一个位置和最后一个位置都是1：
for(size_t i=0;i<vv.size();i++)
{
vv[i].resize(i+1,0);
vv[i][0]=vv[i][vv[i].size()-1]=1;
}在填表的时候，遍历这个数组，注意要计算一行的中第i个数据，就要用到i-1行的数据:
for(size_t i=0;i<vv.size();i++)
{
for(size_t j=0;j<vv[i].size();j++)
{
if(vv[i][j]==0)
{
vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
}
}
}最后返回这个顺序表就行。
2.2 代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for(size_t i=0;i<vv.size();i++)
{
vv[i].resize(i+1,0);
vv[i][0]=vv[i][vv[i].size()-1]=1;
}
for(size_t i=0;i<vv.size();i++)
{
for(size_t j=0;j<vv[i].size();j++)
{
if(vv[i][j]==0)
{
vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
}
}
}
return vv;
}
};3. 119.杨辉三角 II
3.1 分析
这里基本和上面那题是一样的，不同的是这里要求返回的是某一行的结果，那么在开空间的时候就得多开一行：vv.resize(rowIndex+1);
其他部分的初始化和计算和上面的都一样，不同就是在返回结果的时候，就直接返回题目要求的那一行return vv[rowIndex];
3.2 代码
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> vv;
vv.resize(rowIndex+1);
for(size_t i=0;i<vv.size();i++)
{
vv[i].resize(i+1,0);
vv[i][0]=vv[i][vv[i].size()-1]=1;
}
for(size_t i=0;i<vv.size();i++)
{
for(size_t j=0;j<vv[i].size();j++)
{
if(vv[i][j]==0)
vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
}
}
return vv[rowIndex];
}
};4.137. 只出现一次的数字 II
4.1 分析
与第一题类似，利用位运算符异或和取反。 如果某一个数字只出现一次，那么进行异或返回的结果就是它本身。 先计算出b，再拿新的b值计算a,当我们遍历完数组中的所有元素后，ab要么是 00，表示答案的第i位是0;要么是 01，表示答案的第 i位是 1。因此我们只需要返回b作为答案即可。
4.2 代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0,b=0;
for (auto e : nums)
{
b = ~a & (b ^ e);
a = ~b & (a ^ e);
}
return b;
}
};5. 260.只出现一次的数字 III
5.1 分析
因为 nums 中出现两次的元素都会因为异或运算的性质抵消掉，那么最终的结果就只剩下出现过一次的元素。
判断一下是否越界：int f= value==INT_MIN ?value:value&(-value);
对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中，对于任意一个在数组 nums中只出现了一次的元素它们会被包含在不同类中。因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到第一个出现一次的元素，另一类会得到第一个出现一次的另一个元素，这样我们就找出了这两个只出现一次的元素。
5.2 代码
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int value = 0;
for (int e: nums) {
value ^= e;
}
int f= value==INT_MIN ?value:value&(-value);
int a = 0, b = 0;
for (int e: nums) {
if (e & f) {
a ^= e;
}
else {
b ^= e;
}
}
return {a, b};
}
};腾讯云开发者
