初级算法-其他

位1的个数

题意：

32位二进制判断1的数量

解：

bitset

代码：

#include<iostream>
#include<bitset>
using namespace std;
int hammingWeight(uint32_t n)
{bitset<32>bs(n);return bs.count();
}
int main()
{uint32_t n;cin>>n;int ans=hammingWeight(n);cout<<ans<<endl;return 0;
}

汉明距离

题意：

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

解：

异或 bitset

代码：

#include<iostream>
#include<bitset>
using namespace std;
int hammingDistance(int x, int y)
{bitset<32>bs(x^y);return bs.count(); 
}
int main()
{int x,y;cin>>x>>y;int ans=hammingDistance(x,y);cout<<ans<<endl;return 0;
}

颠倒二进制位

题意：

如题

解：

双指针翻转bitset

代码：

#include<iostream>
#include<bitset>
#include<algorithm> 
using namespace std;
uint32_t reverseBits(uint32_t n)
{bitset<32>bs(n);int l=0,r=31;while(l<r){bool temp=bs[l];bs[l]=bs[r];bs[r]=temp;l++;r--;}uint32_t ret=bs.to_ulong();return ret;
}
int main()
{uint32_t n;cin>>n; int ans=reverseBits(n);cout<<ans<<endl;return 0;
}

杨辉三角

题意：

如题

解：

数学推导

代码：

#include<iostream>
#include<bitset>
#include<algorithm> 
using namespace std;
vector<vector<int>> generate(int numRows)
{vector<vector<int>>ret;for(int i=1;i<=numRows;i++){//cout<<"i:"<<i<<endl;vector<int>temp;for(int j=0;j<i;j++){//cout<<"j:"<<j<<endl;if(j==0||j==i-1) temp.push_back(1);else temp.push_back(ret[i-2][j-1]+ret[i-2][j]);}ret.push_back(temp);}return ret;
}
int main()
{int n;cin>>n; vector<vector<int>>ans=generate(n);for(auto &row:ans){for(auto &col:row) cout<<col<<ends;cout<<endl;}return 0;
}

有效的括号

题意：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

解：

经典栈处理

代码：

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s)
{vector<char>stackVec(s.size());int cnt=0;map<char,char>mp={ {'{',' '},{'}','{'},{'[',' '},{']','['},{'(',' '},{')','('}};for(const auto &ch:s){//cout<<"ch:"<<ch<<"&cnt:"<<cnt<<endl;if(cnt==0) stackVec[cnt++]=ch;else{if(mp[ch]==stackVec[cnt-1]){cnt--;}else stackVec[cnt++]=ch;}//cout<<"ch:"<<ch<<"&cnt:"<<cnt<<endl;}return (cnt==0?true:false);
}
int main()
{string s;cin>>s;bool ans=isValid(s);cout<<boolalpha<<ans<<endl;return 0;
}

缺失数字

题意：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

解：

经典异或

主要原理：0^x=x 和 x^x=0，所以出现两遍的数字不会影响结果

代码：

#include<bits/stdc++.h>
using namespace std;
int missingNumber(vector<int>& nums)
{int n=nums.size(),ret=0;for(auto &num:nums) ret^=num;for(int i=0;i<=n;i++) ret^=i;return ret;
}
int main()
{vector<int>nums;int temp;while(cin>>temp) nums.push_back(temp);int ans=missingNumber(nums);cout<<ans<<endl;
}