C++ 算法(五)

༺ 个人主页 · 纪念229 ༻

🏠我的博客主页🏠

༒专栏目录：《数据结构》༒

༒专栏目录：《算法》༒

༒专栏目录：《C++》༒

༒专栏目录：《MySQL数据库》༒

༒专栏目录：《前端开发》༒

༒其它有趣的计算机知识༒

༺世上本没有路，走的人多了自然就有了༻

本篇文章讲述的是有关vector的题,希望对你有所帮助

题目链接： 杨辉三角 只出现一次的数字i 只出现一次的数ii

文章目录

• 1.杨辉三角
• 2.只出现一次的数字i
• 3.只出现一次的数ii
• 4.拓展有兴趣做一下

1.杨辉三角

杨辉三角是从第三行开始到指定行除去第一个元素和最后一个元素其它数据的值都为该位置上一个元素和该位置上一个元素的前一个元素之和,这里我们用的是C++我们可以设计一个vector<vector>(就是数组里的元素是整形数组)我们根据杨辉三角先将每一行所具有的个数(定义的该对象每个元素都为一个整形数组（也就是我们所说的行））)定义为1在不用考虑下标因为它只要求每行符合它所有的个数,然后从第三行开始(数组的下标2)）每一行除了第一个元素和最后一个元素它的值都为该下标正对上一行的元素和该元素前面的元素和

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> v;

// int num;

// cin >> num;//没看题目给的参数应该用numRows(它已经给你了不用管)

for(int i = 1; i <= numRows; i++)

{

v.push_back(vector<int>(i,1));

}

for(int j = 2; j < numRows; j++)

// for(int j = 2; j < v.size(); j++)//这里的v.size()可以改用numSize能用变量就不用函数

{

for(int i = 1;i < v[j].size() – 1; i++)

{

v[j][i] = v[j – 1][i –1] + v[j – 1][i];

// v[j][i] = v[j – 1][i] + v[j – 1][i + 1];这个错了因该是上一行左上加上上一行正上

}

//最后记得返回v函数返回类型是vector<vector<int>>

}

return v;

}

};

vector<vector<int>> v; 这里我们先定义一个每个元素都为一个整形数组的数组

然后我们将每个元素拥有的元素个数定义好（第一个元素指的是第一行第二个元素第二行以此类推）

for (int i = 1; i <= numRows; i++)

{

v.push_back(vector<int>(i, 1));
}

这里从一开始i 为1因为我们的vector类型的对象要push_back一个只有一个元素且元素都为1的用vector<int(i , 1)>这里说明一点看起来传的是临时对象但是不是，vector<int(i , 1)>在函数里面作为参数就是一个普通对象不是临时对象生命周期长

然后一个个插入循环放入形成符合杨辉三角的形状

for (int j = 2; j < numRows; j++)

// for(int j = 2; j < v.size();
// j++)//这里的v.size()可以改用numSize能用变量就不用函数

{

for (int i = 1; i < v[j].size() – 1; i++)

{

v[j][i] = v[j – 1][i – 1] + v[j – 1][i];

// v[j][i] = v[j – 1][i] + v[j – 1][i +
// 1];这个错了因该是上一行左上加上上一行正上
}

// 最后记得返回v函数返回类型是vector<vector<int>>
}

接着我们从第三行开始(下标的2)开始将除了第一个元素和最后一个元素其它元素都为它自身下标正上方的下标所指向的元素以及该元素前一个下标所指向的元素之和 我们利用两个for循环解决第一个 j= < Rownums是因为Rownums – 1就是最后一行 第二个循环 i = 1 到 v[j].size() – 2 是因为第一个元素和最后一个元素不用改(该行下标为0的位置指向的元素为1最后一个元素的下标为 v[j].size() – 1 指向的元素为 1)

return v;

最后返回定义的对象v即使我们所设计的杨辉三角

2.只出现一次的数字i

题目要求给你一个整形数组(vector)数组里只有一个数据只有一个其它数据相同的数据都是成对存在的

这里我们用^按位异或定义一个变量开始为0将整形数组的数据一个与这个数据按位异或就可以得到只出现一次的数字

原因当整形数组只有一个出现一次其它都只出现两次的时候用将它们互相按位异或得到的最终结果是只出现一次的那个数据

按位XX的我们一般都用在有32位的整型上

按位异或： 假如有两个整数 将第一个整数32位中(从右往左下标0到下标31)每一位于第二个整数它们所对应的下标进行匹配相同的为0不同为1所以如果两个整数相等所以它们的32位上的 数字相等所以返回的是32为上都为0的整数(这个整数为0) ，0按位异或任何数都为我们用按位异或0的那个数

所以我们将一个整形数组（该数组只有一个出现一次其它数据都出现为偶数）按位异或得到的就是只出现一次的那个数字

class Solution {

public:

int singleNumber(vector<int>& nums) {

int result = 0;

//利用范围for遍历以及异或求出只出现一次的数（且只有一个数出现一次）前提是其它数据的个数都是偶数

for(auto e: nums)

{

result ^= e;

}

return result;//0异或任何数都是那个数（与0异或的数）

}

};

int result = 0; 首先我们定义一个int类型的result为0因为0按位异或任何整数都为该数

然后利用范围for遍历nums对象(整形数组)将数组中的每个数据都于result按位异或最后返回的就是只出现一次的数据

3.只出现一次的数ii

这里要求是有一个只出现一次的数据其它的数据都出现三次 上一个题是其它的数据都出现二次这里不能用按位异或因为按位异或只能抵消出现次数为偶数的 我们这里有一个通法有一个只出现一次的数据其它的数据都出现k次(其它只出现两次也可以用只是用for循环按位异或代码少)

这里讲一下按位与和按位或

我们这里讨论的32位指的是2进制的32位 &(按位与) 同为1才为1否则为0 |(按位或) 有1就为1否则为0

解释一下 int num; num >> i(i为整型)是什么意思 我们知道num为整形 将它 >> i的意思是将num的32位整体往后移动i个位置32前面的的位置补0 num << i的意思是将num的32位整体往前移动i个位置32后面的的位置补0

//这种题只有一个数据为一个其它数据都为为k个的都可以用按位统计

//之前那个其它为2个的可以用按位异或简化代码

class Solution {

public:

int singleNumber(vector<int>& nums) {

int result = 0;//留着放只有一个的数据

//整数有32位（第32位是正负值天然符合正负值整数）我们将32位遍历将某位上只有一个的数据值保留（将k个的% k去除）返回就是只出现一次的数字(32位从右到左下标是从0开始所以最后一个下标为31)

for(int i = 0; i < 32; i++)

{

int count = 0;//统计数组中所有数据里的第i位的和最后将其% k若是有数据(1)说明只有一个的数据在该位有1放入result里遍历32位将32位里存着只有一个的数据的位上的1全放入result中所得的就是该数组中只有一个的数据（利用按位与和按位或以及>> << 将位数移动即可实现）

//用范围for遍历数组将该位上的数据加起来

for(auto num : nums)

{

count += (num >> i) & 1;//按位与(&)两个数据某位上都为1才为1否则全为0利用这个只留下该位的数据（可能为0也可能为1）其余位上都为0（num >> i 的意思是将数据的32位整体向右移动i位利用这个我们可以遍历所有数据中该位的值(这个是位移运算符优先级大于按位与和按位或)）

//判断该位上是否可以余k(数据相同的个数)不为0说明该位上有只有一个的数据在该位上的数据将它移到result

//判断count是否可以 % 3后有余数在count加完在判断

}

if(count % 3 != 0)

result |= 1 << i;//(x << i意思是将某数据向左移动i位这里目的是将某位上的只有一个数的数据在改位上的1放在result上（这两个位移运算符实际上是将该数据改变）)（按位或意思是有1就为1没就为0将位移后的1所形成的数据（该数据就在I位有1其余都为0）按位与result里因为之前的数据位数上有一也有0有一的还是1为0的位与右边数据同位上的数也为0（i移动的那位有1那一定是1））

}

return result;

}

};

我们先定义一个result为0，32位都为0 我们题目是要求有数据相同个数为3个这些相同的数据32位对应的每一位相加（这里我们不用管某位为0的）1在 余(%)3得到的就是0 如果有一个只出现一次的数据也参数32位所对应的位上的加(这里我门只管位为1的0的不用管)那么该位余数就为1不为0说明该位上有只出现一次的数据的1我们只要把32位中只出现一次的数据在32位上的1全找出来就可以得到只出现一次的数据(二进制位上只有1和0)

int result = 0;//留着放只有一个的数据

首先我们定义一个result将所有数据的32为遍历一遍将32位上只出现一次的数据上的32为位上为1的放到对应的位上result得到的就是只出现一次的数据

for(int i = 0; i < 32; i++)

{

int count = 0;//统计数组中所有数据里的第i位的和最后将其% k若是有数据(1)说明只有一个的数据在该位有1放入result里遍历32位将32位里存着只有一个的数据的位上的1全放入result中所得的就是该数组中只有一个的数据（利用按位与和按位或以及>> << 将位数移动即可实现）

//用范围for遍历数组将该位上的数据加起来

for(auto num : nums)

{

count += (num >> i) & 1;//按位与(&)两个数据某位上都为1才为1否则全为0利用这个只留下该位的数据（可能为0也可能为1）其余位上都为0（num >> i 的意思是将数据的32位整体向右移动i位利用这个我们可以遍历所有数据中该位的值(这个是位移运算符优先级大于按位与和按位或)）

//判断该位上是否可以余k(数据相同的个数)不为0说明该位上有只有一个的数据在该位上的数据将它移到result

//判断count是否可以 % 3后有余数在count加完在判断

}

if(count % 3 != 0)

result |= 1 << i;//(x << i意思是将某数据向左移动i位这里目的是将某位上的只有一个数的数据在改位上的1放在result上（这两个位移运算符实际上是将该数据改变）)（按位或意思是有1就为1没就为0将位移后的1所形成的数据（该数据就在I位有1其余都为0）按位与result里因为之前的数据位数上有一也有0有一的还是1为0的位与右边数据同位上的数也为0（i移动的那位有1那一定是1））

}

return result;

我们遍历32位(有下标从0到31)我们先从所有数据下标为0所指向的位数开始将数据全部相加 count += (num >> i) & 1;这个我前面介绍过 然后判断这位上%3(这里可以是3或者其它只要是整形数组只有一个只出现一次其它只出现k次时就可以用此方法)后是否为0不为0的话就将该位上的1移到result上

遍历完32位时我们返回的result就是只出现一次的数据

4.拓展有兴趣做一下

只出现一次的数iii 数组中出现次数超过一半的数字

文章到此就告一段落，希望对你有所帮助，感谢观看!