class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n){
count++;
n = n & (n-1);
}
return count;
}
};
维护一下最小堆，时间复杂度$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;
}
};
