邯郸做移动网站的地方,网站建设公司成就,文案发布平台,巴中网站建设网站推广1.只出现一次的数字 我们可以使用异或运算来解决这个问题#xff1a; 异或运算有一个重要的性质#xff1a;两个相同的数进行异或运算结果为 0#xff0c;任何数与 0 异或结果为其本身。对于数组中的元素#xff0c;依次进行异或运算#xff0c;出现两次的元素异…1.只出现一次的数字 我们可以使用异或运算来解决这个问题 异或运算有一个重要的性质两个相同的数进行异或运算结果为 0任何数与 0 异或结果为其本身。对于数组中的元素依次进行异或运算出现两次的元素异或后会变成 0最后剩下的就是只出现一次的那个元素。 以下是具体步骤 数组 [2,2,1]2^200^11所以输出 1。
那么请看正确代码
class Solution {
public:int singleNumber(vectorint nums) {int val0;for(auto e :nums)val^e;return val;}
};
这是一种方法然而还有一种传统的方法
class Solution {
public:int singleNumber(vectorint nums) {int flag0;for(size_t i0;inums.size();i){flag0;for(size_t j0;jnums.size();j){if(nums[i]nums[j]i!j)flag1;}if(flag0)return nums[i];}return 0;}
}; 上述代码首先创建一个变量flag并将其初始化为0用于标记是否找到了只出现一次的元素。然后使用两个嵌套的循环遍历数组。外层循环用于遍历每个元素内层循环用于比较当前元素与其他元素是否相等。如果找到了一个与当前元素相等且索引不同的元素说明当前元素不是只出现一次的元素将flag标记为1。最后在外层循环中判断flag的值如果flag为0则说明当前元素是只出现一次的元素直接返回该元素。如果循环结束后都没有找到只出现一次的元素则返回0。
2.杨辉三角 杨辉三角是一个数列其第n行由 n个数字构成每个数字等于它上方两个数字之和。首先我们来看一下杨辉三角的定义每一行的两侧数字都是1中间的数字等于上一行对应位置的两个数字之和。可以使用二维数组来表示整个杨辉三角其中第i行第j列的数字可以表示为triangle[i][j]。那么我们可以使用以下的编程思路来生成杨辉三角
创建一个二维数组triangle初始化为一个空的二维数组。使用两个嵌套的循环来遍历杨辉三角的每一行和每一列外层循环控制行数内层循环控制列数。在内层循环中对于每一行的第一个位置和最后一个位置将其值设置为1。对于其他位置将其值设置为其上一行对应位置的两个数字之和即triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]。内层循环结束后将当前行的数组添加到triangle中。外层循环结束后triangle中存储的就是完整的杨辉三角
请看正确代码
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint triangle;if (numRows 0) {return triangle;}for (int i 0; i numRows; i) {vectorint row(i1, 1); // 初始化每一行为1for (int j 1; j i; j) {row[j] triangle[i-1][j-1] triangle[i-1][j]; // 计算其他位置的值}triangle.push_back(row); // 将当前行添加到triangle中}return triangle;}
}; 这段代码使用了一个二维数组triangle来存储杨辉三角的每一行的数字。首先判断numRows的值如果小于等于0则直接返回空的triangle。然后使用两个嵌套的循环来遍历杨辉三角的每一行和每一列。外层循环控制行数内层循环控制列数。在内层循环中对于每一行的第一个位置和最后一个位置将其值设置为1。对于其他位置将其值设置为其上一行对应位置的两个数字之和。内层循环结束后将当前行的数组添加到triangle中。最后返回triangle即可得到完整的杨辉三角。这段代码的时间复杂度为O(numRows^2)其中numRows为所要生成杨辉三角的行数。因为需要使用两个嵌套的循环来遍历杨辉三角的每一行和每一列时间复杂度较高。
3.删除有序数组中的重复项 删除有序数组中的重复项可以使用双指针的方法来实现。具体的编程思路如下
初始化两个指针一个指针i用于遍历整个数组另一个指针j用于指向当前确定的不重复元素的位置。从数组的第二个元素开始遍历即i1。如果当前元素nums[i]与前一个元素nums[i-1]相等表示出现了重复元素此时指针i继续向后移动一位。如果当前元素nums[i]与前一个元素nums[i-1]不相等表示找到了一个不重复的元素将其复制到指针j的位置并将指针j向后移动一位。重复步骤3和步骤4直到遍历完整个数组。返回指针j的位置1即为删除重复项后的数组长度。
class Solution {
public:int removeDuplicates(vectorint nums) {if (nums.size() 0) {return 0;}int j 1; // 指针j初始指向第一个不重复元素的位置for (int i 1; i nums.size(); i) {if (nums[i] ! nums[i-1]) {nums[j] nums[i]; // 复制非重复元素到指针j的位置}}return j;}
};这段代码使用了两个指针i和j。指针i用于遍历整个数组指针j用于指向当前确定的不重复元素的位置。首先判断数组的长度是否为0如果是则直接返回0。然后从数组的第二个元素开始遍历即i1。如果当前元素nums[i]与前一个元素nums[i-1]相等表示出现了重复元素此时指针i继续向后移动一位。如果当前元素nums[i]与前一个元素nums[i-1]不相等表示找到了一个不重复的元素将其复制到指针j的位置并将指针j向后移动一位。重复上述步骤直到遍历完整个数组最后返回指针j的位置1即为删除重复项后的数组长度。这段代码的时间复杂度为O(n)其中n为数组的长度。只需要遍历一次数组即可删除重复项时间复杂度较低。
4.只出现一次的数字2.0 这道题和第一道题思路大概一致只不过这里的重复次数变成了3次还能不能使用异或呢显然不能了那我们第一道题的第二种方法能不能解呢答案是可以的那么请看示例代码
class Solution {
public:int singleNumber(vectorint nums) {int flag0;for(size_t i0;inums.size();i){flag0;for(size_t j0;jnums.size();j){if(nums[i]nums[j]i!j)flag1;}if(flag0)return nums[i];}return 0;}
}; 这里就不在解析了思路和第一题的第二种方法一样。
5.只出现一次的数字3.0 思路依旧类似只不过需要返回多个元素只需要尾插到顺序表中即可请看示例代码
class Solution {
public:vectorint singleNumber(vectorint nums) {vectorint vv;int flag0;for(size_t i0;inums.size();i){flag0;for(size_t j0;jnums.size();j){if(nums[i]nums[j]i!j)flag1;}if(flag0)vv.push_back(nums[i]);}return vv;}
}; 写法和前两种基本相似不同之处在于找到之后不会直接返回而是尾插到顺序表中最后一块返回。
6.数组中出现次数超过一半的数字 常规写法就是统计他们出现的总次数然后进行判断是否大于数组长度的一半请看示例代码 int count0;for(size_t i0;inumbers.size();i){count1;for(size_t j0;jnumbers.size();j){if(numbers[i]numbers[j]i!j)count; }if(countnumbers.size()/2)return numbers[i];}return 0; 上述代码的具体的分析如下 1. 初始化计数变量count为0。 2. 使用嵌套的循环结构遍历数组元素外层循环是遍历数组中的每一个元素内层循环是用来统计数组中该元素出现的次数。 3. 对于每一个外层循环迭代的元素首先将计数变量count重置为1表示当前元素至少出现了一次。 4. 然后通过内层循环遍历数组中的每一个元素如果发现数组中有与当前元素相等的元素且索引不同就将计数变量count加1。 5. 在内层循环结束后判断计数变量count是否超过了数组长度的一半如果超过了则说明该元素出现次数超过了数组长度的一半直接返回该元素。 6. 如果没有找到出现次数超过数组长度一半的元素最后返回0。 这段代码的时间复杂度为O(n^2)其中n为数组的长度。因为嵌套循环的复杂度为O(n^2)每个元素都需要遍历一次数组进行统计。所以在数组较大时性能可能比较差。
那么有没有什么简单的方法呢 分析一下题中的关键字“数组长度的一半“能不能想到把这个数组排序一下中间的就是我们要找的呢哈哈巧妙吧那么请看示例代码吧
class Solution {
public:int MoreThanHalfNum_Solution(vectorint numbers) {sort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}
};
直接对数组进行排序取其中间值就行。 到此我们只是简单的讲解了一下STL中vector的相关习题~,后续我们会一一展开学习的,希望这篇博客能给您带来一些启发和思考!那我们下次再一起探险喽,欢迎在评论区进行讨论~~~
