头像

开水白菜




离线:24天前



class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n){
            count++;
            n = n & (n-1);
        }
        return count;
    }
};

n-1 把最右边1变成0,1右边的0全部变成1;

n & (n-1) 则是把最右边的1变成0,这个1右边的0保持不变




维护一下最小堆,时间复杂度$O(nlogk)$,空间复杂度$O(k)$

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k == 0 ) return vector<int>();
        priority_queue<int> q;
        for(int & a : arr){
            if(q.size() < k){
                q.push(a);
            }
            else {
                if(q.top() <= a) continue;
                else{
                    q.pop();
                    q.push(a);
                }
            }
        }
        vector<int> res;
        while(!q.empty()){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

QuickSelect 快速选择,和快排一样,只需要左半边就可以

时间复杂度 空间复杂度

抄的代码,还没开始研究

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }

    // 基于随机的划分
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

    void randomized_selected(vector<int>& arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomized_partition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomized_selected(arr, l, pos - 1, k);
        } else {
            randomized_selected(arr, pos + 1, r, k - num);
        }
    }

public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        srand((unsigned)time(NULL));
        randomized_selected(arr, 0, (int)arr.size() - 1, k);
        vector<int> vec;
        for (int i = 0; i < k; ++i) {
            vec.push_back(arr[i]);
        }
        return vec;
    }
};




class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        for(int l = 1 ,r =1 ,sum = 0 ;r< target ;r++){
            sum+=r;
            while(sum >target){
                sum -= l;
                l++;
            }
            if(sum == target){
                vector<int> tmp(r-l+1);
                for(int i = 0 ; i< tmp.size();i++){
                    tmp[i] = l + i;
                }
                res.emplace_back(tmp);
            }
        }
        return res;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //d用来存深度信息,v用来存节点值
    TreeNode* build(queue<int>& d,queue<int>& v,int depth){
        if(d.front() != depth) return nullptr;//说明不是当前的子树了
        TreeNode* root = new TreeNode(v.front());
        d.pop();
        v.pop();
        root->left = build(d,v,depth+1);
        root->right = build(d,v,depth+1);
        return root;
    }
    TreeNode* recoverFromPreorder(string S) {
        int left = 0;//left为-的开始位置,i记录结束位置,记录深度
        queue<int> d,v;
        for(int i = 0;i < S.size();i++){
            if(S[i] != '-'){ //不是 - 了
                d.push(i-left);
                left = i;
                while(i < S.size() && S[i] !='-') i++;//确定数字长度
                v.push(stoi(S.substr(left,i-left)));
                left = i;
            }
        }
        return build(d,v,0);
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if(root == nullptr) return nullptr;
        root->left = removeLeafNodes(root->left,target);
        root->right = removeLeafNodes(root->right,target);
        if(root->val == target && root->left == nullptr && root->right == nullptr){
            return nullptr;
        } 
        return root;
    }
};



有一个数据相当恶心,要用unsigned long long

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxW = 0;
    int widthOfBinaryTree(TreeNode* root) {
        vector<unsigned long long> left;
        dfs(root,1,1,left);
        return maxW;
    }
    void dfs(TreeNode* r, int level,unsigned long long index, vector<unsigned long long>& left){
        if(r == nullptr) return ;
        if(level > left.size()) left.emplace_back(index);
        maxW = maxW > (index - left[level-1] +1) ? maxW : (index - left[level-1] +1);
        dfs(r->left,level+1,index*2,left);
        dfs(r->right,level+1,index*2+1,left);
    }
};



给根节点添加虚拟的父节点和祖父节点,递归时把当前节点的父节点更新为当前节点左右孩子的祖先节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumEvenGrandparent(TreeNode* root) {
        return sumEvenGrandparent(root,-1,-1);
    }
    int sumEvenGrandparent(TreeNode* root, int parent, int grandparent){
        if(root == NULL) return 0;
        int res = 0;
        if(grandparent%2 == 0) res+=root->val;
        res += sumEvenGrandparent(root->left,root->val,parent);
        res += sumEvenGrandparent(root->right,root->val,parent);
        return res;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool dfs(ListNode* head,TreeNode* root){
        if(!head) return true;
        if(!root) return false;
        if(root->val != head->val) return false;
        return dfs(head->next,root->left) || dfs(head->next,root->right);
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        if(!head) return true;
        if(!root) return false;
        if(dfs(head,root)) return true;
        return isSubPath(head,root->left) || isSubPath(head,root->right);
        //决定从哪个点开始匹配
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //边界数据恶心人 2147483647 int最大
    bool isValidBST(TreeNode* root) {
        return isValidBST(root,LONG_MIN,LONG_MAX);
    }
    bool isValidBST(TreeNode* root , long min,long max){
        return root == NULL || (root->val > min && root->val < max && isValidBST(root->left,min,root->val) && isValidBST(root->right,root->val,max));
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(root->left == nullptr && root->right == nullptr && root->val == 0)
            return nullptr;
        return root;
    }
};