算法基础操作

in 算法基础 with 1 comment view 49 times

位操作

计算有多少个0或者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个数字

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;
}

按词频排序输出

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;
}
Responses
  1. Darkmaster

    Reply