Day23 对称的二叉树 + 不用加减乘除做加法 + 数据流中的

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