五、位运算
常见位运算总结
&：有0就是0；
|：有1就是1
^：相同为0，相异就是1/无进位相加
给定一个数n,确定它的二进制表示中的第x位是0还是1：二进制中权值最小的是第0位，所以int整型是从第0位到第31位。于是n>>x &1就可以了
将一个数n的二进制表示的第x位修改成为1： (1<<x) | n
将一个数n的二进制表示的第x位修改成为0：(~(1<<x)) & n
提取一个数n的二进制表示中最右侧的1：n&(-n)，正数变成负数的二进制表示就是按位取法再加1。-n的本质是将最右侧的1的左边区域（不包括最右侧的1也就是当前位置）全部变成相反，其余的都不变。
干掉一个数n二进制表示中最右侧的1，也就是将这个1变成0：n&(n-1) ,n-1的本质是将最右侧的1右边的区域（包含1）全部变成相反。
异或：a^a=0；a^0=a；a^b^c=a^(b^c)；交换律；采用无进位相加很容易证明
1.判断字符是否唯一
采用位图的思想：因为单独的一个整型变量就有32位比特位优化点：鸽巢原理，也就是如果字符串的长度超过26，必定存在重复字符。
class Solution { public: bool isUnique(string astr) { //利用鸽巢原理进行优化 if(astr.size()>26) return false; int bitmap=0; for(auto ch:astr) { //判断字符出现在哈希表中 if((1<<(ch-'a')) & bitmap) return false; //将当前字符加入到位图中 else bitmap+=(1<<(ch-'a'));//bitmap |= (1<<(ch-'a')) } return true; } };
2.丢失的数字
class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size()+1; int result=0; for(auto ch:nums) result^=ch; for(int i=0;i<n;i++) result^=i; return result; } };
3.两整数之和（巧妙）
利用异或的无进位相加，然后找到需要进位的地方。通过a&b可以找到需要进位的地方，因为只有1&1才能得到1，而这也是我们需要进位的地方。（a&b)<<1才是我们需要进位的位置。
class Solution { public: int getSum(int a, int b) { while(b) { int temp_a=a; a=temp_a^b;//先算出无进位相加的结果 b=(temp_a&b)<<1;//算出进位 } return a; } };
4.只出现一次的数字
class Solution { public: int singleNumber(vector<int>& nums) { int ret=0; for(int i=0;i<32;i++)//依次去修改ret中的每一位 { int sum=0;//统计nums中第i比特位出现1的次数 for(auto ch:nums) if(ch & (1<<i)) sum++; if(sum%3) ret |= (1<<i);//修改ret的第i比特位 } return ret; } };
5.消失的两个数
class Solution { public: vector<int> missingTwo(vector<int>& nums) { vector<int> result; //将所有的数全部都异或到一起 int tmp=0; int n=nums.size(); for(auto ch:nums) tmp^=ch; for(int i=1;i<=n+2;i++) tmp^=i; //找到tmp中，比特位为1的那一位pos，在该比特位上a和b的比特值是不一样的。 int pos; for(pos=0;pos<32;pos++) if((tmp>>pos)&1) break; //根据pos位的不同，划分成为两类来异或 int a=0,b=0; for(auto ch:nums) { if((ch>>pos)&1) a^=ch; else b^=ch; } for(int i=1;i<=n+2;i++) { if((i>>pos)&1) a^=i; else b^=i; } return {a,b}; } };
六、模拟算法
模拟算法就是依葫芦画瓢，思路比较简单，但是算法流程存在很多细节，将流程转换成为算法有比多要注意的细节。模拟题找优化一般都是通过找规律进行的。
6.替换所有的问号
class Solution { public: string modifyString(string s) { int n=s.size(); //遍历字符串 for(int i=0;i<n;i++) { //找到？字符 if(s[i]=='?') { //遍历26个字母替换该字符 for(char ch='a';ch<='z';ch++) { //找到符合要求的字符，下面的if条件是关键 if((i==0 || ch!=s[i-1]) && (i==n-1 || ch!=s[i+1])) { s[i]=ch; break; } } } } return s; } };
7.提莫攻击
class Solution { public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int result=0; for(int i=0;i<timeSeries.size()-1;i++) { if(timeSeries[i+1]-timeSeries[i]>=duration) result+=duration; else result+=(timeSeries[i+1]-timeSeries[i]); } return result+duration; } };
8.Z字形变换
class Solution { public: string convert(string s, int numRows) { //处理边界情况 if(numRows==1) return s; string result; int n=s.size(); int d=numRows*2-2;//公差d //1.先处理第一行 for(int i=0;i<n;i+=d) { result+=s[i];// } //2.处理中间行 for(int k=1;k<numRows-1;k++)//枚举每一行 { for(int i=k,j=d-k;i<n || j<n;i+=d,j+=d)//注意不要将i<n || j<n写成了i<n && j<n { if(i<n) result+=s[i]; if(j<n) result+=s[j]; } } //3.最后处理最后一行 for(int i=numRows-1;i<n;i+=d) { result+=s[i]; } return result; } };
9.外观数列
class Solution { public: string countAndSay(int n) { string result="1"; if(n==1) return result; for(int i=1;i<n;i++)//翻译n次 { string tmp; int len=result.size(); //采用双指针来进行翻译 for(int left=0,right=0;right<len;) { while(right<len && result[left]==result[right]) right++;//当right=len-1的边界情况也可以正确处理 tmp+=to_string(right-left);//to_string函数处理下标left和right的值不同的时候 tmp+=result[left]; left=right; } result=tmp; } return result; } };
10.数青蛙
上述总结就是代码的逻辑非常重要
class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string t="croak"; int n=t.size(); vector<int> hash(n);//用数组来模拟哈希表 unordered_map<char,int> index;//存储t字符串每个字符char以及对应的下标int for(int i=0;i<n;i++) index[t[i]]=i; //遍历字符串 for(auto ch:croakOfFrogs) { //1、如果ch不在字符串t的范围内 if(index.count(ch)==0) return -1; //2、如果字符ch不是c并且前面并没有匹配的字符 if(ch!=t[0] && hash[index[ch]-1]<1) return -1; //3、正常运作 if(ch==t[0] && hash[n-1]<1) hash[0]++; else if(ch==t[0] && hash[n-1]>=1) hash[0]++,hash[n-1]--; else hash[index[ch]]++,hash[index[ch]-1]--; } for(int i=0;i<n-1;i++) if(hash[i]!=0) return -1; return hash[n-1]; } };
七、分治
分治就是分而治之，将一个大问题转换成为若干个相同或者相似的子问题，直到划分到子问题可以快速解决为止。
10.颜色分类(快排关键）
class Solution { public: void sortColors(vector<int>& nums) { int n=nums.size(); int left=-1,right=n; for(int i=0;i<right;)//条件是i<right不是i<n，这是一个易错点。 { if(nums[i]==0) swap(nums[++left],nums[i++]); else if(nums[i]==1) i++; else swap(nums[--right],nums[i]); } } };
11.排序数组 （快排）
class Solution { public: int getrandom(vector<int>& nums,int left,int right) { int r=rand(); return nums[r % (right-left+1) + left]; } void sortArray_help(vector<int>& nums,int l,int r) { //定义递归出口 if(l>=r) return; //随机方式选择基准元素 int standar=getrandom(nums,l,r); int left=l-1; int right=r+1; //分成三块 for(int i=l;i<right;) { if(nums[i]<standar) swap(nums[++left],nums[i++]); else if(nums[i]==standar) i++; else swap(nums[--right],nums[i]); } sortArray_help(nums,l,left); sortArray_help(nums,right,r); } vector<int> sortArray(vector<int>& nums) { srand(time(NULL));//种下一棵随机数种子 sortArray_help(nums,0,nums.size()-1); return nums; } };
12.数组中的第k个最大元素
class Solution { public: int getrandom(vector<int>&nums,int left,int right) { int r=rand(); return nums[r%(right-left+1)+left]; } int qsort(vector<int>& nums,int l,int r,int k) { if(l==r) return nums[l];//容易遗漏的点 //1、随机选择基准元素 int standard=getrandom(nums,l,r); //2、根据基准元素将数组分成三块 int left=l-1; int right=r+1; int i=l; while(i<right) { if(nums[i]<standard) swap(nums[++left],nums[i++]); else if(nums[i]==standard) i++; else swap(nums[--right],nums[i]); } //分情况讨论 //下面的三个条件判断是关键 if(r-right+1>=k) return qsort(nums,right,r,k); else if(r-left>=k) return standard; else return qsort(nums,l,left,k-r+left); } int findKthLargest(vector<int>& nums, int k) { srand(time(NULL)); return qsort(nums,0,nums.size()-1,k); } };
13.最小k个数（未做）
14.归并排序（归并排序）
class Solution { public: vector<int> tmp;//辅助数组用来排序 void mergesort(vector<int>& nums,int left,int right) { if(right<=left) return; //1、选择中间点划分区间 int mid=(left+right)/2; //2、将左右区间排序 int left1=left; int right1=mid; int left2=mid+1; int right2=right; mergesort(nums,left1,right1); mergesort(nums,left2,right2); int i=0; //3、合并两个有序数组 while(left1<=right1 && left2<=right2) tmp[i++]=nums[left1]<=nums[left2]?nums[left1++]:nums[left2++]; //4、处理没有遍历完的数组 while(left1<=right1) tmp[i++]=nums[left1++]; while(left2<=right2) tmp[i++]=nums[left2++]; //5、还原 for(int i=left;i<=right;i++) nums[i]=tmp[i-left]; } vector<int> sortArray(vector<int>& nums) { tmp.resize(nums.size()); mergesort(nums,0,nums.size()-1); return nums; } };
15.交易逆序对的总数（未做）
class Solution { public: int reversePairs_helper(vector<int>& nums,int left,int right) { if(left>=right) return 0; int ret=0; //1、找中间点，将数组分成两部分 int mid=(left+right)>>1; //2.左边的个数+排序+右边的个数+排序 ret +=reversePairs_helper(nums,left,mid); ret +=reversePairs_helper(nums,mid+1,right); //3.一左一右的个数 int cur1=left,cur2=mid+1,i=0; vector<int> tmp(right-left+2); while(cur1<=mid && cur2<=right) { if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur1++]; else { ret+= mid-cur1+1; tmp[i++]=nums[cur2++]; } } while(cur1<=mid) tmp[i++]=nums[cur1++]; while(cur2<=right) tmp[i++]=nums[cur2++]; for(int j=left;j<=right;j++) nums[j]=tmp[j-left]; return ret; } int reversePairs(vector<int>& record) { return reversePairs_helper(record,0,record.size()-1); } };
16.計算右側小於當前元素的個數
class Solution { vector<int> ret; vector<int> index;//记录nums当前元素的下标、 int tmpNums[500010]; int tmpIndex[500010]; public: vector<int> countSmaller(vector<int>& nums) { int n=nums.size(); ret.resize(n); index.resize(n); for(int i=0;i<n;i++) index[i]=i; mergesort(nums,0,nums.size()-1); return ret; } void mergesort(vector<int>& nums,int left,int right) { if(left>=right) return; int mid=(left+right)>>1; mergesort(nums,left,mid); mergesort(nums,mid+1,right); int cur1=left,cur2=mid+1,i=0; while(cur1<=mid && cur2<=right) { if(nums[cur1]>nums[cur2]) { tmpNums[i]=nums[cur1]; ret[index[cur1]]+=right-cur2+1; tmpIndex[i]=index[cur1]; i++; cur1++; } else { tmpNums[i]=nums[cur2]; tmpIndex[i]=index[cur2]; i++; cur2++; } } while(cur1<=mid) { tmpNums[i]=nums[cur1]; tmpIndex[i]=index[cur1]; i++; cur1++; } while(cur2<=right) { tmpNums[i]=nums[cur2]; tmpIndex[i]=index[cur2]; i++; cur2++; } for(int j=left;j<=right;j++) { nums[j]=tmpNums[j-left]; index[j]=tmpIndex[j-left]; } } };
