位操作
计算有多少个0或者1
- '<<': 左移运算符,num << 1,相当于num乘以2
- '>>' : 右移运算符,num >> 1,相当于num除以2
- '>>>':无符号右移,忽略符号位,空位都以0补齐,x>>>=1 无符号右移然后赋值给自己
- 与1位与得1就是奇数,1只有最后一位是1
求解二进制数n中1的个数
解法一:
int get_1_num(int n){
int count = 0;
while(n != 0)
{
if((n&1)==1)
count++;
n>>>=1;
}
return count;
}
解法二:
int get_1_num(int n){
int count = 0;
while(n != 0)
{
n = n&(n-1);
count++;
}
return count;
}
计算高位有多少个0
public static int numberOfLeadingZeros0(int i){
if(i == 0)return 32;
int n = 0;
int mask = 0x80000000;
int j = i & mask;
while(j == 0){
n++;
i <<= 1;
j = i & mask;
}
return n;
}
返回位数组
vector* get_bit_array(int n){
vector vec;
int i=32;
while(i--){
vec.push_back(n&1);
n>>=1;
}
return &vec;
}
二叉树
二叉搜索树第k小的结点
二叉搜索树的中序遍历就是排好序的,所以只要找中序遍历的第k个节点
int count = 0;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot != NULL) {
TreeNode leftNode = KthNode(pRoot->left, k);
if(leftNode != NULL)
return leftNode;
count++;
if(count == k)
return pRoot;
TreeNode rightNode = KthNode(pRoot->right, k);
if(rightNode != NULL)
return rightNode;
}
return NULL;
}
排序
统计数字或者字母个数
取出现次数最多的k个数字
- 题目要求
Given [1,1,1,2,2,3] and k = 2, return [1,2].
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}
vector<int> res;
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int> > pq; // 从大到小
//priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
按词频排序输出
- 题目要求
Input:"tree"; Output:"eert"
string frequencySort(string s) {
map<char,int> c_frq;
for(char c : s){
c_frq[c]++;
cout<<c;
}
priority_queue <pair<int,char>> pq;
for(auto it=c_frq.begin();it!=c_frq.end();it++){
pq.push(make_pair(it->second,it->first));
}
string ans="";
while(!pq.empty()){
int time = pq.top().first;
char c = pq.top().second;
pq.pop();
while(time--){
ans+=c;
}
}
return ans;
}
本文由 admin 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: May 30, 2019 at 05:40 pm
赞