浙江注册公司网站,免费域名申请 tk,微信网站开发模板,免费二维码推广平台一、杨辉三角 class Solution {
public:vectorvectorint generate(int numRows) {}
}; 这里给你一个vectorvectorint类型
也就是说vector中的各个数据#xff0c;存的是各个不同的vector
思路#xff1a;先给vector开空间#xff0c;然后…一、杨辉三角 class Solution {
public:vectorvectorint generate(int numRows) {}
}; 这里给你一个vectorvectorint类型
也就是说vector中的各个数据存的是各个不同的vector
思路先给vector开空间然后给vector中的vector开空间并且初始化
最后根据数学关系找规律 class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows);for(int i 0;i numRows; i){vv[i].resize(i1,0); vv[i][i] 1;vv[i][0] 1;}for(int i 2;i vv.size();i){for(int j 1;jvv[i].size()-1;j){vv[i][j] vv[i-1][j-1]vv[i-1][j];}}return vv;}
};
二、删除有序数组中的重复项 法一
就是简便的比较如果相等则删除又因为erase函数删除后后面的数据往前移动所以比较的下标要不变
class Solution {
public:int removeDuplicates(vectorint nums) {int count nums.size();std::vectorint::iterator it nums.begin();//1 1 1for (int i 0; i nums.size(); i){//for (int j i 1; j nums.size(); j){if (nums[i] nums[j]){count--;nums.erase(it j);j--;}}}return count;}
}; 法二
双指针
思路
如果有fast前后是相同的数字slow指针不移动直到fast指针找到不相同的数再向前移动slow class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 0) {return 0;}int fast 1, slow 1;while (fast n) {if (nums[fast] ! nums[fast - 1]) {nums[slow] nums[fast];slow;}fast;}return slow;}
};
三、只出现一次数据②
这里是参考比特老师所写的方法------ 这个方法简直妙蛙种子吃了妙脆角走进了米奇妙妙屋 想法思路真是太妙了
题目说只有一个数字出现一次其余数字均出现3次假设数组为{3,5,3,3}
通过分析可知
3的二进制0 0 0 0 0 0 1 1
5的二进制0 0 0 0 0 1 0 1
3的二进制0 0 0 0 0 0 1 1
3的二进制0 0 0 0 0 0 1 10 0 0 0 0 1 3 4 二进制1的总数
对于出现3次的数字各位出现的次数都是3的倍数因此对统计的为1的比特总数%30 0 0 0 0 1 0 1 5结果就是只出现一次的数字
class Solution {
public:int singleNumber(vectorint nums) {int ans 0;for (int i 0; i 32; i) {// 统计该每个数字第i个比特位为1的总数int total 0;for (int num : nums) {total ((num i) 1);//太妙了}// 如果total能够被3整除说明只出现一次的数字在该位置上一定是0// 否则在该位置上一定是1if (total % 3) {ans | (1 i);//太妙了}}return ans;}
};
有操作符概念不了解的可以从下面这篇文章了解一下
http://t.csdnimg.cn/APANq
total ((num i) 1);
ans | (1 i);这里就好比给32位比特位全为0哪个位置需要改就在哪里换个1最后就是那一个数
特别是这两行代码写的真是太妙了
. - 力扣LeetCode
四、只出现一次数据③ 参考leetcode的大佬所写
大佬们的方法简直就是--妙蛙种子吃了妙脆角走进了米奇妙妙屋 class Solution {
public:vectorint singleNumber(vectorint nums) {unsigned int x 0;for(int e : nums){x ^ e;}int x1 x (-x);int type1 0,type2 0;for (int e: nums) {if (e x1) {type1 ^ e;}else {type2 ^ e;}}return {type1, type2};}
};
这里采用的是
异或做法----前面也有提过
a^a 0
a^a^b b 下面我就开始讲一下这位灵茶山艾府大佬的代码与leetcode官方代码的结合版
首先为什么用unsigned int x 0直接用int不就好了吗?先带着这个问题往下看
我们把所有数据都异或一遍后因为相同的数异或为0只剩下两个单身狗设为x1x2
也就是说第一个循环走完以后unsigned int x x1^x2
我们得出x也就是x1与x2的混合体要混合体有什么用我们要的是单独的x1与x2如何把这个混合体分开
因为异或性质是相同为0相异为1也就是说x中二进制位中的一个1也就是x1与x2不同的位数要么x1这个位数为1要么x2中这个位数为0或者x1这个位数为0x2这个位数为1举个例子
6的二进制是 0110
10 1010
异或为 1100
我们知道这个了以后只保留二进制最低位的1
x 1100
~x 0011
~x1 0100 根据补码的定义就是-x 如果 数据是-1 -1 0 -2147483648对-2147483648取负数据就溢出了所以这里取unsigned int 按位与 只有0就是0两个同时为1才是1
(x -x) 0100 我们得到二进制最低位的1
之后就是分组分组的根据是什么分组能把x1与x2分开且对于其他数没有任何影响反正最后异或后都为0 最后就是找单身狗的问题
