TODO:*
都不大会做都重做一遍吧！
剑指 Offer 28. 对称的二叉树(简单)
方法一
class Solution {
public:
bool is(TreeNode* L, TreeNode* R){
if(L==nullptr && R==nullptr) return true;
else if(L == nullptr || R == nullptr ||(L->val != R->val)) return false;
return is(L->left,R->right) && is(L->right,R->left);
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
return is(root->left,root->right);
}
};
剑指 Offer 65. 不用加减乘除做加法(简单)
《C++ Primer》当我们赋给无符号类型一个超出它表示范围的值时，结果是初始值对无符号类型表示数值取模后的余数。
当我们给带符号类型一个超出它表示范围的值时，结果是未定义的。
❗ 如果不加unsigned Leetcode会觉得越界访问从而报错。
image.png
1）在c 中左移也就是所说的逻辑移位，右端补0；
而右移是算数移位，左端补齐的是最高位的符号位。
2）故负数左移，有可能变成正数；但负数右移，肯定还是负数。
class Solution {
public:
int add(int a, int b) {
int c =0, add = 0;
while(a){
add = (unsigned int)(a&b)<<1;//⭐
c = a^b;
a = add;
b = c;
}
return b;
}
};
剑指 Offer 41. 数据流中的中位数(困难)
sort方法是nlogn的时间复杂度使用它会超时。这里借助堆，可使时间复杂度降为logn。大小根堆入堆出堆问题想了好久。
题解
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int,vector<int>,greater<int>> max_que;
priority_queue<int>min_que;
MedianFinder() {
}
void addNum(int num) {
int min_sz = min_que.size();
int max_sz = max_que.size();
if(min_sz == max_sz){
min_que.push(num);
int t = min_que.top();
min_que.pop();
max_que.push(t);
}else{
max_que.push(num);
int t = max_que.top();
max_que.pop();
min_que.push(t);
}
}
double findMedian() {
bool flag = (min_que.size()+max_que.size())%2 == 0?true:false;
return flag?(min_que.top()+max_que.top())*1.0/2:max_que.top();
}
};
